Leetcode Hot 100

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

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> hashMap = new HashMap<>();
        for (String str : strs) {
            // 转为字符数组排序
            char[] array = str.toCharArray();
            Arrays.sort(array);
            // 转为String为key，做判断
            String key = Arrays.toString(array);
            // 判断是否存在该单词
            List<String> ans = hashMap.getOrDefault(key, new ArrayList<>());
            ans.add(str);
            hashMap.put(key,ans);
        }
        // 结果集
        return new ArrayList<List<String>>(hashMap.values());
    }
}

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        // 去重
        for(int num : nums){
            set.add(num);
        }
        int maxL = 0;
        //x-1 的序列长度 >> x 的序列长度
        for(int x : set){
            if(set.contains(x - 1)){
                continue;
            }else{
                int curL = 1;
                while(set.contains(x + 1)){
                    curL ++;
                    x ++;
                }
                maxL = Math.max(maxL,curL);
            }
        }
        return maxL;
    }
}

class Solution {
    public void moveZeroes(int[] nums) {
        int head = 0;
        int tail = 0;
        // 将不为0的num[tail]依次插入num[head]
        while (tail < nums.length) {
            if (nums[tail] != 0) {
                int temp = nums[head];
                nums[head] = nums[tail];
                nums[tail] = temp;
                head++;
            }
            tail ++;
        }
    }
}

class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int area = -1;
        while(left < right) {
            area = Math.max(area,(right - left) * Math.min(height[left],height[right]));
            // 移动短板
            if(height[left] >= height[right]){
                right --;
            }else{
                left ++;
            }
        }
        return area;
    }
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        // a + b + c = sum
        for(int i = 0; i < nums.length - 2; i++) {
            int a = nums[i];
            // 去重
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            // 双指针枚举[i + 1, nums.length]中元素
            int l = i + 1;
            int r = nums.length - 1;
            while(l < r){
                int sum = a + nums[l] + nums[r];
                if(sum > 0){
                    while(l < r && nums[r] == nums[--r]);
                }else if(sum < 0) {
                    while(l < r && nums[l] == nums[++l]);
                }else{
                    List<Integer> ans = new ArrayList<>();
                    ans.add(a);
                    ans.add(nums[l]);
                    ans.add(nums[r]);
                    res.add(ans);
                    // 去重
                    while(l < r && nums[r] == nums[--r]);
                    while(l < r && nums[l] == nums[++l]);
                }
            }
        }
        return res;
    }
}

class Solution {
    public int trap(int[] height) {
        // maxL[i]为左边柱子的最大高度，包括本身
        int[] maxL = new int[height.length]; 
        // maxL[i]为右边柱子的最大高度，包括本身
        int[] maxR = new int[height.length]; 
        maxL[0] = height[0];
        maxR[height.length - 1] = height[height.length - 1];
        for (int i = 1; i < height.length; i++) {
            maxL[i] = Math.max(maxL[i - 1], height[i]);
        }
        for (int i = height.length - 2; i >= 0; i --) {
            maxR[i] = Math.max(maxR[i + 1], height[i]);
        }
        // 接的雨水为当前柱子i Min{maxL[i],maxR[i]} - height[i]
        int cnt = 0;
        for(int i = 1; i < height.length - 1; i++) {
            int res = Math.min(maxL[i - 1],maxR[i + 1]) - height[i];
            cnt += Math.max(res, 0);
        }
        return cnt;
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() <= 0) return 0;
        char[] arr = s.toCharArray();
        Set<Character> set = new HashSet<>();
        int head = 0;
        int tail = 1;
        set.add(arr[0]);
        int res = 1;
        while(tail < arr.length){
            // 伸缩
            while(head < tail && set.contains(arr[tail])) {
                set.remove(arr[head]);
                head ++;
            }
            // 扩张
            set.add(arr[tail]);
            res = Math.max(res,tail - head + 1);
            tail ++;
        }
        return res;
    }
}

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if(s.length() < p.length()) return new ArrayList<>();
        int[] base = new int[26];
        for(char c: p.toCharArray()) {
            base[c - 'a'] ++;
        }
        int[] cnt = new int[26];
        for(int i = 0; i < p.length(); i++){
            cnt[s.charAt(i) - 'a'] ++;
        }
        int l = 0;
        int r = p.length() - 1;
        List<Integer> res = new ArrayList<>();
        while(r < s.length()){
            if(Arrays.equals(cnt,base)){
                res.add(l);
            }
            // 防止越界
            if(r == s.length() - 1){
                break;
            }
            cnt[s.charAt(l++) - 'a'] --;
            cnt[s.charAt(++r) - 'a'] ++;
        }
        return res;
    }
}

// 解法一: 直接枚举所有子数组
class Solution {
    public int subarraySum(int[] nums, int k) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            int ans = 0;
            for (int j = i; j < nums.length; j++) {
                ans += nums[j];
                if (ans == k) {
                    res ++;
                }
            }
        }
        return res;
    }
}
// 解法二：动态规划
class Solution {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> mp = new HashMap<>();
        int res = 0;
        int suf = 0;
        // 当suf[i] - k = 0 即suf[i] = k时的初始值
        mp.put(0, 1); 
        for (int i = nums.length - 1; i >= 0; i--) {
            suf+=nums[i];
            if (mp.containsKey(suf - k)) {
                res += mp.get(suf - k);
            }
            mp.put(suf, mp.getOrDefault(suf, 0) + 1);
        }
        return res;
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 优先队列（大根堆）
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] pair1, int[] pair2) {
                // 如果2个数相等，那么index大的在前面
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });
        for (int i = 0; i < k; ++i) {
            pq.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[nums.length - k + 1];
        ans[0] = pq.peek()[0];
        for (int i = k; i < nums.length; ++i) {
            pq.offer(new int[]{nums[i], i});
            // 只有当最大值不在在窗口内则删除，其余的不用管
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }
}

class Solution {
    public String minWindow(String s, String t) {
        if(t.length() > s.length()) return "";
        HashMap<Character,Integer> map = new HashMap<>();
        char[] arr1 = t.toCharArray();
        for(char c : arr1){
            map.put(c,map.getOrDefault(c,0) + 1);
        }
        int left = 0;
        int right = 0;
        int need = 0;
        char[] arr2 = s.toCharArray();
        int minL = 0;
        int minR = -1;
        while(right < s.length()){
            if(map.containsKey(arr2[right])){
                int size = map.get(arr2[right]);
                map.put(arr2[right],size - 1);
                if(size == 1){
                    need ++;
                }
            }
            // 收缩
            while(left <= right && need == map.size()){
                if(minR == -1 || right - left < minR - minL){
                    minL = left;
                    minR = right;
                }
                if(map.containsKey(arr2[left])){
                    int size = map.get(arr2[left]);
                    map.put(arr2[left],size + 1);
                    if(size == 0){
                        need --;
                    }
                }
                left ++;
            }
            right ++;
        }
        return s.substring(minL,minR + 1);
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = dp[0];
        for(int i = 1; i < nums.length; i++){
            dp[i] = Math.max(dp[i-1] + nums[i],nums[i]);
            res = Math.max(dp[i],res);
        }
        return res;
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new ArrayList<>();
        Arrays.sort(intervals, (o1,o2) -> o1[0] - o2[0]);
        for(int i = 0; i < intervals.length; i ++){
            // 相交 x1<=x2<=y1<=y2(x1<=x2<=y2<=y1)
            while(i+1 < intervals.length && intervals[i][1] >= intervals[i+1][0]){
                // 合并
                intervals[i+1][0] = intervals[i][0];
                intervals[i+1][1] = Math.max(intervals[i][1],intervals[i+1][1]);
                i++;
            }
            // 相隔 x1<y1<x2<y2
            res.add(intervals[i]);
        }
        return res.toArray(new int[res.size()][2]);
    }
}

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        int count = 0; // 移动的次数，每一个元素移动1次 共n次
        int cntIndex = 0; // 初始索引
        int nextIndex = k % n ; // 下一个位置索引
        int move = nums[0]; // 移动的元素值
        while (count < n) {
            int next = nums[nextIndex];
            nums[nextIndex] = move;
            move = next;
            count++;
            // 成环
            if (count < n && cntIndex == nextIndex) {
                cntIndex ++;
                move = nums[cntIndex];
                nextIndex =  (cntIndex + k) % n;
                continue;
            }
            nextIndex = (nextIndex + k) % n;
        }
    }
}

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        // 整体反转 0->n-1
        reverse(0,n - 1,nums);
        // 反转0->k -1
        reverse(0,k-1,nums);
        // 反转n-k -> n - 1
        reverse(k,n - 1,nums);
    }
    public void reverse(int l,int r,int[] nums) {
        while (l < r) {
            int temp = nums[l];
            nums[l ++] = nums[r];
            nums[r --] = temp;
        }
    }
}

nums   = "--->-->"; k =3
result = "-->--->"; 
// 解释
reverse "--->-->" we can get "<--<-----" 
reverse "<--"     we can get "--><-----" 
reverse "<-----"  we can get "-->----->" 

class Solution {
    public void rotate(int[] nums, int k) {
        if(k == 0) return;
        int n = nums.length;
        int index = n - (k % n);
        int[] copy = new int[n];
        int j = 0;
        for(int i = index; i < n; i++){
            copy[j++] = nums[i];
        }
        for(int i = 0; i < index; i++){
            copy[j++] = nums[i];
        }
        for(int i = 0; i < n; i++){
            nums[i] = copy[i];
        }
        return;
    }
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        int[] suf = new int[n];
        suf[n-1] = 1;
        for(int i = n-2; i >= 0; i--){
            suf[i] = suf[i+1] * nums[i+1];
        }
        int pre = 1;
        for(int i = 0; i < n; i++){
            answer[i] = pre * suf[i];
            pre *= nums[i];
        }
        return answer;
    }
}

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

class Solution {
    public void setZeroes(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        int[] rowS = new int[row];
        int[] colS = new int[col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == 0) {
                    // i行j列需要为0
                    rowS[i] = -1;
                    colS[j] = -1;
                }
            }
        }
        for (int i = 0; i < row; i++) {
            if (rowS[i] == -1) {
                for (int j = 0; j < col; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int i = 0; i < col; i++) {
            if (colS[i] == -1) {
                for (int j = 0; j < row; j++) {
                    matrix[j][i] = 0;
                }
            }
        }
    }
}

class Solution {
    public void setZeroes(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        // 第一行和第一列的状态
        boolean row0 = false;
        boolean col0 = false;
        for (int i = 0; i < row; i++) {
            if (matrix[i][0] == 0) {
                col0 = true;
                break;
            }
        }
        for (int i = 0; i < col; i++) {
            if (matrix[0][i] == 0) {
                row0 = true;
                break;
            }
        }
        // 用matrix的第一行和第一列记录matrix的状态
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < row; i++) {
            if (matrix[i][0] == 0) {
                for (int j = 0; j < col; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int i = 1; i< col; i++) {
            if (matrix[0][i] == 0) {
                for (int j = 0; j < row; j++) {
                    matrix[j][i] = 0;
                }
            }
        }
        if (row0) {
            for (int i = 0; i < col; i++) {
                matrix[0][i] = 0;
            }
        }
        if (col0) {
            for (int i = 0; i < row; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
      int m = matrix.length;
      int n = matrix[0].length;
      List<Integer> res = new ArrayList<>();
      int left = 0;
      int right = n-1;
      int top = 0;
      int down = m-1;
      while(res.size() < m*n){
        for(int i = left; i <= right; i++){
          res.add(matrix[top][i]);
        }
        for(int i = top+1; i <= down; i++){
          res.add(matrix[i][right]);
        }
        if(left < right && top < down){
          for(int i = right - 1; i > left; i--){
            res.add(matrix[down][i]);
          }
          for(int i = down; i > top; i--){
            res.add(matrix[i][left]);
          }
        }
        left ++;
        right --;
        top ++;
        down --;
      }
      return res;
    }
}

 class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 沿对角线 \ 翻转
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                int temp = matrix[j][i];
                matrix[j][i] = matrix[i][j];
                matrix[i][j] = temp;
            }
        }
        // 左右翻转
        for(int i = 0; i < n; i++){
            for(int l=0,r=n-1; l < r; l++,r--){
                int temp = matrix[i][r];
                matrix[i][r] = matrix[i][l];
                matrix[i][l] = temp;
            }
        }
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 模拟搜索树
        int row = matrix.length;
        int col = matrix[0].length;
        int i = 0;
        int j = col - 1;
        while (i < row && i >= 0 && j < col && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] < target) {
                i++;
            } else {
                j--;
            }
        }
        return false;
    }
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // a+b+c = c+b+a
        ListNode nodeA = headA;
        ListNode nodeB = headB;
        while(nodeA != null || nodeB != null){
            if(nodeA == nodeB){
                return nodeA;
            }
            nodeA = nodeA == null ? headB:nodeA.next;
            nodeB = nodeB == null ? headA:nodeB.next;
        }
        return null;
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode cntNode = head;
        ListNode pre = null;
        while(cntNode != null){
            ListNode temp = cntNode.next;
            cntNode.next = pre;
            pre = cntNode;
            cntNode = temp;
        }
        return pre;
    }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head.next == null){
            return true;
        }
        // 先反转再判断
        ListNode s = head;
        ListNode f = head;
        while(f != null && f.next != null){
            s = s.next;
            f = f.next.next;
        }
        ListNode pre = null;
        while(s != null){
            ListNode temp = s.next;
            s.next = pre;
            pre = s;
            s = temp;
        }
        while(pre != null && head != null){
            if(pre.val == head.val){
                pre = pre.next;
                head = head.next;
            }else{
                return false;
            }
        }
        return true;
    }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> hashSet = new HashSet<>();
        ListNode cur = head;
        while(cur != null){
            if(hashSet.contains(cur)){
                return true;
            }
            hashSet.add(cur);
            cur = cur.next;
        }
        return false;
    }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
          slow = slow.next;
          fast = fast.next.next;
          // 有环
          if(slow == fast){
            break;
          }
        }
        // 无环
        if(fast == null || fast.next == null){
            return null;
        }
        // 相交节点
        while(slow != head){
            slow = slow.next;
            head = head.next;
        }
        return slow;
    }
}

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode();
        ListNode node = head;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                node.next = list1;
                list1 = list1.next;
            }else{
                node.next = list2;
                list2 = list2.next;
            }
            node = node.next;
        }
        if(list1 == null && list2 != null){
            node.next = list2;
        }
        if(list2 == null && list1 != null){
            node.next = list1;
        }
        return head.next;
    }
}

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode();
        ListNode cnt = head;
        int jw = 0;
        while(l1 != null || l2 != null){
            int val = jw;
            if(l1 != null){
                val += l1.val;
                l1 = l1.next;
            }
            if(l2 != null){
                val += l2.val;
                l2 = l2.next;
            }
            jw = val / 10;
            val = val % 10;
            cnt.next = new ListNode(val);
            cnt = cnt.next;
        }
        if(jw != 0){
            cnt.next = new ListNode(jw);
        }
        return head.next;
    }
}