leecode Hot100 学习记录

//leecode303.区域和检索：计算前缀和的模版实现

public class NumArray {
    private final int [] s;
    public NumArray(int [] nums) {
        s = new int [nums.length+1];
        for (int i = 0; i <nums.length; i++) {
            s[i+1] =s[i] + nums[i];//默认定义了s【0】为0
        }
    }
    public int sumRange(int left, int right) {
        return s[right+1]-s[left];
    }
}

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;
    }

//数学规律
-----------------------------------------------------------------------------------------
//    判断一个数是不是平衡码
    private int isBanlanceCode(long num){
        String str = String.valueOf(num);
        int sum = 0;
        for (char c:str.toCharArray()){
            sum += c-'0';
        }
        return  sum%2==0?1:0;
    }
    //计算0-x之间的平衡码个数，数学规律:0-9平衡和不平衡是和奇偶一样交替的。
    //如果是奇数，每个尾数为0-9的区间，都是平衡和不平衡对半分，最后一个区间也有偶数个元素，也是对半分，因此总共是（x+1）/2平衡的个数(包含0）
    private long countBalanced(long num){
        if(num==0){
            return 1;
        }
        if (num%2!=0){
            //如果是奇数就好办了
            return (num+1)/2;
        }else{
            //如果是偶数,前面就按奇数处理，并加上最后x的结果
            return num/2 + isBanlanceCode(num);
        }
    }

//数位DP
-----------------------------------------------------------------------------------------
    //定义记忆缓存：描述当前位的情况
    long[][][] dp;
    //使用数位DP去求0-x有多少平衡码，拆分位数，一位一位地去填，统计数位之和状态
    private long countBalanced2(long num){
        if(num==0){
            return 1;
        }
        String str = String.valueOf(num);
        int len = str.length();
        int[]digit = new int[len];
        for (int i=0;i<len;i++){
            digit[i] = str.charAt(i)-'0';
        }
        dp = new long[len][2][2];
        for (int i=0;i<len;i++){
            for (int j=0;j<2;j++){
                for (int k=0;k<2;k++){
                    dp[i][j][k] = -1;//初始化缓存
                }
            }
        }
       return dfsBalanceCode(0,0,1,digit);
    }

    //02 dfs写数位DP的做法

    /**
     * @param pos    当前要填写的位置
     * @param parity 当前填写之前数位之和是否能%2（0就是偶数）
     * @param limit  当前填写能否无限制填（0-9）
     * @param digit  待检测的数字X
     * @return 所有位置填完之后统计出来的平衡码的个数
     */
    private long dfsBalanceCode(int pos,int parity, int limit,int[]digit){
        if(pos==dp.length){
            return parity==0?1:0;
        }
        if (dp[pos][parity][limit]!=-1){
            return dp[pos][parity][limit];
        }
        long res = 0;
        int maxDigit = limit == 1 ? digit[pos] : 9; // 当前位能填的最大数字
        for (int i=0;i<=maxDigit;i++){
            // 计算新的限制：上一轮受限 + 当前填了最大值 → 下一轮受限
            int newLimit = (limit == 1 && i == maxDigit) ? 1 : 0;
            // 计算新的奇偶性：当前奇偶 + 当前数字，取模2
            int newParity = (parity + i) % 2;
            res += dfsBalanceCode(pos + 1, newParity, newLimit, digit);
        }
        dp[pos][parity][limit] = res;
        return res;
    }
-----------------------------------------------------------------------------------------
    //3.22蚂蚁笔试
    //01平衡码问题,寻找区间[l,r]之间的"数位之和为偶数"的元素个数
    public void banlanceCode(String []args){
        //需要写输入
        Scanner sc = new Scanner(System.in);
        //一共有几组数据
        int total  =  sc.nextInt();
        for (int i=0;i<total;i++){
            //每组数据的输入
            long left  =  sc.nextLong();
            long right  =  sc.nextLong();
            //解决问题：统计区间之间的平衡码个数
//            方法1：使用数学规律做法
            long res = countBalanced(right) - countBalanced(left-1);

//            方法2：数位DP
            long resDP = countBalanced2(right) - countBalanced2(left-1);
            System.out.println(resDP);

        }
        sc.close();
    }

class Solution {
   private boolean isCovered(int[] cntS, int[] cntT) {
        for (int i = 'A'; i <= 'Z'; i++) {
            if (cntS[i] < cntT[i]) {
                return false;//反着来快，有一个反例就不行
            }
        }
        for (int i = 'a'; i <= 'z'; i++) {
            if (cntS[i] < cntT[i]) {
                return false;
            }
        }
        return true;
    }

      public String minWindow(String s, String t) {
        int [] countT = new int[128];
        int [] countS = new int[128];
        Map<Integer,String> map = new HashMap<>();
        int min = Integer.MAX_VALUE;
        for (int i=0;i<t.length();i++){
            countT[t.charAt(i)]++;
        }//统计出来每个字母的频率
        int left = 0;
        int right = 0;
        while (right < s.length()){
            countS[s.charAt(right)]++;
            right++;
            if (isCovered(countS, countT)){
                while(left<right && isCovered(countS, countT)){
                    countS[s.charAt(left)]--;
                    left++;//这个left一定会加，好处就是实际上最后的left一定是新的滑动窗口起点，继续找子串，而不是停留在原地陷入死循环。
                }
                map.put(right-left+1,s.substring(left-1,right)) ;//这里得注意，left一定要减一，right前面也是加了之后的所以直接用就行。substring是左闭右开，这里不需要用right+1；
                min = Math.min(min,right-left+1);
            }
        }
        if (map.containsKey(min)){
            return map.get(min);
        }
    return "";
    }
}

//普通方法
public int[] productExceptSelf(int[] nums) {
//        先计算前缀后缀
        int [] pre =  new int[nums.length+1];
        pre[0] = 1;
        int [] suf =  new int[nums.length+1];
        suf[nums.length-1] =1;//注意前缀和后缀的初始化都是基于源数组的起始和末尾的，乘积所以用1初始化
        for (int i = 1; i <=nums.length; i++){
            pre[i] = pre[i-1]*nums[i-1];
        }
        for (int i = nums.length-2; i >=0; i--){
            suf[i] = suf[i+1]*nums[i+1];
        }
    
        int []res =  new int[nums.length];
        for(int i =0;i<nums.length;i++){
            res[i] = pre[i]*suf[i];
        }
        return res;
    }



//优化空间复杂度的方法
public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        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++) {
            // 此时 pre 为 nums[0] 到 nums[i-1] 的乘积，直接乘到 suf[i] 中
            suf[i] *= pre;
            pre *= nums[i];
        }

        return suf;
    }

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 统计节点个数
        int n = 0;
        for (ListNode cur = head; cur != null; cur = cur.next) {
            n++;
        }

        ListNode dummy = new ListNode(0, head);
        ListNode p0 = dummy;
        ListNode pre = null;
        ListNode cur = head;

        // k 个一组处理
        for (; n >= k; n -= k) {
            for (int i = 0; i < k; i++) { // 同 92 题
                ListNode nxt = cur.next;
                cur.next = pre; // 每次循环只修改一个 next，方便大家理解
                pre = cur;
                cur = nxt;
            }

            // 见视频
            ListNode nxt = p0.next;
            p0.next.next = cur;
            p0.next = pre;
            p0 = nxt;
        }
        return dummy.next;
    }
}

作者：灵茶山艾府
链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/solutions/1992228/you-xie-cuo-liao-yi-ge-shi-pin-jiang-tou-plfs/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public ListNode sortList(ListNode head) {
        // 如果链表为空或者只有一个节点，无需排序
        if (head == null || head.next == null) {
            return head;
        }
        // 找到中间节点 head2，并断开 head2 与其前一个节点的连接
        // 比如 head=[4,2,1,3]，那么 middleNode 调用结束后 head=[4,2] head2=[1,3]
        ListNode head2 = middleNode(head);
        // 分治
        head = sortList(head);
        head2 = sortList(head2);
        // 合并
        return mergeTwoLists(head, head2);
    }

    // 876. 链表的中间结点（快慢指针）
    private ListNode middleNode(ListNode head) {
        ListNode pre = head;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            pre = slow; // 记录 slow 的前一个节点
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null; // 断开 slow 的前一个节点和 slow 的连接
        return slow;
    }

    // 21. 合并两个有序链表（双指针）
    private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(); // 用哨兵节点简化代码逻辑
        ListNode cur = dummy; // cur 指向新链表的末尾
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1; // 把 list1 加到新链表中
                list1 = list1.next;
            } else { // 注：相等的情况加哪个节点都是可以的
                cur.next = list2; // 把 list2 加到新链表中
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 != null ? list1 : list2; // 拼接剩余链表
        return dummy.next;
    }
}

class LRUCache {
    private static class Node {
        int key, value;
        Node prev, next;

        Node(int k, int v) {
            key = k;
            value = v;
        }
    }

    private final int capacity;
    private final Node dummy = new Node(0, 0); // 哨兵节点
    private final Map<Integer, Node> keyToNode = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        dummy.prev = dummy;
        dummy.next = dummy;
    }

    public int get(int key) {
        Node node = getNode(key); // getNode 会把对应节点移到链表头部
        return node != null ? node.value : -1;
    }

    public void put(int key, int value) {
        Node node = getNode(key); // getNode 会把对应节点移到链表头部
        if (node != null) { // 有这本书
            node.value = value; // 更新 value
            return;
        }
        node = new Node(key, value); // 新书
        keyToNode.put(key, node);
        pushFront(node); // 放到最上面
        if (keyToNode.size() > capacity) { // 书太多了
            Node backNode = dummy.prev;
            keyToNode.remove(backNode.key);
            remove(backNode); // 去掉最后一本书
        }
    }

    // 获取 key 对应的节点，同时把该节点移到链表头部
    private Node getNode(int key) {
        if (!keyToNode.containsKey(key)) { // 没有这本书
            return null;
        }
        Node node = keyToNode.get(key); // 有这本书
        remove(node); // 把这本书抽出来
        pushFront(node); // 放到最上面
        return node;
    }

    // 删除一个节点（抽出一本书）
    private void remove(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
    }

    // 在链表头添加一个节点（把一本书放到最上面）
    private void pushFront(Node x) {
        x.prev = dummy;
        x.next = dummy.next;
        x.prev.next = x;
        x.next.prev = x;
    }
}