Merge remote-tracking branch 'origin/master'

yuanguangxin · yuanguangxin · commit 7cfdb1282a08 · 2020-03-26T23:10:39.000+08:00
# Conflicts:
#	.idea/workspace.xml
#	README.md
diff --git a/.idea/workspace.xml b/.idea/workspace.xml
diff --git a/README.md b/README.md
@@ -9,6 +9,8 @@
 ### 链表操作
 
 * [q2_两数相加](/src/链表操作/q2_两数相加)
+* [q19_删除链表的倒数第N个节点](/src/链表操作/q19_删除链表的倒数第N个节点)
+* [q61_旋转链表](/src/链表操作/q61_旋转链表)
 * [q138_复制带随机指针的链表](/src/链表操作/q138_复制带随机指针的链表)
 * [q206_反转链表](/src/链表操作/q206_反转链表)
 
@@ -52,10 +54,13 @@
 
 * [q54_螺旋矩阵](/src/数组操作/q54_螺旋矩阵)
 * [q73_矩阵置零](/src/数组操作/q73_矩阵置零)
+* [q945_使数组唯一的最小增量](/src/数组操作/q945_使数组唯一的最小增量)
 
 ### 栈相关
 
 * [q20_有效的括号](/src/栈相关/q20_有效的括号)
+* [q32_最长有效括号](/src/栈相关/q32_最长有效括号)
+* [q155_最小栈](/src/栈相关/q155_最小栈)
 * [q224_基本计算器](/src/栈相关/q224_基本计算器)
 * [q316_去除重复字母](/src/栈相关/q316_去除重复字母)
 
@@ -68,18 +73,22 @@
 
 * [q21_合并两个有序链表](/src/递归/q21_合并两个有序链表)
 * [q101_对称二叉树](/src/递归/q101_对称二叉树)
+* [q104_二叉树的最大深度](/src/递归/q104_二叉树的最大深度)
 * [q226_翻转二叉树](/src/递归/q226_翻转二叉树)
 * [q236_二叉树的最近公共祖先](/src/递归/q236_二叉树的最近公共祖先)
 
 ### 分治法/二分法
 
 * [q23_合并K个排序链表](/src/分治法/q23_合并K个排序链表)
 * [q33_搜索旋转排序数组](/src/分治法/q33_搜索旋转排序数组)
+* [q34_在排序数组中查找元素的第一个和最后一个位置](/src/分治法/q34_在排序数组中查找元素的第一个和最后一个位置)
 
 ### 动态规划
 
 * [q5_最长回文子串](/src/动态规划/q5_最长回文子串)
 * [q53_最大子序和](/src/动态规划/q53_最大子序和)
+* [q64_最小路径和](/src/动态规划/q64_最小路径和)
+* [q70_爬楼梯](/src/动态规划/q70_爬楼梯)
 * [q118_杨辉三角](/src/动态规划/q118_杨辉三角)
 * [q300_最长上升子序列](/src/动态规划/q300_最长上升子序列)
 * [q746_使用最小花费爬楼梯](/src/动态规划/q746_使用最小花费爬楼梯)
diff --git a/Rocket.md b/Rocket.md
@@ -601,7 +601,6 @@ TCP是一个双向通信协议，通信双方都有能力发送信息，并接
 
 因为当Server端收到Client端的SYN连接请求报文后，可以直接发送SYN+ACK报文。其中ACK报文是用来应答的，SYN报文是用来同步的。但是关闭连接时，当Server端收到FIN报文时，很可能并不会立即关闭SOCKET，所以只能先回复一个ACK报文，告诉Client端，"你发的FIN报文我收到了"。只有等到我Server端所有的报文都发送完了，我才能发送FIN报文，因此不能一起发送。故需要四步握手。
 
-
 ## 数据结构与算法
 
 ### 排序算法
diff --git a/src/分治法/q34_在排序数组中查找元素的第一个和最后一个位置/Solution.java b/src/分治法/q34_在排序数组中查找元素的第一个和最后一个位置/Solution.java
@@ -0,0 +1,60 @@
+package 分治法.q34_在排序数组中查找元素的第一个和最后一个位置;
+
+/**
+ * 二分法 o(log(n))
+ */
+public class Solution {
+
+    public int[] searchRange(int[] nums, int target) {
+        if (nums == null || nums.length < 1) {
+            return new int[]{-1, -1};
+        }
+        int midIndex = find(0, nums.length - 1, nums, target);
+        int[] rs = new int[2];
+        rs[0] = midIndex;
+        rs[1] = midIndex;
+        if (midIndex == -1) {
+            return rs;
+        }
+        while (nums[rs[0]] == target && rs[0] > 0) {
+            int temp = find(0, rs[0] - 1, nums, target);
+            if (temp == -1) {
+                break;
+            } else {
+                rs[0] = temp;
+            }
+        }
+
+        while (nums[rs[1]] == target && rs[1] < nums.length - 1) {
+            int temp = find(rs[1] + 1, nums.length - 1, nums, target);
+            if (temp == -1) {
+                break;
+            } else {
+                rs[1] = temp;
+            }
+        }
+        return rs;
+    }
+
+    public int find(int beginIndex, int endIndex, int[] nums, int target) {
+        if (beginIndex == endIndex) {
+            if (nums[beginIndex] == target) {
+                return beginIndex;
+            } else {
+                return -1;
+            }
+        }
+        int mid = (endIndex - beginIndex) / 2 + beginIndex;
+        if (nums[mid] > target) {
+            return find(beginIndex, mid, nums, target);
+        } else if (nums[mid] < target) {
+            return find(mid + 1, endIndex, nums, target);
+        } else {
+            return mid;
+        }
+    }
+
+    public static void main(String[] args) {
+        new Solution().searchRange(new int[]{2, 2}, 2);
+    }
+}
diff --git a/src/动态规划/q64_最小路径和/Solution.java b/src/动态规划/q64_最小路径和/Solution.java
@@ -0,0 +1,26 @@
+package 动态规划.q64_最小路径和;
+
+/**
+ * 动态规划 dp(j)=grid(i,j)+min(dp(j),dp(j+1)) o(m*n)
+ */
+public class Solution {
+
+    public int minPathSum(int[][] grid) {
+        int[] dp = new int[grid[0].length];
+        for (int i = grid.length - 1; i >= 0; i--) {
+            for (int j = grid[0].length - 1; j >= 0; j--) {
+                if (i == grid.length - 1 && j != grid[0].length - 1) {
+                    dp[j] = grid[i][j] + dp[j + 1];
+                } else if (j == grid[0].length - 1 && i != grid.length - 1) {
+                    dp[j] = grid[i][j] + dp[j];
+                } else if (j != grid[0].length - 1 && i != grid.length - 1) {
+                    dp[j] = grid[i][j] + Math.min(dp[j], dp[j + 1]);
+
+                } else {
+                    dp[j] = grid[i][j];
+                }
+            }
+        }
+        return dp[0];
+    }
+}
diff --git a/src/动态规划/q70_爬楼梯/Solution.java b/src/动态规划/q70_爬楼梯/Solution.java
@@ -0,0 +1,20 @@
+package 动态规划.q70_爬楼梯;
+
+/**
+ * 动态规划 dp[i]表示到达第i阶的方法总数dp[i]=dp[i−1]+dp[i−2] o(n)
+ */
+public class Solution {
+
+    public int climbStairs(int n) {
+        if (n == 1) {
+            return 1;
+        }
+        int[] dp = new int[n + 1];
+        dp[1] = 1;
+        dp[2] = 2;
+        for (int i = 3; i <= n; i++) {
+            dp[i] = dp[i - 1] + dp[i - 2];
+        }
+        return dp[n];
+    }
+}
diff --git a/src/数组操作/q945_使数组唯一的最小增量/Solution.java b/src/数组操作/q945_使数组唯一的最小增量/Solution.java
@@ -0,0 +1,28 @@
+package 数组操作.q945_使数组唯一的最小增量;
+
+import java.util.Arrays;
+
+/**
+ * 先排序再遍历一次 o(n*log(n))
+ */
+public class Solution {
+
+    public int minIncrementForUnique(int[] A) {
+        if (A == null || A.length == 0 || A.length == 1) {
+            return 0;
+        }
+
+        int rs = 0;
+        Arrays.sort(A);
+
+        int t = A[0];
+        for (int i = 1; i < A.length; i++) {
+            if (A[i] <= t) {
+                rs = rs + t - A[i] + 1;
+                A[i] = t + 1;
+            }
+            t = A[i];
+        }
+        return rs;
+    }
+}
diff --git a/src/栈相关/q155_最小栈/MinStack.java b/src/栈相关/q155_最小栈/MinStack.java
@@ -0,0 +1,43 @@
+package 栈相关.q155_最小栈;
+
+import java.util.Stack;
+
+/**
+ * 不使用辅助栈，每次push两个元素
+ */
+public class MinStack {
+
+    private Stack<Integer> stack;
+
+    public MinStack() {
+        stack = new Stack<>();
+    }
+
+    public void push(int x) {
+        if (stack.isEmpty()) {
+            stack.push(x);
+            stack.push(x);
+        } else {
+            int tmp = stack.peek();
+            stack.push(x);
+            if (tmp < x) {
+                stack.push(tmp);
+            } else {
+                stack.push(x);
+            }
+        }
+    }
+
+    public void pop() {
+        stack.pop();
+        stack.pop();
+    }
+
+    public int top() {
+        return stack.get(stack.size() - 2);
+    }
+
+    public int getMin() {
+        return stack.peek();
+    }
+}
diff --git a/src/栈相关/q32_最长有效括号/Solution.java b/src/栈相关/q32_最长有效括号/Solution.java
@@ -0,0 +1,38 @@
+package 栈相关.q32_最长有效括号;
+
+import java.util.Stack;
+
+/**
+ * 利用索引栈 o(n)
+ */
+public class Solution {
+
+    public int longestValidParentheses(String s) {
+        if (s == null || s.length() < 2) {
+            return 0;
+        }
+
+        int maxLen = 0;
+        Stack<Integer> stack = new Stack<>();
+        stack.push(-1);
+        for (int i = 0; i < s.length(); i++) {
+            char temp = s.charAt(i);
+            if (temp == '(') {
+                stack.push(i);
+            } else {
+                stack.pop();
+                if (stack.empty()) {
+                    stack.push(i);
+                } else {
+                    maxLen = Math.max(maxLen, i - stack.peek());
+                }
+            }
+        }
+
+        return maxLen;
+    }
+
+    public static void main(String[] args) {
+        System.out.println(new Solution().longestValidParentheses(")()())"));
+    }
+}
diff --git a/src/递归/q104_二叉树的最大深度/Solution.java b/src/递归/q104_二叉树的最大深度/Solution.java
@@ -0,0 +1,17 @@
+package 递归.q104_二叉树的最大深度;
+
+/**
+ * 递归 o(n)
+ */
+public class Solution {
+
+    public int maxDepth(TreeNode root) {
+        if (root == null) {
+            return 0;
+        } else {
+            int leftHeight = maxDepth(root.left);
+            int rightHeight = maxDepth(root.right);
+            return Math.max(leftHeight, rightHeight) + 1;
+        }
+    }
+}
diff --git a/src/递归/q104_二叉树的最大深度/TreeNode.java b/src/递归/q104_二叉树的最大深度/TreeNode.java
@@ -0,0 +1,11 @@
+package 递归.q104_二叉树的最大深度;
+
+public class TreeNode {
+    int val;
+    TreeNode left;
+    TreeNode right;
+
+    TreeNode(int x) {
+        val = x;
+    }
+}
diff --git a/src/链表操作/q19_删除链表的倒数第N个节点/ListNode.java b/src/链表操作/q19_删除链表的倒数第N个节点/ListNode.java
@@ -0,0 +1,12 @@
+package 链表操作.q19_删除链表的倒数第N个节点;
+
+
+public class ListNode {
+    int val;
+    ListNode next;
+
+    ListNode(int x) {
+        val = x;
+    }
+}
+
diff --git a/src/链表操作/q19_删除链表的倒数第N个节点/Solution.java b/src/链表操作/q19_删除链表的倒数第N个节点/Solution.java
@@ -0,0 +1,25 @@
+package 链表操作.q19_删除链表的倒数第N个节点;
+
+/**
+ * 利用两个指针 o(n)
+ */
+public class Solution {
+
+    public ListNode removeNthFromEnd(ListNode head, int n) {
+        ListNode dummy = new ListNode(0);
+        dummy.next = head;
+        ListNode first = dummy;
+        ListNode second = dummy;
+
+        for (int i = 1; i <= n + 1; i++) {
+            first = first.next;
+        }
+
+        while (first != null) {
+            first = first.next;
+            second = second.next;
+        }
+        second.next = second.next.next;
+        return dummy.next;
+    }
+}
diff --git a/src/链表操作/q61_旋转链表/ListNode.java b/src/链表操作/q61_旋转链表/ListNode.java
@@ -0,0 +1,10 @@
+package 链表操作.q61_旋转链表;
+
+public class ListNode {
+    int val;
+    ListNode next;
+
+    ListNode(int x) {
+        val = x;
+    }
+}
diff --git a/src/链表操作/q61_旋转链表/Solution.java b/src/链表操作/q61_旋转链表/Solution.java
@@ -0,0 +1,31 @@
+package 链表操作.q61_旋转链表;
+
+/**
+ * 先连接成环再找断点 o(n)
+ */
+public class Solution {
+
+    public ListNode rotateRight(ListNode head, int k) {
+        if (head == null) {
+            return null;
+        }
+        if (head.next == null) {
+            return head;
+        }
+
+        ListNode oldTail = head;
+        int n;
+        for (n = 1; oldTail.next != null; n++) {
+            oldTail = oldTail.next;
+        }
+        oldTail.next = head;
+        ListNode newTail = head;
+        for (int i = 0; i < n - k % n - 1; i++) {
+            newTail = newTail.next;
+        }
+        ListNode newHead = newTail.next;
+        newTail.next = null;
+
+        return newHead;
+    }
+}
