当前位置： 首页 > article >正文

hot100-3、438、560、239、240、160、234（2简3中1难）

article 2025/2/22 4:10:31

滑窗问题↓

3. 无重复字符的最长子串（中等）

方法一、滑动窗口

数组结合哈希表=ascii码，滑动出口。其实可以优化为left = Math.max(left,map.get(s.charAt(i)) + 1)，数组的话就是全部初始化为-1，用来计算最新下标而不是出现的位置。当然，为了避免查找到i的位置，需要注意先判断、再更新。

import java.util.*;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int res = 0,n = s.length(),l = 0;
        int[] alpha = new int[256];
        for(int i = 0;i < n;i++){
            alpha[s.charAt(i)]++;
            while(alpha[s.charAt(i)] > 1){
                alpha[l]--;
                l++;
            }
            res = Math.max(res,i-l+1);
        }
        return res;
    }
}

438. 找到字符串中所有字母异位词(中等) 

方法一、滑窗

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int sL = s.length(), pL = p.length();
        if (sL < pL) return res;

        // 创建一个频率数组，记录p中各个字符的出现次数
        int[] pCount = new int[26];
        for (int i = 0; i < pL; i++) {
            pCount[p.charAt(i) - 'a']++;
        }

        int[] sCount = new int[26];

        for (int i = 0; i < pL; i++) {
            sCount[s.charAt(i) - 'a']++;
        }

        if (Arrays.equals(pCount, sCount)) {
            res.add(0);
        }

        for (int i = pL; i < sL; i++) {
            // 加入新字符到窗口
            sCount[s.charAt(i) - 'a']++;

            // 移除旧字符出窗口
            sCount[s.charAt(i - pL) - 'a']--;

            // 如果当前窗口的字符频率数组和p的字符频率数组相同，说明是一个异位词
            if (Arrays.equals(pCount, sCount)) {
                res.add(i - pL + 1);
            }
        }

        return res;
    }
}

子串问题↓

560. 和为 K 的子数组（中等）
 

方法一、哈希表+前缀和

一开始使用了滑动窗口（如代码①），最后看了答案改成②。反思：不能使用滑动窗口的原因是滑窗原理为右边界扩充可能使原本符合条件的不再符合，左边界缩小可以使不再符合的条件变得符合。而在这里并不达成，原因是数组中可能出现负数（负数对这道题做法影响好大）。如果全正数，滑窗+前缀和是可行的。

此外，这里还考虑到了返回值对解法的改变，正是因为不考虑具体的解、只关心个数，才会能这样。对一个新出现的前缀和preSum，它一定会导致和前面所有t个(preSum-k)的部分达成新增加t个解，而每次对preSum的遍历，都是一次天然的记录，核心是：刚查找到即处理，则不需要记录。

class Solution {
    public int subarraySum(int[] nums, int k) {
       int n = nums.length,l = 0,r = 0,res = 0;
       boolean gai = false;
       int[] sum = new int[n+1];
       for(int i = 1;i <= n;i++){
           sum[i] = sum[i-1]+nums[i-1];
       }
       //sum数组查询:sum[r-l+1]
        while(r<n){
            int s = sum[r+1] - sum[l];
            if(s > k){//大了
                l++;
                if(r < l)r++;
            }else if(s < k){
                r++;
            }else{
                res++;
                r++;
            }
        }
        return res;
    }
}
class Solution {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer,Integer> hm = new HashMap<>();
        int preSum = 0,res = 0,n = nums.length;
        hm.put(0,1);
        for(int i = 0;i<n;i++){
           preSum+=nums[i];
           if(hm.containsKey(preSum-k)){
               res+=hm.get(preSum-k);
           }
           hm.put(preSum,hm.getOrDefault(preSum,0)+1);
        }
        return res;
    }
}

239. 滑动窗口最大值（困难） 

方法一、单调队列 

学到了单调栈和单调队列本质上都是思想，结合需求灵活变通数据类型

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> dq = new ArrayDeque<>();
        int n = nums.length;
        int[] res = new int[n-k+1];
        int count = 0;
        for(int i = 0;i < n;i++){
            //入栈
            while (!dq.isEmpty() &&nums[dq.peekLast()] <= nums[i]){
                dq.pollLast();
            }
            dq.add(i);
            //出栈
            if(!dq.isEmpty() && i - dq.peek()>= k){
                dq.pop();
            }
            //打印
            if(i >= k-1){
                res[count]+=nums[dq.peek()];
                count++;
            }

        }
        return res;
    }
}

240. 搜索二维矩阵 II(中等)

方法一、搜索二叉树 

对于右上点为根，左侧小右侧大

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length,m = matrix[0].length,x=0,y=m-1;
        while(y >= 0 && x < n && matrix[x][y] != target){
            if(matrix[x][y] > target){
                y--;
            }else{
                x++;
            }
        }
        return y >= 0 && x < n;
    }
}

方法二、同时二分

效率不高 距离看视频有段时间 二分边界还有点不会

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length,m = matrix[0].length;
        return search(matrix,target,0,n-1,0,m-1);

    }
    public boolean search(int[][] matrix,int target,int r_l,int r_r,int c_l,int c_r){
        if(r_l <= r_r && c_l <= c_r){//不包的情况
            int rMid = r_l + (r_r - r_l) / 2;
            int cMid = c_l + (c_r - c_l) / 2;
            if(matrix[rMid][cMid] > target){//大的情况下左上 本质上就是c往左，r往上
                return search(matrix,target,r_l,rMid-1,c_l,c_r)||search(matrix,target,r_l,r_r,c_l,cMid-1);
            }else if(matrix[rMid][cMid] < target){//小的情况下右下 本质上就是c往右，r往下
                return search(matrix,target,r_l,r_r,cMid+1,c_r)||search(matrix,target,rMid+1,r_r,c_l,c_r);
            }else{
                return true;
            }
        }
        return false;
    }
}

160. 相交链表(简单)

方法一、集合

Set太耗时但思路简单


public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        ListNode temp = headA;
        while(temp != null){
            set.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while(temp != null){
            if(set.contains(temp))return temp;
            temp = temp.next;
        }
        return null;
    }
}

方法二、数学证明

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


234. 回文链表（简单）

方法一、数组+双指针


class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> vals = new ArrayList<Integer>();

        // 将链表的值复制到数组中
        ListNode currentNode = head;
        while (currentNode != null) {
            vals.add(currentNode.val);
            currentNode = currentNode.next;
        }

        // 使用双指针判断是否回文
        int front = 0;
        int back = vals.size() - 1;
        while (front < back) {
            if (!vals.get(front).equals(vals.get(back))) {
                return false;
            }
            front++;
            back--;
        }
        return true;
    }
}

方法二、递归 （*）

递归最神奇的就是能够完成单向链表的反向遍历，靠函数返回值进行。全局变量进行控制，递归到头时更改全局变量的内容，很神奇的一个做法，简单题但意义大于简单

class Solution {
    private ListNode frontPointer;

    private boolean recursivelyCheck(ListNode currentNode) {
        if (currentNode != null) {
            if (!recursivelyCheck(currentNode.next)) {
                return false;
            }
            if (currentNode.val != frontPointer.val) {
                return false;
            }
            frontPointer = frontPointer.next;
        }
        return true;
    }

    public boolean isPalindrome(ListNode head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/palindrome-linked-list/solutions/457059/hui-wen-lian-biao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

碎碎念

熟悉了一下数据结构（Deque模拟栈之类的，以及常用函数），比较惊艳240的二叉树模拟做法、160的思想（链表可能具有某种可数学证明的长度关系）和234的回文链表的思想（递归可以满足倒序查看单向链表）。

二分还不太熟


http://www.kler.cn/a/553015.html

相关文章：

  • 网络原理-
  • Miniconda + VSCode 的Python环境搭建
  • 【架构思维基础：如何科学定义问题】
  • 青少年编程与数学 02-009 Django 5 Web 编程 23课题、安全性
  • 使用Java爬虫获取京东商品SKU信息的完整指南
  • JS应用原生代码Ajax技术JQuery库Axios库前端校验安全结合
  • 前七章综合练习
  • C++基础知识学习记录—模版和泛型编程
  • 前沿科技：改变生活的十大趋势
  • 如何在谷歌搜索中获得更好的排名？
  • nginx ngx_http_module(9) 指令详解
  • Webpack，Vite打包的理解
  • 框架--Mybatis 2
  • 第三方库XLSX: 前端上传excel文件，并对excel文件内容做校验。
  • ERP对制造业务有何价值？
  • No.39 蓝队 | 网络安全实战笔记：系统加固与资产梳理
  • Spring框架详解(一)
  • DeepSeek私有化部署3：openEuler 24.03-LTS-SP1国产化操作系统安装nVidia驱动
  • 纯新手教程：用llama.cpp本地部署DeepSeek蒸馏模型
  • Windows逆向工程入门之堆栈回溯