HOT100-简单题

linwt · linwt · commit 3d7e20d19b52 · 2022-02-07T22:54:23.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -1,10 +1,20 @@
+1. 两数之和
+20. 有效的括号
+21. 合并两个有序链表
+53. 最大子数组和
+70. 爬楼梯
 94. 二叉树的中序遍历
 101. 对称二叉树
 102. 二叉树的层序遍历
 104. 二叉树的最大深度
 105. 从前序与中序遍历序列构造二叉树
 114. 二叉树展开为链表
+121. 买卖股票的最佳时机
+136. 只出现一次的数字
+141. 环形链表
 144. 二叉树的前序遍历
 145. 二叉树的后序遍历
+155. 最小栈
+160. 相交链表
 226. 翻转二叉树
 589. N叉树的前序遍历
diff --git a/leetcode_Java/Solution0001.java b/leetcode_Java/Solution0001.java
@@ -0,0 +1,24 @@
+// 两数之和
+
+
+/*
+思路：
+1、中间数据使用HashMap存放，记录值和索引。结果数据使用整型数组存放
+2、输入的数组使用for循环遍历，通过目标值相减的方式获取输入数组中和HashMap中满足条件的两个整数，获取其索引存入结果数组
+ */
+class Solution {
+    public int[] twoSum(int[] nums, int target) {
+        HashMap<Integer, Integer> map = new HashMap<>();
+        int[] res = new int[2];
+        for (int i = 0; i < nums.length; i++) {
+            if (map.containsKey(target - nums[i])) {
+                res[0] = i;
+                res[1] = map.get(target - nums[i]);
+                return res;
+            } else {
+                map.put(nums[i], i);
+            }
+        }
+        return res;
+    }
+}
diff --git a/leetcode_Java/Solution0020.java b/leetcode_Java/Solution0020.java
@@ -0,0 +1,52 @@
+// 有效的括号
+
+
+/*
+思路：
+1、括号有序，即使多层嵌套也必然至少有一对相邻有序出现，从内部逐层抵消
+2、使用while循环判断字符串的相邻有序对
+ */
+class Solution {
+    public boolean isValid(String s) {
+        while (s.contains("()") || s.contains("{}") || s.contains("[]")) {
+            if (s.contains("()")) {
+                s = s.replace("()", "");
+            }
+            if (s.contains("{}")) {
+                s = s.replace("{}", "");
+            }
+            if ( s.contains("[]")) {
+                s = s.replace("[]", "");
+            }
+        }
+        return s.isEmpty();
+    }
+}
+
+
+/*
+思路：
+1、使用HashMap存放括号对，方便映射获取
+2、由括号的顺序特点，使用栈存放左括号，以后进先出的方式与右括号抵消
+3、字符串使用for循环遍历处理每个字符，维护一个栈，碰到左括号就入栈，碰到右括号则取出栈顶元素，判断栈顶元素和右括号是否匹配
+4、栈为空或括号不匹配，则为false，否则true
+ */
+class Solution {
+    public boolean isValid(String s) {
+        HashMap<Character, Character> map = new HashMap<Character, Character>() {{
+            put('(', ')');
+            put('{', '}');
+            put('[', ']');
+        }};
+        Stack<Character> stack = new Stack<>();
+        for (int i = 0; i < s.length(); i++) {
+            char c = s.charAt(i);
+            if (map.containsKey(c)) {
+                stack.push(c);
+            } else if (stack.isEmpty() || map.get(stack.pop()) != c) {
+                return false;
+            }
+        }
+        return stack.isEmpty();
+    }
+}
diff --git a/leetcode_Java/Solution0021.java b/leetcode_Java/Solution0021.java
@@ -0,0 +1,63 @@
+// 合并两个有序链表
+
+
+/**
+ * Definition for singly-linked list.
+ * public class ListNode {
+ *     int val;
+ *     ListNode next;
+ *     ListNode() {}
+ *     ListNode(int val) { this.val = val; }
+ *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
+ * }
+ */
+
+
+/*
+递归思路：
+1、终止条件：其中一个节点为空
+2、方法功能：入参两个节点，比较值的大小，返回值较小的节点
+3、递归逻辑：下一个有序节点同样可以通过调用这个方法得到，一次递归获得值较小的节点，返回给上一层拼接成链表，最后得到有序的链表
+ */
+class Solution {
+    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
+        if (list1 == null) {
+            return list2;
+        } else if (list2 == null) {
+            return list1;
+        } else if (list1.val < list2.val) {
+            list1.next = mergeTwoLists(list1.next, list2);
+            return list1;
+        } else {
+            list2.next = mergeTwoLists(list1, list2.next);
+            return list2;
+        }
+    }
+}
+
+
+/*
+迭代思路：
+1、创建一个新结点，用于最后返回链表头
+2、使用pre指针，连接结点成链表
+3、使用while循环判断并连接两个链表值较小的节点，链表的节点被连接后，该链表指针指向下一个节点继续判断
+4、其中一个链表为空后循环结束，连接另一个不为空的链表的剩余部分
+ */
+class Solution {
+    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
+        ListNode head = new ListNode(-1);
+        ListNode pre = head;
+        while (list1 != null && list2 != null) {
+            if (list1.val < list2.val) {
+                pre.next = list1;
+                list1 = list1.next;
+            } else {
+                pre.next = list2;
+                list2 = list2.next;
+            }
+            pre = pre.next;
+        }
+        pre.next = list1 == null ? list2 : list1;
+        return head.next;
+    }
+}
diff --git a/leetcode_Java/Solution0053.java b/leetcode_Java/Solution0053.java
@@ -0,0 +1,71 @@
+// 最大子数组和
+
+
+/*
+贪心思路：
+1、遍历数组，当前元素的 之前和大于0 时，则加上当前值得到当前和，这样累加值才会更大，否则将当前值赋给当前和
+2、当前和只是一个中间变量，记录过程中每个局部最大和。比较历史最大值 和 当前和，得到较大值
+ */
+class Solution {
+    public int maxSubArray(int[] nums) {
+        int res = nums[0];
+        int sum = 0;
+        for (int num : nums) {
+            if (sum > 0) {
+                sum += num;
+            } else {
+                sum = num;
+            }
+            res = Math.max(res, sum);
+        }
+        return res;
+    }
+}
+
+
+/*
+贪心思路：
+1、核心思路都是判断以前一个元素结尾的子序列的最大值能不能给当前元素结尾的序列提供增益
+2、如果之前和为负数就不能提供增益，加上当前元素后会比当前元素小，因此通过比较大小就能获得当前和的最大值
+ */
+class Solution {
+    public int maxSubArray(int[] nums) {
+        int res = nums[0];
+        int sum = 0;
+        for (int num : nums) {
+            sum = Math.max(sum + num, num);
+            res = Math.max(res, sum);
+        }
+        return res;
+    }
+}
+
+
+/*
+动态规划思路：
+1、dp[i]表示以i结尾子串的最大值
+2、初始条件：dp[0] = nums[0]
+3、状态转移方程：
+    if (dp[i - 1] > 0) dp[i] = dp[i - 1] + nums[i];
+    else dp[i] = nums[i];
+4、从dp数组中每个局部最大值获取全局最大值
+ */
+class Solution {
+    public int maxSubArray(int[] nums) {
+        int n = nums.length;
+        int[] dp = new int[n];
+        dp[0] = nums[0];
+        for (int i = 1; i < n; i++) {
+            if (dp[i - 1] > 0) {
+                dp[i] = dp[i - 1] + nums[i];
+            } else {
+                dp[i] = nums[i];
+            }
+        }
+        int res = dp[0];
+        for (int i = 1; i < n; i++) {
+            res = Math.max(res, dp[i]);
+        }
+        return res;
+    }
+}
diff --git a/leetcode_Java/Solution0070.java b/leetcode_Java/Solution0070.java
@@ -0,0 +1,39 @@
+// 爬楼梯
+
+
+/*
+递推思路：
+1、规律：1,2,3,5,8  后一个数是前两个数的和
+2、初始化两个值，根据规律逐渐推算出第n个数的值
+ */
+class Solution {
+    public int climbStairs(int n) {
+        int a = 1, b = 1;
+        int temp;
+        while (n > 1) {
+            temp = b;
+            b += a;
+            a = temp;
+            n -= 1;
+        }
+        return b;
+    }
+}
+
+
+/*
+动态规划思路：
+1、dp[i]表示i阶楼梯的方法数量
+2、初始条件：dp[0] = dp[1] = 1
+3、状态转移方程：dp[i] = dp[i - 1] + dp[i - 2]
+ */
+class Solution {
+    public int climbStairs(int n) {
+        int[] dp = new int[n + 1];
+        dp[0] = dp[1] = 1;
+        for (int i = 2; i <= n; i++) {
+            dp[i] = dp[i - 1] + dp[i - 2];
+        }
+        return dp[n];
+    }
+}
diff --git a/leetcode_Java/Solution0121.java b/leetcode_Java/Solution0121.java
@@ -0,0 +1,39 @@
+// 买卖股票的最佳时机
+
+
+/*
+动态规划思路：
+1、dp[i]表示前i+1天可获得的最大利润
+2、初始条件：dp[0] = 0，第1天的最大利润为0
+3、状态转移方程：dp[i] = Math.max(dp[i - 1], prices[i] - minPrice)
+ */
+class Solution {
+    public int maxProfit(int[] prices) {
+        int n = prices.length;
+        int[] dp = new int[n];
+        dp[0] = 0;
+        int minPrice = prices[0];
+        for (int i = 1; i < n; i++) {
+            minPrice = Math.min(minPrice, prices[i]);
+            dp[i] = Math.max(dp[i - 1], prices[i] - minPrice);
+        }
+        return dp[n - 1];
+    }
+}
+
+
+/*
+思路：
+1、动态规划维护的dp数组，存放的每个元素只用一次就不需要了，因此可以直接用一个变量来表示利润最大值
+2、遍历列表，计算到当天为止的价格最小值、利润最大值
+ */
+class Solution {
+    public int maxProfit(int[] prices) {
+        int minPrice = 99999, maxProfit = 0;
+        for (int price : prices) {
+            minPrice = Math.min(minPrice, price);
+            maxProfit = Math.max(maxProfit, price - minPrice);
+        }
+        return maxProfit;
+    }
+}
diff --git a/leetcode_Java/Solution0136.java b/leetcode_Java/Solution0136.java
@@ -0,0 +1,59 @@
+// 只出现一次的数字
+
+
+/*
+思路：使用HashMap记录每个数出现的次数，遍历HashMap查找只出现一次的数字
+ */
+class Solution {
+    public int singleNumber(int[] nums) {
+        HashMap<Integer, Integer> map = new HashMap<>();
+        for (int num : nums) {
+            int count = map.getOrDefault(num, 0);
+            map.put(num, ++count);
+        }
+        for (int num : map.keySet()) {
+            if (map.get(num) == 1) {
+                return num;
+            }
+        }
+        return -1;
+    }
+}
+
+
+/*
+思路：使用列表存放数字。没有出现过则存入，出现过则移除，最后剩下一个只出现一次的数字
+ */
+class Solution {
+    public int singleNumber(int[] nums) {
+        List<Integer> list = new ArrayList<>();
+        for (int num : nums) {
+            Integer numObj = num;
+            if (list.contains(numObj)) {
+                list.remove(numObj);
+            } else {
+                list.add(numObj);
+            }
+        }
+        return list.get(0);
+    }
+}
+
+
+/*
+思路：
+既满足时间复杂度又满足空间复杂度，就要提到位运算中的异或运算 XOR，主要因为异或运算有以下几个特点：
+一个数和 0 做 XOR 运算等于本身：a⊕0 = a
+一个数和其本身做 XOR 运算等于 0：a⊕a = 0
+XOR 运算满足交换律和结合律：a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b
+故而在以上的基础条件上，将所有数字按照顺序做异或运算，最后剩下的结果即为唯一的数字
+ */
+class Solution {
+    public int singleNumber(int[] nums) {
+        int res = 0;
+        for (int num : nums) {
+            res ^= num;
+        }
+        return res;
+    }
+}
diff --git a/leetcode_Java/Solution0141.java b/leetcode_Java/Solution0141.java
diff --git a/leetcode_Java/Solution0155.java b/leetcode_Java/Solution0155.java
diff --git a/leetcode_Java/Solution0160.java b/leetcode_Java/Solution0160.java
