LeetCode-Hot100-列表题解

一.解法

一句话描述解法

1.1-10

7	11.盛最多水的容器		（1）双指针+贪心：每次移动较低的指针，因为移动较高的指针，容积只能变小。 移动过程中统计全局最大容积即可，时间O（N)	中等

9	17.电话号码的字母组合	给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。	（1）递归+回溯：在叶子节点时将当前组合加入到结果集中，对每一个数字（也是一个节点）遍历其映射的所有可能字符。	中等

2.11-20

20	42.接雨水	给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。	思路：得到每个柱子左边和右边的最大高度就可以得到该柱子能盛的水量了。 （1）动态规划：使用两个数组，leftMax[i]表示位置i及其左边位置的最大高度，rightMax[i]表示位置i及其右边位置的最大高度 leftMax[i]=max(leftMax[i-1], height[i])； rightMax[i]=max(rightMax[i+1], height[i]); 位置i能盛的水量为min(leftMax[i],rightMax[i]) - height[i]，所以遍历height数组得到所有位置的盛水量即可 （2）单调栈：难理解 （3）双指针：难理解 （4）最大值+分割为2部分：扫描一趟，得到最大的height[x]，位置x就是最高点，然后将其分割为两部分， 左部分从左向右遍历，计算当前位置i及其左边的最大值leftMax，能盛容量leftMax-height[i]; 右部分从右向左遍历，计算当前j及其右边的最大值rightMax，能盛容量rightMax-height[j]	困难

3.21-30

4.31-40

5.41-50

6.51-60

7.61-70

8.71-80

9.81-90

10.91-100

二.代码

2.两数相加

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //尾插法
        ListNode helpNode = new ListNode(0);
        ListNode p=helpNode;
        int carry=0;
        int sum = 0;
        while(l1!=null || l2!=null){
            sum = carry;
            carry=0;
            if(l1!=null){
                sum += l1.val;
                l1 = l1.next;
            }
            if(l2!=null){
                sum += l2.val;
                l2 = l2.next;
            }
            sum += carry;
            if(sum>9){
                carry=1;
                sum = sum%10;
            }
            ListNode one = new ListNode(sum);
            p.next = one;
            p = one;
        }
        if(carry==1){
            p.next = new ListNode(1);
        }
        return helpNode.next;
    }

5.最长回文子串

动态规划：
枚举中心，扩展法：

    String answer = "";
    int answerLen = 0;
    // 扩展法
    public String longestPalindrome(String s) {
        int len = s.length();
        for(int i=0;i<len;i++){
            expand(s, i, i+1);
            expand(s, i, i);
        }
        return answer;
    }
    public void expand(String s, int start, int end){
        if(end>=s.length()){
            return;
        }
        // 扩展过程中有一对(i,j)不是回文就停止扩展
        while(start>=0 && end<s.length() && s.charAt(start) == s.charAt(end)){
            if(answerLen<end-start+1){
                answerLen = end-start+1;
                answer = s.substring(start,end+1);
            }
            start--;
            end++;
        }
    }

15.三数之和

    // 排序+双指针+去重(外循环去重+内循环去重), 时间O(NlogN)
    public List<List<Integer>> threeSum(int[] nums) {
        if(nums.length<3){
            return new ArrayList<>();
        }
        // 排序
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for(int i=0;i<nums.length-2;i++){
            // 外循环去重
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            int low = i + 1, high = nums.length - 1;
            while(low<high){
                int sum = nums[low]+nums[high];
                if(sum == -nums[i]){
                    res.add(Arrays.asList(nums[i], nums[low], nums[high]));
                    // 内循环low去重
                    while(low<high && nums[low]==nums[low+1]){
                        low++;
                    }
                    // 内循环high去重
                    while(low<high && nums[high]==nums[high-1]){
                        high--;
                    }
                    // 不能有重复则自增
                    low++;
                    high--;
                }else if(sum < -nums[i]){
                    low++;
                }else{
                    high--;
                }
            }
        }
        return res;
    }

17. 电话号码的字母组合

    // 设digits长度为n，就是有n个槽位，每个槽位都有对应的可能的几种字符，把所有可能的字符组合输出即可
    // 在叶子节点将选择的组合加入结果集：必须每个槽位都放置了字符时才可以输出
    public List<String> letterCombinations(String digits) {
        if(digits.length()==0){
            return new ArrayList<>();
        }
        Map<Character, String> map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
        List<String> res = new ArrayList<>();
        search(digits, res, new StringBuffer(), 0, map);
        return res;
    }
    // 递归
    // res结果集, current是当前放置了字符的所有槽位的字符组合
    public void search(String digits, List<String> res, StringBuffer current, int idx, Map<Character, String> map){
        // 每个槽位都放置了字符时才可以输出
        if(current.length() == digits.length()){
            res.add(current.toString());
            return;
        }
        char digit = digits.charAt(idx);
        String chars = map.get(digit);
        // 对每一个数字遍历其映射的所有字符
        for(int i=0;i<chars.length();i++){
            current.append(chars.charAt(i));
            search(digits, res, current, idx+1, map);
            current.deleteCharAt(current.length()-1);
        }
    }

19.删除链表的倒数第 N 个结点

    public ListNode removeNthFromEnd(ListNode head, int n) {
        //加上一个辅助头结点来避免讨论两种情况
        ListNode helpNode = new ListNode(0);
        helpNode.next = head;
        ListNode pre = helpNode;
        int move = n-1;
        ListNode p1=head,p2=head;
        // 让p2先走n-1步
        while(move>0){
            p2 = p2.next;
            move--;
        }
        while(p2.next!=null){
            p1 = p1.next;
            p2 = p2.next;
            pre = pre.next;
        }
        pre.next = p1.next;
        return helpNode.next;
    }

39.组合总和

递归+回溯：

    // 每个元素都大于0, 所以累积和达到target就可以停止向下搜索
    // (1)递归+回溯, 排序:当target小于0时就停止向下搜索
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        combinationSum(0, candidates, target, res, new ArrayList<>());
        return res;
    }
    /**
    * target: 当前目标值, 会一直减小
    * res: 全局结果集
    * current: 当前组合
    * idx:考虑输入数组的idx位置元素是否被选择
    */ 
    public void combinationSum(int idx, int[] candidates, int target, List<List<Integer>> res, List<Integer> current){
        if(target==0){
            res.add(new ArrayList<>(current));
            return;
        }
        // 考虑了所有位置元素是否选择后结束搜索
        // 放在当前组合加入全局结果集代码后面的原因：
        // 因为当前位置被选择后, 当前组合是否被加入全局结果集要在下次搜索时判断
        if(target<0 || idx>=candidates.length){
            return;
        }
        for(int i=idx;i<candidates.length;i++){
            current.add(candidates[i]);
            combinationSum(i, candidates, target-candidates[i], res, current);
            current.remove(current.size()-1);
        }

递归+回溯+循环：

    // 每个元素都大于0, 所以累积和达到target就可以停止向下搜索
    // (1)递归+回溯, 排序:当target小于0时就停止向下搜索
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        combinationSum(0, candidates, target, res, new ArrayList<>());
        return res;
    }
    /**
    * target: 当前目标值, 会一直减小
    * res: 全局结果集
    * current: 当前组合
    * idx:考虑输入数组的idx位置元素是否被选择
    */ 
    public void combinationSum(int idx, int[] candidates, int target, List<List<Integer>> res, List<Integer> current){
        if(target==0){
            res.add(new ArrayList<>(current));
            return;
        }
        // 考虑了所有位置元素后结束搜索
        // 放在当前组合加入全局结果集代码后面的原因：
        // 因为当前位置被选择后, 当前组合是否被加入全局结果集要在下次搜索时判断
        if(target<0 || idx>=candidates.length){
            return; 
        }
        // 当前组合选择 idx 位置元素
        current.add(candidates[idx]);
        // 因为可以重复选则, 所以下次选择还是从idx位置开始
        combinationSum(idx, candidates, target-candidates[idx], res, current);
        // 当前组合不选择 idx 位置元素, 不选择了就从 idx+1 开始
        current.remove(current.size()-1);
        combinationSum(idx+1, candidates, target, res, current);
    }

42.接雨水

最大值+划分两部分：

    public int trap(int[] height) {
        int len = height.length;
        // 要能盛水至少要三根柱子
        if(len<3){
            return 0;
        }
        int volume = 0, maxHeightIndex = 0, maxHeight = Integer.MIN_VALUE;
        for(int i=0;i<len;i++){
            if(height[i]>maxHeight){
                maxHeight = height[i];
                maxHeightIndex = i;
            }
        }
        int leftMax=height[0], rightMax=height[len-1];
        // 遍历左部分
        for(int i=0;i<=maxHeightIndex-1;i++){
            leftMax = Math.max(leftMax, height[i]);
            volume += leftMax - height[i];
        }
        // 遍历右部分
        for(int j=len-1;j>=maxHeightIndex+1;j--){
            rightMax = Math.max(rightMax, height[j]);
            volume += rightMax - height[j];
        }
        return volume;
    }

46.全排列

    // 递归 + 循环 + 回溯 + 状态
    public List<List<Integer>> permute(int[] nums) {
        if(nums==null || nums.length==0){
            return new ArrayList<>();
        }
        List<List<Integer>> res = new ArrayList<>();
        permute(nums, res, new ArrayList<>(), new boolean[nums.length]);
        return res;
    }
    // 第一调用该函数时，for循环会把所有元素都尝试放在第一个位置，然后继续调用函数
    public void permute(int[] nums, List<List<Integer>> res, List<Integer> current, boolean[] status){
        if(current.size()==nums.length){
            res.add(new ArrayList<>(current));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(status[i]){
                continue;
            }
            current.add(nums[i]);
            status[i] = true;
            permute(nums, res, current, status);
            current.remove(current.size()-1);
            status[i] = false;
        }
    }

75.颜色分类

    // 两趟遍历,O(1)空间
    public void sortColors(int[] nums) {
        if(nums==null || nums.length==0){
            return;
        }
        int index=0;
        // 将所有的0放到头部
        // 有没有可能的元素和要待交换的位置index的元素都是0既nums[index]、nums[i]都是0
        // 只可能出现在最开始位置，比如对于序列0、0、1、0，前两个0对应的i、index都是0，但从1
        // 之后就不是了
        for(int i=0;i<nums.length;i++){
            if(nums[i]==0){
                swap(nums, index, i);
                index++;
            }
        }
        // 将所有的1放到头部的0后面
        for(int i=0;i<nums.length;i++){
            if(nums[i]==1){
                swap(nums, index, i);
                index++;
            }
        }
    }
    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

98.验证二叉搜索树

递归：hep函数，节点值应该在一(lowBorder, highBorder)内

    // help(root, lowBorder, highBorder)
    // 输入可能是Integer.MIN_VALUE或Integer.MAX_VALUE这种极端情况,所以使用long的最大值、最小值来规避
    public boolean isValidBST(TreeNode root) {
        return help(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    public boolean help(TreeNode root, long lowBorder, long highBorder){
        if(root == null){
            return true;
        }
        if(root.val<=lowBorder || root.val >=highBorder){
            return false;
        }
        return help(root.left, lowBorder, root.val) && help(root.right, root.val ,highBorder);
    }

中序遍历：

    // 输入可能是Integer.MIN_VALUE或Integer.MAX_VALUE这种极端情况,所以使用long的最小值来规避
    private long pre = Long.MIN_VALUE;
    private boolean flag = true;
    public boolean isValidBST(TreeNode root) {
        inOrder(root);
        return flag;
    }
    public void inOrder(TreeNode root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        if(root.val>pre){
            pre = root.val;
        }else{
            flag = false;
            return;
        }
        inOrder(root.right);
    }

169.多数元素

摩尔投票法：

    public int majorityElement(int[] nums) {
        int target = -1;
        int count = 0;
        for(int num:nums){
            if(count==0){
                target = num;
            }else{
                if(num!=target){
                    count--;
                }else{
                    count++;
                }
            }
        }
        return target;
    }

206.反转链表

递归：

    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode nextNode = head.next;
        ListNode root = reverseList(nextNode);
        head.next = null;
        nextNode.next = head;
        return root;
    }

迭代：

    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode p1 = head;
        ListNode p2 = head.next;
        // 防止循环
        head.next = null;
        while(p2!=null){
            // 保存p2的next
            ListNode nextNode = p2.next;
            // 反转指针
            p2.next = p1;
            // 移动p1, p2
            p1 = p2;
            p2 = nextNode;
        }
        return p1;
    }

128.最长连续序列

哈希表，时间O(N)

    public int longestConsecutive(int[] nums) {
        if(nums==null || nums.length==0){
            return 0;
        }
        Set<Integer> set = new HashSet<>();
        for(int num:nums){
            set.add(num);
        }
        int maxLen = 1;
        for(int num:nums){
            if(set.contains(num-1)){
                continue;
            }
            int count = 0;
            while(set.contains(num)){
                count++;
                num++;
            }
            maxLen = Math.max(maxLen, count);
        }
        return maxLen;
    }

139.单词拆分

动态规划

    public boolean wordBreak(String s, List<String> wordDict) {
        if(s==null || s.length()==0){
            return true;
        }
        int len = s.length();
        Set<String> set = new HashSet<>();
        for(String str: wordDict){
            set.add(str);
        }
        // dp[0]表示空串是否在wordDict中存在, dp[i]表示s的[0,i-1]区间是否可以拆分后存在于wordDict
        boolean[] dp = new boolean[len+1];
        dp[0] = true;
        // 枚举所有长度, 小于等于len
        for(int i=1;i<=len;i++){
            // 枚举i的所有子区间
            for(int j=0;j<i;j++){
                if(dp[j] && set.contains(s.substring(j,i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }

141.环形链表

    public boolean hasCycle(ListNode head) {
        if(head==null || head.next==null){
            return false;
        }
        ListNode slow = head.next;
        ListNode fast = head.next.next;
        while(fast!=null && fast.next!=null){
            if(fast==slow){
                return true;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return false;
    }

207.课程表

拓扑排序+DFS

    // 拓扑排序+DFS
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] edges = new ArrayList[numCourses];
        // 入度数组, inDegree[i]表示课程i的前置课程数量
        int[] inDegree = new int[numCourses];
        // 构建临接表
        for(int[] pre: prerequisites){
            int inNumber = pre[0];
            int outNumber = pre[1];
            inDegree[inNumber]++;
            if(edges[outNumber]==null){
                edges[outNumber] = new ArrayList<>();
            }
            edges[outNumber].add(inNumber);
        }
        Deque<Integer> queue = new LinkedList<>();
        for(int i=0;i<inDegree.length;i++){
            if(inDegree[i]==0){
                queue.add(i);
            }
        }
        int count = 0;
        while(queue.size()>0){
            int courseNumber = queue.poll();
            count++;
            if(edges[courseNumber]!=null){
                for(int num: edges[courseNumber]){
                    inDegree[num]--;
                    if(inDegree[num]==0){
                        queue.add(num);
                    }
                }
            }
        }
        return count==numCourses;
    }

208.实现 Trie (前缀树)

class Trie {
    Trie[] children;
    boolean isEnd;
    /** Initialize your data structure here. */
    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        Trie node = this;
        for(int i=0;i<word.length();i++){
            int index = word.charAt(i) - 'a';
            if(node.children[index]==null){
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node!=null && node.isEnd;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix)!=null;
    }
    public Trie searchPrefix(String word){
        Trie node = this;
        for(int i=0;i<word.length();i++){
            int index = word.charAt(i) - 'a';
            if(node.children[index]==null){
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}

234. 回文链表

快慢指针找中点+翻转后半段+遍历前半段和翻转后的后半段，空间O(N)，如果是用迭代翻转就是O(1)

    public boolean isPalindrome(ListNode head) {
        if(head==null || head.next==null){
            return true;
        }
        ListNode midPre = getMid(head);
        ListNode nextHalfHead = midPre.next;
        midPre.next = null;
        nextHalfHead = reverse(nextHalfHead);
        while(head!=null){
            if(head.val!=nextHalfHead.val){
                return false;
            }
            head = head.next;
            nextHalfHead = nextHalfHead.next;
        }
        return true;
    }
    // 返回中点的pre节点,当节点数为奇数时,后半段会比前半段多一个，但是不影响判断
    // 因为反转后多的这一个处于后半段的最后一个位置
    public ListNode getMid(ListNode head){
        // 只有两个节点时,将head返回
        if(head.next.next==null){
            return head;
        }
        ListNode slow = head.next;
        ListNode fast = head.next.next;
        // slow的前驱,既中点的前驱节点
        ListNode pre = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            pre = pre.next;
        }
        return pre;
    }
    // 返回翻转后的链表
    public ListNode reverse(ListNode head){
        if(head==null || head.next==null){
            return head;
        }
        ListNode nextTemp = head.next;
        ListNode root = reverse(nextTemp);
        head.next = null;
        nextTemp.next = head;
        return root;
    }

236.二叉树的最近公共祖先

递归

    TreeNode answer = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        nodeContains(root, p, q);
        return answer;
    }
    public boolean nodeContains(TreeNode root, TreeNode p, TreeNode q){
        if(root==null){
            return false;
        }
        boolean leftContain = nodeContains(root.left, p, q);
        boolean rightContain = nodeContains(root.right, p, q);
        // root是p或q, 同时左右子树中有一颗树包含p或q
        if((root==p || root==q) && (leftContain || rightContain)){
            answer = root;
            return true;
        }
        // 左右子树都包含p或q
        if(leftContain && rightContain){
            answer = root;
            return true;
        }
        return root==p || root==q || leftContain || rightContain;
    }

存储父节点

    TreeNode answer = null;
    // 记录父节点信息
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode, TreeNode> map = new HashMap<>();
        recordParent(root, map);
        Set<TreeNode> set = new HashSet<>();
        visitUp(p, set, map);
        visitUp(q, set, map);
        return answer;
    }
    public void recordParent(TreeNode root, Map<TreeNode,TreeNode> map){
        if(root==null){
            return;
        }
        if(root.left!=null){
            map.put(root.left, root);
            recordParent(root.left, map);
        }
        if(root.right!=null){
            map.put(root.right, root);
            recordParent(root.right, map);
        }
    }
    // 从node节点一直向上遍历
    public void visitUp(TreeNode node, Set<TreeNode> set, Map<TreeNode, TreeNode> map){
        if(node==null){
            return;
        }
        if(set.contains(node)){
            answer = node;
            return;
        }
        set.add(node);
        visitUp(map.get(node), set, map);
    }

找到从root到p、q的路径，分叉点就是LCA

238. 除自身以外数组的乘积

左右乘积列表，使用结果集res作为左乘积列表，动态构建右乘积列表，并将其乘到res对应位置上

    // 左右乘积数组
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] res = new int[len];
        res[0] = 1;
        // 构造左乘积数组
        for(int i=1;i<len;i++){
            res[i] = nums[i-1]*res[i-1];
        }
        // 
        int rightProduct = 1;
        for(int i=len-2;i>=0;i--){
            // 动态构建右乘积
            rightProduct *= nums[i+1];
            // 将右乘积乘到结果集对应位置上
            res[i] *= rightProduct;
        }
        return res;
    }

461.汉明距离

Brian W. Kernighan算法
时间复杂度O(logn)

    public int hammingDistance(int x, int y) {
        int s = x ^ y, ret = 0;
        while (s != 0) {
            s &= s - 1;
            ret++;
        }
        return ret;
    }