力扣爆刷第119天之CodeTop100五连刷81-85

一、14. 最长公共前缀

题目链接：https://leetcode.cn/problems/longest-common-prefix/description/
思路：求最长公共前缀，直接取第一个字符串，然后每一个字符就遍历剩余的字符串，时间复杂度O（N）2.

class Solution {public String longestCommonPrefix(String[] strs) {if(strs.length == 0 || strs[0].equals("")) return strs[0];StringBuilder builder = new StringBuilder();String s0 = strs[0];int k = 0;for(int i = 0; i < s0.length(); i++) {char c = s0.charAt(i);for(int j = 1; j < strs.length; j++) {if(i >= strs[j].length() || c != strs[j].charAt(i)) {return builder.toString();}}builder.append(c);}return builder.toString();}
}

二、718. 最长重复子数组

题目链接：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/
思路：最长重复子数组是连续的子数组，定义dp[i][j]表示，以nums1[i]和nums2[j]为结尾的区间的最长重复子数组，根据这个定义，若nums1[i] != nums2[j]，则以这两为结尾的字符子串长度为0，相等为dp[i+1][j+1] = dp[i][j] + 1;
定义好dp然后根据定义去推导递推关系。

class Solution {public int findLength(int[] nums1, int[] nums2) {int m = nums1.length, n = nums2.length, max = Integer.MIN_VALUE;int[][] dp = new int[m+1][n+1];for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(nums1[i] == nums2[j]) {dp[i+1][j+1] = dp[i][j] + 1;}max = Math.max(max, dp[i+1][j+1]);}}return max;}
}

三、169. 多数元素

题目链接：https://leetcode.cn/problems/majority-element/description/
思路：利用一个元素用来计数，相同的数加1，不同的数减1，最后剩下的数就是多数元素。

class Solution {public int majorityElement(int[] nums) {int count = 0, res = 0;for(int n : nums) {if(count == 0) {res = n;}count = res == n ? count + 1 : count - 1;}return res;}
}

四、662. 二叉树最大宽度

题目链接：https://leetcode.cn/problems/maximum-width-of-binary-tree/description/
思路：本题求最大宽度，是需要利用满二叉树的特性的，采用前序遍历，给每一个节点编号，root=id，左孩子=id2，右孩子=id2+1，只需要记录下每一行最左边的节点的id，后面每次递归都计算当前节点与这一层最左边的距离，id相减就是距离，那么如何收集最左边的节点呢，采用先序遍历，list元素个数和深度相等就收集。

class Solution {ArrayList<Integer> list = new ArrayList<>();int max = 1;public int widthOfBinaryTree(TreeNode root) {traverse(root, 1, 1);return max;}void traverse(TreeNode root, int id, int deep) {if(root == null) return;if(list.size() == deep-1) {list.add(id);}else{max = Math.max(max, id - list.get(deep-1) + 1);}traverse(root.left, id * 2, deep + 1);traverse(root.right, id * 2 + 1, deep + 1);}
}

五、128. 最长连续序列

题目链接：https://leetcode.cn/problems/longest-consecutive-sequence/description/
思路：列表无序，也不要求顺序，求最长连续序列，还要求O(N)，那么就不能排序了，可以利用set集合，如果连续一定是一段一段的，我们只需要找到每一个连续段的开头，从这个地方开始技术，全部统计完就可以，注意，只从连续段的头开始计算。

class Solution {public int longestConsecutive(int[] nums) {HashSet<Integer> set = new HashSet<>();int max = 0;for(int i : nums) {set.add(i);}for(int i : set) {if(!set.contains(i-1)) {int t = 0;while(set.contains(i)) {t++;i++;}max = Math.max(max, t);}}return max;}
}