leecode Hot100 学习记录

public int subarraySum(int[] nums, int k) {
        int [] s = new int[nums.length+1];
        for (int i=0;i<nums.length;i++){
            s[i+1] =  s[i]+nums[i];
        }
        int ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i <s.length ; i++) {
            ans += map.getOrDefault(s[i]-k,0);//查询已有的哈希表
            map.put(s[i],map.getOrDefault(s[i],0)+1);//创建前缀和的值的哈希表元素
        }
        return ans;
    }

public int maxSubArray(int[] nums) {
           int []sum =  new int[nums.length+1];
           for (int i = 0; i < nums.length; i++) {
                    sum[i+1] = sum[i] + nums[i];
           }//求出前缀和数组
           int min = 0;
           int maxVal = Integer.MIN_VALUE;
           for (int i = 1; i < sum.length; i++) {
               if (sum[i]-min > maxVal){
                   maxVal = sum[i]-min;
               }
               if (sum[i] < min){
                   min = sum[i];
               }
           }
           return maxVal;
    }

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] ans = new int[nums.length-k+1];
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
//           进
            while (!q.isEmpty() && nums[q.getLast()] < nums[i] ) {
                //后来者更大，需要删除已有的最新的，保证只留下最可能成为最大值的,可能要去掉多个所以用的是while而不是if
                q.removeLast();
            }
            q.addLast(i);
//            出，能出or该出就出
            int left = i-k+1;
            if (left >q.getFirst() ) {
                q.removeFirst();
            }
//            记录元素
            if (left>=0){
                ans[left]=nums[q.getFirst()];
            }
        }
        return ans;
    }
}

 public int[][] merge(int[][] intervals) {
        List<int []> ans = new ArrayList<>();
        Arrays.sort(intervals,(a,b)->a[0]-b[0]);//正序排序左端点
        for (int i = 0; i < intervals.length; i++) {
            if (!ans.isEmpty() && ans.getLast()[1]>=intervals[i][0]){
                ans.getLast()[1]=Math.max(ans.getLast()[1],intervals[i][1]);
            }else  {
                ans.addLast(intervals[i]);
            } 
        }
        return ans.toArray(new int[ans.size()][]);
    }

class Solution {
    public void ratateUtil(int [] nums,int start,int end){
        int l = start;
        int r = end;
        while( l < r){
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
            l++;
            r--;
        }
    }

    public void rotate(int[] nums, int k) {
            k = k % nums.length;
            ratateUtil(nums,0,nums.length-1);
            ratateUtil(nums,0,k-1);
            ratateUtil(nums,k,nums.length-1);
        
        
    }
}

 public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            //给数组的每个数找他们应该在的位置，发现不对就交换。让原本的数组从1开始。所以这里用的是=nums[nums[i]-1]
            while(nums[i]>=1 && nums[i]<=nums.length && nums[i]!=nums[nums[i]-1]){
                int temp = nums[nums[i]-1];
                nums[nums[i]-1] = nums[i];
                nums[i] = temp;
            }
        }
     //因此这里的判断是i+1，因为当前格子实际数组是1-n的顺序，是比索引大一。
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i+1) {
                return i+1;
            }
        }
        return nums.length+1;
    }

public List<Integer> spiralOrder(int[][] matrix) {
        int m =  matrix.length;
        int n = matrix[0].length;
        List<Integer> ans = new ArrayList<>();
        int[][] copy = new int[m][n];//防止更改原本的数组
        for (int i = 0; i < matrix.length; i++) {
            copy[i] = Arrays.copyOf(matrix[i], matrix[i].length);
        }
        int [][]DIRECTION = new int [][]{{0,1},{1,0},{0,-1},{-1,0}};
        int i=0,j=0;
        int di = 0;//表示现在是哪个方向
        for (int k = 0; k < n*m; k++) {
            ans.add(matrix[i][j]);
            copy[i][j] = Integer.MAX_VALUE;
            int x = i+DIRECTION[di][0];
            int y = j+DIRECTION[di][1];
            if (x<0 || x>=m || y<0 || y>=n || copy[x][y]==Integer.MAX_VALUE) {
                di = (di+1) % 4;//该转向了
            }
            i = i+DIRECTION[di][0];
            j = j+DIRECTION[di][1];
        }

        return ans;
    }

   public void rotate(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < i; j++) {//转置只对对角线下的元素操作。
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length/2; j++) {
                int temp  = matrix[i][j];
                matrix[i][j] = matrix[i][matrix[i].length-j-1];//对称交换
                matrix[i][matrix[i].length-j-1] = temp;
            }
        }
    }

public boolean searchMatrix(int[][] matrix, int target) {
       int i = 0;
       int j = matrix[0].length-1;
       while (i < matrix.length && j >= 0){
           if (matrix[i][j] == target){
               return true;
           }else if (matrix[i][j] > target){
               j--;
           }else {
               i++;
           }
       }
        return false;
    }

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p = headA;
        ListNode q = headB;
        while (p != q) {
            p = p != null ? p.next : headB;
            q = q != null ? q.next : headA;
        }
        return p;
    }
}

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0); // 虚拟头节点
        ListNode curr = dummy;
        int carry = 0;
        
        while (l1 != null || l2 != null || carry != 0) {//概括三种情况
            int x = (l1 != null) ? l1.val : 0;//第一条链表的值
            int y = (l2 != null) ? l2.val : 0;//第二条链表的值
            int sum = carry + x + y;//暂时的和
            
            carry = sum / 10;//是否进位
            curr.next = new ListNode(sum % 10);//结果
            curr = curr.next;//下一个
            
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        
        return dummy.next;
    }
}

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode pHead = new ListNode(0);
        pHead.next = head;
        ListNode fast = pHead;
        ListNode slow = pHead;
        int count = 0;
        while(fast!=null&&count<n){
            fast = fast.next;
            count++;
        }
        while(fast!=null && fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;

        return pHead.next;
    }

//反转链表2-片段反转  需要哨兵+pre /cur/next三个指针保证当前指向前面的，最后连接原链表和反转后的尾巴和头部。返回哨兵下一个
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new  ListNode(0) ;
        dummy.next = head;
        ListNode p = dummy;
        int count = 0;
        while (count < left-1) {
            p = p.next;
            count++;
        }//p在left前一个，从这里开始反转
        ListNode pre = null;
        ListNode cur = p.next;
        while (count < right) {//遍历最后一次结束cur是反转的下一个，pre时反转的最后一个
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
            count++;
        }
        p.next.next = cur;
        p.next = pre;
        return dummy.next;
    }