leetcode热题HOT100汇总——java题解已完结撒花

前言

为了学习本文捋顺的汇总 方便自己秋招刷题 仅作刷题笔记使用 感兴趣的小伙伴点一个赞吧

1. 两数之和

题解 请

2. 两数相加

用链表演示数字相加的过程

3.无重复字符的最长子串

hashMap中的方法

4. 寻找两个正序数组的中位数

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int total = nums1.length + nums2.length ;
        if(total % 2 == 0){
            int left = f(nums1, 0 ,nums2 ,0 , total / 2 );
             int right = f(nums1, 0 ,nums2 ,0 , total / 2 + 1 );
             return (left + right) / 2.0 ;
        }else{
                return f(nums1 , 0 , nums2 , 0 , total / 2 + 1);
        }
    }
    public int f(int[] nums1 , int i , int[] nums2 , int j , int k){
        //默认长度 第一个小
        if(nums1.length - i > nums2.length - j) return f(nums2 ,j ,nums1,i ,k);
        // 处理边界问题 如果第一个数组用完
        if(nums1.length == i) return nums2[j + k -1];
        if(k == 1) return Math.min(nums1[i] , nums2[j]);
       int si = Math.min(nums1.length,i + k /2) ;
      //int si = i + k / 2 ;
        //si如果不取最小的话  就会出现出界的问题  因为si可能为0 本身就短
        int sj = j + k - k /2 ;
        //也就是第1种情况  去掉第一个的前半段
        if(nums1[si-1] < nums2 [sj-1]) return f(nums1,si,nums2,j,k - (si - i));
       else return f(nums1,i,nums2,sj,k -(sj-j));
 
    }
}

5. 最长回文子串

l 和r 是左右边界 进行操作时候从i 向两边扩展 如果是奇数的话 所以这个时候 l-- r++ 然后当两个字符串字母相等的时候 还会进行一次l-- r++ 所以这时候长度就为 l -1 和 r+1 之间 所以长度为l - r - 1 ;

10. 正则表达式匹配

二刷：
把a*当作一个整体 也就是abcc abc* 这里面的c*是一个整体
当p[j] == ‘#' 时候 按照*可以表示几个字符来 区分 * 表示l零个字符 那就是f[i][j-2]

class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length() ;
        int m = p.length() ;
        s = " "+ s ;
        p = " " + p ;
        boolean[][] f = new boolean[n+10][m+10] ;
        f[0][0] = true ;
        for(int i = 0 ; i <= n ;i++){
            for(int j = 1 ; j <= m ;j++){//f[1][0]肯定是不行的 所以要从1开始
            //a*是一个整体  * 不能单独用 
                if(j + 1 <= m && p.charAt(j+1) == '*')continue ;
                if(p.charAt(j) != '*'){
                    boolean flag = s.charAt(i)== p.charAt(j) || p.charAt(j) == '.';
                    f[i][j] = (i != 0)&& f[i-1][j-1] && flag ;
                }else{
                     boolean flag = s.charAt(i)== p.charAt(j-1) || p.charAt(j-1) == '.';
                     f[i][j] = f[i][j-2] || (i != 0)&& f[i-1][j] && flag ;
                }
            }
        }
        return f[n][m];
    }
}

11. 盛最多水的容器

贪心加双指针
题解中给出了双指针为什么正确

15. 三数之和

这里面的是数组转换成列表的函数方法ans.add(Arrays.asList(nums[i],nums[j],nums[k]));
同时是试探的下一个数 所以用到的是k-1

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
     List<List<Integer>> ans = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        for(int i = 0 ; i < nums.length ; i++){
            if(i > 0 && nums[i] ==nums[i-1] ) continue ;
            for(int j = i+1 , k = nums.length -1 ; j< k ; j++){
                if( j > i + 1 && nums[j] == nums[j - 1])continue ;
                while(j < k - 1 && nums[j] + nums[j] + nums[k-1] >= 0){
                    k--;
                }
                if(nums[i]+nums[j]+nums[k] == 0){
                    ans.add(Arrays.asList(nums[i],nums[j],nums[k]));
                }
            }
        }
        return ans  ;
    }
}

17. 电话号码的字母组合

递归和迭代知道一种写法就好了 就是hashmap要提前写好 然后简单的dfs

19. 删除链表的倒数第 N 个结点

20. 有效的括号

巧妙的运用配对的符号 ASCII码数值相差不到2

21. 合并两个有序链表

22. 括号生成

23. 合并K个升序链表

31. 下一个排列

如： 231 -> 24531-> 换完序之后顺序排列变成 24135
找到非降序的那个数 然后再右边找到第一个比当前这个数大的数

32. 最长有效括号

栈中存放的是括号元素的下标
栈的用法 如果( 和空就加入栈 否则pop() 并且ans = i - s.peek()

33. 搜索旋转排序数组

二分其实是找不满足单调性的临界点 出来

class Solution {
    public int search(int[] nums, int target) {
        int l = 0 ;
        int r = nums.length - 1;
        while(l < r){
            int mid = l + r + 1 >> 1 ;
            if(nums[mid] >= nums[0]) l = mid ;
            else r = mid - 1 ;
        }
        //先二分出7的那个点
        if(target >= nums[0] ) l = 0;//赋值前l和r相等  都在最右边的
        else {
            l = r + 1 ;
            r = nums.length - 1;
        }
        while(l < r){
            int mid = l + r >> 1 ;
            if(nums[mid] >= target) r = mid ;
            else l = mid+1 ;
        }
        if(nums[r] == target) return r ;
        else return -1 ;
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置

39. 组合总和

dfs的模板 但是恢复现场的时候 是枚举了多少次 就恢复了多少次 因为每个元素使用的不止一次

42. 接雨水

46. 全排列

48. 旋转图像

旋转90°的意思就是沿对角线翻转 在左右翻转

49. 字母异位词分组

53. 最大子数组和

55. 跳跃游戏

56. 合并区间

注意点有点小多 看题解的时候别忘记

62. 不同路径

. 最小路径和

70. 爬楼梯

72. 编辑距离

75. 颜色分类

76. 最小覆盖子串

字符串哈希

78. 子集

分为选和不选两部分

79. 单词搜索

84. 柱状图中最大的矩形

单调栈模板

85. 最大矩形

94. 二叉树的中序遍历

96. 不同的二叉搜索树

98. 验证二叉搜索树

101. 对称二叉树

102. 二叉树的层序遍历

104. 二叉树的最大深度

105. 从前序与中序遍历序列构造二叉树

114. 二叉树展开为链表

121. 买卖股票的最佳时机

124. 二叉树中的最大路径和

128. 最长连续序列

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

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

题解详解
思路（hashset）：

将所有数字放入hashset，遍历hashset中的元素

向后枚举相邻的数字（即不断加一），判断后面一个数字是否在哈希表中

由于要求时间复杂度为O(n)，因此要对上述过程进行优化：

为了避免重复枚举序列，因此只对序列的起始数字向后枚举，因此需要判断一下当前数是否是序列的起始数

如何判断当前数x是不是某一个序列的起点呢？
只需要判断x-1是否存在即可，若x-1存在，那么说明这个数前面还有连续的数，即这个数不是起点。

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for(int a : nums)s.add(a);
        int res = 0 ;
        for(int i = 0 ; i < nums.length ; i++ ){
            int x = nums[i] ;
            if(!s.contains(x -1 )){
                int y = x;
                while(s.contains(y+1)) y++ ;
                res = Math.max(res , y - x + 1);
            }
        }
        return res;
    }
}

136. 只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
题解详解

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0 ;
        for(int a : nums) res ^= a ;
        return res ;
    }
}

139. 单词拆分

141. 环形链表

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

142. 环形链表 II

146. LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

题解

哈希表 + 双向链表

最近最少使用：表示在特定的几个点中，新进来的点会替代这几个点最前使用过的点

• 1、若哈希表中存在 key 值，则对 key 的映射值进行修改，并把 key 对应的 Node 放在双向链表头部分，即进行删除当前结构体 并 在队头加入结构体的操作
• 2、若哈希表中不存在 key 值，若双向链表存的个数已经达到n（给定的个数），则将最尾部的 Node 删除，在队头添加新的结构体，若双向链表存的个数已经达不到n（给定的个数），则在队头添加新的结构体

class LRUCache {
    static Node head, tail;
    static HashMap<Integer, Node> map = new HashMap<Integer,Node>();
    static int n;
    static void remove(Node p){
        p.right.left = p.left ;
        p.left.right = p.right;

    }
    static void insert(Node p){
        p.right = head.right ;
        head.right.left = p ;
        p.left = head ;
        head.right = p ;
    }
    public LRUCache(int capacity) {
        n = capacity ;
        head = new Node(-1 , -1 );
        tail = new Node(-1 , -1 );
        head.right = tail ;
        tail.left = head ;
        map.clear() ;
    }
    
    public int get(int key) {
        if(!map.containsKey(key))return -1 ;
        Node p = map.get(key);
        remove(p);
        insert(p);
        return p.val;
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)){
            Node p = map.get(key);
            p.val = value ;
            remove(p);
            insert(p);
        }else{
            if(map.size() == n){
                Node p = tail.left ;
                remove(p);
                map.remove(p.key);
            }
            Node t = new Node(key , value);
            insert(t);
            map.put(key , t);
        }
    }
   
    
}
class Node{
    int key , val ;
    Node left , right ;
    Node(int key , int val){
        this.key = key ;
        this.val = val ;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

148. 排序链表

152. 乘积最大子数组

155. 最小栈

160. 相交链表

169. 多数元素

198. 打家劫舍

200. 岛屿数量

题解详解

206. 反转链表

207. 课程表

208. 实现 Trie (前缀树)

215. 数组中的第K个最大元素

221. 最大正方形

226. 翻转二叉树

234. 回文链表

236. 二叉树的最近公共祖先

238. 除自身以外数组的乘积

239. 滑动窗口最大值

240. 搜索二维矩阵 II

279. 完全平方数

283. 移动零

287. 寻找重复数

297. 二叉树的序列化与反序列化

300. 最长递增子序列

301. 删除无效的括号

309. 最佳买卖股票时机含冷冻期

312. 戳气球

322. 零钱兑换

337. 打家劫舍 III

338. 比特位计数

347. 前 K 个高频元素

394. 字符串解码

399. 除法求值

406. 根据身高重建队列

416. 分割等和子集

437. 路径总和 III

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

448. 找到所有数组中消失的数字

461. 汉明距离

494. 目标和

538. 把二叉搜索树转换为累加树

3. 二叉树的直径

560. 和为 K 的子数组

581. 最短无序连续子数组

617. 合并二叉树

621. 任务调度器

7. 回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”

题解详解

当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。

当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况

• 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
• 情况二：下标i 与 j相差为1，例如aa，也是回文子串
• 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int res = 0 ;
        boolean[][] f = new boolean[n+1][n+1];
        for(int i = n-1 ; i >= 0 ; i--){
            for(int j = i ; j < n ; j++){
                if(s.charAt(i) == s.charAt(j)){
                    if(j - i <= 1){
                        f[i][j] =true;
                        res++;
                    }else if(f[i+1][j-1]){
                        res++;
                        f[i][j] = true;
                    }

                }
            }
        }
        return res;
    }
}

739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

题解详解

class Solution {
    public int[] dailyTemperatures(int[] t ) {
        //板子题  单调栈的应用：求左边第一个比它小的数
            int n = t.length;
            int[] res = new int[n];
            Stack<Integer> s  = new Stack<>();
            for(int i = n - 1; i >= 0  ; i --){
                while(!s.isEmpty() && t[s.peek()] <= t[i])s.pop();
                if(!s.isEmpty()) res[i] = s.peek() - i ;//几天后
                s.push(i);
            }
            return res;
    }
}