algorithm001 · alxjerr · Apr 20, 2019 · Apr 28, 2019 · May 5, 2019 · May 12, 2019
diff --git a/Week_01/id_97/24.SwapNodesinPairs.java b/Week_01/id_97/24.SwapNodesinPairs.java
@@ -0,0 +1,27 @@
+/**
+ * Definition for singly-linked list.
+ * public class ListNode {
+ *     int val;
+ *     ListNode next;
+ *     ListNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public ListNode swapPairs(ListNode head) {
+        ListNode dummyHead = new ListNode(-1);
+        dummyHead.next = head;
+        ListNode pre = dummyHead;
+        ListNode cur = head;
+        while(cur != null && cur.next != null){
+            ListNode temp = cur.next;
+
+            cur.next = temp.next;
+            temp.next = cur;
+            pre.next = temp;
+
+            pre = cur;
+            cur = cur.next;
+        }
+        return dummyHead.next;
+    }
+}
diff --git a/Week_01/id_97/83. Remove Duplicates from Sorted List b/Week_01/id_97/83. Remove Duplicates from Sorted List
@@ -0,0 +1,27 @@
+/**
+ * Definition for singly-linked list.
+ * public class ListNode {
+ *     int val;
+ *     ListNode next;
+ *     ListNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public ListNode deleteDuplicates(ListNode head) {
+        if(head == null){
+            return null;
+        }
+        ListNode cur = head;
+
+        while(cur != null){
+            ListNode temp = cur.next;
+            if (temp != null && cur.val == temp.val ) {
+                cur.next = temp.next;
+            }else {
+                cur = cur.next;
+            }
+        }
+
+        return head;
+    }
+}
diff --git a/Week_01/id_97/905. Sort Array By Parity b/Week_01/id_97/905. Sort Array By Parity
@@ -0,0 +1,34 @@
+class Solution {
+    public int[] sortArrayByParity(int[] A) {
+        if(A == null || A.length == 1)
+            return A;
+
+        int left = 0;
+        int right = A.length - 1;
+
+        if(left>right)
+            return null;
+
+        int i = left;
+        int j = right;
+        int t ;
+
+        while (i != j){
+
+            while (A[j] % 2 != 0 && i < j)
+                j--;
+
+            while (A[i] % 2 == 0 && i < j)
+                i++;
+
+            if (i < j){
+                t = A[i];
+                A[i] = A[j];
+                A[j] = t;
+            }
+        }
+
+        return A;
+
+    }
+}
diff --git a/Week_01/id_97/NOTE.md b/Week_01/id_97/NOTE.md
@@ -1 +1,20 @@
-# 学习笔记
+# 学习笔记
+
+## 使用栈解决括号匹配：
+
+首先声明一个栈，然后从左向右遍历字符串，遇到左括号入栈(不论是小、中、大括号)。
+
+如果遇到的字符是个右括号，然后我们看栈顶的括号是否匹配。匹配出栈。
+
+## 两两交换链表中的节点
+定义一个dummyHead。
+定义三个“指针”，分别是前指针pre、现指针cur、后继指针next
+
+## 删除链表中重复元素
+
+## 按奇偶排序数组
+定义两个“指针”，分别从数组的两端遍历数组。数组左半部分存放偶数，右半部分存放奇数。
+
+
+
+
diff --git a/Week_01/id_97/ValidParentheses.java b/Week_01/id_97/ValidParentheses.java
@@ -0,0 +1,47 @@
+package com.leetcode.stack;
+
+import java.util.Stack;
+
+/**
+ *  20. 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
+ *
+ * 有效字符串需满足：
+ *
+ * 左括号必须用相同类型的右括号闭合。
+ * 左括号必须以正确的顺序闭合。
+ *
+ * 输入: "()[]{}"
+ * 输出: true
+ *
+ * 输入: "(]"
+ * 输出: false
+ */
+public class ValidParentheses {
+
+    public boolean isValid(String s) {
+        Stack<Character> stack = new Stack<>();
+
+        for (int i = 0;i < s.length();i++){
+            char c = s.charAt(i);
+            if (c == '(' || c == '[' || c == '{')
+                stack.push(c);
+            else {
+                if (stack.isEmpty()) return false;
+
+                char topChar = stack.pop();
+                if (c == ')' && topChar != '(')
+                    return false;
+                if(c == ']' && topChar != '[')
+                    return false;
+                if(c == '}' && topChar != '{')
+                    return false;
+            }
+        }
+        return stack.isEmpty();
+    }
+
+    public static void main(String[] args) {
+        String s =  "()[]{}";
+    }
+
+}
diff --git a/Week_02/id_97/LeetCode_242_097.java b/Week_02/id_97/LeetCode_242_097.java
@@ -0,0 +1,33 @@
+package com.leetcode.hash;
+
+/**
+ * 242. 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。
+ *  示例 1:
+ *      输入: s = "anagram", t = "nagaram"
+ *      输出: true
+ *
+ *  示例 2:
+ *      输入: s = "rat", t = "car"
+ *      输出: false
+ *
+ *  思路分析：只要记录两个字符串各个字符串出现的次数，然后判断是否相同即可。（时间复杂度O(n)，空间复杂度O(1)）
+ */
+public class ValidAnagram {
+
+    public boolean isAnagram(String s, String t) {
+        int[] cntVec = new int[26];
+
+        for (int i = 0;i < s.length();i++)
+            cntVec[s.charAt(i) - 'a'] += 1;
+
+        for (int j = 0;j <t.length();j++)
+            cntVec[t.charAt(j) - 'a'] -= 1;
+
+        for (int k = 0; k < cntVec.length;k++){
+            if (cntVec[k] != 0)
+                return false;
+        }
+        return true;
+    }
+
+}
diff --git a/Week_02/id_97/LeetCode_671_097.java b/Week_02/id_97/LeetCode_671_097.java
@@ -0,0 +1,50 @@
+package com.leetcode.binarytree;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+
+/**
+ * 给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。
+ *
+ * 给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。
+ *
+ * 示例 1:
+ *
+ * 输入:
+ *     2
+ *    / \
+ *   2   5
+ *      / \
+ *     5   7
+ *
+ * 输出: 5
+ * 说明: 最小的值是 2 ，第二小的值是 5 。
+ *
+ *
+ * 输入:
+ *     2
+ *    / \
+ *   2   2
+ *
+ * 输出: -1
+ * 说明: 最小的值是 2, 但是不存在第二小的值。
+ */
+public class SecondMinimumNodeInaBinaryTree671 {
+
+    public int findSecondMinimumValue(TreeNode root) {
+        long ans = traversal(root, root.val);
+        return ans > Integer.MAX_VALUE ? -1 : (int)ans;
+    }
+
+    //所有大于value节点的最小值即为第二小的节点
+    public long traversal(TreeNode root, int value){
+        if(root != null){
+            if(root.val > value)
+                return root.val;
+            return Math.min(traversal(root.left, value), traversal(root.right, value));
+        }
+        return (long)Integer.MAX_VALUE + 1;
+    }
+
+}
diff --git a/Week_02/id_97/LeetCode_783_097.java b/Week_02/id_97/LeetCode_783_097.java
@@ -0,0 +1,64 @@
+package com.leetcode.binarytree;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ *
+ * 给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。
+ *
+ * 示例：
+ *
+ * 输入: root = [4,2,6,1,3,null,null]
+ * 输出: 1
+ * 解释:
+ * 注意，root是树结点对象(TreeNode object)，而不是数组。
+ *
+ * 给定的树 [4,2,6,1,3,null,null] 可表示为下图:
+ *
+ *           4
+ *         /   \
+ *       2      6
+ *      / \
+ *     1   3
+ *
+ * 最小的差值是 1, 它是节点1和节点2的差值, 也是节点3和节点2的差值。
+ * 注意：
+ *
+ * 二叉树的大小范围在 2 到 100。
+ * 二叉树总是有效的，每个节点的值都是整数，且不重复。
+ *
+ */
+public class MinimumDistanceBetweenBSTNodes783 {
+
+    List<Integer> res = new ArrayList<>();
+
+    public int min =0;
+
+    public int minDiffInBST(TreeNode root) {
+        if (root == null) return 0;
+        getInOrder(root);
+        return min;
+    }
+
+    public void getInOrder(TreeNode node){
+
+        if (node == null) {
+            return ;
+        }
+
+        getInOrder(node.left);
+
+        res.add(node.val);
+        int size = res.size();
+        if(size == 2){
+            min = res.get(1) - res.get(0);
+        }else if (size > 2){
+            min = Math.min(res.get(size-1) - res.get(size -2),min);
+        }
+
+        getInOrder(node.right);
+
+    }
+
+}
diff --git a/Week_03/id_97/LeetCode_104_097.java b/Week_03/id_97/LeetCode_104_097.java
@@ -0,0 +1,15 @@
+
+public class Solution{
+
+	public int maxDepth(TreeNode root) {
+        if (root == null){
+            return 0;
+        }
+
+        int leftMaxDepth = maxDepth(root.left); //求左子树的最大深度
+        int rightMaxDepth = maxDepth(root.right); //求当前节点的右子树最大深度
+
+        return Math.max(leftMaxDepth,rightMaxDepth) + 1;
+    }
+}
+
diff --git a/Week_03/id_97/LeetCode_997_097.java b/Week_03/id_97/LeetCode_997_097.java
@@ -0,0 +1,18 @@
+public class Solution{
+
+ public static int findJudge(int N, int[][] trust) {
+        int[][] people = new int[N][2];
+        for (int[] person : trust){
+            int out = person[0];
+            int in = person[1];
+            people[out - 1][0]++;
+            people[in - 1][1]++;
+        }
+        for(int i = 0; i < N; i ++){
+            if(people[i][0] == 0 && people[i][1] == N - 1)
+                return i + 1;
+        }
+        return -1;
+    }
+
+}
diff --git a/Week_04/id_97/LeetCode_169_097.java b/Week_04/id_97/LeetCode_169_097.java
@@ -0,0 +1,16 @@
+class Solution {
+    public int majorityElement(int[] nums) {
+          Map<Integer,Integer> map = new HashMap<>();
+            for(int num:nums){
+                map.put(num,map.getOrDefault(num,0)+1);
+            }
+            Integer numsD = nums.length/2;
+           // BigDecimal   nums2  = new BigDecimal(numsD);
+            for(Integer key:map.keySet()){
+                if(map.get(key) > numsD ){
+                        return  key;
+                }
+            }
+            return  0;
+    }
+}
diff --git a/Week_04/id_97/LeetCode_746_097.java b/Week_04/id_97/LeetCode_746_097.java
@@ -0,0 +1,12 @@
+class Solution {
+    public int minCostClimbingStairs(int[] cost) {
+         int len = cost.length;
+        int[] dp = new int[len];
+        dp[0] = cost[0];
+        dp[1] = cost[1];
+        for (int i = 2; i < len; i++) {
+          dp[i] = Math.min(dp[i-1],dp[i-2]) + cost[i];
+        }
+        return Math.min(dp[len-1],dp[len-2]); 
+    }
+}