leetcode hot100 链接
1.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个
整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
暴力
class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[0];
}
}
哈希
哈希解法原理： 相当于每个路过的人，都记下来他想找谁。后面遇到的时候，那个人看到记录里面有人想找他，这时就可以返回了。
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
}
2.两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
提示：
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零
模拟
思路：这种思路可以想想为两个链表同时遍历，取出每一个值进行相加，同时这个值可能还要进一位，这就导致了我们需要两个虚拟链表，一个链表用于计算，另一个链表指向这个链表的首地址，为了return才使用第二个链表，同时，对于每位的运算，需要一个中间值d代表的进位设置，循环遍历；整除10，大于1代表需要进位，链表要扩展。
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = null, tail = null;
int carry = 0;
while (l1 != null || l2 != null) {
int n1 = l1 != null ? l1.val : 0;
int n2 = l2 != null ? l2.val : 0;
int sum = n1 + n2 + carry;
if (head == null) {
head = tail = new ListNode(sum % 10);
} else {
tail.next = new ListNode(sum % 10);
tail = tail.next;
}
carry = sum / 10;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
if (carry > 0) {
tail.next = new ListNode(carry);
}
return head;
}
}
维护进位变量t
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(-1), pre = dummyHead;
int t = 0;
while (l1 != null || l2 != null || t != 0) {
if (l1 != null) {
t += l1.val;
l1 = l1.next;
}
if (l2 != null) {
t += l2.val;
l2 = l2.next;
}
pre.next = new ListNode(t % 10);
pre = pre.next;
t /= 10;
}
return dummyHead.next;
}
}
20. 有效的括号
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。
栈
class Solution {
public boolean isValid(String s) {
int n = s.length();
if(n % 2 == 1){
return false;
}
Map<Character, Character> map = new HashMap<Character, Character>() {{
// 将 })] 作为key
put('}', '{');
put(']', '[');
put(')', '(');
}};
// 新建一个栈
LinkedList<Character> stack = new LinkedList<>();
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
// 如果c是 })], 则判断， 否则说明是({[ , 直接入栈
if(map.containsKey(c)){
// stack.peek() 获取栈顶元素
if(stack.isEmpty() || stack.peek() != map.get(c)){
return false;
}
// 将栈顶移除(先进后出，栈顶是最接近 c 的左括号)
stack.pop();
}else{
// 说明c是({[ , 直接入栈
stack.push(c);
}
}
return stack.isEmpty();
}
}
巧妙低效方法
class Solution {
public boolean isValid(String s) {
int length = s.length() / 2;
if(length % 2 == 1){
return false;
}
//最多循环长度的一般，把如下规则的慢慢消除
for (int i = 0; i < length; i++) {
s = s.replace("()", "").replace("{}", "").replace("[]", "");
}
return s.length() == 0;
}
}
21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
递归
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}。
迭代
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
prev.next = l1 == null ? l2 : l1;
return prehead.next;
}
}
141. 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos
来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
提示：
链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。
进阶：你能用 O(1)（即，常量）内存解决此问题吗？
哈希
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> seen = new HashSet<ListNode>();
while (head != null) {
if (!seen.add(head)) {
return true;
}
head = head.next;
}
return false;
}
}
快慢指针
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}
160. 相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
提示：
listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]
进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
哈希
双指针
11.盛最多水的容器
15.三数之和
17.电话号码的字母组合
19.删除链表的倒数第N个结点
20.有效的括号
21.合并两个有序链表
22.括号生成
23.合并K个升序链表
31.下一个排列
32.最长有效括号
33.搜索旋转排序数组
34.在排序数组中查找元素的第——…
39.组合总和
42.接雨水
46.全排列
48.旋转图像
49.字母异位词分组
53.最大子数组和
55.跳跃游戏
56.合并区间
62.不同路径
64.最小路径和
70.爬楼梯
72.编辑距离
75.颜色分类
76.最小覆盖子串
78.子集
79.单词搜索
84.柱状图中最大的矩形
85.最大矩形
94.二叉树的中序遍历
96.不同的二叉搜索树
98.验证二叉搜索树
101.对称二叉树
102.二叉树的层序遍历
104.二叉树的最大深度
105.从前序与中序遍历序列构造二…
114.二叉树展开为链表
121.买卖股票的最佳时机
124.二叉树中的最大路径和
128.最长连续序列
136.只出现—次的数字
139.单词拆分
141.环形链表
160.相交链表
169.多数元素
198.打家劫舍
200.岛屿数量
206.反转链表
207.课程表
208.实现 Trie (前缀树)
215.数组中的第K个最大元素
221.最大正方形
226.翻转二叉树
234.回文链表
236.二叉树的最近公共祖先
238.除自身以外数组的乘积
239.滑动窗口最大值
240.搜索二维矩阵l
253.会议室ⅡPlus
279.完全平方数
283.移动零
287.寻找重复数
297.二叉树的序列化与反序列化
300.最长递增子序列
301.删除无效的括号
309.最佳买卖股票时机含冷冻期
312.戳气球
322.零钱兑换
337.打家劫舍Ⅲ
338.比特位计数
347.前K个高频元素
394.亨符串解码
399.除法求值
406.根据身高重建队列
416.分割等和子集
437.路径总和Ⅲ
438.找到字符串中所有字母异位词
448.找到所有数组中消失的数字
461.汉明距离
494.目标和
538.把二叉搜索树转换为累加树
543.二叉树的直径
560.和为K的子数组
581.最短无序连续子数组
617.合并二叉树
621.任务调度器
647.回文子串
739.每日温度