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

力扣爆刷第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();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

二、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;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

三、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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

四、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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

五、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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20