HOT100-中等题2道

linwt · linwt · commit 864e76af92ac · 2022-02-09T22:18:37.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -1,4 +1,6 @@
 1. 两数之和
+2. 两数相加
+3. 无重复字符的最长子串
 20. 有效的括号
 21. 合并两个有序链表
 53. 最大子数组和
diff --git a/leetcode_Java/Solution0002.java b/leetcode_Java/Solution0002.java
@@ -0,0 +1,38 @@
+// 两数相加
+
+
+/**
+ * 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、两个链表长度不同，则短链表后面默认为0
+3、链表遍历结束后，如果进位值为1，需要再加一个节点
+ */
+class Solution {
+    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
+        ListNode head = new ListNode(0);
+        ListNode cur = head;
+        int add = 0;
+        while (l1 != null || l2 != null || add != 0) {
+            int l1Val = l1 != null ? l1.val : 0;
+            int l2Val = l2 != null ? l2.val : 0;
+            int num = l1Val + l2Val + add;
+            add = num / 10;
+            cur.next = new ListNode(num % 10);
+            cur = cur.next;
+            l1 = l1 != null ? l1.next : null;
+            l2 = l2 != null ? l2.next : null;
+        }
+        return head.next;
+    }
+}
diff --git a/leetcode_Java/Solution0003.java b/leetcode_Java/Solution0003.java
@@ -0,0 +1,54 @@
+// 无重复字符的最长子串
+
+
+/*
+索引定位收缩左区间：
+1、HashMap保存滑动窗口中的字符的索引
+2、如果右指针移动过程新的字符 出现 在滑动窗口中，则更新左指针位置
+3、更新当前字符在HashMap中的索引
+4、右指针每移动一次后，计算新窗口的长度，比较并保存最大长度
+ */
+class Solution {
+    public int lengthOfLongestSubstring(String s) {
+        int maxLen = 0, start = 0;
+        Map<Character, Integer> map = new HashMap<>();
+        for (int i = 0; i < s.length(); i++) {
+            char c = s.charAt(i);
+            if (map.containsKey(c)) {
+                start = Math.max(map.get(c) + 1, start);
+            }
+            map.put(c, i);
+            maxLen = Math.max(maxLen, i - start + 1);
+        }
+        return maxLen;
+    }
+}
+
+
+/*
+左指针右移收缩左区间：
+1、HashMap保存滑动窗口中的字符的出现次数
+2、如果右指针移动过程新的字符 没有 在滑动窗口中，则将字符添加到HashMap中，次数记为1
+3、如果右指针移动过程新的字符 出现 在滑动窗口中，则移动左指针直到同样该字符的下一位，移动过程指向的字符在HashMap中出现次数减1
+4、右指针每移动一次后，计算新窗口的长度，比较并保存最大长度
+ */
+class Solution {
+    public int lengthOfLongestSubstring(String s) {
+        int maxLen = 0, start = 0;
+        Map<Character, Integer> map = new HashMap<>();
+        for (int i = 0; i < s.length(); i++) {
+            char c = s.charAt(i);
+            if (map.getOrDefault(c, 0) == 0) {
+                map.put(c, 1);
+            } else {
+                while (s.charAt(start) != c) {
+                    map.put(s.charAt(start), map.get(s.charAt(start)) -1);
+                    start++;
+                }
+                start++;
+            }
+            maxLen = Math.max(maxLen, i - start + 1);
+        }
+        return maxLen;
+    }
+}
diff --git a/leetcode_Java/Solution0234.java b/leetcode_Java/Solution0234.java
@@ -39,6 +39,7 @@ public boolean isPalindrome(ListNode head) {
 1、通过递归实现在链表上双指针判断首尾元素是否一样
 2、使用成员变量作为头部指针，该指针不受递归影响，每次判断完向后移动一步
 3、通过递归直接到达链表尾部指针，此时通过首尾指针判断元素是否一样，下一层递归结束后返回上一层，相当于尾部指针往前移动一步
+4、先判断上一层处理结果元素是否一样，是的话再判断当前层元素是否一样
  */
 class Solution {
     private ListNode left;
