算法LeetCode Hot 100

一哈希

要点：

构造一个 Map，利用 Map 的O（1）复杂度取值的方式，来完成目标。如两数之和

如果元素较多，可以将其通过 encode 的方式转为 string 等字符串，完成编码。如字母异位词分组

1. 两数之和


    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int t = target - nums[i];
            if (map.containsKey(t) && map.get(t) != i) {
                return new int[] { i, map.get(t) };
            }
        }
        return null;
    }

2. 字母异位词分组

💡

这里利用了’int index = c-'a';’ 计算 char 的 index。

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

解释：

在 strs 中没有字符串可以通过重新排列来形成 "bat"。

字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。

字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。


       public List<List<String>> groupAnagrams(String[] strs) {
            // 编码到分组的映射
            Map<String,List<String>> codeToStrsMap = new HashMap<>();

            for(String str : strs){
                String code = encode(str);
                // 如果是新的 code，则先创建一个 list
                codeToStrsMap.putIfAbsent(code, new ArrayList<>());
                codeToStrsMap.get(code).add(str);
            }

            List<List<String>> result = new ArrayList<>();
            for(List<String> value : codeToStrsMap.values()){
                result.add(value);
            }

            return result;
        }

        private String encode(String str) {
            char[] code = new char[26];
            for (char c : str.toCharArray()) {
                int index = c-'a';
                code[index]++;
            }
            return new String(code);
        }

3. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

用一个 HashMap 存放所有的数字，然后通过num-1 就可以判断当前数字是否有前置数字（如果有则跳过）只统计开头数字的连续长度。


        public int longestConsecutive(int[] nums) {
            HashSet<Integer> set = new HashSet<>();
            for (int num : nums) {
                set.add(num);
            }

            int maxCount = 0;

            // 注意!遍历的不是 nums 而是 set
            for (int num : set) {
                if (set.contains(num - 1)) {
                    // 1. 寻找这个数字是不是开头，当有 -1 存在，不是开头。
                    continue;
                }

                // 2. 如果是开头，判断能持续多长
                int curNum = num;
                int curLen = 1;
                while (set.contains(curNum + 1)) {
                    curLen++;
                    curNum++;
                }
                maxCount = Math.max(maxCount, curLen);
            }
            return maxCount;
        }

二双指针

双指针详细思路可以参考

🚮

算法数据结构-数组

要点：

快慢指针从同一侧开始移动，如移动零

在求和问题中，通过左右指针向中间移动的方式求解。如盛水最多的容器

4. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。


    public void moveZeroes(int[] nums) {
        int slow = 0, fast = 0;

            while (fast < nums.length) {
                if (nums[fast] != 0) {
                    nums[slow] = nums[fast];
                    slow++;
                }
                fast++;
            }

            while (slow < nums.length) {
                nums[slow] = 0;
                slow++;
            }
    }

5. 盛水最多的容器盛水最多的rong

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。


        public int maxArea(int[] height) {
            // 双指针方式
            int left = 0, right = height.length - 1;
            int maxArea = 0;

            while (left < right) {
                int area = (right - left) * Math.min(height[left], height[right]);
                maxArea = Math.max(maxArea, area);

                // 缩小边界，移动较低的一边，这样才可能有更大的值出现（因为较短的边仍然限制了高度）
                if (height[left] < height[right]) {
                    left++;
                } else {
                    right--;
                }
            }

            return maxArea;
        }

6. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。.

💡

n 数之和问题可以统一解法，利用递归+两数之和的方式。


        public List<List<Integer>> threeSum(int[] nums) {

            Arrays.sort(nums);

            return nSumTarget(nums, 3, 0, 0);

        }

        // 注意：调用函数前一定要 sort
        // 通用解法，n 数之和。
        private List<List<Integer>> nSumTarget(int[] nums, int n, int start, int target) {
            List<List<Integer>> res = new ArrayList<>();
            int len = nums.length;
            // 至少是 2sum
            if (n < 2 || len < n) {
                return res;
            }

            if (n == 2) {
                // 经典两数之和
                int left = start, right = len - 1;
                while (left < right) {
                    int l = nums[left], r = nums[right];
                    int sum = nums[left] + nums[right];
                    if (sum == target) {
                        res.add(Arrays.asList(l, r));
                        while (left < right && nums[left] == l)
                            left++;
                        while (left < right && nums[right] == r)
                            right--;
                    } else if (sum < target) {
                        while (left < right && nums[left] == l)
                            left++;
                    } else {
                        while (left < right && nums[right] == r)
                            right--;
                    }
                }
            } else {
                // n > 2, reduce to n-1 sum
                for (int i = start; i < len; i++) {
                    List<List<Integer>> subRes = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
                    for (List<Integer> list : subRes) {
                        List<Integer> subList = new ArrayList<>(list);
                        subList.add(nums[i]);
                        res.add(subList);
                    }
                    while (i < len - 1 && nums[i] == nums[i + 1]) {
                        i++;
                    }

                }
            }
            return res;

        }

    }

7. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水


        public int trapTowPoint(int[] height) {
            // 双指针
            if (height.length == 0) {
                return 0;
            }

            int res = 0;
            int left = 0, right = height.length - 1;
            int leftMax = 0, rightMax = 0;

            while (left < right) {
                if (height[left] < height[right]) {
                    // 移动左边
                    if (height[left] > leftMax) {
                        // 该列，无法存水，左边有低的（右边有什么都无关）
                        leftMax = height[left];
                    } else {
                        // 该列可以存水，存水多少取决于短边，因为上面的判断所以左边短边
                        res += leftMax - height[left];
                    }
                    left++;

                } else {
                    if (height[right] >= rightMax)
                        rightMax = height[right];
                    else
                        res += rightMax - height[right];
                    right--;
                }
            }

            return res;
        }

三滑动窗口

滑动窗口专项可参考

🚮

算法核心框架-滑动窗口

要点：

滑动窗口的框架固定，要注意是什么时候滑动右侧和左侧，以及窗口中逻辑是什么，左侧推出时的逻辑是什么。

8. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。


class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> window = new HashMap<>();

        int left = 0, right = 0;
        // 记录结果
        int res = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            // 进行窗口内数据的一系列更新
            window.put(c, window.getOrDefault(c, 0) + 1);
            // 判断左侧窗口是否要收缩
            while (window.get(c) > 1) {
                char d = s.charAt(left);
                left++;
                // 进行窗口内数据的一系列更新
                window.put(d, window.get(d) - 1);
            }
            // 在这里更新答案
            res = Math.max(res, right - left);
        }
        return res;
    }
}

9. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。


class Solution {
    public List<Integer> findAnagrams(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0;
        int valid = 0;
        // 记录结果
        List<Integer> res = new ArrayList<>();
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            // 进行窗口内数据的一系列更新
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            // 判断左侧窗口是否要收缩
            while (right - left >= t.length()) {
                // 当窗口符合条件时，把起始索引加入 res
                if (valid == need.size()) {
                    res.add(left);
                }
                char d = s.charAt(left);
                left++;
                // 进行窗口内数据的一系列更新
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return res;
    }
}