Hot100

哈希

两数之和

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

字母异位分组

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String,LinkedList<String>>cur=new HashMap<>();
        for(String str:strs){
            char[] c1=str.toCharArray();
            Arrays.sort(c1);
            String s=String.valueOf(c1);
            if(!cur.containsKey(s)){
                cur.put(s,new LinkedList<>());
                cur.get(s).add(str);
            }else{
                cur.get(s).add(str);
            }
        }
        return new LinkedList(cur.values());
    }

}

最长连续序列：给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度

class Solution {
    public int longestConsecutive(int[] nums) {
        int ans = 0;
        Set<Integer> st = new HashSet<>();
        for (int num : nums) {
            st.add(num); // 把 nums 转成哈希集合
        }
        for (int x : st) { 
            if (st.contains(x - 1)) {
                continue;
            }
            // x 是序列的起点
            int y = x + 1;
            while (st.contains(y)) { // 不断查找下一个数是否在哈希集合中
                y++;
            }
            // 循环结束后，y-1 是最后一个在哈希集合中的数
            ans = Math.max(ans, y - x); // 从 x 到 y-1 一共 y-x 个数
        }
        return ans;
    }
}

双指针

移动零

class Solution {
    public void moveZeroes(int[] nums) {
        int l=0;
        for(int j=0;j<nums.length;j++){
            if(nums[j]!=0){
                nums[l]=nums[j];
                l++;
            }
        }
        for(int i=l;i<nums.length;i++){
            nums[i]=0;
        }
    }
}

盛最多水的容器

class Solution {
    public int maxArea(int[] height) {
        int res=0;
        int l=0,r=height.length-1;
        while(l<r){
            int max=0;
            if(height[l]<height[r]){
                max=height[l]*(r-l);
                l++;
            }else{
                max=height[r]*(r-l);
                r--;
            }
            res=Math.max(res,max);
        }
        return res;
    }
}

三数之和

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>>res=new LinkedList<>();
        int len=nums.length;
        for(int i=0;i<len-2;i++){
            if(i>0&&nums[i]==nums[i-1])
                continue;

            int l=i+1,r=nums.length-1;
            while(l<r){
                int sum=nums[i]+nums[l]+nums[r];
                if(sum==0){
                   LinkedList<Integer>track=new LinkedList<>();
                    track.add(nums[l]);
                    track.add(nums[i]);
                    track.add(nums[r]);
                    res.add(track);
                    while(l<r&&nums[l]==nums[l+1]){
                    l++;
                    }
                    while(l<r&&nums[r]==nums[r-1]){
                    r--;
                    }
                    l++;
                    r--; 
                }else if(sum>0){
                    r--;
                }else{
                    l++;
                }
            }
        }
        return res;
    }
}

无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len=s.length();
        if(len<=1){
            return len;
        }
        int[] res=new int[128];
        int l=0,r=0,max=0;
        while(r<len){
            char c=s.charAt(r++);
            res[c]++;
            while(res[c]>1){
                char c1=s.charAt(l++);
                res[c1]--;
            }
            max=Math.max(max,r-l);
        }
        return max;
    }
}

找到字符串中所有字母异位词

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer>res=new LinkedList<>();
        HashMap<Character,Integer>need=new HashMap<>();
        HashMap<Character,Integer>window=new HashMap<>();
        for(char c:p.toCharArray()){
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int left=0,right=0,viald=0;
        while(right<s.length()){
            char c=s.charAt(right++);
            if(need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if(window.get(c).equals(need.get(c))){
                    viald++;//p都是单个的，可直接匹配
                }
            }
            while(right-left>=p.length()){
                if(viald==need.size()){
                    res.add(left);
                }
                char d=s.charAt(left++);
                if(need.containsKey(d)){
                    if(window.get(d).equals(need.get(d))){
                        viald--;
                    }
                    window.put(d,window.get(d)-1);
                }
            }
        }
        return res;
    }
}

子串

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列

class Solution {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer,Integer>map=new HashMap<>();
        int cur=0,res=0;
        map.put(k,1);
        for(int num:nums){
            cur+=num;
            if(map.containsKey(cur)){
                res+=map.get(cur);
            }
            map.put(cur+k,map.getOrDefault(cur+k,0)+1);
        }
        return res;
    }
}

前缀和，假设：hash第一次存前缀和+k，如果之后前缀和可以在hash中找到，那么说明之间距离为k hash存这个前缀和数字出现次数

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位

返回 滑动窗口中的最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> q = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            while (!q.isEmpty() && nums[i] > q.peekLast()) {
                q.pollLast();//只放最大
            }
            q.addLast(nums[i]);
        }
        int res[] = new int[nums.length - k + 1];
        res[0] = q.peekFirst();
        int temp = 1;
        for (int i = k, j = 0; i < nums.length; i++, j++) {
            if (nums[j] == q.peekFirst()) {//按滑动窗口去除
                q.pollFirst();
            }
            while (!q.isEmpty() && nums[i] > q.peekLast()) {
                q.pollLast();//只放最大的
            }
            q.addLast(nums[i]);
            res[temp++] = q.peekFirst();//最大永远在前面
        }
        return res;
    }
}

双端队列从左往右，那么左边为last，右边为first（想成汽车）

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""

class Solution {
    public String minWindow(String s, String t) {
        // 初始化 need 和 window 哈希表
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();

        // 统计 t 中每个字符的出现次数
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        // 初始化变量
        int temp = 0; // 记录窗口中满足 need 条件的字符个数
        int start = 0; // 记录最小子串的起始位置
        int len = Integer.MAX_VALUE; // 记录最小子串的长度
        String res = ""; // 最终结果
        int left = 0, right = 0; // 滑动窗口的左右边界

        // 开始滑动窗口
        while (right < s.length()) {
            char c = s.charAt(right); // 获取当前字符
            right++; // 扩大窗口

            // 如果当前字符是 t 中的字符，更新 window 哈希表
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);

                // 如果当前字符的出现次数满足 need 的条件，temp++
                if (window.get(c).equals(need.get(c))) {
                    temp++;
                }
            }

            // 当窗口满足条件时，尝试缩小窗口
            while (temp == need.size()) {
                // 更新最小子串的起始位置和长度
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }

                char d = s.charAt(left); // 获取左边界字符
                left++; // 缩小窗口

                // 如果左边界字符是 t 中的字符，更新 window 哈希表
                if (need.containsKey(d)) {
                    // 如果当前字符的出现次数不再满足 need 的条件，temp--
                    if (window.get(d).equals(need.get(d))) {
                        temp--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }

        // 返回结果
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}

数组

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length<1){
            return 0;
        }
        int res=nums[0],max=0;
        for(int num:nums){//上次能否大于0，为这次使用
            if(max<=0){
                max=num;
            }else{
                max=max+num;
            }
            res=Math.max(res,max);
        }
        return res;
    }
}

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间

class Solution {
    public int[][] merge(int[][] intervals) {
    if(intervals==null||intervals.length<2){
            return intervals;
    } 
    ArrayList<int[]>list1=new ArrayList<>();
    Arrays.sort(intervals, (e1, e2) -> Integer.compare(e1[0], e2[0]));
    for(int[] interval:intervals){
        if(list1.isEmpty()||interval[0]>list1.get(list1.size()-1)[1]){
            list1.add(interval);
        }else{
            list1.get(list1.size()-1)[1]=Math.max(list1.get(list1.size()-1)[1],interval[1]);
        }
    }
    return list1.toArray(new int[list1.size()][2]);    
    }
}

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数

class Solution {
    public void rotate(int[] nums, int k) {
        int len=nums.length;
        k=k%len;
        reverse(nums,0,len-1);
        reverse(nums,0,k-1);
        reverse(nums,k,len-1);
    }
    private void reverse(int[] nums, int i, int j) {
        while (i < j) {
            int temp = nums[i];
            nums[i++] = nums[j];
            nums[j--] = temp;
        }
    }
}

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 **不要使用除法，**且在 O(n) 时间复杂度内完成此题

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len=nums.length;
        int[]res=new int[len];
        int k=1;
        for(int i=0;i<len;i++){
            res[i]=k;
            k=k*nums[i];
        }
        k=1;
        for(int i=len-1;i>=0;i--){
            res[i]*=k;
            k=k*nums[i];
        }
        return res;
    }
}

矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer>res=new LinkedList<>();
        int l=0,r=matrix[0].length-1;
        int u=0,d=matrix.length-1;
        while(l<=r&&u<=d){
            for(int i=l;i<=r;i++){
                res.add(matrix[l][i]);
            }
            for(int i=l+1;i<=d;i++){
                res.add(matrix[i][r]);
            }
            if(u==d||l==r){
                break;
            }
            for(int i=r-1;i>=l;i--){
                res.add(matrix[d][i]);
            }
            for(int i=d-1;i>u;i--){
                res.add(matrix[i][l]);
            }
            u++;
            d--;
            l++;
            r--;
        }
        return res;
    }
}

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在** 原地** 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像

class Solution {
    public void rotate(int[][] matrix) {
        int n=matrix.length;
        for(int i=0;i<n;i++){
            for(int j=0;j<(n-i);j++){
                    int temp=matrix[i][j];
                    matrix[i][j]=matrix[n-j-1][n-i-1];
                    matrix[n-j-1][n-i-1]=temp;

            }
        }
        for(int i=0;i<n/2;i++){
            for(int j=0;j<n;j++){
                int temp=matrix[i][j];
                matrix[i][j]=matrix[n-1-i][j];
                matrix[n-1-i][j]=temp;
            }
        }
    }
}

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列

class Solution {
   public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
    int m = matrix.length, n = matrix[0].length;
    int row = 0, col = n - 1;
    while (row < m && col >= 0) {
        if (target == matrix[row][col]) return true;
        else if (target < matrix[row][col]) col--;
        else row++;
    }
    return false;
	}
}

链表

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1=headA,p2=headB;
        while(p1!=p2){
            if(p1!=null){
                p1=p1.next;
            }else{
                p1=headB;
            }
            if(p2!=null){
                p2=p2.next;
            }else{
                p2=headA;
            }
        }
        return p1;
    }
}

反转链表

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

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow=head,fast=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        if(fast!=null&&fast.next==null){//为奇数设置
            slow=slow.next;
        }
        ListNode flag=head;
        ListNode temp=serve(slow);
        while(temp!=null){
            if(temp.val!=flag.val){
                return false;
            }
            temp=temp.next;
            flag=flag.next;
        }
        return true;
    }
    public ListNode serve(ListNode head){//反转
        ListNode cur=head,pre=null;
        while(cur!=null){
            ListNode nex=cur.next;
            cur.next=pre;
            pre=cur;
            cur=nex;
        }
        return pre;
    }
}

给你一个链表的头节点 head ，判断链表中是否有环

public class Solution {
    public boolean hasCycle(ListNode head) {
    ListNode fast=head;
    ListNode slow=head;
    while(fast!=null&&fast.next!=null){
        fast=fast.next.next;
        slow=slow.next;
        if(fast==slow){
            return true;
        }
    }
    return false;  
    }
}

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null

public class Solution {
    public ListNode detectCycle(ListNode head) {
    ListNode fast=head,slow=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;
    fast=head;
    while(fast!=slow){
        slow=slow.next;
        fast=fast.next;
    }
    return fast;
    }
}

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode p1=list1;
        ListNode p2=list2;
        ListNode cur=new ListNode();
        ListNode res=cur;
        while(p1!=null&&p2!=null){
            if(p1.val<p2.val){
                res.next=p1;
                p1=p1.next;

            }else{
                res.next=p2;
                p2=p2.next;

            }
             res=res.next;
        }
        while(p1!=null){
            res.next=p1;
            p1=p1.next;
            res=res.next;
        }
        while(p2!=null){
            res.next=p2;
            p2=p2.next;
            res=res.next;
        }
        return cur.next;
    }
}

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {   
        if(head==null||n==0){
            return head;
        }
        ListNode dummy = new ListNode(0, head);//防止n刚好删去头结点
        ListNode fast=dummy;
        ListNode slow=dummy;
        while(fast!=null&&n-->0)
            fast=fast.next;
        if(n>0){
            return null;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return dummy.next;
    }
}

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode last=head;
        for(int i=0;i<k;i++){
            if(last==null){
                return head;
            }
            last=last.next;
        }
        ListNode t=res(head,last);
        ListNode temp=t;//反转后的位置逻辑和head其实一样
        for(int i=0;i<k-1;i++){
            temp=temp.next;
        }
       temp.next=reverseKGroup(last,k);
        return t;
    }
    public ListNode res(ListNode head,ListNode tail){
        if(head==null||head.next==null){
            return head;
        }
        ListNode cur=head,nex=head;
        ListNode pre=tail;
        while(nex!=tail){
            nex=nex.next;
            cur.next=pre;
            pre=cur;
            cur=nex;
        }
        return pre;
    }
}

Hot100#

哈希#

双指针#

子串#

数组#

矩阵#

链表#

Hot100

哈希

双指针

子串

数组

矩阵

链表