算法刷题笔记(上)
预览主题default
代码主题atom
跳过
找出字符串中第一个匹配项的下标(字符串 kmp解法)
重复的子字符串(字符串 kmp解法)
滑动窗口最大值(栈与队列)
二叉树
332. 重新安排行程 - 力扣（LeetCode）
37. 解数独 - 力扣（LeetCode）
数组
在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
plain
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]示例 2：
plain
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]示例 3：
plain
输入：nums = [], target = 0
输出：[-1,-1]
java
class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums.length < 1) {
return new int[] { -1, -1 };
}
int left = 0, right = nums.length - 1;
int[] result = new int[2];
// 找到第一个大于或者大于等于target的下标
while (left < nums.length && nums[left] < target) {
left++;
}
if (left >= nums.length) {
return new int[] { -1, -1 };
} else if (nums[left] != target) {
return new int[] { -1, -1 };
} else {
result[0] = left;
}
// 找到第一个小于或者小于等于target的下标
while (right >= left && nums[right] > target ) {
right--;
}
if (right < left) {
return new int[] { -1, -1 };
} else if (nums[right] != target) {
return new int[] { -1, -1 };
} else {
result[1] = right;
}
return result;
}
}
java
class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums.length < 1) {
return new int[] { -1, -1 };
}
int left = 0, right = nums.length - 1;
int[] result = new int[2];
while (left < nums.length && nums[left] < target) {
left++;
}
if (left >= nums.length) {
return new int[] { -1, -1 };
} else if (nums[left] != target) {
return new int[] { -1, -1 };
} else {
result[0] = left;
}
while (right >= left && nums[right] > target ) {
right--;
}
// 优化 当代码走到这一步的时候说明nums中一定存在target值，此时的nums[right] == target一定成立，且是最后一个
result[1] = right;
return result;
}
}思路
先找第一个索引，从左边逐步遍历，直到找到第一个大于或者等于target的下标，这个时候left的取值可以分情况讨论，有下面几种情况：
- 超出数组边界，代表target不存在与数组中，直接返回[-1, -1]
- num[left]不等于target值，因为数组是非递减的，所以后面也不会有值等于target，直接返回[-1, -1]
- num[left]等于target值，添加到result[0]
至此第一个位置已经找到。接下来找第二个索引，思路和第一个一样
删除排序数组中的重复项
26. 删除有序数组中的重复项 - 力扣（LeetCode）
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
你不需要考虑数组中超出新长度后面的元素。
java
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 1)
return 1;
int slow = 1, fast = 1;
while (fast < nums.length) {
if (nums[fast] != nums[fast - 1]) {
nums[slow++] = nums[fast];
}
fast++;
}
return slow;
}
}思路
双指针， 慢指针记录不重复元素，确保[0, slow)的元素都是唯一，利用数组非严格递增的特点快指针用来比较相邻元素是否相等，不相等则更新慢指针位置，相等则继续完后移动比较，直至结束。
移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
plain
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]示例 2:
plain
输入: nums = [0]
输出: [0]提示:
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1
快慢指针，[0, slow)为非零元素，移动完成之后再将后面的元素统一置零
java
class Solution {
public void moveZeroes(int[] nums) {
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] != 0) {
nums[slow++] = nums[fast];
}
fast++;
}
while (slow < nums.length) {
nums[slow++] = 0;
}
}
}比较含退格的字符串
https://leetcode.cn/problems/backspace-string-compare/
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
示例 1：
plain
输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。示例 2：
plain
输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。示例 3：
plain
输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 "c"，但 t 仍然是 "b"。提示：
1 <= s.length, t.length <= 200s和t只含有小写字母以及字符'#'
先分别计算两个字符串退格后的结果，再比较两个字符串是否相等，计算退格后的字符串：双指针，慢指针用来保存非'#'字符，快指针用来遍历字符串，一旦出现'#'则回退慢指针
java
class Solution {
public boolean backspaceCompare(String s, String t) {
StringBuilder sResult = removeBack(s);
StringBuilder tResult = removeBack(t);
return sResult.toString().equals(tResult.toString());
}
private static StringBuilder removeBack(String s) {
int slow = 0, fast = 0;
StringBuilder result = new StringBuilder();
while (fast < s.length()) {
char charAt = s.charAt(fast);
if (charAt != '#') {
result.append(charAt);
slow++;
} else {
if (slow > 0) {
result.deleteCharAt(slow - 1);
slow--;
}
}
fast++;
}
return result;
}
}有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
plain
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]示例 2：
plain
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]提示：
1 <= nums.length <= 104-104 <= nums[i] <= 104nums已按 非递减顺序 排序
数组非递减，也就是越往两边靠的绝对值越大，平方也更大，可以利用双指针从左右两个边界往中间遍历
java
class Solution {
public int[] sortedSquares(int[] nums) {
int left = 0, right = nums.length - 1;
int[] ans = new int[nums.length];
int ansIndex = nums.length - 1;
while (ansIndex >= 0) {
if (nums[left] * nums[left] > nums[right] * nums[right]) {
ans[ansIndex] = nums[left] * nums[left];
left++;
} else {
ans[ansIndex] = nums[right] * nums[right];
right--;
}
ansIndex--;
}
return ans;
}
}长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
plain
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。示例 2：
plain
输入：target = 4, nums = [1,4,4]
输出：1示例 3：
plain
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0提示：
1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 105
滑动窗口，固定左指针，逐步向右移动右指针，计算整个窗口和，如果和大于target值则以当前窗口区间不断将左指针向右移动缩小区间，更新最小长度，直到窗口和小于target值
java
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int ans = Integer.MAX_VALUE, sum = 0;
for (int left = 0, right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
sum -= nums[left];
int currLength = right - left + 1;
ans = ans > currLength ? currLength : ans;
left++;
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}水果成篮
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果类型 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
- 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
- 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
翻译成人话就是 ：找至多包含两种元素的最长子串，返回其长度
示例 1：
plain
输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。示例 2：
plain
输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。示例 3：
plain
输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。滑动窗口，窗口的定义：保证最多只能装两种果子的情况下最多能连续经过几棵树，也就是代码中的HashMap的value值的累加和
java
class Solution {
public int totalFruit(int[] fruits) {
int ans = 0;
Map<Integer, Integer> hash = new HashMap<>();
for (int left = 0, right = 0; right < fruits.length; right++) {
hash.put(fruits[right], hash.getOrDefault(fruits[right], 0) + 1);
// 采摘的果子种类超过2 开始缩小窗口
while (hash.size() > 2) {
hash.put(fruits[left], hash.get(fruits[left]) - 1);
// 如果已经完全没有这种果子了需要将其移除
if (hash.get(fruits[left]) == 0) {
hash.remove(fruits[left]);
}
left++;
}
int current = right - left + 1;
ans = Math.max(current, ans);
}
return ans;
}
}区间和
题目描述
给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。
输入描述
第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间下标：a，b （b > = a），直至文件结束。
输出描述
输出每个指定区间内元素的总和。
输入示例
bash
5
1
2
3
4
5
0 1
1 3输出示例
bash
3
9提示信息
数据范围：
0 < n <= 100000
暴力解法，根据输入的区间累加，但是这样在大数据会出现超时，比如查询m次，每次查询的区间是0~n-1，这样时间复杂度就会来到O(m * n)；解决这个可以使用前缀和，利用前缀和复用之前计算过的子数组之和。这里定义前缀和为prefixAnd，其中prefixAnd[i]表示区间
0 - i的和，指定区间[left, right]的和，其实等于prefixAnd[right] - prefixAnd[left - 1]
java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
// 保存用户输入数组元素
int[] arr = new int[n];
// 保存并前缀和
int[] prefixAnd = new int[n];
int sum = 0;
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
// 用户便输入边计算前缀和
sum += arr[i];
prefixAnd[i] = sum;
}
while (scanner.hasNextInt()) {
int left = scanner.nextInt();
int right = scanner.nextInt();
if (left == 0) {
System.out.println(prefixAnd[right]);
} else {
System.out.println(prefixAnd[right] - prefixAnd[left - 1]);
}
}
scanner.close();
}
}螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
plain
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]示例 2：
plain
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100
模拟路径，先往左，再往下，再往左，再往上，每一次方向改变的时候都要更新四个边界
java
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int left = 0, right = matrix[0].length - 1, top = 0, bottom = matrix.length - 1;
int sum = (right + 1) * (bottom + 1);
int index = 0;
List<Integer> result= new ArrayList<>(sum);
while (index < sum) {
// 从左到右
for (int j = left; j <= right; j++) {
result.add(matrix[top][j]);
index++;
}
// 这里条件不是 ++top >= bottom，是因为bottom初始值是matrix.length - 1，
// 即使下标取bottm依旧是有意义的，而不会产生数组越界
// 这里要注意是++top 先更新了边界再判断是否越界
if (++top > bottom) break;
// 从上到下
for (int j = top; j <= bottom; j++) {
result.add(matrix[j][right]);
index++;
}
if (left > --right) break;
// 从右到左
for (int j = right; j >= left; j--) {
result.add(matrix[bottom][j]);
index++;
}
if (top > --bottom) break;
// 从下到上
for (int j = bottom; j >= top; j--) {
result.add(matrix[j][left]);
index++;
}
if (++left > right) break;
}
return result;
}
}链表
设计链表
你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类：
MyLinkedList()初始化MyLinkedList对象。int get(int index)获取链表中下标为index的节点的值。如果下标无效，则返回-1。void addAtHead(int val)将一个值为val的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。void addAtTail(int val)将一个值为val的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val)将一个值为val的节点插入到链表中下标为index的节点之前。如果index等于链表的长度，那么该节点会被追加到链表的末尾。如果index比长度更大，该节点将 不会插入 到链表中。void deleteAtIndex(int index)如果下标有效，则删除链表中下标为index的节点。
示例：
plain
输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]
解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3
myLinkedList.get(1); // 返回 2
myLinkedList.deleteAtIndex(1); // 现在，链表变为 1->3
myLinkedList.get(1); // 返回 3提示：
0 <= index, val <= 1000- 请不要使用内置的 LinkedList 库。
- 调用
get、addAtHead、addAtTail、addAtIndex和deleteAtIndex的次数不超过2000。
添加虚拟头节点方便操作
java
class MyLinkedList {
private Node dummyHead;
private int len;
public MyLinkedList() {
len = 0;
dummyHead = new Node(0);
}
public int get(int index) {
if (index >= len || index < 0) {
return -1;
}
Node tmp = dummyHead;
int i = 0;
while (i <= index) {
tmp = tmp.next;
i++;
}
return tmp.val;
}
public void addAtHead(int val) {
Node newHead = new Node(val);
newHead.next = dummyHead.next;
dummyHead.next = newHead;
len++;
}
public void addAtTail(int val) {
Node tail = new Node(val, null);
Node tmp = dummyHead;
while (tmp.next != null) {
tmp = tmp.next;
}
tmp.next = tail;
len++;
}
public void addAtIndex(int index, int val) {
if (index < 0 || index > len) {
return;
}
Node newNode = new Node(val);
Node tmp = dummyHead;
for (int i = 0; i < index; i++) {
tmp = tmp.next;
}
newNode.next = tmp.next;
tmp.next = newNode;
len++;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= len) {
return;
}
Node tmp = dummyHead;
for (int i = 0; i < index; i++) {
tmp = tmp.next;
}
tmp.next = tmp.next.next;
len--;
}
}
class Node {
int val;
Node next;
public Node() {
}
public Node(int val) {
this.val = val;
}
public Node(int val, Node next) {
this.val = val;
this.next = next;
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
plain
输入：head = [1,2,3,4]
输出：[2,1,4,3]示例 2：
plain
输入：head = []
输出：[]示例 3：
plain
输入：head = [1]
输出：[1]提示：
- 链表中节点的数目在范围
[0, 100]内 0 <= Node.val <= 100
java
/**
* 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 swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode tmp = dummyHead;
while (tmp.next != null && tmp.next.next != null) {
ListNode node1 = tmp.next;
ListNode node2 = tmp.next.next;
tmp.next = node2;
node1.next = node2.next;
node2.next = node1;
tmp = node1;
}
return dummyHead.next;
}
}删除链表的倒数第 N 个结点
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
plain
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]示例 2：
plain
输入：head = [1], n = 1
输出：[]示例 3：
plain
输入：head = [1,2], n = 1
输出：[1]提示：
- 链表中结点的数目为
sz 1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
解法一
先计算出链表长度，再遍历至待删除节点的前一个结点
java
/**
* 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 removeNthFromEnd(ListNode head, int n) {
int len = 0;
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode curr = dummyHead;
while (curr.next != null) {
len++;
curr = curr.next;
}
curr = dummyHead;
for (int i = 0; i < len - n; i++) {
curr = curr.next;
}
curr.next = curr.next.next;
return dummyHead.next;
}
}解法二
解法一需要遍历两轮，使用栈只需要遍历一轮，利用栈的先进后出特性，将所有节点压入栈中，随后出栈n次后栈顶元素即是待删除节点的前驱节点
java
/**
* 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 removeNthFromEnd(ListNode head, int n) {
Deque<ListNode> stack = new LinkedList<ListNode>();
ListNode dummy = new ListNode(0, head);
ListNode curr = dummy;
// 注意这里要把虚拟头节点也放入栈中，这样确保删除指定节点后，栈不为空
// 否则当原链表只有一个元素的时候，取得前驱节点prev会导致空指针
while (curr != null) {
stack.push(curr);
curr = curr.next;
}
for (int i = 0; i < n; i++) {
stack.pop();
}
// 此时待删除的节点的前驱节点已经在栈顶了
ListNode prev = stack.peek();
prev.next = prev.next.next;
return dummy.next;
}
}解法三：
双指针解法，先让first节点从头节点遍历n次，之后second节点从虚拟头节点开始遍历，直到first节点为空，这个时候second节点即为待删除节点的前驱节点。下面是验证分析：
删除节点我们需要找到这个节点的前驱节点，假设链表长度为len(把虚拟节点也算上，也就是说len等于head.length + 1)，那么待删除节点的下标就是len - n，它的前驱节点下标是len - n - 1，first节点从头节点遍历n次后，它的下标是n + 1，之后second节点开始从虚拟头节点遍历，first为空的时候一共需要遍历len - n -1次，此时second的下标是len - n - 1，恰好是待删除节点的前驱节点
java
/**
* 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 removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode first = head, second = dummy;
for (int i = 0; i < n; i++) {
first = first.next;
}
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
}环形链表II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
plain
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。示例 2：
plain
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。示例 3：
plain
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。提示：
- 链表中节点的数目范围在范围
[0, 104]内 -105 <= Node.val <= 105pos的值为-1或者链表中的一个有效索引
解法一
哈希表，走过的节点记录下来，如果遇到哈希表中已有这个节点说明遇到环了
java
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
Set<ListNode> set = new HashSet<ListNode>();
ListNode curr = head;
while (curr != null) {
if (set.contains(curr)) {
return curr;
}
set.add(curr);
curr = curr.next;
}
return null;
}
}解法二
双指针，fast指针每次走两步，slow指针每次走一步，
java
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null) {
if (fast.next == null) {
return null;
}
fast = fast.next.next;
slow = slow.next;
if (slow == fast) {
ListNode ans = head;
while (ans != slow) {
ans = ans.next;
slow = slow.next;
}
return ans;
}
}
return null;
}
}哈希表
找到字符串中所有字母异位词
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
示例 1:
plain
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。示例 2:
plain
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。提示:
1 <= s.length, p.length <= 3 * 104s和p仅包含小写字母
滑动窗口，构建一个长度与字符串p长度一样的窗口，然后判断这个窗口的字母是否满足字母异位词
java
class Solution {
public List<Integer> findAnagrams(String s, String p) {
if (s.length() < p.length()) {
return new ArrayList<Integer>();
}
List<Integer> result = new ArrayList<>();
int sLen = s.length(), pLen = p.length();
int[] sBucket = new int[26];
int[] pBucket = new int[26];
for (int i = 0; i < pLen; i++) {
sBucket[s.charAt(i) - 'a']++;
pBucket[p.charAt(i) - 'a']++;
}
// s p长度一样且满足条件
if (Arrays.equals(sBucket, pBucket)) {
result.add(0);
}
for (int i = 0; i < sLen - pLen; i++) {
// 窗口向后滑动
sBucket[s.charAt(i) - 'a']--;
sBucket[s.charAt(i + pLen) - 'a']++;
if (Arrays.equals(sBucket, pBucket)) {
result.add(i + 1);
}
}
return result;
}
}两个数组的交集
给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1：
plain
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]示例 2：
plain
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的提示：
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
解法一：
排序+双指针，比较两个指针所指的值的大小，小的一方移动指针，如果相等，要判断该位置元素是否已经存在于存储交集的result数组中，已存在则不加入，反之加入，然后两个指针都向后移动；因为原两个数组被排序过，所以result数组必定是有序的，判断是否存在只需要跟result最后一个元素比较即可。
复杂度分析：
- 时间复杂度：排序两个数组的复杂度是O(mlogm + nlogn)，双指针遍历O(m + n)，总的时间复杂度O(nlogn+mlogm+n+m)=O(nlogn+mlogm)；
- 空间复杂度：结果数组result空间复杂度O(m + n)，其他变量常量级O(1)，最终空间复杂度O(m + n)；
java
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int len1 = nums1.length, len2 = nums2.length;
int[] result = new int[len1 + len2];
int index = 0, index1 = 0, index2 = 0;
while (index1 < len1 && index2 < len2) {
if (nums1[index1] < nums2[index2]) {
index1++;
} else if (nums1[index1] > nums2[index2]) {
index2++;
} else {
// 这里需要注意遇到第一个交集元素
if (index == 0 || nums1[index1] != result[index - 1]) {
result[index++] = nums1[index1];
}
index1++;
index2++;
}
}
return Arrays.copyOfRange(result, 0, index);
}
}解法二
哈希表，先遍历其中一个数组，以数组的值作为哈希的key，value值为1，再遍历第二个数组，如果哈希表存在元素，则计数值自减1，如果减完后恰好为0，则添加到结果集中
复杂度分析：
- 空间复杂度：O(n+m)
- 时间复杂度：O(k)
java
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
int[] cnt = new int[1001];
List<Integer> result = new ArrayList<>();
int index = 0;
for (int n : nums1) {
cnt[n] = 1;
}
for (int n : nums2) {
--cnt[n];
if (cnt[n] == 0) {
result.add(n);
}
}
return result.stream().mapToInt(Integer::intValue).toArray();
}
}两个数组的交集 II
350. 两个数组的交集 II - 力扣（LeetCode）
给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
示例 1：
plain
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]示例 2:
plain
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]提示：
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
解法一：
排序+计数，使用两个桶统计各个元素出现的个数，再随意遍历任意一个数组，判断是否有交集，有交集的话取计数值较小的添加到结果集中
java
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int[] cnt1 = new int[1001], cnt2 = new int[1001];
for (int n : nums1) {
cnt1[n]++;
}
for (int n : nums2) {
cnt2[n]++;
}
int[] result = new int[1001];
int index = 0;
for (int n : nums1) {
if (cnt2[n] > 0 && (index == 0 || n != result[index - 1])) {
if (cnt1[n] > cnt2[n]) {
for (int i = 0; i < cnt2[n]; i++) {
result[index++] = n;
}
} else {
for (int i = 0; i < cnt1[n]; i++) {
result[index++] = n;
}
}
}
}
return Arrays.copyOfRange(result, 0, index);
}
}- 时间复杂度: O(nlogn+mlogm)；
- 空间复杂度: O(k)
三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
plain
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。示例 2：
plain
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。示例 3：
plain
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
先排序，然后用双指针，固定一个初始指针 i ，使用left和right分别指向左右两端，其中left = i + 1，计算nums[i] + nums[left] + nums[right]，如果大于0，右指针左移；小于0左指针右移；等于0说明找到目标元组，但是题目要求不能存在重复元组，这时候需要去重，当我们找到目标元组之后，left右边与nums[left]相等的值都没有意义了，right左边与nums[right]相等的值同样没有意义了，所以我们需要在找到目标元组之后根据这个原则再次移动左右指针，从而达到对left right去重的目的；另外对于 i 指针去重，i和right移动方向一样，同样是i左边的元素与nums[i]相等就失去一样了。
java
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) continue;
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum > 0) {
--right;
} else if (sum < 0) {
++left;
} else {
result.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
left++;
right--;
}
}
}
return result;
}
}时间复杂度：O(n2) 空间复杂度：O(n)
字符串
反转字符串 II
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
- 如果剩余字符少于
k个，则将剩余字符全部反转。 - 如果剩余字符小于
2k但大于或等于k个，则反转前k个字符，其余字符保持原样。
示例 1：
plain
输入：s = "abcdefg", k = 2
输出："bacdfeg"示例 2：
plain
输入：s = "abcd", k = 2
输出："bacd"提示：
1 <= s.length <= 104s仅由小写英文组成1 <= k <= 104
模拟即可，需要注意的点是按2*k计数，所以每次循环的步长是2 * k。
java
class Solution {
public String reverseStr(String s, int k) {
int len = s.length();
char[] arr = s.toCharArray();
for (int i = 0; i < len;) {
int sub = len - i;
if (sub < k) {
reverse(arr, i, len - 1);
break;
} else if (sub >= k && sub < 2 * k) {
reverse(arr, i, i + k - 1);
i += 2 * k;
} else {
i += 2 * k;
reverse(arr, i - 2 * k, i - k - 1);
}
}
return new String(arr);
}
public void reverse(char[] arr, int start, int end) {
while (end > start) {
char tmp = arr[start];
arr[start++] = arr[end];
arr[end--] = tmp;
}
}
}时间复杂度： O(n)， 空间复杂度：O(n)
替换数字
54. 替换数字（第八期模拟笔试） (kamacoder.com)
题目描述
给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。
数据范围：
1 <= s.length < 10000。
先统计字符串中的数字个数，随后申请一个扩容后的数组，从后开始遍历旧数组，遇到数字就替换number填充到新数组中
java
import java.util.Scanner;
/**
* @author LinShanglei
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 用户输入的字符串，使用正则表达式限制包含小写字母和数字
String regex = "^[a-z0-9]+$";
String str = scanner.next(regex);
int count = 0;
for (int i = 0; i < str.length(); i++) {
if (Character.isDigit(str.charAt(i))) {
++count;
}
}
char[] newStr = new char[str.length() + count * 5];
int i = str.length() - 1, j = newStr.length - 1;
while (i >= 0) {
if (Character.isDigit(str.charAt(i))) {
newStr[j--] = 'r';
newStr[j--] = 'e';
newStr[j--] = 'b';
newStr[j--] = 'm';
newStr[j--] = 'u';
newStr[j--] = 'n';
} else {
newStr[j--] = str.charAt(i);
}
i--;
}
System.out.println(new String(newStr));
scanner.close();
}
}反转字符串中的单词
给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
示例 1：
plain
输入：s = "the sky is blue"
输出："blue is sky the"示例 2：
plain
输入：s = " hello world "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。示例 3：
plain
输入：s = "a good example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。提示：
1 <= s.length <= 104s包含英文大小写字母、数字和空格' 's中 至少存在一个 单词
解法一：
利用栈先进后出的特性，从后开始遍历，每次遇到字母时压入栈中，遇到非字母且栈不为空时出栈
java
class Solution {
public String reverseWords(String s) {
StringBuilder result = new StringBuilder();
Deque<Character> stack = new LinkedList<>();
for (int i = s.length() - 1; i >= 0; i--) {
char c = s.charAt(i);
if (c != ' ') {
stack.push(c);
} else {
// 栈不为空出栈，即是一个单词
if (!stack.isEmpty()) {
while (!stack.isEmpty()) {
result.append(stack.pop());
}
result.append(' ');
}
}
}
while (!stack.isEmpty()) {
result.append(stack.pop());
}
return result.toString().trim();
}
}解法二
先去除调多余的空格，这样首尾没有空格，每个单词之间也只有一个空格，之后再将整个字符串翻转，这样单词也翻转了，然后再针对每一个单词做一次单独的翻转即可，例如" the sky is blue "
- 去除多余空格，字符串变为"the sky is blue"
- 反转字符串："eulb si yks eht"
- 反转每个单词："blue is sky the"
java
class Solution {
public String reverseWords(String s) {
StringBuilder result = trimSpace(s);
reverse(result, 0, result.length() - 1);
reverseEachWord(result);
return new String(result);
}
// 去除头尾和单词之间多余的空格
public StringBuilder trimSpace(String s) {
int left = 0, right = s.length() - 1;
// 去除首尾空格
while (left <= right && s.charAt(left) == ' ') {
++left;
}
while (left <= right && s.charAt(right) == ' ') {
--right;
}
// 去除单词间的空格
StringBuilder result = new StringBuilder();
while (left <= right) {
if (s.charAt(left) != ' ') {
result.append(s.charAt(left));
} else if (result.charAt(result.length() - 1) != ' ') {
// 如果result最后一个字符不是空格，说明单词之间没有添加空格
result.append(' ');
}
left++;
}
return result;
}
// 反转字符串
public void reverse(StringBuilder s, int left, int right) {
while (left < right) {
char tmp = s.charAt(left);
s.setCharAt(left++, s.charAt(right));
s.setCharAt(right--, tmp);
}
}
// 反转每个单词
public void reverseEachWord(StringBuilder s) {
int start = 0, len = s.length(), end = 0;
while (start < len) {
while (end < len && s.charAt(end) != ' ') {
end++;
}
reverse(s, start, end - 1);
start = end + 1;
++end;
}
}
}右旋字符串
55. 右旋字符串（第八期模拟笔试） (kamacoder.com)
题目描述
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。
例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。
输入描述
输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。
输出描述
输出共一行，为进行了右旋转操作后的字符串。
输入示例
plain
2
abcdefg输出示例
plain
fgabcde提示信息
数据范围：
1 <= k < 10000,
1 <= s.length < 10000;
先将整个字符串反转，再将字符串以k为分界点，分别反转两段子串
java
import java.util.Scanner;
/**
* @author LinShanglei
*/
public class RightRotationString {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int k = Integer.parseInt(scanner.nextLine());
String s = scanner.nextLine();
char[] array = s.toCharArray();
reverse(array, 0, s.length() - 1);
reverse(array, 0, k - 1);
reverse(array, k, s.length() - 1);
System.out.println(array);
scanner.close();
}
public static void reverse(char[] s, int left, int right) {
while (left < right) {
s[left] ^= s[right];
s[right] ^= s[left];
s[left] ^= s[right];
left++;
right--;
}
}
}异或交换解释：
异或即相异计算得1，相同计算得0，满足以下性质
交换律：a ^ b = b ^ a
结合律：a ^ (b ^ c) = (a ^ b) ^ c
自反性：a ^ b ^ b = a (推导： a ^ b ^ b = a ^ (b ^ b) = a)
异或交换：
int a = 1;
int b = 2;
a = a ^ b; // 假设此时得到的值用a1表示，a1 = a ^ b;
b = a ^ b; // b1 = a1 ^ b = a ^ b ^ b = a
a = a ^ b; // a2 = a1 ^ b1 = a ^ b ^ a1 ^ b = a ^ b ^ a ^ b ^ b = b
找出字符串中第一个匹配项的下标
28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例 1：
plain
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。示例 2：
plain
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。提示：
1 <= haystack.length, needle.length <= 104haystack和needle仅由小写英文字符组成
解法一
枚举
haystack每一个字符作为起点，依次匹配needle
java
class Solution {
public int strStr(String haystack, String needle) {
int index1 = 0, index2 = 0;
while (index2 < needle.length() && index1 < haystack.length()) {
int result = index1;
while (index1 < haystack.length()) {
if (haystack.charAt(index1) == needle.charAt(index2)) {
index1++;
index2++;
if (index2 == needle.length()) {
return result;
}
} else {
break;
}
}
index1 = result + 1;
index2 = 0;
}
return -1;
}
}双指针
移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
- 更改
nums数组，使nums的前k个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。 - 返回
k。
用户评测：
评测机将使用以下代码测试您的解决方案：
plain
int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
// 它以不等于 val 的值排序。
int k = removeElement(nums, val); // 调用你的实现
assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}如果所有的断言都通过，你的解决方案将会 通过。
示例 1：
plain
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。示例 2：
plain
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。提示：
0 <= nums.length <= 1000 <= nums[i] <= 500 <= val <= 100
双指针，一个指针用来遍历数组，一个指针用来记录存储非val值的下标，遇到非val值的元素同时更新两个指针，其他指针只更新遍历数组指针
java
class Solution {
public int removeElement(int[] nums, int val) {
int result = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != val) {
nums[result++] = nums[i];
}
}
return result;
}
}删除有序数组中的重复项
26. 删除有序数组中的重复项 - 力扣（LeetCode）
给你一个 非严格递增排列 的数组 nums ，请你原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
- 更改数组
nums，使nums的前k个元素包含唯一元素，并按照它们最初在nums中出现的顺序排列。nums的其余元素与nums的大小不重要。 - 返回
k。
判题标准:
系统会用下面的代码来测试你的题解:
plain
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}如果所有断言都通过，那么您的题解将被 通过。
示例 1：
plain
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。示例 2：
plain
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。提示：
1 <= nums.length <= 3 * 104-104 <= nums[i] <= 104nums已按 非严格递增 排列
java
class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
int j = 0;
for (int i = 0; i < n; i++) {
if (nums[i] != nums[j]) {
nums[++j] = nums[i];
}
}
return j + 1;
}
}移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
plain
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]示例 2:
plain
输入: nums = [0]
输出: [0]提示:
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1
双指针，i用于遍历，index用于记录非0，i遍历完之后，所有的非零元素就按照原顺序排在数组最前面，此时的index就是非零元素和零元素的分界线，在index后面的元素设置为0即可
java
class Solution {
public void moveZeroes(int[] nums) {
int index = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[index++] = nums[i];
}
}
for (; index < nums.length; index++) {
nums[index] = 0;
}
}
}栈与队列
用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
注意：
- 你只能使用队列的标准操作 —— 也就是
push to back、peek/pop from front、size和is empty这些操作。 - 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
解法一：
使用两个队列，主队列stack一直保证和真正的栈一样的顺序，另一个队列用于辅助，当push的时候要先把stack队列的元素依次弹出放入待辅助队列中，再将元素压入stack队列中，随后把辅助队列的元素依次弹出压入stack中，这样stack队列的顺序就和真正的栈一样了
java
class MyStack {
// 用于保存真正的栈顺序的队列
Queue<Integer> stack;
// 辅助队列
Queue<Integer> assist;
public MyStack() {
stack = new ArrayDeque<>();
assist = new ArrayDeque<>();
}
public void push(int x) {
while (stack.size() > 0) {
assist.add(stack.poll());
}
stack.add(x);
while (assist.size() > 0) {
stack.add(assist.poll());
}
}
public int pop() {
return stack.poll();
}
public int top() {
return stack.peek();
}
public boolean empty() {
return stack.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/解法二：
使用一个队列，push的时候先把元素加入队列末尾，然后循环queue.size - 1次，把之前的元素依次出队再入队，这样就能保证队头的元素是栈顶元素了
java
class MyStack {
Queue<Integer> stack;
public MyStack() {
stack = new ArrayDeque<>();
}
public void push(int x) {
stack.add(x);
int size = stack.size();
for (int i = 0; i < size - 1; i++) {
stack.add(stack.poll());
}
}
public int pop() {
return stack.poll();
}
public int top() {
return stack.peek();
}
public boolean empty() {
return stack.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false
说明：
- 你 只能 使用标准的栈操作 —— 也就是只有
push to top,peek/pop from top,size, 和is empty操作是合法的。 - 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
plain
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false提示：
1 <= x <= 9- 最多调用
100次push、pop、peek和empty - 假设所有操作都是有效的 （例如，一个空的队列不会调用
pop或者peek操作）
使用两个栈，一个栈用于入队，一个用于出队，入队的时候把元素压入入队栈。出队的时候把入队栈的元素依次出队压入出队栈
java
class MyQueue {
Deque<Integer> in;
Deque<Integer> out;
public MyQueue() {
in = new ArrayDeque<Integer>();
out = new ArrayDeque<Integer>();
}
public void push(int x) {
in.push(x);
}
public int pop() {
int result = this.peek();
out.pop();
return result;
}
public int peek() {
if (!out.isEmpty()) return out.peek();
if (in.isEmpty()) return -1;
while (!in.isEmpty()) {
out.push(in.pop());
}
return out.peek();
}
public boolean empty() {
return in.isEmpty() && out.isEmpty();
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([])"
输出：true
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
利用栈，每次遇到左括号的时候就入栈，遇到非左括号时就和栈顶元素是否匹配，不匹配直接返回false，匹配的话则将栈顶元素出栈
java
class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new LinkedList<Character>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (ch == '(' || ch == '[' || ch == '{') {
stack.push(ch);
} else {
if (stack.isEmpty()) return false;
if (ch == ')' && stack.peek() != '(') {
return false;
}
if (ch == ']' && stack.peek() != '[') {
return false;
}
if (ch == '}' && stack.peek() != '{') {
return false;
}
stack.pop();
}
}
return stack.isEmpty();
}
}删除字符串中的所有相邻重复项
1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）
给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 s 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
plain
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。提示：
1 <= s.length <= 105s仅由小写英文字母组成。
利用栈，遍历每个元素，入栈前判断是否和栈顶的元素相同，相同的话出栈，不相同则入栈，最后再逆序拼接栈中元素
java
class Solution {
public String removeDuplicates(String s) {
Deque<Character> stack = new LinkedList<Character>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!stack.isEmpty() && c == stack.peek()) {
stack.pop();
} else {
stack.push(c);
}
}
char[] result = new char[stack.size()];
for (int i = stack.size() - 1; i >= 0; i--) {
result[i] = stack.pop();
}
return new String(result);
}
}逆波兰表达式求值
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为
'+'、'-'、'*'和'/'。 - 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
示例 1：
plain
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9示例 2：
plain
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6示例 3：
plain
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22提示：
1 <= tokens.length <= 104tokens[i]是一个算符（"+"、"-"、"*"或"/"），或是在范围[-200, 200]内的一个整数
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式，如
( 1 + 2 ) * ( 3 + 4 )。 - 该算式的逆波兰表达式写法为
( ( 1 2 + ) ( 3 4 + ) * )。
逆波兰表达式主要有以下两个优点：
- 去掉括号后表达式无歧义，上式即便写成
1 2 + 3 4 + *也可以依据次序计算出正确结果。 - 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
遇到非符号压入栈中，遇到符号取出前两个元素计算，将计算结果压入栈中
java
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new LinkedList<>();
for (int i = 0; i < tokens.length; i++) {
String s = tokens[i];
if (s.equals("+")) {
int a = stack.pop();
int b = stack.pop();
stack.push(a + b);
continue;
}
if (s.equals("-")) {
int a = stack.pop();
int b = stack.pop();
stack.push(b - a);
continue;
}
if (s.equals("*")) {
int a = stack.pop();
int b = stack.pop();
stack.push(b * a);
continue;
}
if (s.equals("/")) {
int a = stack.pop();
int b = stack.pop();
stack.push(b / a);
continue;
}
stack.push(Integer.valueOf(s));
}
return stack.pop();
}
}前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
plain
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]示例 2:
plain
输入: nums = [1], k = 1
输出: [1]提示：
1 <= nums.length <= 105k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一，换句话说，数组中前
k个高频元素的集合是唯一的
进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
使用哈希表记录每个元素出现的个数，也就得到一个计数桶，之后再对这个计数桶进行排序，取出前k个元素；利用最小堆，遍历计数桶：
- 当前堆大小 < k，直接将当前值加入堆
- 当前堆大小 == k，如果当前值大于堆顶元素，弹出堆顶元素，将当前值加入堆，否则抛弃当前值
java
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
cnt.put(nums[i], cnt.getOrDefault(nums[i], 0) + 1);
}
PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
int num = entry.getKey();
int count = entry.getValue();
if (queue.size() == k) {
if (queue.peek()[1] < count) {
queue.poll();
queue.offer(new int[] { num, count });
}
} else {
queue.offer(new int[] { num, count });
}
}
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = queue.poll()[0];
}
return result;
}
}二叉树
二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
解释：
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[1,2,4,5,6,7,3,8,9]
解释：
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
递归：
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
preorder(root, result);
return result;
}
public void preorder(TreeNode curr, List<Integer> result) {
if (curr == null) {
return ;
}
result.add(curr.val);
preorder(curr.left, result);
preorder(curr.right, result);
}
}迭代法
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<Integer>();
}
Stack<TreeNode> stack = new Stack<>();
List<Integer> result = new ArrayList<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return result;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
Deque<TreeNode> stack = new ArrayDeque<>();
List<Integer> result = new ArrayList<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return result;
}
}二叉树的中序遍历
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<Integer>();
}
List<Integer> result = new ArrayList<Integer>();
Deque<TreeNode> stack = new LinkedList<>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
result.add(node.val);
node = node.right;
}
return result;
}
}二叉树的后序遍历
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
解释：
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[4,6,7,5,2,9,8,3,1]
解释：
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
提示：
- 树中节点的数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>();
List<Integer> result = new ArrayList<>();
TreeNode prev = null;
while (root != null || !stack.isEmpty()) {
// 遍历到最左节点
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
// 遍历右节点
// 如果右节点存在且之前没有被访问过，继续遍历直到最右节点
if (root.right != null && root.right != prev) {
stack.push(root);
root = root.right;
} else {
// 右节点不存在或者之前被访问过
result.add(root.val);
// 更新访问历史节点
prev = root;
// 处理完当前节点需要置空 避免重复处理
root = null;
}
}
return result;
}
}二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
plain
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]示例 2：
plain
输入：root = [1]
输出：[[1]]示例 3：
plain
输入：root = []
输出：[]提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if (root != null) {
queue.add(root);
}
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode curr = queue.poll();
level.add(curr.val);
if (curr.left != null) {
queue.add(curr.left);
}
if (curr.right != null) {
queue.add(curr.right);
}
}
result.add(level);
}
return result;
}
}二叉树的右视图
二叉树的层序遍历的基础上，判断是否遍历到单层的最后一个元素，是的话加入结果集
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode curr = queue.poll();
if (i == size - 1) {
result.add(curr.val);
}
if (curr.left != null) {
queue.add(curr.left);
}
if (curr.right != null) {
queue.add(curr.right);
}
}
}
return result;
}
}二叉树的层平均值
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
double sum = 0.0;
for (int i = 0; i < size; i++) {
TreeNode curr = queue.poll();
sum += curr.val;
if (curr.left != null) {
queue.add(curr.left);
}
if (curr.right != null) {
queue.add(curr.right);
}
}
result.add(sum / size);
}
return result;
}
}N 叉树的层序遍历
java
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
Node curr = queue.poll();
level.add(curr.val);
for (int j = 0; j < curr.children.size(); j++) {
queue.add(curr.children.get(j));
}
}
result.add(level);
}
return result;
}
}填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
plain
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例 1：
plain
输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。示例 2:
plain
输入：root = []
输出：[]提示：
- 树中节点的数量在
[0, 212 - 1]范围内 -1000 <= node.val <= 1000
进阶：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
java
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
if (root == null) {
return null;
}
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Node node = queue.poll();
if (i == size - 1) {
node.next = null;
} else {
node.next = queue.peek();
}
// 拓展下一层节点
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
return root;
}
}二叉树的最大深度
解法一：层序遍历
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int result = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
// 拓展下一层节点
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
result++;
}
return result;
}
}解法二：DFS
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
plain
输入：root = [3,9,20,null,null,15,7]
输出：2示例 2：
plain
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5提示：
- 树中节点数的范围在
[0, 105]内 -1000 <= Node.val <= 1000
解法一：层序遍历
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int result = 0;
while (!queue.isEmpty()) {
int size = queue.size();
result++;
for (int i = 0; i < size; i++) {
TreeNode tmp = queue.poll();
if (tmp.left == null && tmp.right == null) {
return result;
}
if (tmp.left != null) {
queue.add(tmp.left);
}
if (tmp.right != null) {
queue.add(tmp.right);
}
}
}
return result;
}
}解法二：DFS
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
int minDepth = Integer.MAX_VALUE;
if (root.left != null) {
minDepth = Math.min(minDepth, minDepth(root.left));
}
if (root.right != null) {
minDepth = Math.min(minDepth, minDepth(root.right));
}
return minDepth + 1;
}
}翻转二叉树
层序遍历：
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode tmp = queue.poll();
swap(tmp);
if (tmp.left != null) {
queue.add(tmp.left);
}
if (tmp.right != null) {
queue.add(tmp.right);
}
}
}
return root;
}
public void swap(TreeNode root) {
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}
}DFS
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}辅助栈迭代
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode curr = stack.pop();
TreeNode tmp = curr.left;
curr.left = curr.right;
curr.right = tmp;
if (curr.left != null) {
stack.push(curr.left);
}
if (curr.right != null) {
stack.push(curr.right);
}
}
return root;
}
}对称二叉树
解法 一：递归
1、确定递归函数的参数和返回值类型
这里需要比较两个子树是否是互相翻转的，所以参数是左右子树，返回值类型是布尔型。
2、确定终止条件
要比较两个子树是否为相互翻转，可以分为下面几种情况讨论
- 两个子树都为空，返回true
- 仅有一个子树为空，返回false
- 两个都不为空，但是value值不等，返回false
3、确定单层循环逻辑
此时已经确定了左右子树都不为空，且value值相等，这个时候就要比较left.right和right.left、left.right和right.left是否相等的，如果这两组都相等则判定为互相翻转。
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return compareSubTree(root.left, root.right);
}
public boolean compareSubTree(TreeNode left, TreeNode right) {
if (left != null && right == null) return false;
if (left == null && right != null) return false;
if (left == null && right == null) return true;
if (left.val != right.val) return false;
boolean outside = compareSubTree(left.left, right.right);
boolean inside = compareSubTree(left.right, right.left);
return inside && outside;
}
}解法二：辅助栈迭代
每次入栈的时候将要比较的两个子树入栈，出栈的时候同样出两个，成对比较
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root.left);
stack.push(root.right);
while (!stack.isEmpty()) {
TreeNode left = stack.pop();
TreeNode right = stack.pop();
if (left == null && right == null) {
continue;
}
if (left == null || right == null || left.val != right.val) {
return false;
}
stack.push(left.left);
stack.push(right.right);
stack.push(left.right);
stack.push(right.left);
}
return true;
}
}完全二叉树的节点个数
java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int countNodes(TreeNode root) {
if (root == null) return 0;
return getNum(root);
}
public int getNum(TreeNode node) {
if (node == null) return 0;
int a = getNum(node.left);
int b = getNum(node.right);
return a + b + 1;
}
}回溯算法
回溯法解决的问题
回溯法，一般可以解决如下几种问题：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
plain
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]示例 2：
plain
输入：n = 1, k = 1
输出：[[1]]提示：
1 <= n <= 201 <= k <= n
java
class Solution {
List<List<Integer>> result = new ArrayList<>();
Deque<Integer> path = new ArrayDeque<>();
public List<List<Integer>> combine(int n, int k) {
dfs(n, k, 1);
return result;
}
public void dfs(int n, int k, int startIndex) {
if (path.size() == k) {
result.add(new ArrayList<>(path));
return ;
}
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
path.addLast(i);
dfs(n, k, i + 1);
path.removeLast();
}
}
}组合总和 III
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
plain
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。示例 2:
plain
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。示例 3:
plain
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
java
class Solution {
List<List<Integer>> result = new ArrayList<>();
Deque<Integer> path = new ArrayDeque<>();
public List<List<Integer>> combinationSum3(int k, int n) {
dfs(n, k, 1, 0);
return result;
}
public void dfs (int n, int k, int startIndex, int sum) {
if (path.size() == k && sum == n) {
result.add(new ArrayList<>(path));
return;
}
if (path.size() > k || sum > n) {
return;
}
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
path.addLast(i);
dfs(n, k, i + 1, sum + i);
path.removeLast();
}
}
}电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
plain
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]示例 2：
plain
输入：digits = ""
输出：[]示例 3：
plain
输入：digits = "2"
输出：["a","b","c"]提示：
0 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
首先建立了一个映射键盘字符串的数组，其次是List
result用于保存符合要求的结果集，path是一个StringBuilder，表示当前遍历树的路径 递归三步走：
1、确认递归函数参数和返回值类型：每一次递归都是在做竖向遍历，所以我们需要一个指向当前映射数组的下标startIndex，返回值是全局变量，所以递归函数返回值为void
2、确认终止条件：当startIndex == digits.length时代表已经找到最后一个键盘，直接返回
3、单层递归逻辑：选中当前数字键盘映射的字符串后，遍历这个字符串，每次取一个字符加入path，回溯的时候去掉
java
class Solution {
List<String> result = new ArrayList<>();
StringBuilder path = new StringBuilder();
String[] map = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) {
return result;
}
dfs(digits, 0);
return result;
}
public void dfs(String digits, int startIndex) {
if (path.length() == digits.length()) {
result.add(new String(path));
return;
}
String curr = map[digits.charAt(startIndex) - '0'];
for (int i = 0; i < curr.length(); i++) {
path.append(curr.charAt(i));
dfs(digits, startIndex + 1);
path.deleteCharAt(path.length() - 1);
}
}
}组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
plain
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。示例 2：
plain
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]示例 3：
plain
输入: candidates = [2], target = 1
输出: []提示：
1 <= candidates.length <= 302 <= candidates[i] <= 40candidates的所有元素 互不相同1 <= target <= 40
题目要求一个元素可以选用多次，所有遍历选取元素的时候考虑了所有的元素，导致了重复路径的出现，所以要在搜索的时候去重，在搜索的时候就要设置下一轮搜索的起点startIndex，比如说：从2开始搜索的时候，就会找出所有[2, ....]的答案，在搜索3的时候就不能再选2了
java
class Solution {
List<List<Integer>> result = new ArrayList<>();
Deque<Integer> path = new ArrayDeque<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
dfs(candidates, 0, target, 0);
return result;
}
public void dfs(int[] candidates, int sum, int target, int startIndex) {
if (sum > target) return;
if (sum == target) {
result.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
// 剪枝优化
if (sum + candidates[i] > target) return;
path.addLast(candidates[i]);
sum += candidates[i];
dfs(candidates, sum, target, i);
path.removeLast();
sum -= candidates[i];
}
}
}组合总和 II
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
示例 1:
plain
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]示例 2:
plain
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]提示:
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30
思路
这道题最重要的地方在于集合本身元素有重复，但是不允许有重复的组合。因此我们需要去重，那就带来一个问题：这个重复是指在同一个树层使用过还是在同一树枝使用过？从题目描述和示例可以看出是同一树层不允许重复，同一树枝可以重复。此外树层去重需要对数组排序。
递归三部曲
-
确定递归函数的参数和返回值
需要题目给定的集合，当前树枝路径的和，树层开始遍历索引、target值，此外去重还需要一个used数组；返回值类型因为定义了全局变量，直接void -
递归终止条件
如果sum == target将路径放入结果集，返回；如果sum > target，直接返回 -
单层递归逻辑
去重的判断：如果
candidates[i] == candidates[i - 1] && used[i - 1] == false就说明上一个树枝使用了candidates[i]，也就是同一树层使用过candidates[i]。
从图中可以得知，在candidates[i] == candidates[i - 1]的情况下：
used[i - 1] == true，说明同一树枝candidates[i - 1]使用过used[i - 1] == false，说明同一树层candidates[i - 1]使用过
为什么 used[i - 1] == false 就是同一树层呢，因为同一树层，used[i - 1] == false 才能表示，当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。
而 used[i - 1] == true，说明是进入下一层递归，去下一个数，所以是树枝上，如图所示：
java
class Solution {
List<List<Integer>> result = new ArrayList<>();
Deque<Integer> path = new ArrayDeque<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
boolean[] used = new boolean[candidates.length];
Arrays.sort(candidates);
Arrays.fill(used, false);
dfs(candidates, 0, target, 0, used);
return result;
}
public void dfs(int[] candidates, int sum, int target, int startIndex, boolean[] used) {
if (sum > target) {
return;
}
if (sum == target) {
result.add(new ArrayList<>(path));
return;
}
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]) {
continue;
}
path.addLast(candidates[i]);
sum += candidates[i];
used[i] = true;
dfs(candidates, sum, target, i + 1, used);
used[i] = false;
sum -= candidates[i];
path.removeLast();
}
}
}分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]示例 2：
输入：s = "a"
输出：[["a"]]提示：
1 <= s.length <= 16s仅由小写英文字母组成
本题还需要startIndex来控制for循环的起始位置，对于组合问题，什么时候需要startIndex呢？
我举过例子，如果是一个集合来求组合的话，就需要startIndex，例如：77.组合 (opens new window)，216.组合总和III (opens new window)。
如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17.电话号码的字母组合
回溯三部曲
-
确定递归函数参数和返回值
全局变量result存储最终的结果集，path存储切割后回文子串，另外还需要一个startIndex来记录切割位置 -
确认终止条件
从上面树形图中可以知道切割到最后面就结束了，在代码里面这个切割线就是startIndex，表示下一轮递归遍历的起始位置。伪代码如下：javapublic void dfs(int startIndex, String s, StringBuilder s) { for (int i = startIndex; i < s.length(); i++) { if (startIndex == s.length()) { // 保存结果 return ; } // 单层递归逻辑 } } -
确定单层递归逻辑
for (int i = startIndex; i < s.length(); i++)，在这里我们需要截取的字符串就是[startIndex, i]，每次截取都需要判断是否为回文子串，是的话放入path中，然后递归下一层
判断回文子串优化
定义dp数组，boolean[][] dp，dp[i][j]为真表示s[i...j]是回文串，那状态转移方程为dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1]
最终代码如下：
java
class Solution {
List<List<String>> result = new ArrayList<>();
List<String> path = new ArrayList<>();
boolean[][] dp;
public List<List<String>> partition(String s) {
char[] charArr = s.toCharArray();
dp = new boolean[s.length() + 1][s.length() + 1];
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j <= i; j++) {
if (charArr[i] == charArr[j] && (i - j <= 2 || dp[j + 1][i - 1])) {
dp[j][i] = true;
}
}
}
dfs(0, s, new StringBuilder());
return result;
}
public void dfs(int startIndex, String s, StringBuilder sb) {
if (startIndex == s.length()) {
result.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < s.length(); i++) {
sb.append(s.charAt(i));
if (dp[startIndex][i]) {
path.add(sb.toString());
dfs(i + 1, s, new StringBuilder());
path.remove(path.size() - 1);
}
}
}
}子集 II
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]示例 2：
输入：nums = [0]
输出：[[],[0]]提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10
思路和[组合综合 II](# 组合总和 II)一样。
java
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new LinkedList<>();
boolean[] used;
public List<List<Integer>> subsetsWithDup(int[] nums) {
used = new boolean[nums.length];
Arrays.fill(used, false);
Arrays.sort(nums);
backTracking(nums, 0);
return result;
}
public void backTracking(int[] nums, int startIndex) {
result.add(new ArrayList<>(path));
if (startIndex >= nums.length) {
return;
}
for (int i = startIndex; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
path.add(nums[i]);
used[i] = true;
backTracking(nums, i + 1);
path.removeLast();
used[i] = false;
}
}
}递增子序列
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
示例 1：
输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]示例 2：
输入：nums = [4,4,3,2,1]
输出：[[4,4]]提示：
1 <= nums.length <= 15-100 <= nums[i] <= 100
思路
这道题最重要的地方在于题目要求返回子序列，也就不能像之前那样使用used数组标记元素来去重，以下图为例：
所以在遍历同一层的元素的时候使用数组来标记使用过的元素，从而达到去重的目的。
java
class Solution {
List<List<Integer>> result = new ArrayList<>();
Deque<Integer> path = new LinkedList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
backTracking(nums, 0);
return result;
}
private void backTracking(int[] nums, int startIndex) {
// 递增子序列中至少有两个元素
if (path.size() > 1) {
result.add(new ArrayList<>(path));
}
if (startIndex >= nums.length) {
return;
}
// 题目规定 -100 <= nums[i] <= 100
int[] used = new int[201];
for (int i = startIndex; i < nums.length; i++) {
if (path.size() > 0 && path.peekLast() > nums[i]) {
continue;
}
if (used[nums[i] + 100] == 1) {
continue;
}
used[nums[i] + 100] = 1;
path.add(nums[i]);
backTracking(nums, i + 1);
path.removeLast();
}
}
}全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]示例 3：
输入：nums = [1]
输出：[[1]]提示：
1 <= nums.length <= 6-10 <= nums[i] <= 10nums中的所有整数 互不相同
三部曲
-
确定返回值和参数
排列是有序的，[1, 2]和[2, 1]是不一样的，使用过的元素在另外的排列里面依旧可以使用，所以不需要startIndex。不过需要一个used数组来标记一趟排列中使用过哪些元素，如图中橘黄色标记：
-
递归终止条件
当path.size()和nums.length相等时代表找到了一个排列，也就是图中叶子节点。 -
单层递归逻辑
每层搜索的时候需要记录使用的元素，并回溯，在加入path前需要先判断元素是否使用过，使用过的直接开启下一轮搜索。
java
class Solution {
List<List<Integer>> result = new ArrayList<>();
Deque<Integer> path = new LinkedList<>();
public List<List<Integer>> permute(int[] nums) {
boolean[] used = new boolean[21];
Arrays.fill(used, false);
backTracking(nums, used);
return result;
}
public void backTracking(int[] nums, boolean[] used) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[nums[i] + 10]) {
continue;
}
path.add(nums[i]);
used[nums[i] + 10] = true;
backTracking(nums, used);
used[nums[i] + 10] = false;
path.removeLast();
}
}
}全排列 II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]提示：
1 <= nums.length <= 8-10 <= nums[i] <= 10
将这个问题看作有 n 个排列成一行的空格，我们需要从左往右依次填入题目给定的 n 个数，每个数只能使用一次。那么很直接的可以想到一种穷举的算法，即从左往右每一个位置都依此尝试填入一个数，看能不能填完这 n 个空格，在程序中我们可以用「回溯法」来模拟这个过程。
我们定义递归函数 backtrack(idx,perm) 表示当前排列为 perm，下一个待填入的位置是第 idx 个位置（下标从 0 开始）。那么整个递归函数分为两个情况：
如果 idx=n，说明我们已经填完了 n 个位置，找到了一个可行的解，我们将 perm 放入答案数组中，递归结束。
如果 idx<n，我们要考虑第 idx 个位置填哪个数。根据题目要求我们肯定不能填已经填过的数，因此很容易想到的一个处理手段是我们定义一个标记数组 vis 来标记已经填过的数，那么在填第 idx 个数的时候我们遍历题目给定的 n 个数，如果这个数没有被标记过，我们就尝试填入，并将其标记，继续尝试填下一个位置，即调用函数 backtrack(idx+1,perm)。搜索回溯的时候要撤销该个位置填的数以及标记，并继续尝试其他没被标记过的数。
但题目解到这里并没有满足「全排列不重复」 的要求，在上述的递归函数中我们会生成大量重复的排列，因为对于第 idx 的位置，如果存在重复的数字 i，我们每次会将重复的数字都重新填上去并继续尝试导致最后答案的重复，因此我们需要处理这个情况。
要解决重复问题，我们只要设定一个规则，保证在填第 idx 个数的时候重复数字只会被填入一次即可。而在本题解中，我们选择对原数组排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」，即如下的判断条件：
java
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}链接：https://leetcode.cn/problems/permutations-ii/solutions/417937/quan-pai-lie-ii-by-leetcode-solution/
java
class Solution {
List<List<Integer>> result = new ArrayList<>();
Deque<Integer> path = new LinkedList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
boolean[] used = new boolean[21];
Arrays.fill(used, false);
Arrays.sort(nums);
backTracking(nums, used);
return result;
}
public void backTracking(int[] nums, boolean[] used) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
if (!used[i]) {
path.add(nums[i]);
used[i] = true;
backTracking(nums, used);
used[i] = false;
path.removeLast();
}
}
}
}关于去重的拓展
大家发现，去重最为关键的代码为：
cpp
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}如果改成 used[i - 1] == true， 也是正确的!，去重代码如下：
cpp
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {
continue;
}这是为什么呢，就是上面我刚说的，如果要对树层中前一位去重，就用used[i - 1] == false，如果要对树枝前一位去重用used[i - 1] == true。
对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！
这么说是不是有点抽象？
来来来，我就用输入: [1,1,1] 来举一个例子。
树层上去重(used[i - 1] == false)，的树形结构如下：
树枝上去重（used[i - 1] == true）的树型结构如下：
大家应该很清晰的看到，树层上对前一位去重非常彻底，效率很高，树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。
N皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2：
输入：n = 1
输出：[["Q"]]提示：
1 <= n <= 9
根据题目可得约束条件：
- 不能在同一列
- 不能在同一行
- 不能在同一斜线
根据约束条件画出树形图，以n = 3为例：
三部曲
- 确定参数和返回值
每一次递归都是往棋盘走下一层，所以需要一个row记录当前的行数，每次单层遍历的时候都是从0开始一直到最后一列，所以需要最大列数，即n，不需要startIndex，还需要一个二维数组来表示棋盘。 - 确定递归终止条件
走到叶子节点就代表了找到一种布局，此时添加入结果集直接return即可。 - 确定单层递归逻辑
递归层数就是棋盘的行数，单层for循环从0开始
java
class Solution {
List<List<String>> result = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
char[][] board = new char[n][n];
for (char[] row : board) {
Arrays.fill(row, '.');
}
backTracking(n, 0, board);
return result;
}
public void backTracking(int n, int row, char[][] board) {
if (row == n) {
result.add(charToStringList(board));
return;
}
for (int i = 0; i < n; i++) {
if (isValid(row, i, board)) {
board[row][i] = 'Q';
backTracking(n, row + 1, board);
board[row][i] = '.';
}
}
}
private boolean isValid(int row, int col, char[][] board) {
// 检查同一列
for (int i = row; i >= 0; i--) {
if (board[i][col] == 'Q') {
return false;
}
}
// 检查45° 单位圆基准轴
for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
if (board[i][j] == 'Q') {
return false;
}
}
// 检查135° 单位圆基准轴
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') {
return false;
}
}
return true;
}
private List<String> charToStringList(char[][] board) {
List<String> list = new ArrayList<>();
for (char[] chars : board) {
list.add(String.valueOf(chars));
}
return list;
}
}作者：LSL
类型：原创
本文链接：https://lslshiba.top/article/12
此文章版权归LSL所有，如有转载请注明原作者。