力扣爆刷第109天之CodeTop100五连刷31-35

力扣爆刷第109天之CodeTop100五连刷31-35

一、56. 合并区间

题目链接：https://leetcode.cn/problems/merge-intervals/description/
思路：合并区间，需要先按照左边界排序，然后维护一个left和right，每次都比较当前的区间的左边界是否落点在right左边，在就合并区间，不在就保存[left, right]，然后再单开一个新区间。

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0]-b[0]);
        List<int[]> list = new ArrayList<>();
        int left = intervals[0][0], right = intervals[0][1];
        for(int i = 0; i < intervals.length; i++) {
            if(intervals[i][0] <= right) {
                right = Math.max(right, intervals[i][1]);
            }else{
                list.add(new int[]{left, right});
                left = intervals[i][0];
                right = intervals[i][1];
            }
        }
        list.add(new int[]{left, right});
        int[][] res = new int[list.size()][2];
        for(int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

二、124. 二叉树中的最大路径和

题目链接：https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/
思路：求最大路径，后序遍历，对于左右节点，只计算大于0的，这种贪心策略才能得到最大值，递归返回只能返回最大的一个子树路径。

class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
       order(root);
       return max;
    }
    
    int order(TreeNode root) {
        if(root == null) return 0;
        int left = order(root.left);
        int right = order(root.right);
        left = left > 0 ? left : 0;
        right = right > 0 ? right : 0;
        max = Math.max(max, root.val + left + right);
        return root.val + Math.max(left, right);
    }
}

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

题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
思路：要找到倒数第n个节点的位置，直接快慢指针，慢指针先不动，然后快指针先走n步，然后再快慢指针一块走，当快指针走到结尾处，慢指针的下一个位置就是要删除的节点。

class Solution {
   public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode root = new ListNode(-1, head);
        ListNode slow = root, fast = root;
        for(int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while(fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        fast = slow.next;
        slow.next = fast.next;
        fast.next = null;
        return root.next;
    }
}

四、72. 编辑距离

题目链接：https://leetcode.cn/problems/edit-distance/description/
思路：编辑距离，定义dp[i][j]表示以word1[i]和word2[j]为结尾的字符串要相等所需的最少改动，如果word[i]==word[j]那么状态自然可以从上一个状态推导出来，即dp[i][j] = dp[i-1][j-1];。如word[i] != word[j]，可以考虑增加、删除、修改，可从三个方向推导出来，dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1])+1;

class Solution {
   public int minDistance(String word1, String word2) {
        int n1 = word1.length(), n2 = word2.length();
        int[][] dp = new int[n1+1][n2+1];
        for(int i = 0; i <= n1; i++) {
            dp[i][0] = i;
        }
        for(int i = 0; i <= n2; i++) {
            dp[0][i] = i;
        }
        for(int i = 1; i <= n1; i++) {
            for(int j = 1; j <= n2; j++) {
                if(word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1])+1;
                }
            }
        }
        return dp[n1][n2];
    }
}

五、93. 复原 IP 地址

题目链接：https://leetcode.cn/problems/restore-ip-addresses/description/
思路：典型的组合题目，组合需要索引位置，出了字符串拼接判断麻烦一点，其他的就是简单的组合。

class Solution {
    List<String> list = new ArrayList<>();
    List<String> temp = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        backTracking(s, 0);
        return list;
    }
    void backTracking(String s, int index) {
        if(temp.size() == 4) {
            if(index == s.length()) {
                list.add(String.join(".", temp));
            }
            return;
        }
        for(int i = index; i < s.length(); i++) {
            if (list.size() == 3 && i-index > 2) return;
            String res = isTrue(s, index, i);
            if(res != null) {
                temp.add(res);
                backTracking(s, i+1);
                temp.remove(temp.size()-1);
            }
        }
    }
    String isTrue(String s, int x, int y) {
        if(y - x > 2) return null;
        if(y - x >= 1 && s.charAt(x) == '0') return null;
        String ss = s.substring(x, y+1);
        int k = Integer.valueOf(ss);
        if(k >= 0 && k <= 255) return ss;
        return null;
    }
}