百题通关(上)[废弃]
1.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1:
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。java
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int choose = nums[i];
int diff = target - choose;
if(map.containsKey(diff)){
return new int[]{i, map.get(diff)};
}
// 否则不包含目标值
map.put(choose, i);
}
// 没从for里return说明就没有
return null;
}2.两数之和
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
java
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode root = new ListNode();
ListNdoe curr = root;
int carry = 0;
// 循环中已经包括了节点都空但是还有进位的情况
while (l1 != null || l2 != null || carry != 0) {
int currV = (l1 == null ? 0 : l1.val)
+ (l2 == null ? 0 : l2.val)
+ carry;
// 10进制的进位这样做更好
if(currV > 9){
currV -= 10;
carry = 1;
}else{
carry = 0;
}
curr.next = new ListNdoe(currV);
curr = curr.next;
// 移动l1和l2的逻辑
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
return root.next;
}3.无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。java
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> keyIndex = new HashMap<>();
// 这里用这个map的意义，更重要的体现在，当遇到重复的元素的时候，下一次窗口的移动就直接能跳到导致重复的元素的后一个位置
// 而且找到这个是用O(1)的速度，并不需要多次循环
int length = s.length();
int maxLength = 0; // 中间结果
int lastIndex = 0; // 其实就是每一回找结果的时候的开头
for (int i = 0; i < length; i++) {
final char c = s.charAt(i);
if (keyIndex.containsKey(c)) {
lastIndex = Math.max(lastIndex, keyIndex.get(c) + 1); // keyIndex.get(c) + 1 导致重复的这个元素的下一个位置
}
keyIndex.put(c, i);
int currLength = i - lastIndex + 1; // 记录当前长度
maxLength = Math.max(maxLength, currLength);
}
return maxLength;
}体会:
这个map存的就是某个字符 最近一次 出现的位置, 当指针指向的字符map中已经存在,
从map中取出 该字符上次出现的下标 + 1, 此时就是一个新的状态
11.盛水最多的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的 最大水量。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。java
// 初始化： 双指针 i , j 分列水槽左右两端；
// 循环收窄： 直至双指针相遇时跳出；
// 选定两板高度中的短板，向中间收窄一格；
// 当你选择收窄时肯定是优先换更短的，因为短的可以换成大的或者小的
public int maxArea(int[] height) {
int res = 0;
int left = 0;
int right = height.length - 1;
while (left < right) {
int leftHeight = height[left];
int rightHeight = height[right];
res = Math.max(res, (right - left) * Math.min(leftHeight, rightHeight));
// 马上要进行下一次计算，但是下一次计算可以
if (leftHeight < rightHeight) {
while (left < right && height[left] <= leftHeight)
left++;
} else {
while (left < right && height[right] <= rightHeight)
right--;
}
}
return res;
}15.三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
java
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> listNest = new ArrayList<>();
if (nums.length < 3) {
// 直接返回空
return listNest;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
Integer num1 = nums[i];
if (num1 > 0) {
// 因为是有序的，当nums[1]为正数时，其他两个数不可能相加是负数
break;
}
if (i > 0 && nums[i] == nums[i - 1]) {
// 避免重复
continue;
}
Integer target = -num1;
// 两个指针分别知道i的后一位和列表的最后一位
int front = i + 1;
int end = nums.length - 1;
while (front < end) {
int sumOfTwo = nums[front] + nums[end];
if (sumOfTwo == target) {
listNest.add(Arrays.asList(nums[i], nums[front], nums[end]));
front++;
end--;
// 这里需要做一个防重复的处理
while (front < end && nums[front] == nums[front - 1]) {
// 相同的数值，第一个指针从左到右前进一步
front++;
}
while (front < end && nums[end] == nums[end + 1]) {
// 相同的数值，第一个指针从右到左前进一步
end--;
}
} else if (sumOfTwo > target) {
end--;
} else {
front++;
}
}
}
return listNest;
}17.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
java
// 数字键与拼音的对应集
final String[] m = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
List<String> res = new ArrayList<>();
// 存储中间结果
StringBuilder line = new StringBuilder();
public List<String> letterCombinations(String digits) {
if (digits.length() == 0) {
return new ArrayList<>();
}
process(digits, 0);
return res;
}
/**
* @param digits 数字串
* @param index 处理到哪一个数字
*/
private void process(String digits, int index) {
if (index == digits.length()) {
// 表示当前已经处理完了所以数字组合
res.add(line.toString());
return;
}
// 当前index处表示的数字
int digitsIndex = digits.charAt(index) - '0';
char[] letter = m[digitsIndex].toCharArray();
for (int i = 0; i < letter.length; i++) {
line.append(letter[i]);
process(digits, index + 1);
line.deleteCharAt(line.length() - 1);
}
}19.删除链表倒数第N个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
java
/**
* 相当于比着一把标尺，快指针和慢指针之间相隔n+1，这样快指针移动到最后一个节点的时候，慢指针就到了待删除节点的前一个
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode root = new ListNode();
root.next = head;
// 其实就是为了n，新建一个空的头结点指向head，并且让head指向这个新的头结点，这样1
head = root;
ListNode res = head;
while (head != null) {
if (n >= 0) {
n--;
} else {
// 当快指针移动了n次以后，慢指针再开始移动
res = res.next;
}
head = head.next;
}
// 删除操作
res.next = res.next.next;
return root.next;
}20.有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
java
public boolean isValid(String s) {
if (s.length() % 2 != 0) {
// 长度是奇数
return false;
}
char[] charArray = s.toCharArray();
// 也可以直接用最基础的Stack
Deque<Character> stack = new LinkedList<>();
Character t;
for (char c : charArray) {
// 左括号就放对应的右括号,这样就可以直接用相等比较了
if (c == '{') {
stack.addFirst('}');
} else if (c == '(') {
stack.addFirst(')');
} else if (c == '[') {
stack.addFirst(']');
} else {
if (stack.isEmpty()) {
return false;
}
// 这里直接出栈,省的后面比较还得出
t = stack.pollFirst();
// 就可以直接用字符是否相等来比较了
if (t != c) {
return false;
}
}
}
return stack.isEmpty();
}21.合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
java
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
// 根节点取决于哪个更小
ListNode root = list1.val < list2.val ? list1 : list2;
ListNode curr = root;
if (list1.val < list2.val) {
list1 = list1.next;
} else {
list2 = list2.next;
}
// 处理完两条链表的的起始位置
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
curr.next = list1;
list1 = list1.next;
} else {
curr.next = list2;
list2 = list2.next;
}
curr = curr.next;
}
// 这时还剩下一条链表,剩下谁就接谁
if (list1 == null) {
curr.next = list2;
}
if (list2 == null) {
curr.next = list1;
}
return root;
}22.括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]java
List<String> res = new ArrayList<>();
/**
* 根据括号的匹配原则,当左右数量相同时,只能添加左括号
* 当左括号小于n时,可以添加左括号
* 当右括号小于n时,可以添加右括号
* 左右括号的数量都必须得小于n
*/
public List<String> generateParenthesis(int n) {
char[] line = new char[n * 2];
process(line, 0, 0, 0, n);
return res;
}
public void process(char[] line, int index, int leftCount, int rightCount, int n){
if (index == n * 2) {
// 说明左右括号的数量已经达到了n对
res.add(new String(line));
return;
}
// 这种情况必须写在最上面, 这样下面就不会出错
if (leftCount == rightCount) {
// 如果左右括号数相等,则此时只能加入左括号
line[index] = '(';
process(line, index + 1, leftCount + 1, rightCount, n);
return;
}
if (leftCount < n) {
line[index] = '(';
process(line, index + 1, leftCount + 1, rightCount, n);
}
if (rightCount < n) {
line[index] = ')';
process(line, index + 1, leftCount, rightCount + 1, n);
}
}24.两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
java
public ListNode swapPairs(ListNode head)
ListNode root = new ListNode(-1, head);
ListNode cur = root;
// 下面的逻辑就是一次动两步，然后期间交换相邻两节点
while (cur.next != null && cur.next.next != null) {
ListNode next = cur.next;
ListNode nextNext = cur.next.next;
// 对于每次循环，指定这段链表的头结点是后一个节点
cur.next = nextNext;
// 为了链接原有的结构
next.next = nextNext.next;
// 这段链表的新头节点指向新靠后的节点
nextNext.next = next;
// 移动两步（因为是交换，next的意义实际是nextNext的意义）
// 也就是下一次逻辑的头节点
cur = next;
}
// 这就是做新节点的好处，即可以操作方便，还可以知道操作完以后真正的头结点是谁
return root.next;
}25.K个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]java
/*
k个一组反转
先拿到这K个长度的链表的尾节点，记录他的下一个节点，用于反转了这K个节点以后将新的头结点链接
*/
public ListNode reverseKGroup(ListNode head, int k) {
ListNode root = new ListNode(-1, head);
ListNode pre = root;
while (true) {
ListNode t = nextTail(pre, k);
if (t == null) {
break;
}
ListNode next = t.next;
ListNode tail = pre.next;
t.next = null;
ListNode newHead = reverse(pre.next);
pre.next = newHead;
tail.next = next;
pre = tail;
}
return root.next;
}
/*
返回下一段K个长度的子链表的尾节点，如果不够K个，就返回null
*/
public ListNode nextTail(ListNode head, int k) {
while (k > 0) {
if (head != null) {
k--;
head = head.next;
} else {
return null;
}
}
return head;
}
/*
反转链表
*/
public ListNode reverse(ListNode head) {
ListNode lastNode = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = lastNode;
lastNode = cur;
cur = next;
}
return lastNode;
}33. 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4java
// 其实就是判断该去哪一边
public int search(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
while (l <= r) {
int m = l + ((r - l) >> 1);
if (nums[m] == target) {
return m;
}
if (nums[m] < nums[r]) {
// 说明现在是在右边的那一侧
if (target > nums[m] && target <= nums[r]) {
// 说明就在右边,继续就可以了
l = m + 1;
} else {
// 说明不在右边在左边
r = m - 1;
}
} else {
// 说明现在在左边一侧
if (target < nums[m] && target >= nums[l]) {
// 说明就在左边,继续就可以了
r = m - 1;
} else {
// 说明不在左边在右边
l = m + 1;
}
}
}
// 没在while里返回,说明没找到
return -1;
}34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]java
public int[] searchRange(int[] nums, int target) {
if (nums.length == 0) {
return new int[]{-1, -1};
}
int l = 0;
int r = nums.length - 1;
int m = 0;
int res = -1;
while (l <= r) {
m = l + ((r - l) >> 1);
if (nums[m] >= target) {
res = m;
r = m - 1;
} else if (nums[m] < target) {
l = m + 1;
}
}
int left = res;
res = -1;
l = 0;
r = nums.length - 1;
m = 0;
while (l <= r) {
m = l + ((r - l) >> 1);
if (nums[m] <= target) {
res = m;
l = m + 1;
} else if (nums[m] > target) {
r = m - 1;
}
}
int right = res;
if (left <= right && left != -1 && right != -1 && nums[left] == target && nums[right] == target) {
return new int[]{left, right};
}
return new int[]{-1, -1};
}35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2java
public int searchInsert(int[] nums, int target) {
// 二分搜索 秒了
int l = 0;
int r = nums.length - 1;
int m = 0;
while (l <= r) {
m = l + ((r - l) >> 1);
if (target == nums[m]) {
return m;
} else if (target > nums[m]) {
l = m + 1;
} else if (target < nums[m]) {
r = m - 1;
}
}
return l;
}39. 组合综合
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。java
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
// 先进行排序
Arrays.sort(candidates);
backtracking(res, new ArrayList<>(), candidates, target, 0, 0);
return res;
}
public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target,
int sum, int idx) {
// 找到了数字和为 target 的组合
if (sum == target) {
res.add(new ArrayList<>(path));
return;
}
for (int i = idx; i < candidates.length; i++) {
// 如果 sum + candidates[i] > target 就终止遍历
if (sum + candidates[i] > target) break;
path.add(candidates[i]);
backtracking(res, path, candidates, target, sum + candidates[i], i);
// 回溯，移除路径 path 最后一个元素
path.remove(path.size() - 1);
}
}40. 组合总和2
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]java
List<List<Integer>> res = new ArrayList<>();
List<Integer> line = new LinkedList<>();
int[] used;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
// 首先要对整个数组做一个排序,目的是让相等的元素放在一起,剪枝也好操作
Arrays.sort(candidates);
used = new int[candidates.length];
// 表示对应每个位置是否使用过
backtracking(candidates, target, 0, 0);
return res;
}
private void backtracking(int[] candidates, int target, int sum, int startIndex) {
if (sum == target) {
// 说明已经找到了,可以放倒结果集中
res.add(new ArrayList<>(line));
return;
}
// 说明当前sum还不满足
for (int i = startIndex; i < candidates.length; i++) {
if (sum + candidates[i] > target) {
// 说明再往下递归也不会找到相等的情况了
return;
}
// 剪枝,在同一层上,表示对应于结果的同一位置,如果重复,且如果前一个元素用过,那就说明这次循环是没必要的
// 因为前一次在更深的递归中已经包含了本次的递归,同时, 如果前一个元素没用过,那相等的话这个元素肯定也用不上
if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == 0) {
// 注意这里是continue不是return,表示的是当前这个元素不用理会了,而不是可以直接返回这一层了
// 这样就把这一层的处理结果都返回去了,但实际还没有处理完
continue;
}
used[i] = 1;
line.add(candidates[i]);
backtracking(candidates, target, sum + candidates[i], i + 1);
used[i] = 0;
line.remove(line.size() - 1);
}
}41. 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。java
public int firstMissingPositive(int[] nums) {
/**
* 非常妙的写法，即做标记
* 首先呢，将所有非正数设为nums.length+1，不让他们影响标记
* 这时所有数都是正数，把小于等于nums.length的数在对应位置上做标记
* 遵循什么原理呢？
* 数组nums上，满足nums[i]=i+1，即nums[i-1]=i
* 所以如何判断nums[i]已经出现了？ ===> 把nums[nums[i] - 1]设置为相反数
* 但是设置相反数的过程修改了数组，所以每次都应该取出绝对值
*/
int n = nums.length;
for (int i = 0; i < n; i++) {
if (nums[i] <= 0) {
nums[i] = n + 1;
}
}
// 全变成了正数
for (int i = 0; i < n; i++) {
int num = Math.abs(nums[i]);
if (num <= n) {
nums[num - 1] = -Math.abs(nums[num - 1]);
}
}
// 只有没做标记的是正数，且对应下标就是（缺失的第一个正数-1）
for (int i = 0; i < n; i++) {
if (nums[i] > 0) {
return i + 1;
}
}
// 如果全做标记了，那就说明原数组缺n+1
return n + 1;
}42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。java
public int trap(int[] height) {
// 求每一列上面积攒多少水，动态规划，每一列对应两个指标，左边最高的高度以及右边最高的高度
// 然后根据左右两端最高高度的最小值，去和当前列比较，就能知道当前列上面有没有水
// 如果那个最小值比当前列还小，说明当前列不可能积水；否则会积水，而且积水量是最小值-当前列高度
int sum = 0;
int[] max_left = new int[height.length];
int[] max_right = new int[height.length];
for (int i = 1; i < height.length - 1; i++) {
max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
}
for (int i = height.length - 2; i >= 0; i--) {
max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
}
for (int i = 1; i < height.length - 1; i++) {
int min = Math.min(max_left[i], max_right[i]);
if (min > height[i]) {
sum = sum + (min - height[i]);
}
}
return sum;
}45. 跳跃游戏2
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。java
public static int jump(int[] nums) {
if (nums.length == 1) {
return 0;
}
int count = 0, i = 0;
int maxDis = 0;
while (i < nums.length) {
// 同时maxDis也是能达到的最远距离的下标
if (maxDis >= nums.length - 1) {
break;
}
maxDis = maxDis(nums, i, maxDis);
i++;
count++;
}
return count;
}
// 获得从所有可选起点起步能跳到的最远的下标
public static int maxDis(int[] nums, int left, int right) {
int maxDis = nums[left] + left;
for (int i = left + 1; i <= right; i++) {
if (maxDis < nums[i] + i) {
maxDis = nums[i] + i;
}
}
return maxDis;
}46. 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]java
List<List<Integer>> res = new ArrayList<>();
List<Integer> line = new LinkedList<>();
public List<List<Integer>> permute(int[] nums) {
// 将每个位置的使用情况记录下来,默认是false
boolean[] used = new boolean[nums.length];
Arrays.fill(used, false);
backtracking(nums, used);
return res;
}
private void backtracking(int[] nums, boolean[] used) {
// 当line里面收集的数量达到nums.length就是收集结果的时候
if (line.size() == nums.length) {
res.add(new ArrayList<>(line));
return;
}
for (int i = 0; i < used.length; i++) {
if (!used[i]) {
line.add(nums[i]);
used[i] = true;
backtracking(nums, used);
line.remove(line.size() - 1);
used[i] = false;
}
}
}47. 全排列2
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]java
//存放结果
List<List<Integer>> result = new ArrayList<>();
//暂存结果
List<Integer> path = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
boolean[] used = new boolean[nums.length];
Arrays.fill(used, false);
Arrays.sort(nums);
backTrack(nums, used);
return result;
}
private void backTrack(int[] nums, boolean[] used) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
// used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
// used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
// 如果同⼀树层nums[i - 1]使⽤过则直接跳过
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
//如果同⼀树⽀nums[i]没使⽤过开始处理
if (used[i] == false) {
used[i] = true;
path.add(nums[i]);
backTrack(nums, used);
path.remove(path.size() - 1);
used[i] = false;//回溯
}
}
}48. 旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]java
public void rotate(int[][] matrix) {
int n = matrix.length;
// 水平翻转
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 - i - 1][j];
matrix[n - i - 1][j] = temp;
}
}
// 主对角线翻转
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}49. 字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]java
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for(String str : strs){
char[] array = str.toCharArray();
Arrays.sort(array);
String key = new String(array);
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
// 添加完以后修改
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}51. N皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。java
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
char[][] chessboard = new char[n][n];
for (char[] c : chessboard) {
Arrays.fill(c, '.');
}
backTrack(n, 0, chessboard);
return res;
}
public void backTrack(int n, int row, char[][] chessboard) {
if (row == n) {
List<String> collect = Arrays.stream(chessboard)
.map(chars -> String.copyValueOf(chars))
.collect(Collectors.toList());
res.add(collect);
return;
}
for (int col = 0; col < n; ++col) {
if (isValid(row, col, n, chessboard)) {
chessboard[row][col] = 'Q';
backTrack(n, row + 1, chessboard);
chessboard[row][col] = '.';
}
}
}
public boolean isValid(int row, int col, int n, char[][] chessboard) {
// 检查列
// 相当于剪枝
for (int i = 0; i < row; ++i) {
if (chessboard[i][col] == 'Q') {
return false;
}
}
// 检查45度对角线
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
// 检查135度对角线
for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
return true;
}53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。java
public int maxSubArray(int[] nums) {
/**
* 贪心策略: 只要连续和是正数,他就有使得当前值增大的可能;如果连续和是负数,那就果断抛弃,重新找
* 对于当前元素
* 如果此前的最大值是>0的，那么当前元素与之相加一定>当前元素
* 如果此前的最大值是<0的，那么当前元素与之相加一定<当前元素
* 只用一次循环，过程中res是不断变化的，最后是记录其中最大的值
* 以[-2,1,-3,4,-1,2,1,-5,4]为例子
* res的中间结果：-2，1，-2，4，3，5，6，1，5
* 所以最大值就是6，所以说白了，其实就是对于每个下标，都记录着当前的最大值
*/
int sum = 0;
int res = Integer.MIN_VALUE;
for (int num : nums) {
// 只要连续和是正数,他就有使得当前值增大的可能;如果连续和是负数,那就果断抛弃,重新找
sum = sum > 0 ? sum + num : num;
res = Math.max(res, sum);
}
return res;
}54. 螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]java
// 判断的边界条件为结果集的大小，大大简化了判断过程ans.size() < size
public List<Integer> spiralOrder(int[][] matrix) {
int col = matrix[0].length;
int row = matrix.length;
int size = col * row;
final List<Integer> ans = new ArrayList<>();
int step = 0;
while (ans.size() < size) {
process(matrix, step++, ans);
}
return ans;
}
/**
* 处理每一圈
*
* @param matrix 输入数组
* @param step 圈数，从外到内
* @param ans 结果集
*/
private void process(int[][] matrix, int step, List<Integer> ans) {
int m = matrix.length;
int n = matrix[0].length;
int top = step;
int bottom = m - step - 1;
int left = step;
int right = n - step - 1;
// 上
for (int i = left; i <= right && ans.size() < n * m; i++) {
ans.add(matrix[top][i]);
}
// 右
for (int i = top + 1; i <= bottom && ans.size() < n * m; i++) {
ans.add(matrix[i][right]);
}
// 下
for (int i = right - 1; i >= left && ans.size() < n * m; i--) {
ans.add(matrix[bottom][i]);
}
// 左
for (int i = bottom - 1; i > top && ans.size() < n * m; i--) {
ans.add(matrix[i][left]);
}
}55. 跳跃游戏
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。分治
java
public boolean canJump(int[] nums) {
// 如果只有一个元素，那就是在终点
if(nums.length == 1){
return true;
}
// 从倒数第二个元素往前给压力,倒数第二个到最后一个只需要跳一步
// 如果可行的话，那么现在就必须让倒数第三个元素能跳到倒数第二个元素
// 如果不可行，也就是从倒数第二个跳不到最后一个，那就得让倒数第三个跳到最后一个，后面的重复这样的逻辑
// 所以这里的step运行中表示从当前位置跳到最后一个位置最少得跳多远
// 只要能跳到就可以到最后一个位置，不行的话就得交给当前位置的前一个，所以step++
// 而只要能跳到step就保证1就行，因为只需要满足当前位置的前一个可以跳1的距离就行
// 而且step=1，也是当前位置能跳到下一个位置的证明，如果到了最开头的一个元素也是这样，那就成功了
int step = 1;
for(int i = nums.length - 2; i >= 0; i--){
if(nums[i] >= step){
step = 1;
}else {
step++;
}
}
return step == 1;
}贪心
java
/**
* 贪心
* 只考虑覆盖面,不关心跳到哪儿跳了几步
*/
public boolean canJump(int[] nums) {
// 如果只有一个元素，那就是在终点
if (nums.length == 1) {
return true;
}
int cover = 0;
// i <= cover 就是用来限制能跳到的最远地方
for (int i = 0; i <= cover; i++) {
// i + nums[i] 表示从当前位置最多可以跳到什么位置
cover = Math.max(cover, i + nums[i]);
if (cover >= nums.length - 1) {
return true;
}
}
return false;
}56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].java
public int[][] merge(int[][] intervals) {
// 对输入数组按照左区间升序排序，这样就只要看后一个区间的左区间与前一个区间的右区间是怎样的关系
// 可能是包含，也可能不包含，不包含的情况就是新的结果了
Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
// Comparator.comparingInt, 该方法传入一个int类型，返回一个基于这个int类型值的比较器Comparator
int l = intervals[0][0];
int r = intervals[0][1];
List<int[]> resList = new ArrayList<>();
for (int i = 1; i < intervals.length; i++) {
// 记录当前元素的左边界和有边界
int curL = intervals[i][0];
int curR = intervals[i][1];
if (curL <= r) {
// 说明可以合并区间,尝试更新右边界
r = Math.max(r, curR);
} else {
// 说明不能合并，新的结果
resList.add(new int[]{l, r});
l = curL;
r = curR;
}
}
// 因为遍历到最后一个元素的时候，如果能合并，更新右边界后for循环就结束了
// 如果不能合并，也只是把前一个结果加到结果集，更新了最新的左边界和右边界，没有把他加进来
// 综上所述，最后一个结果并没有加进来
resList.add(new int[]{l, r});
int[][] res = new int[resList.size()][];
return resList.toArray(res);
}62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28java
/**
* 等同于二维爬楼梯
* dp[i][j]的含义是从(0,0)出发到(i,j)有多少种不同路径
* 在i和j满足条件的情况下,dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
*/
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
//初始化,首行和首列都是1
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
return dp[m - 1][n - 1];
}63. 不同路径2
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右java
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
//如果在起点或终点出现了障碍，直接返回0
if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
return 0;
}
//初始化首行和首列
for (int i = 0; i < m; i++) {
if (obstacleGrid[i][0] == 1) {
break;
}
dp[i][0] = 1;
}
for (int i = 0; i < n; i++) {
if (obstacleGrid[0][i] == 1) {
break;
}
dp[0][i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = obstacleGrid[i][j] == 0 ? dp[i][j - 1] + dp[i - 1][j] : 0;
}
}
return dp[m - 1][n - 1];
}70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶可以优化, 不需要设定dp数组
java
/**
* 斐波那契数列的变种
* 要记住是 多少种不同的方法可以爬到楼顶
* 而不是 爬到楼顶多少步
* 因为每次能跳1或者2步,所以到楼顶就要看到了倒数第二个和倒数第三个楼梯各有多少方法之和
* dp[i] = dp[i - 1] + dp[i - 2]
* 1 <= n <= 45
*/
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
// dp数组,dp[i]表示到i + 1 层有几种方法
// int[] dp = new int[n];
int c = 0;
int a = 1;
int b = 2;
// dp[0] = 1;
// dp[1] = 2;
for (int i = 2; i < n; i++) {
// dp[i] = dp[i - 1] + dp[i - 2];
c = a + b;
a = b;
b = c;
}
// return dp[n - 1];
return c;
}