力扣hot100-哈希

题目：两数之和

原题链接：两数之和

方法1-暴力

我最先想到的方法就是暴力，两层for循环，也能通过。（拿到算法题在没有思路的时候暴力就是思路，哈哈哈）

public class T1 {public static int[] twoSum(int[] nums, int target) {for (int i = 0; i < nums.length; i++) {for (int j = i+1; j < nums.length; j++) {if(nums[i]+nums[j]==target){return new int[]{i,j};}}}return null; //这行代码没用  不写不行 随便返回一个数组即可}public static void main(String[] args) {int[] nums = {2,7,11,15};int target = 9;int[] res = twoSum(nums, target);System.out.println(Arrays.toString(res));}
}

方法2-哈希

public class T1 {public static int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {if(map.containsKey(target-nums[i])){return new int[]{i, map.get(target-nums[i])};}map.put(nums[i],i);}return null;}public static void main(String[] args) {int[] nums = {2,7,11,15};int target = 9;int[] res = twoSum(nums, target);System.out.println(Arrays.toString(res));}
}

使用哈希表：

• 使用HashMap来存储数组中的每一个数和它的索引。
• 在遍历数组时，对于每个数，计算其补数（即target - nums[i]），并检查这个补数是否在哈希表中。
• 如果补数存在，直接返回它的索引和当前数的索引

可能刚开始接触有点疑惑。
用两个for，可能更容易看懂，时间复杂度不变O(n)

    public static int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {map.put(nums[i],i);}for (int i = 0; i < nums.length; i++) {if(map.containsKey(target-nums[i])){return new int[]{i, map.get(target-nums[i])};}}return null;}

---

题目：字母异位词分组

原题链接：字母异位词分组

题解

我的思路是通过排序后的字符串作为哈希表的键，将原字符串作为值添加到相应的键对应的列表中。每次遍历字符串数组strs，将排序后的字符串作为键查找或添加到哈希表中。

1. 遍历字符串数组strs。
2. 对每个字符串进行排序，将排序后的字符串作为哈希表的键。
3. 检查哈希表中是否存在该键：
   • 如果存在，将原字符串添加到该键对应的列表中。
   • 如果不存在，创建一个新的列表，并将该字符串添加到新列表中。
4. 最终返回哈希表中所有值。

public class Test {public static String sort(String s){char[] charArray = s.toCharArray();Arrays.sort(charArray);return new String(charArray);}public static List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMap<>();for (String str : strs) {String s = sort(str);List<String> list = map.getOrDefault(s, new ArrayList<>());list.add(str);map.put(s,list);}return new ArrayList<List<String>>(map.values());}public static void main(String[] args) {String[] strs={"eat", "tea", "tan", "ate", "nat", "bat"};System.out.println(groupAnagrams(strs));}
}

---

题目：最长连续序列

原题链接：最长连续序列

题解

思路：

• 先把 nums 数组中的元素放入 set 集合
• 对集合中的每个元素进行如下处理：
  • 检查该元素是否是某个连续序列的起点（即 num - 1 不在集合中）。
  • 如果是序列的起点，则开始计算这个序列的长度：
    • 初始化一个计数器 cnt 为 1。
    • 使用 while 循环检查 num + 1 是否在集合中。如果在，则将 cnt 加 1，并将 num 增加 1。
  • 更新 res，使其始终保持最大值。

public class Test {public static int longestConsecutive(int[] nums) {if (nums == null || nums.length == 0) {return 0;}HashSet<Integer> set = new HashSet<>();for (int num : nums) {set.add(num);}int res = 0;for (Integer num : set) {if (!set.contains(num - 1)) {int cnt = 1;while (set.contains(num + 1)) {cnt++;num++;}res = Math.max(res, cnt);}}return res;}public static void main(String[] args) {int[] nums = {100, 4, 200, 1, 3, 2};System.out.println(longestConsecutive(nums));}
}

解释代码

内部条件检查
if (!numSet.contains(num - 1))

• 对于每个元素，我们检查它是否是一个序列的起点。
• 如果 num - 1 不在集合中，这意味着 num 是序列的起点。
• 每个元素最多被检查一次。

序列扩展（while循环）

while (set.contains(num + 1)) {cnt++;num++;}

• 只有当一个元素是序列的起点时，才会进入这个 while 循环。
• 从序列的起点开始，扩展这个序列，直到不能再扩展为止。

这个算法的时间复杂度是 O(n)，因为：

1. 哈希集合的构建是 O(n)。
2. 外层 for 循环遍历每个元素是 O(n)。
3. while 循环在整个算法过程中，每个元素最多被访问一次，总共也是 O(n)。（while里面最多会把每个元素遍历一次 eg：nums=[1,3,6,9,11] 所以O(n)）

时间复杂度别理解成了O(n²)

---

下面这个才是O(n²)，外层i加1，内层n次打印。(n*n)

  for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {System.out.println("hello");}}

力扣hot100-双指针

题目：移动零

原题链接：移动零

题解

思路：快慢指针（双指针）法

public class Test {public static void moveZeroes(int[] nums) {int l = 0; // 非零元素应该存放的位置 下标[0,l)都是非零元素int h = 0; // 遍历数组for (; h < nums.length; h++) {if (nums[h] != 0) {nums[l++] = nums[h];}}for (; l < nums.length; l++) {nums[l] = 0;}}public static void main(String[] args) {int[] nums = {0, 1, 0, 3, 12};moveZeroes(nums);System.out.println(Arrays.toString(nums));}
}

---

题目：盛最多水的容器

原题链接：盛最多水的容器

题解

思路：双指针

public class Test {public static int maxArea(int[] height) {int l = 0;int h = height.length - 1;int area = 0;while (l < h) {area = Math.max(Math.min(height[l], height[h]) * (h - l), area);//(h - l)矩形宽度if (height[l] < height[h]) {l++;} else {h--;}}return area;}public static void main(String[] args) {int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};System.out.println(maxArea(height));}
}

• 如果移动较小高度的指针，有可能找到一个更高的柱子，从而增加可能的最大面积。
• 反之，如果移动较高高度的指针，由于高度已经固定为较小值，移动较高指针只会减小宽度，不会增加高度，因此可能会导致面积减小或保持不变。

---

题目：三数之和

原题链接：三数之和

题解

思路：一层枚举+双指针

public class Test {public static List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();if (nums.length < 3) return res;Arrays.sort(nums);int target = 0;for (int i = 0; i < nums.length; i++) {if (i > 0 && nums[i] == nums[i - 1]) continue;//因为数组排序了 如果num[i]大于0  则后面不可能选出三个数和为0if (nums[i] > 0) break;target = 0 - nums[i];int l = i + 1, h = nums.length - 1;while (l < h) {if (nums[l] + nums[h] > target) {h--;} else if (nums[l] + nums[h] < target) {l++;} else if (nums[l] + nums[h] == target) {// 跳过重复元素while (l < h && nums[l] == nums[l + 1]) l++;while (l < h && nums[h] == nums[h - 1]) h--;res.add(new ArrayList<>(Arrays.asList(nums[i], nums[l], nums[h])));h--;l++;}}}return res;}public static void main(String[] args) {int[] nums = {-1, 0, 1, 2, -1, -4};System.out.println(threeSum(nums));}
}

while里面的去重， 可以用下面两种方法。（为什么去重？看一个数组[-2, 0, 0, 2, 2]）

 // 跳过重复元素while (l < h && nums[l] == nums[l + 1]) l++;while (l < h && nums[h] == nums[h - 1]) h--;if (nums[l] == nums[l - 1] && ((h + 1) < nums.length && nums[h] == nums[h + 1])) {l++;h--;continue;
}

---

题目：接雨水

原题链接：接雨水

题解

思路：双指针
核心思想：对于任意位置 i，能够存储的雨水量取决于位置 i 左侧和右侧的最大高度中的较小值减去 height[i]。即 min(leftMax, rightMax) - height[i]。我感觉这个很好理解，理解了这个，这道题就简单了

public class T42 {public static int trap(int[] height) {if (height == null || height.length <= 2) {return 0;}int left = 0, right = height.length - 1;int leftMax = 0, rightMax = 0;int res = 0;while (left < right) {if (height[left] < height[right]) {if (height[left] >= leftMax) {leftMax = height[left];} else {res += leftMax - height[left];}left++;} else {if (height[right] >= rightMax) {rightMax = height[right];} else {res += rightMax - height[right];}right--;}}return res;}public static void main(String[] args) {int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};System.out.println(trap(height)); }
}

解释代码

• left 和 right 指针分别初始化为数组的最左和最右端。
• leftMax 和 rightMax 分别记录遍历过程中左侧和右侧的最大高度。
• res 用于累计存储的雨水量。

比较左右高度

if (height[left] < height[right]) {

• 如果左侧高度小于右侧高度，则处理左侧：
  • 更新左侧最大高度：

    if (height[left] >= leftMax) {leftMax = height[left];
    }
    

    • 如果当前左侧高度大于等于 leftMax，更新 leftMax。
  • 计算左侧可以存储的雨水：

    else {res += leftMax - height[left];
    }
    

    • 否则，当前柱子可以存储的雨水量为 leftMax - height[left]。将其累加到 res。
  • 移动左指针：

    left++;
    

处理右侧

else {

• 如果右侧高度小于等于左侧高度，则处理右侧：
  • 更新右侧最大高度：

    if (height[right] >= rightMax) {rightMax = height[right];
    }
    

    • 如果当前右侧高度大于等于 rightMax，更新 rightMax。
  • 计算右侧可以存储的雨水：

    else {res += rightMax - height[right];
    }
    

    • 否则，当前柱子可以存储的雨水量为 rightMax - height[right]。将其累加到 res。
  • 移动右指针：

    right--;
    

为什么双指针法有效

• 关键思想：
  • 对于任意位置 i，能够存储的雨水量取决于位置 i 左侧和右侧的最大高度中的较小值减去 height[i]。即 min(leftMax, rightMax) - height[i]。
• 左右指针：
  • 当 height[left] < height[right] 时，右侧的高度至少是 height[right]，这意味着左侧的最大高度决定了当前柱子 left 的存储量。
  • 同理，当 height[left] >= height[right] 时，左侧的高度至少是 height[left]，这意味着右侧的最大高度决定了当前柱子 right 的存储量。

---

力扣有一位大佬给出5种方法，确实让人佩服。5种解答

力扣hot100-滑动窗口

滑动窗口

滑动窗口是一种常用的算法技巧，适用于需要在一个数组或字符串中找出满足特定条件的连续子数组或子字符串的问题。它通过维护一个窗口范围来减少重复计算，从而优化算法的时间复杂度

滑动窗口算法通常涉及两个指针，分别表示窗口的左边界和右边界。窗口在数组或字符串上滑动，并在滑动过程中动态调整窗口的大小和位置，以满足特定条件。主要步骤如下：

1. 初始化窗口边界：设置窗口的初始左边界和右边界。
2. 移动右边界：扩大窗口的右边界，直到窗口内的元素满足特定条件。
3. 调整左边界：当窗口内的元素满足特定条件时，尝试移动左边界以缩小窗口，同时保持窗口内的元素仍然满足条件。
4. 记录结果：在每次窗口满足条件时，记录当前窗口的大小或内容。
5. 重复步骤 2 和 3：直到右边界到达数组或字符串的末尾。

题目1-无重复字符的最长子串

方法一

第一种：【第一次接触可能第一种方法容易理解】

public class Test {public static int lengthOfLongestSubstring(String s) {Map<Character, Integer> map = new HashMap<>();char[] charArray = s.toCharArray();int left = 0, right = 0;int res = 0;while (right < charArray.length) {if (map.containsKey(charArray[right])) {map.remove(charArray[left]);left++;} else {map.put(charArray[right], 1);res = Math.max(res, right - left + 1);right++;}}return res;}public static void main(String[] args) {String s = "abcabcbb";System.out.println(lengthOfLongestSubstring(s));}
}

方法二

第二种：可以跳跃式地移动 left 指针

public class Test {public static int lengthOfLongestSubstring(String s) {Map<Character, Integer> map = new HashMap<>();char[] charArray = s.toCharArray();int left = 0, right = 0;int res = 0;for (; right < s.length(); right++) {if (map.containsKey(charArray[right])) {left = Math.max(left, map.get(charArray[right]) + 1);}map.put(charArray[right], right);res = Math.max(res, right - left + 1);}return res;}public static void main(String[] args) {String s = "abcabcbb";System.out.println(lengthOfLongestSubstring(s));}
}

题目2-找到字符串中所有字母异位词

方法一

第一种方法：（不建议，容易超时）
这是我第一想到的方法

public class Test {public static String stringSort(String s) {char[] charArray = s.toCharArray();Arrays.sort(charArray);return new String(charArray);}public static List<Integer> findAnagrams(String s, String p) {List<Integer> res = new ArrayList<>();if (s.length() < p.length()) return res;String sortedP = stringSort(p);int s_len = s.toCharArray().length;int p_len = p.toCharArray().length;int left = 0, right = 0;while (right < s_len) {if (right - left + 1 == p_len) {if (stringSort(s.substring(left, right + 1)).equals(sortedP)) {res.add(left);}left++;right++;} else {right++;}}return res;}public static void main(String[] args) {String s = "cbaebabacd", p = "abc";System.out.println(findAnagrams(s, p));}
}

方法二

第二种方法：

public class Test {public static List<Integer> findAnagrams(String s, String p) {List<Integer> res = new ArrayList<>();if (s.length() < p.length()) return res;int p_len = p.length();int s_len = s.length();int[] pCount = new int[26];for (char c : p.toCharArray()) {pCount[c - 'a']++;}int[] sCount = new int[26];for (int i = 0; i < s_len; i++) {sCount[s.charAt(i) - 'a']++;if (i >= p_len) {sCount[s.charAt(i - p_len) - 'a']--;}if (check(pCount, sCount)) {res.add(i - p_len + 1);}}return res;}private static boolean check(int[] pCount, int[] sCount) {for (int i = 0; i < 26; i++) {if (pCount[i] != sCount[i]) {return false;}}return true;}public static void main(String[] args) {String s = "cbaebabacd";String p = "abc";System.out.println(findAnagrams(s, p));}
}

力扣hot100-普通数组

题目：最大子数组和

原题链接：最大子数组和

方法1 动态规划

public class T53 {//动态规划public static int maxSubArray(int[] nums) {if (nums.length == 0) return 0;int[] dp = new int[nums.length]; // dp[i] 表示以 nums[i] 结尾的最大子数组和dp[0] = nums[0]; // 初始化状态int res = dp[0]; // 初始化最大子数组和// 动态规划状态转移for (int i = 1; i < nums.length; i++) {dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);  //状态转移方程res = Math.max(res, dp[i]);}return res;}public static void main(String[] args) {int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};System.out.println(maxSubArray(nums)); // 输出: 6}
}

方法2

方法二可能不容易想到

public class T53 {public int maxSubArray(int[] nums) {// 初始化为int类型最小值int res = nums[0];int tempTotal = 0;for (int i = 0; i < nums.length; i++) {tempTotal += nums[i];// 记录最大数值res = Math.max(tempTotal, res);if (tempTotal < 0) {// 如果和小于0,就重置为0，因为任何数加上一个负数一定小于当前数值tempTotal = 0;  //0加任何数都等于任何数}}return res;}public static void main(String[] args) {int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};System.out.println(maxSubArray(nums)); // 输出: 6}
}

---

题目：合并区间

原题链接：合并区间

题解

    public static int[][] merge(int[][] intervals) {if (intervals.length == 0) {return new int[0][2];}// 可使用Lambda表达式Arrays.sort(intervals, new Comparator<int[]>() {@Overridepublic int compare(int[] interval1, int[] interval2) {return interval1[0]-interval2[0];}});List<int[]> merged = new ArrayList<>();for (int[] interval : intervals) {int L = interval[0], R = interval[1];// 如果merged列表为空，或者当前区间与上一个区间不重叠，直接添加当前区间if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < L) {merged.add(new int[]{L, R});} else {// 否则更新上一个区间的右边界merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);}}//List.toArray(T[] a) 方法将列表中的所有元素存储到指定类型的数组中return merged.toArray(new int[merged.size()][]);}

核心:
如果新区间的起始值大于 merged 列表中最后一个区间的结束值，则直接将新的区间添加到 merged 列表中；否则，更新 merged 列表中最后一个区间的结束值。

• 排序区间: 确保区间按照起始值从小到大排列，方便后续合并操作。
• 遍历和合并: 遍历排序后的区间数组，使用一个 merged 列表来存储合并后的区间。如果当前区间与前一个区间不重叠，直接添加到 merged 列表；如果重叠，更新 merged 列表中最后一个区间的结束值。

---

题目：轮转数组

原题链接：轮转数组

方法1-使用额外的数组

方法1是自己写出来的。方法2参考的别人的，方法2太👍了，不易发现这个规律

    public static void rotate(int[] nums, int k) {int[] temp = new int[nums.length];int j = 0;k = k % nums.length; // 数组长度大于k时，旋转次数取余---关键for (int i = nums.length - k; i < nums.length; i++) {temp[j++] = nums[i];}for (int i = 0; i < nums.length - k; i++) {temp[j++] = nums[i];}System.arraycopy(temp, 0, nums, 0, nums.length);}

方法2-三次反转数组

    private static void reverse(int[] nums, int start, int end) {while (start < end) {int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start++;end--;}}public static void rotate1(int[] nums, int k) {k = k % nums.length;  reverse(nums, 0, nums.length - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.length - 1);}

题目：除自身以外数组的乘积

原题链接：除自身以外数组的乘积

方法1-用到了除法

当时没看题目中不让用除法，当时一下就想到这个思路了，哈哈哈

    public static int[] productExceptSelf(int[] nums) {int temp = 1;int zero = 0;// 先看数组中0的个数  大于1则结果数组全为0  等于1则结果数组中0的位置为其他元素乘积for (int num : nums) {if (num != 0) {temp *= num;} else {zero++;if (zero > 1) return new int[nums.length];}}List<Integer> res = new ArrayList<>();for (int num : nums) {if (zero == 1) {//num==0 则当前结果数组该位置的结果为其他元素乘积res.add(num == 0 ? temp : 0);} else {res.add(temp / num);}}return res.stream().mapToInt(Integer::intValue).toArray();}

方法2-前后缀乘积法

方法2使用两次遍历分别计算数组元素左边和右边的乘积，从而构建出结果数组

    public static int[] productExceptSelf1(int[] nums) {int n = nums.length;int[] res = new int[n];// 第一次遍历，计算左边所有元素的乘积res[0] = 1;for (int i = 1; i < n; i++) {res[i] = res[i - 1] * nums[i - 1];}// 第二次遍历，计算右边所有元素的乘积，并更新结果数组int right = 1;for (int i = n - 1; i >= 0; i--) {res[i] *= right; //res[i]是当前i左边元素全部乘积right *= nums[i]; //用一个变量记录当前元素右边的所有元素乘积}return res;}

力扣hot100-链表

概要

链表（Linked List）是数据结构中的一种，用于存储具有线性关系的数据。在链表中，每个元素称为一个节点（Node），每个节点包含两个部分：一个是数据域（存储数据），另一个是指针域（指向下一个节点）。链表的结构使得它在某些情况下比数组更加高效，特别是在插入和删除操作上。

链表的类型

1. 单向链表（Singly Linked List）：

   • 每个节点只有一个指向下一个节点的指针。
   • 头节点（Head）是链表的起点，尾节点（Tail）指向 null。

2. 双向链表（Doubly Linked List）：

   • 每个节点有两个指针，分别指向前一个节点和下一个节点。
   • 头节点的前指针和尾节点的后指针都指向 null。

3. 循环链表（Circular Linked List）：

   • 单向链表或双向链表的变种。
   • 尾节点的下一个指针指向头节点，形成一个循环。

题目：相交链表

原题链接：相交链表

题解

核心：其实就是让2个指针走一样的距离，消除步行差，那就一定可以一起走到相交点

因为两个链表如果相交，则它们从相交点到结尾的所有节点都是相同的。因此，我们让指针 p1 和 p2 分别遍历两个链表。如果 p1 到达链表 A 的末尾，则将其重定位到链表 B 的头部；同样地，如果 p2 到达链表 B 的末尾，则将其重定位到链表 A 的头部。这样，两指针最终会在相交点处相遇，即第一个共同节点，即为相交点。

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode p1 = headA;ListNode p2 = headB;while (p1 != p2) {p1 = p1 == null ? headB : p1.next;p2 = p2 == null ? headA : p2.next;}return p1;}

评论区看到一个【还有句话：走到尽头见不到你，于是走过你来时的路，等到相遇时才发现，你也走过我来时的路。】

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode she = headA;ListNode he = headB;// 直到两人相遇while (she != he) {if (she != null) {she = she.next;// 如果她没走到尽头就一直走下去} else {she = headB;// 直到尽头也没遇见他，所以她去往他走过的路}if (he != null) {he = he.next;} else {he = headA;}}return he;// 返回两人第一次相遇的地方}

---

题目：反转链表

原题链接：反转链表

题解

方法1：创建新节点并插入新链表头部，更新新链表头指针

public static ListNode reverseList(ListNode head) {// 如果链表为空，直接返回nullif (head == null) {return null;}// 初始化新链表的头节点ListNode root = null;// 遍历原链表，将节点逐个插入到新链表的头部while (head != null) {// 保存当前节点的值ListNode temp = new ListNode(head.val);// 将新节点插入到新链表的头部temp.next = root;// 更新新链表的头节点root = temp;// 移动到下一个节点head = head.next;}// 返回新链表的头节点return root;
}

---

下面这个是用next记录了下一节点

public static ListNode reverseList(ListNode head) {ListNode prev = null; // 用于指向当前节点的前一个节点while (head != null) {ListNode next = head.next; // 保存当前节点的下一个节点head.next = prev; // 反转当前节点的指针prev = head; // 将 prev 移动到当前节点head = next; // 将 head 移动到下一个节点}return prev; // prev 最后指向的新头节点
}

注意：root = temp; 表示 root 指向 temp 所指向的节点

• head 的定义：

  head 是一个指向链表头节点的指针。它用于表示整个链表的起点。
  例如，在一个链表 1 -> 2 -> 3 -> null 中，head 指向节点 1。

• ListNode p = head; 的作用：
  这行代码创建了一个新的指针p，并使它指向与 head 相同的节点（即链表的头节点）。

---

题目：回文链表

原题链接：回文链表

方法1

方法1：把链表的值用数组记录下来

    public static boolean isPalindrome(ListNode head) {ArrayList<Integer> list = new ArrayList<>();while (head != null) {list.add(head.val);head = head.next;}for (int i = 0; i < list.size() / 2; i++) {if (list.get(i) != list.get(list.size() - i - 1)) {return false;}}return true;}

方法2

方法2：快慢指针找链表中点+翻转

public boolean isPalindrome(ListNode head) {if (head == null || head.next == null) {return true;}// 使用快慢指针找到链表的中间节点ListNode fast = head, slow = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}// 反转后半部分链表ListNode secondHalfStart = reverseList(slow);ListNode firstHalfStart = head;// 比较前半部分和反转后的后半部分while (secondHalfStart != null) {if (firstHalfStart.val != secondHalfStart.val) {return false;}firstHalfStart = firstHalfStart.next;secondHalfStart = secondHalfStart.next;}return true;
}private ListNode reverseList(ListNode head) {ListNode prev = null;while (head != null) {ListNode next = head.next;head.next = prev;prev = head;head = next;}return prev;
}

---

题目：环形链表

原题链接：环形链表

题解

    public static boolean hasCycle(ListNode head) {HashSet<ListNode> set = new HashSet<>();while (head != null) {if (!set.add(head)) {return true;}head = head.next;}return false;}

因为 set 中存储的是链表节点的引用（即 ListNode 对象的引用）。因为 HashSet 使用的是对象的引用进行比较，所以如果两个节点是同一个节点（即内存地址相同）,HashSet 会检测到这个重复的引用，从而判断链表中存在环。

---

题目：环形链表Ⅱ

原题链接：环形链表Ⅱ

题解

    public ListNode detectCycle(ListNode head) {ListNode res = new ListNode();HashSet<ListNode> set = new HashSet<>();while (head != null) {if (!set.add(head)) {return head; //返回节点即可}head = head.next;}return null;}

其实理解了环形链表这个题就很简单。在环形链表中，只需改动：返回true的时候返回节点即可，返回false的时候返回null

---

题目：合并两个有序链表

原题链接：合并两个有序链表

题解

1. 初始化：创建一个哑节点 res 作为合并后链表的头节点，temp 用于构建新链表。【哑节点简化了边缘情况处理，不需要特别处理头节点】
2. 遍历和比较：同时遍历 list1 和 list2，将较小节点链接到 temp 后，并移动 list1 或 list2 的指针。
3. 处理剩余节点：在遍历结束后，将剩余的非空链表直接链接到 temp 后。
4. 返回结果：返回 res.next，跳过哑节点，得到合并后的链表。

    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode res = new ListNode(0);ListNode temp = res;while (list1 != null && list2 != null) {if (list1.val < list2.val) {temp.next = list1;list1 = list1.next;} else {temp.next = list2;list2 = list2.next;}//temp节点始终指向末尾节点 每次将一个节点添加到合并链表后，temp会移动到新的末尾节点temp = temp.next;}temp.next = list1 == null ? list2 : list1;return res.next;}

---

题目：两数相加

原题链接：两数相加

题解

思路是通过遍历两个链表，计算对应节点值与进位的和，处理进位并构建新链表，最后返回不含虚拟头节点的结果链表。

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {int carry = 0;ListNode dummy = new ListNode(0);ListNode temp = dummy;while (l1 != null || l2 != null) {// 简化写法int val1 = (l1 != null) ? l1.val : 0;int val2 = (l2 != null) ? l2.val : 0;int sum = val1 + val2 + carry;carry = sum / 10;temp.next = new ListNode(sum % 10);temp = temp.next;if (l1 != null) l1 = l1.next;if (l2 != null) l2 = l2.next;}if (carry > 0) {temp.next = new ListNode(carry);}return dummy.next;}

力扣hot100-二叉树

概要

二叉树（Binary Tree）是一种树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树在算法和计算机科学中具有广泛的应用，特别是在表达式解析、搜索算法、排序算法、优先级队列、堆和其他数据结构中。

二叉树的基本概念

1. 节点 (Node)：二叉树中的每个元素。
2. 根节点 (Root Node)：二叉树的顶端节点。
3. 叶节点 (Leaf Node)：没有子节点的节点。
4. 子节点 (Child Node)：某节点的直接后继。
5. 父节点 (Parent Node)：某节点的直接前驱。
6. 高度 (Height)：从根节点到叶节点的最长路径上的节点数。
7. 深度 (Depth)：从根节点到某节点的路径上的节点数。
8. 层次 (Level)：从根节点开始，第 1 层为根节点，其子节点为第 2 层，以此类推。

常见的二叉树类型

1. 完全二叉树 (Complete Binary Tree)：除了最后一层，其他每一层的节点都达到最大数，最后一层的节点全部集中在最左边。
2. 满二叉树 (Full Binary Tree)：每个节点要么是叶子节点，要么有两个子节点。
3. 二叉搜索树 (Binary Search Tree, BST)：对于树中的每个节点，其左子树的所有节点值小于该节点值，右子树的所有节点值大于该节点值。
4. 平衡二叉树 (Balanced Binary Tree)：左右子树的高度差不超过 1。

常用的二叉树遍历

1. 前序遍历 (Pre-order Traversal)：根节点 -> 左子树 -> 右子树。
2. 中序遍历 (In-order Traversal)：左子树 -> 根节点 -> 右子树。
3. 后序遍历 (Post-order Traversal)：左子树 -> 右子树 -> 根节点。
4. 层次遍历 (Level-order Traversal)：按层次从上到下、从左到右遍历。

二叉树的常用技巧

1. 递归：

   • 许多二叉树问题可以通过递归来解决，因为二叉树的结构天然适合递归思想。
   • 例如，求二叉树的高度可以通过递归求左右子树的高度，然后取最大值加一。

2. 迭代：

   • 使用栈或队列来模拟递归过程，实现非递归的遍历方法。
   • 例如，中序遍历可以通过显式栈来实现。

3. 回溯：

   • 回溯法常用于在树中寻找路径或解决路径问题。
   • 例如，在路径和为某一值的情况下，回溯法可以在遍历的过程中动态构建路径并回退。

4. 动态规划：

   • 在处理一些优化问题时，可以在二叉树上应用动态规划，通过存储子问题的结果来减少重复计算。
   • 例如，在二叉树上查找最长路径等问题中。

5. 分治法：

   • 将问题分解为若干子问题分别解决，然后合并子问题的结果。
   • 例如，合并两棵二叉树、构造平衡二叉树等。

题目：二叉树的中序遍历

原题链接：二叉树的中序遍历

方法1–递归遍历

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();inorder(root, list);return list;}public void inorder(TreeNode root, List<Integer> list) {if (root == null) return;inorder(root.left, list);list.add(root.val);inorder(root.right, list);}
}

方法2–使用栈

栈（Stack）：利用栈来模拟递归的行为。栈在遍历左子树时保存节点，确保能够回到父节点，并遍历右子树。

对于二叉树的中序遍历，访问节点的顺序是：左子树 -> 根节点 -> 右子树。代码的关键在于使用了一个栈来模拟递归调用的过程。

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();LinkedList<TreeNode> stack = new LinkedList<>();while (root != null || !stack.isEmpty()) {while (root != null) {stack.push(root);root = root.left;}root = stack.pop();list.add(root.val);root = root.right;}return list;}
}

题目 二叉树的最大深度

原题链接: 二叉树的最大深度

题解

用递归！

 public int maxDepth(TreeNode root) {if (root == null) return 0;return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));}

题目：翻转二叉树

原题链接：翻转二叉树

方法1–递归

从下到上

 public TreeNode invertTree(TreeNode root) {// 如果当前节点为空，直接返回空if (root == null) {return null;}// 递归翻转左右子树TreeNode left = invertTree(root.left);TreeNode right = invertTree(root.right);// 交换左右子树root.left = right;root.right = left;// 返回当前节点return root;}

从上到下

    public TreeNode invertTree(TreeNode root) {if (root == null) return null;TreeNode temp = root.left;root.left = root.right;root.right = temp;invertTree(root.left);invertTree(root.right);return root;}

方法2–非递归

不用递归，用迭代的方法，通常使用栈或队列来模拟递归的调用栈

public TreeNode invertTree(TreeNode root) {if (root == null) return null;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode current = queue.poll();// 交换左右子节点TreeNode temp = current.left;current.left = current.right;current.right = temp;// 将子节点加入队列以处理它们的子节点if (current.left != null) queue.offer(current.left);if (current.right != null) queue.offer(current.right);}return root;
}

题目

原题链接: 对称二叉树

题解

   public boolean isSymmetric(TreeNode root) {if (root == null) {return true;}return isMirror(root.left, root.right);}private boolean isMirror(TreeNode left, TreeNode right) {if (left == null && right == null) {return true;}if (left == null || right == null) {return false;//不对称}return (left.val == right.val)&& isMirror(left.left, right.right)&& isMirror(left.right, right.left);}

• 左子树的左子节点 left.left 与右子树的右子节点 right.right 要镜像对称。
• 左子树的右子节点 left.right 与右子树的左子节点 right.left 要镜像对称。

left.val == right.val：2 == 2，满足。
isMirror(left.left, right.right)：即 3 与 3，满足。
isMirror(left.right, right.left)：即 4 与 4，满足。

    1/ \2   2/ \ / \
3  4 4  3

题目：二叉树的直径

原题链接：二叉树的直径

题解

方法：分解问题

最大深度的计算：

• 二叉树的直径可以通过计算每个节点的左右子树的最大深度来获得。
• 对于每个节点，计算其左子树和右子树的深度。
• 节点的直径等于左子树深度加右子树深度。

public class T543 {private int res = 0;public int diameterOfBinaryTree(TreeNode root) {depth(root);return res;}private int depth(TreeNode node) {if (node == null) {return 0;}int left = depth(node.left);int right = depth(node.right);// 计算经过当前节点的直径res = Math.max(res, left + right);// 返回当前节点的深度return Math.max(left, right) + 1;}
}···其实这道题和`二叉树的最大深度`有很大关系的，我们看看`二叉树的最大深度`代码
```javapublic int maxDepth(TreeNode root) {if (root == null) return 0;int left = maxDepth(root.left);int right = maxDepth(root.right);// return Math.max(left, right) + 1;}

在上面源码中的//那里添加动态更新最大路径就是本道题的答案。

二叉树的直径这个题，针对一个节点，我需要把左子树，右子树深度都计算出来，然后动态更新直径，所以在后序位置更新直径。

题目：二叉树的层序遍历

原题链接：二叉树的层序遍历

题解

方法：借助队列这个数据结构

    public static List<List<Integer>> levelOrder(TreeNode root) {ArrayList<List<Integer>> res = new ArrayList<>();if (root == null) return res;Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {int size = queue.size();ArrayList<Integer> temp = new ArrayList<>();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}temp.add(node.val);}res.add(temp);}return res;}

在while循环的每次迭代开始时，queue存储的是当前层的所有节点。

题目：将有序数组转换为二又搜索树

原题链接：将有序数组转换为二又搜索树

题解

将有序数组转换为二叉搜索树的关键在于利用数组的中间元素作为树的根节点，然后递归地对左右子数组执行相同的操作，构建左右子树

 public static TreeNode sortedArrayToBST(int[] nums) {return convertToBST(nums, 0, nums.length - 1);}private static TreeNode convertToBST(int[] nums, int left, int right) {if (left > right) return null;int mid = (left + right) / 2;TreeNode node = new TreeNode(nums[mid]);node.left = convertToBST(nums, left, mid - 1);node.right = convertToBST(nums, mid + 1, right);return node;}

删除链表的倒数第 N 个结点

原题链接：删除链表的倒数第 N 个结点

方法1

先将链表节点值存入列表，移除列表中倒数第 n 个值，再重新构建链表返回。

    public static ListNode removeNthFromEnd(ListNode head, int n) {ArrayList<Integer> list = new ArrayList<>();while (head != null) {list.add(head.val);head = head.next;}list.remove(list.size() - n);ListNode res = new ListNode();ListNode temp = res;for (Integer i : list) {ListNode node = new ListNode();node.val = i;temp.next = node;temp = temp.next;}return res.next;}

方法2

创建一个虚拟头节点，通过计算链表长度找到要删除节点的前一个节点，然后将其指向删除节点的下一个节点，从而实现删除倒数第 n 个节点，其中链表长度通过单独的方法计算得出。

    public static ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode cur = dummy;for (int i = 0; i < getLength(head) - n; i++) {cur = cur.next;}cur.next = cur.next.next;return dummy.next;}public static int getLength(ListNode head) {int len = 0;while (head != null) {len++;head = head.next;}return len;}

题目：两两交换链表中的节点

原题链接：两两交换链表中的节点

题解

该方法创建虚拟头节点，遍历链表，对于每对相邻节点进行交换，交换后移动指针准备处理下一对节点，最终返回处理后的链表，其中虚拟头节点用于统一处理可能的边界情况。

public static ListNode swapPairs(ListNode head) {if (head == null || head.next == null) return head;ListNode dummy = new ListNode(0);dummy.next = head;ListNode cur = dummy;// 遍历链表，并交换每对相邻的节点while (cur.next != null && cur.next.next != null) {ListNode first = cur.next;  // 第一个节点ListNode second = cur.next.next;  // 第二个节点// 交换这两个节点first.next = second.next;second.next = first;cur.next = second;// 移动指针，准备交换下一对节点cur = first;}return dummy.next;}

力扣hot100-栈

题目：有效的括号

原题链接：有效的括号

题解

遇到左括号就入栈，遇到右括号就出栈，然后比较是否配对？（map存配对的括号，key是反括号，value是正括号。假设遇到了右括号，然后从map中取出配对的括号和栈顶括号比较，相同则是配对的，不同直接返回false）

    public boolean isValid(String s) {// 长度为奇数直接返回falseif (s.length() % 2 == 1) return false;HashMap<Character, Character> map = new HashMap<>();map.put(')', '(');map.put('}', '{');map.put(']', '[');LinkedList<Character> stack = new LinkedList<>();for (char c : s.toCharArray()) {if (c == '(' || c == '{' || c == '[') {stack.push(c);} else if (stack.isEmpty() || map.get(c) != stack.pop()) {return false;}}return stack.isEmpty();}

题目：字符串解码

原题链接：字符串解码

题解

利用两个栈：

• counts 栈：用于存储当前的重复次数 k，即数字 k 是指 k 次重复括号中的内容。
• result 栈：用于存储之前的解码字符串，帮助拼接。

eg：3[a2[c]]

遍历字符串：

• 数字：字符如果是数字 ，则通过 currentNumber = currentNumber * 10 + (c - '0') 更新当前的 k，这个操作考虑了多位数字（例如：10[string]）。
• 左括号 [：遇到左括号时，说明即将进入一个新的一段重复模式。此时将 currentNumber（即重复次数）压入 counts 栈，将 currentString（当前字符串内容）压入 result 栈。然后，重置 currentString，开始新的字符串的构建。
• 右括号 ]：遇到右括号时，说明这一段的字符串已经结束。此时需要：
  • 从栈中弹出一个 k（重复次数）和之前的字符串。
  • 将当前的 currentString（即解码出来的字符串）重复 k 次，并拼接到从 result 栈中弹出的字符串上。
• 普通字符：如果是普通字符，直接将其加到 currentString 上。

    public String decodeString(String s) {Stack<Integer> counts = new Stack<>();  // 用于存储数字kStack<StringBuilder> result = new Stack<>();  // 用于存储解码的结果StringBuilder currentString = new StringBuilder();  // 当前正在解码的字符串int currentNumber = 0;for (char c : s.toCharArray()) {if (Character.isDigit(c)) {currentNumber = currentNumber * 10 + (c - '0');} else if (c == '[') {// 遇到 '[' 时，当前数字 k 和当前的字符串加入栈中counts.push(currentNumber);result.push(currentString);currentString = new StringBuilder();  // 重新开始构建新的字符串currentNumber = 0;  // 重置数字} else if (c == ']') {// 遇到 ']' 时，弹出栈顶的数字k和字符串StringBuilder decodedString = currentString;currentString = result.pop();int repeatCount = counts.pop();// 将当前字符串重复 k 次并拼接到栈顶字符串后for (int i = 0; i < repeatCount; i++) {currentString.append(decodedString);}} else {currentString.append(c);}}return currentString.toString();}

题目：每日温度

原题链接：每日温度

这个题在笔试的时候遇到过，哈哈哈，但是笔试前没刷过原题，用了其他方法a出来了。

方法1–暴力

我们可以对每一天的温度，遍历之后的每一天，直到找到一个比当前温度更高的值。这个方法效率较低，因为会进行大量的比较，时间复杂度为 O(n^2)。当然暴力过不了，但是思路是正确的。

    public int[] dailyTemperatures(int[] temperatures) {int[] answer = new int[temperatures.length];  // 初始化答案数组，默认值为 0for (int i = 0; i < temperatures.length; i++) {for (int j = i + 1; j < temperatures.length; j++) {if (temperatures[j] > temperatures[i]) {answer[i] = j - i;break;}}}return answer;}

方法2

栈的作用是帮助我们跟踪那些还没有找到“下一个更高温度”的天数。栈是单调栈，栈底元素最大，到栈顶依次减小。

    public int[] dailyTemperatures(int[] temperatures) {int[] answer = new int[temperatures.length];Stack<Integer> stack = new Stack<>();  // 用来存储温度的下标 (因为是计算天数 不是计算温差 所以存下标)for (int i = 0; i < temperatures.length; i++) {// 当前温度大于栈顶下表对应的温度时，说明找到了下一个更高温度while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {int index = stack.pop();  // 弹出栈顶元素[下标]answer[index] = i - index;}stack.push(i);}return answer;}

题目：柱状图中最大的矩形

原题链接：柱状图中最大的矩形

方法1

暴力方法：S = 底宽 * 高 （想要 S 最大，只需要固定一个，让另一个最大），显然固定高比较容易。针对每一个柱子(i) ，要是两边的柱子高于或等于当前柱子(i)，则向两边扩展。S = (right - left + 1) * heights[i])。

虽然暴力算法无法通过较大的测试用例，但优化通常是在时间复杂度较高的算法基础上进行的。能够通过暴力解法得出结果，说明你已经对这个问题有了基本的理解。

    public int largestRectangleArea(int[] heights) {int maxArea = 0;for (int i = 0; i < heights.length; ++i) {int left = i, right = i;// 确定左边界while (left - 1 >= 0 && heights[left - 1] >= heights[i]) {--left;}// 确定右边界while (right + 1 < heights.length && heights[right + 1] >= heights[i]) { ++right;}maxArea = Math.max(maxArea, (right - left + 1) * heights[i]);}return maxArea;}

方法2

1. 栈的作用：

   • 栈用于存储柱子的下标，目的是帮助我们找到每个柱子的“最大宽度”，进而计算出最大矩形面积。
   • 栈中的柱子高度是单调递增的：栈底的柱子高度小，栈顶的柱子高度大。

2. 虚拟柱子：

   • for (int i = 0; i <= heights.length; i++)：
     • i == heights.length 这个条件相当于在数组末尾加了一个高度为 0 的虚拟柱子，这样可以确保栈中的所有柱子都能被弹出，避免遗漏任何矩形面积的计算。

3. 核心逻辑：

   • 在循环中，每次我们检查当前柱子是否比栈顶的柱子矮。如果是，就意味着栈顶柱子构成的矩形已经无法继续扩展，所以我们需要计算这个矩形的面积。
   • heights[i] < heights[stack.peek()]：这个条件表示当前柱子比栈顶的柱子矮，或者遍历到了虚拟柱子（高度为 0），需要结束栈顶柱子的扩展。
   • 弹出栈顶柱子，计算以该柱子为最小高度的矩形的面积。

4. 面积计算：

   • 当栈顶柱子弹出时，它所构成的矩形的高度是 heights[stack.pop()]。
   • 宽度是从栈中当前元素的下标到当前柱子的下标之间的距离(矩形的宽度是从 stack.peek() + 1 到 i - 1 之间的所有柱子。因此宽度就是 i - stack.peek() - 1。(两者做差再加1))。如果栈为空，表示当前柱子是该区间的最小柱子，宽度为从 0 到当前位置 i；如果栈不为空，宽度是从栈顶的下标 stack.peek() 到当前柱子下标 i 之间的距离。
     • int width = (stack.isEmpty()) ? i : i - stack.peek() - 1;
     • 这里 stack.isEmpty() 用来判断栈是否为空。如果栈为空，表示当前柱子是该区间的最小柱子，宽度就是从索引 0 到 i，即 i。否则，宽度是 i - stack.peek() - 1。

5. 更新最大面积：

   • 每次计算出矩形面积后，使用 Math.max(maxArea, h * width) 更新最大面积。

    public int largestRectangleArea(int[] heights) {// 创建一个栈，用来存储柱子的下标Stack<Integer> stack = new Stack<>();int maxArea = 0; // 存储最大的矩形面积for (int i = 0; i <= heights.length; i++) {// 当栈不为空，且当前柱子比栈顶柱子矮时// 或者遍历到最后一个柱子后的一个虚拟柱子（高度为0），以确保栈会被清空while (!stack.isEmpty() && (i == heights.length || heights[i] < heights[stack.peek()])) {int h = heights[stack.pop()];// 如果栈为空，说明栈顶柱子是当前区间中的最小柱子，所以宽度是从0到当前iint width = (stack.isEmpty()) ? i : i - stack.peek() - 1;maxArea = Math.max(maxArea, h * width);}// 将当前柱子的下标压入栈stack.push(i);}return maxArea;}

---

❤觉得有用的可以留个关注❤