《剑指Offer》刷题笔记
思维导图
- 力扣和牛客《剑指Offer》对比刷题笔记，题解大多是力扣题解区大佬智慧的结晶，个人学习使用
数组
剑指03 数组中重复的数字
题目：找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3
分析：
- 条件给了数组长度为n，元素范围为0到n-1，显然是想让我们使用下标和元素值对应
- 数字存在重复，很容易想到index==nums[index],第一次遇到肯定是不返回
- 当index!=nums[index]
- 第二次遇见nums[index]==nums[nums[index]],就是该元素重复，直接返回
- 否则，即不是未重复的也不是下标对应的，那就是未排序乱序的其他元素，交换nums[index]与index上元素，使其归位
public class Solution {
// 题目：nums长度为n，数字为0到n-1，有些数字重复了，找出任意重复的一个数字
// 方法:数组下标与元素对应
public int findRepeatNumber(int[] nums) {
int index = 0;
while (index < nums.length) {
// 元素值和坐标对应，遍历指针后移+进行下次循环
if (nums[index] == index) {
index++;
continue;
}
// 当元素值和坐标不对应
// 情况1：第二次来到该位置，就是重复元素
if (nums[index] == nums[nums[index]]) {
return nums[index];
} else {// 情况2：归位，让其归位到第一次出现的位置
int temp = nums[index];
nums[index] = nums[temp];
nums[temp] = temp;
}
}
return -1;
}
} 牛客JZ50
public class JZ50 {
public int duplicate(int[] numbers) {
int index = 0;
// 不能用for，因为只有index == numbers[index]才index++
while (index <= numbers.length - 1) {
// 元素值和坐标对应，遍历指针后移+进行下次循环
if (index == numbers[index]) {
index++;
continue;
}
// 当元素值和坐标不对应
// 情况1：第二次来到该位置，就是重复元素
if (numbers[index] == numbers[numbers[index]]) {
return numbers[index];
} else {
// 情况2：归位，让其归位到第一次出现的位置
int temp = numbers[index];
numbers[index] = numbers[temp];// temp既是记录数还是记录下标
numbers[temp] = temp;
}
}
return -1;
}
public static void main(String[] args) {
JZ50 jz50 = new JZ50();
int[] arr = {2, 3, 1, 0, 2, 5, 3};
System.out.println(jz50.duplicate(arr));
}
}
剑指04 二维数据的查找
题目:在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下： [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
分析：双指针
因为二维数组行列值都是递增的，首选二分法
双指针问题：以左下角坐标
[matrix.len-1][0]开始进行二分查找
- 小于，列+1
- 大于，行-1
- 等于，皆大欢喜直接返回true
public class Solution {
// 二分搜索法:从矩阵左下角开始
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) {
return false;
}
// 最左下角坐标:[matrix.length-1][0]
int i = matrix.length - 1;
int j = 0;
while (i >= 0 && j <= matrix[0].length - 1) {
if (matrix[i][j] < target) {
j++;
} else if (matrix[i][j] > target) {
i--;
} else {
return true;
}
}
return false;
}
} 牛客JZ1
public class JZ1 {
public boolean Find(int target, int[][] array) {
if (array == null || array.length == 0) {
return false;
}
int i = array.length - 1;
int j = 0;
while (i >= 0 && j < array[0].length) {
if (array[i][j] < target) {
j++;
} else if (array[i][j] > target) {
i--;
} else {
return true;
}
}
return false;
}
}
剑指11 旋转数组的最小值
题目:把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
示例 1：
输入：[3,4,5,1,2] 输出：1
示例 2：
输入：[2,2,2,0,1] 输出：0
分析：
正常递增数组查找某个元素，确定好
target就行，使用二分法就好旋转递增数组的一部分，说明某一部分一定是递增排序好的，定义
target=右边界值来二分
- 小于，和未旋转二分查找类似=最小值在左边，但因为要包含右边界确定target，所以right=mid
- 大于，最小值在右边，mid已经检查过，left=mid+1
- 等于，无法确定最小值在左边还是右边，前移右边界重新循环，right-–
示例一 [1, 0, 1, 1, 1] 示例二 [1, 1, 1, 0, 1]
循环条件
left<rightorleft<=right皆可，但返回值一定是nums[left]，因为最小值一定先碰到left返回值：二分结束，
left指向旋转数组最小值，返回nums[left]
public class Solution {
// 旋转数组的最小值
public int minArray(int[] numbers) {
int left = 0;
int right = numbers.length - 1;
// 循环条件是<;二分查找是<=
while (left < right) {
int mid = left + (right - left) / 2;
// 数组部分旋转,目标值改为数组最右边元素
int target = numbers[right];
if (numbers[mid] < target) {
// 中间值<右边值 = 右边递增
// 最小值在左边,取得到mid
right = mid;
} else if (numbers[mid] > target) {
// 中间值>右边值 = 右边递减
// 最小值在右边,取不到mid
left = mid + 1;
} else {
// 中间值=右边值,无法判断在左边还是右边,但最小值一定靠近左边,缩小mid=缩小target=right--
right--;
}
}
// 返回值是left位置的数
return numbers[left];
}
} 牛客JZ6
public class JZ6 {
public int minNumberInRotateArray(int[] arr) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int target = arr[right];
if (arr[mid] < target) {
right = mid;
} else if (arr[mid] > target) {
left = mid + 1;
} else {
right--;
}
}
return arr[left];
}
} 剑指21 奇数位于偶数前面
题目:输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
示例：
输入：nums = [1,2,3,4] 输出：[1,3,2,4] 注：[3,1,2,4] 也是正确的答案之一。
分析：
- 双指针，
i遍历前面，j遍历后面
- i遇到非偶数就后移，j遇到偶数就前移
- 遍历到
i=j就结束,因为一个数不用交换,所以循环条件是while(i<j)
public class Solution {
// 双指针法：left为奇数就后移，right为偶数就前移
public int[] exchange(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
while (left < right && (nums[left] % 2) != 0) {
left++;
}
while (left < right && (nums[right] % 2) == 0) {
right--;
}
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
return nums;
}
} 牛客JZ13
注意：牛客此题要求保持奇偶相对次序不改变
public int[] reOrderArray(int[] array) {
int[] res = new int[array.length];
int index = 0;
// 先遍历奇数
for (int num : array) {
if (num % 2 != 0) {
res[index++] = num;
}
}
// 再遍历偶数
for (int num : array) {
if (num % 2 == 0) {
res[index++] = num;
}
}
return res;
} 剑指29 顺时针打印矩阵
题目:输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：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]
分析：
数组为空，返回空的一维数组
初始化左上角坐标
(tR,tC)=(0,0)，右下角坐标(dR,dC)=( matrix.length - 1,matrix[0].length - 1)初始化
res[matrix.length*matrix[0].length]和遍历index循环条件
while (tR <= dR && tC <= dC)，因为赋值给res时一个点也可以赋值
- 特殊情况：tR==dR或tC==dC，简单遍历赋值即可
- 一般情况：保证顺时针，生成一个遍历坐标（curR,curC）
- 左到右：先固定tR，动curC++
- 上到下：固定dC，动curR++
- 右到左：固定dR，动curC- -
- 下到上：固定tC，动curR- -
- curR,curC遍历时，遍历条件是！=即可，不能遍历到端点
public class Solution {
public int[] spiralOrder(int[][] matrix) {
// 输入空列，返回空数组
if (matrix.length == 0) {
return new int[0];
}
// 初始化左上角、右下角坐标
int tR = 0, tC = 0;
int dR = matrix.length - 1, dC = matrix[0].length - 1;
// 结果二维数组大小=原始数组大小
int[] res = new int[matrix.length * matrix[0].length];
// 数组遍历坐标
int index = 0;
while (tR <= dR && tC <= dC) {
index = spiralMatrix(matrix, index, res, tR++, tC++, dR--, dC--);
}
return res;
}
private int spiralMatrix(int[][] matrix, int index, int[] res, int tR, int tC, int dR, int dC) {
if (tR == dR) {// 子矩阵只有一行,就复制列
for (int i = tC; i <= dC; i++) {
res[index++] = matrix[tR][i];
}
} else if (tC == dC) {// 子矩阵只有一列,就复制行
for (int i = tR; i <= dR; i++) {
res[index++] = matrix[i][tC];
}
} else {// 一般情况
for (int i = tC; i < dC; i++) {
res[index++] = (matrix[tR][i]);
}
for (int i = tR; i < dR; i++) {
res[index++] = (matrix[i][dC]);
}
for (int i = dC; i > tC; i--) {
res[index++] = (matrix[dR][i]);
}
for (int i = dR; i > tR; i--) {
res[index++] = (matrix[i][tC]);
}
}
return index;
}
} 牛客JZ19
public class Solution1 {
// 牛客:顺时针打印矩阵，与力扣的区别是返回值不一样
public ArrayList<Integer> printMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return new ArrayList<>();
}
ArrayList<Integer> res = new ArrayList<>();
int tR = 0, tC = 0;
int dR = matrix.length - 1, dC = matrix[0].length - 1;
while (tR <= dR && tC <= dC) {
print(matrix, res, tR++, tC++, dR--, dC--);
}
return res;
}
private void print(int[][] matrix, ArrayList<Integer> res, int tR, int tC, int dR, int dC) {
// 只有一行一列时，i可以到端点
if (tR == dR) {
for (int i = tC; i <= dC; i++) {
res.add(matrix[tR][i]);
}
} else if (tC == dC) {
for (int i = tR; i <= dR; i++) {
res.add(matrix[i][tC]);
}
} else {// 一般情况时，i不能到端点
for (int i = tC; i < dC; i++) {
res.add(matrix[tR][i]);
}
for (int i = tR; i < dR; i++) {
res.add(matrix[i][dC]);
}
for (int i = dC; i > tC; i--) {
res.add(matrix[dR][i]);
}
for (int i = dR; i > tR; i--) {
res.add(matrix[i][tC]);
}
}
}
public static void main(String[] args) {
Solution1 solution1 = new Solution1();
int[][] m = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
ArrayList<Integer> res = solution1.printMatrix(m);
// 正确：[1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]
System.out.println(res);
}
} 剑指39 次数超一半的数
题目:数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]输出: 2
分析：
- 摩尔投票法
- 初始化：cur记录当前数字和count记录当前数字出现的次数
- 处理情况：遍历数组
- count==0时，更新cur==num
- 更新cur完毕后，如果再遇到cur==num，count+1；否则count-1
- 返回：最后返回cur
- 排序法
- 数组中次数超过一半的数字，一定在排序后的数组中的中间位置，直接返回中间位置即可
- Hash法
- 遍历数组，使用哈希表统计<元素，次数>，同时比较次数最大值
- 遍历哈希表，取出次数最大值的key，就是次数超过一半的数字
public class Solution {
// 方法1:摩尔投票法
// 出现次数超过一半的数，一定不会被抵消掉，最后留下的一定是它
public int majorityElement(int[] nums) {
int cur = 0, count = 0;
for (int num : nums) {
// count = 0 说明需要更新cur为当前数字
if (count == 0) {
cur = num;
}
// cur遇见相同数字，就count+1;否则count-1
if (cur == num) {
count++;
} else {
count--;
}
}
return cur;
}
// 方法2:排序法
public int majorityElement1(int[] nums) {
Arrays.sort(nums);
// 因为数组中一定有超过半数以上的数,排序后中间元素一定是它
return nums[nums.length / 2];
}
// 方法3:哈希法
public int majorityElement2(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
int maxCount = 1;
// map存(元素,出现的次数),并且记录最多出现次数的个数
for (int num : nums) {
if (!map.containsKey(num)) {
map.put(num, 1);
} else {
map.put(num, map.get(num) + 1);
maxCount = Math.max(maxCount, map.get(num));
}
}
// 遍历map,返回最大次数的key
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() == maxCount) {
return entry.getKey();
}
}
throw new RuntimeException("not element");
}
} 牛客JZ28
public class JZ28 {
// 牛客：只能用摩尔投票法，其他方法限制了不能导包
public int MoreThanHalfNum_Solution(int[] nums) {
int cur = 0, count = 0;
for (int num : nums) {
if (count == 0) {
cur = num;
}
if (cur == num) {
count++;
} else {
count--;
}
}
return cur;
}
} 剑指45 数组排成最小的数
题目：输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]输出: "102"
示例 2:
输入: [3,30,34,5,9]输出: "3033459"
提示:
0 < nums.length <= 100
说明:
输出结果可能非常大，所以你需要返回一个字符串而不是整数拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
分析：
- 两个字符比较，按照小大排序的比较规则是：
(x, y) -> (x + y).compareTo(y + x)
- (x+y)<(y+x)，则x排序y的前面
- (x+y)>(y+x)，则x排序y的后面
- 证明见力扣题解评论区：如下
将nums数组转换为字符数组
利用库排序函数
Array.sort()将字符数组按照上诉的比较器规则进行比较将排序后的字符串数组，转换为字符串，就是排成的最小数
public class Solution {
// 调用Arrays.sort，速度最快
public String minNumber1(int[] nums) {
// 将nums转换为字符串数组
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
strs[i] = String.valueOf(nums[i]);
}
// 将strs按(x + y).compareTo(y + x)进行排序
Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
// 将排序后的strs转换为str返回
StringBuilder sb = new StringBuilder();
for (String str : strs) {
sb.append(str);
}
return sb.toString();
}
// 手写比较逻辑，速度较慢
public String minNumber2(int[] nums) {
if (nums == null || nums.length == 0) {
return "";
}
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
int x = nums[i];
int y = nums[j];
long num1 = Long.parseLong(x + "" + y);
long num2 = Long.parseLong(y + "" + x);
// 如果字符串：x+y>y+x，则y在前
if (num1 > num2) {
nums[i] = y;
nums[j] = x;
}
// 如果字符串：x+y<y+x，则x在前
}
}
StringBuilder sb = new StringBuilder();
for (int num : nums) {
sb.append(num);
}
return sb.toString();
}
} 牛客JZ32
public class JZ32 {
// 牛客：不能使用Arrays
public String PrintMinNumber(int[] numbers) {
if (numbers == null || numbers.length == 0) {
return "";
}
for (int i = 0; i < numbers.length; i++) {
for (int j = i + 1; j < numbers.length; j++) {
int x = numbers[i];
int y = numbers[j];
long num1 = Long.parseLong(x + "" + y);
long num2 = Long.parseLong(y + "" + x);
// 如果字符串：x+y>y+x，则y在前
if (num1 > num2) {
numbers[i] = y;
numbers[j] = x;
}
// 如果字符串：x+y<y+x，则x在前
}
}
StringBuilder sb = new StringBuilder();
for (int num : numbers) {
sb.append(num);
}
return sb.toString();
}
public static void main(String[] args) {
JZ32 jz32 = new JZ32();
int[] arr = {3, 32, 321};
String res = jz32.PrintMinNumber(arr);
// 正确：321323
System.out.println(res);
}
} 剑指51 数组中的逆序对
题目：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]输出: 5
分析：
- 逆序对问题，对应的就是归并排序，改变归并排序的一行代码即可
- 归并排序中merge中，合并两个数组到一个数组时，出现前面>后面，这时候的差值就是该论逆序对的数量
- Debug记录下计算的过程：条件，给arr={4,3,2,1}
- {4,3}：4>3，形成一个逆序对，数组变成{3,4}。{2,1}：形成一个逆序对，数组变成{1,2}
- {3,4,1,2}：3和1比较，3>1，形成2个逆序对；3和2比较，形成2个逆序对；
- 数组归并为{1,2,3,4}，结束
public class Solution {
// 将res作为参数传递,会出现各种问题,直接定义成员变量省事
private int res;
// 归并排序法，原理是利用nums[i]>nums[j],那么[i,mid]中都是逆序对个数
public int reversePairs(int[] nums) {
int[] temp = new int[nums.length];
res = 0;
mergeSort(nums, 0, nums.length - 1, temp);
return res;
}
private void mergeSort(int[] nums, int l, int r, int[] temp) {
if (l >= r) {
return;
}
int mid = l + (r - l) / 2;
mergeSort(nums, l, mid, temp);
mergeSort(nums, mid + 1, r, temp);
if (nums[mid] > nums[mid + 1]) {
merge(nums, l, mid, r, temp);
}
}
private void merge(int[] nums, int l, int mid, int r, int[] temp) {
System.arraycopy(nums, l, temp, l, r - l + 1);
int p = l, q = mid + 1;
for (int i = l; i <= r; i++) {
if (p > mid) {
nums[i] = temp[q++];
} else if (q > r) {
nums[i] = temp[p++];
} else if (temp[p] <= temp[q]) {
// <=区域不会形成逆序对,所以和归并排序过程一样
nums[i] = temp[p++];
} else {
// >说明必构成逆序对:[p,mid]与[mid+1,...]构成逆序对mid-p+1
// 注意：力扣题不要求% 1000000007
res += mid - p + 1;
nums[i] = temp[q++];
}
}
}
} 归并排序
public class MergeSort{
private MergeSort() {
}
public static void mergeSort(int[] arr) {
// 临时数组一开始就创建,传递到merge将arr复制给temp数组
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
}
private static void mergeSort(int[] arr, int l, int r, int[] temp) {
if (l >= r) {
return;
}
// 先递归,划分区域
int mid = l + (r - l) / 2;
mergeSort(arr, l, mid, temp);
mergeSort(arr, mid + 1, r, temp);
// 再归并,mid>前一个数才归并
if (arr[mid] > arr[mid + 1]) {
merge(arr, l, mid, r, temp);
}
}
private static void merge(int[] arr, int l, int mid, int r, int[] temp) {
System.arraycopy(arr, l, temp, l, r - l + 1);
int p = l, q = mid + 1;
for (int i = l; i <= r; i++) {
// 先判断两个指针越界的情况
if (p > mid) {
arr[i] = temp[q++];
} else if (q > r) {
arr[i] = temp[p++];
} else if (temp[p] <= temp[q]) {// 一般情况,比较辅助中的值,放回arr中
arr[i] = temp[p++];
} else {
arr[i] = temp[q++];
}
}
}
} 牛客JZ35
- 注意：牛客JZ35，需要取模
res = (res + mid - p + 1) % 1000000007
public class JZ35 {
// 牛客：要求结果% 1000000007
private int res;
public int InversePairs(int[] nums) {
int[] temp = new int[nums.length];
res = 0;
mergeSort(nums, 0, nums.length - 1, temp);
return res;
}
private void mergeSort(int[] nums, int l, int r, int[] temp) {
if (l >= r) {
return;
}
int mid = l + (r - l) / 2;
mergeSort(nums, l, mid, temp);
mergeSort(nums, mid + 1, r, temp);
if (nums[mid] > nums[mid + 1]) {
merge(nums, l, mid, r, temp);
}
}
private void merge(int[] nums, int l, int mid, int r, int[] temp) {
System.arraycopy(nums, l, temp, l, r - l + 1);
int p = l, q = mid + 1;
for (int i = l; i <= r; i++) {
if (p > mid) {
nums[i] = temp[q++];
} else if (q > r) {
nums[i] = temp[p++];
} else if (temp[p] <= temp[q]) {
// <=区域不会形成逆序对,所以和归并排序过程一样
nums[i] = temp[p++];
} else {
// >说明必构成逆序对:[p,mid]与[mid+1,...]构成逆序对mid-p+1
// 注意：牛客要求% 1000000007
res = (res + mid - p + 1) % 1000000007;
nums[i] = temp[q++];
}
}
}
} 剑指53-I 排序数组中查找数字
题目:统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6输出: 0
分析：
[5,7,7,8,8,10],t=8的出现的次数 = 10的下标-第一个8的下标 = 大于8的第一个数索引-大于7的第一个数索引定义一个函数获取
>k元素的第一个数索引，>k-1元素的第一个索引注意：
left≤right，因为等于时，也是一个数量次数不能忽略
public class Solution {
// 问题:在排序数组中统计数字出现的次数
// 二分法:因为数组有序找target,思考用二分法
public int search(int[] nums, int target) {
// [5,7,7,8,8,10],t=8的出现的次数
// 代码复用:8的次数=10的下标-第一个8的下标,发现可以复用二分查找代码
return getRightMargin(nums, target) - getRightMargin(nums, target - 1);
}
// 返回target右边第一个数下标
private int getRightMargin(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// 经验:二分法中<=就是返回t的右边界
if (arr[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
} 牛客JZ37
public class JZ37 {
public int GetNumberOfK(int[] array, int k) {
return rightBinarySearch(array, k) - rightBinarySearch(array, k - 1);
}
// 为了防止越界，返回等于目标值的最后一个坐标的下一个坐标
private int rightBinarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= target) {
left = mid + 1;
} else if (arr[mid] > target) {
right = mid - 1;
}
}
return left;
}
public static void main(String[] args) {
int[] arr1 = {1, 2, 3, 3, 3, 3};
int[] arr2 = {1, 3, 3, 3, 3, 4, 5};
JZ37 solution = new JZ37();
System.out.println(solution.GetNumberOfK(arr1, 3));
System.out.println(solution.GetNumberOfK(arr2, 2));
}
} 剑指53-II 缺失的数字
题目：一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1:
输入: [0,1,3]输出: 2
示例 2:
输入: [0,1,2,3,4,5,6,7,9]输出: 8
分析：
- 数组元素与下标对应完整,比如:[0]返回1,[0,1]返回2,[0,1,2]返回3
public class Solution {
public int missingNumber1(int[] nums) {
for (int i = 0; i < nums.length; i++) {
// 情况1:数组元素与下标对应完整,比如:[0]返回1,[0,1]返回2,[0,1,2]返回3
if (nums[i] == i && i == nums.length - 1) {
return nums.length;
}
// 情况2:数组元素与下标对应不完整,比如:[0,1,3]返回2
if (nums[i] != i) {
return nums[i] - 1;
}
}
return -1;
}
} 牛客无此题
说明：此题牛客没有原题，可以看看JZ40 出现一次的两个数
JZ40 出现一次的两个数
题目：一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
示例：
输入：[1,4,1,6]返回值：[4,6]说明：返回的结果中较小的数排在前面
分析：、
- 只有一个出现奇数次的数，其余出现偶数次
// Q:一个数为奇数次，其他数为偶数次
public static int question(int[] arr) {
int res = 0;
for (int cur : arr) {
res ^= cur;
}
return res;
} - 本题是有两个出现1次的数，其余出现2次，可以扩展为有两个出现奇数次的数，其余出现偶数次的数
- 利用上面的方法，可以获得数1^数2的结果
- 利用这个结果，可以找到数1和数2不相同的第一个二进制位（右往左）
- 再次遍历原数组，可以利用这个不相同的二进制位，因为出现偶数次的数还是会两两异或为0，就可以区分出两个数
- 注意：只能用！=0或者==0来判断是需要哪一个阵营
public int[] FindNumsAppearOnce(int[] array) {
int a = 0, b = 0;
// 第一次遍历,a = 数1^数2
for (int cur : array) {
a ^= cur;
}
// 找到a中第一个不相同的二进制位=数1和数2不相同的一个二进制位
// 由于是十进制表示，所以rightOne 是2^n的表示形式
int rightOne = a & (~a + 1);
a = 0;// 重置a为0，便于下面^操作
// 第二次遍历,利用不相同的二进制位,将原数组分为独立含数1和数2的两个部分
for (int cur : array) {
if ((rightOne & cur) == 0) {// 这里只能用！=0或者==0来判断是需要哪一个阵营
b ^= cur;
} else {
a ^= cur;
}
}
int num1 = Math.min(a, b);
int num2 = Math.max(a, b);
return new int[]{num1, num2};
} 剑指57-I 和为s的两个数
题目：输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
示例 1：
输入：nums = [2,7,11,15], target = 9输出：[2,7] 或者 [7,2]
示例 2：
输入：nums = [10,26,30,31,47,60], target = 40输出：[10,30] 或者 [30,10]
分析：
数组递增有序，要查找两个和为s的两个数，我们把s看成一个target+数组有序=用二分查找
定义两个首尾指针，注意遍历条件
while (left < right)，因为返回的是两个数，left=right直接停止循环确定target：
target = nums[left] + nums[right]，剩下的和标准二分查找一模一样
public class Solution {
public int[] twoSum(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum < target) {
// 数组有序,sum<t时,说明nums[left]不够大,所有与当前left要匹配的right都构不成t
left++;
} else if (sum > target) {
right--;
} else {
return new int[]{nums[left], nums[right]};
}
}
return new int[]{};
}
} 牛客JZ42
public class JZ42 {
public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
int left = 0;
int right = array.length - 1;
ArrayList<Integer> res = new ArrayList<>();
while (left < right) {
int temp = array[left] + array[right];
if (temp < sum) {
left++;
} else if (temp > sum) {
right--;
} else if (temp == sum) {
res.add(array[left]);
res.add(array[right]);
break;
}
}
return res;
}
public static void main(String[] args) {
JZ42 jz42 = new JZ42();
int[] arr = {1, 2, 4, 7, 11, 15};
int sum = 15;
System.out.println(jz42.FindNumbersWithSum(arr, sum));
}
} 剑指57-II 和为s的连续正数序列
题目:输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：
输入：target = 9输出：[[2,3,4],[4,5]]
示例 2：
输入：target = 15输出：[[1,2,3,4,5],[4,5,6],[7,8]]
分析：滑动窗口（双指针）
- 初始化：
i = 1, j = 2, sum = 3，i代表左边界的数，j代表右边界的数，sum表示这个边界的数字之和 - 根据示例，
list中暂存int[] - 循环结束条件：
i==j就结束，因为边界起码要2个数- 窗口太小，右移指针再窗口值加大
- 窗口太大，窗口值减少再左移指针
- 窗口值等于目标值,获取这一次的temp暂存进list中,再左移指针
- 返回值：
list转化为二维数组返回
public class Solution {
public int[][] findContinuousSequence(int target) {
// 初始化：窗口左右指针，窗口和
int left = 1, right = 2, windowsSum = 3;
// 根据示例，list中暂存int[]
List<int[]> list = new ArrayList<>();
while (left < right) {
if (windowsSum < target) {// 窗口太小，右移指针再窗口值加大
windowsSum += ++right;
} else if (windowsSum > target) {// 窗口太大，窗口值减少再左移指针
windowsSum -= left++;
} else {// 窗口值等于目标值
// 获取这一次的temp暂存进list中
int[] temp = new int[right - left + 1];
for (int i = left; i <= right; i++) {
temp[i - left] = i;
}
list.add(temp);
// 左移窗口
windowsSum -= left++;
}
}
// list转化为二维数组返回
return list.toArray(new int[0][]);
}
} 牛客JZ41
- 逻辑和力扣剑指57-II完全一样，可以换一种写法：
windowsSum > sum和windowsSum == sum移动指针的逻辑是相同的，我们可以把左移指针统一到windowsSum >= sum- 注意，此时
windowsSum == sum就要提前写，并且两个if和else分开
public class JZ41 {
// 生成目标数的连续正数序列
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
int left = 1;// 左边界的值
int right = 2;// 右边界的值
int windowsSum = 3;// 整个左右窗口的值
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
ArrayList<Integer> temp;
while (left < right) {// 左边界遇到右边界就停止
// 如果本轮区间和为sum，就生成结果集
if (windowsSum == sum) {
temp = new ArrayList<>();
for (int i = left; i <= right; i++) {
temp.add(i);
}
res.add(temp);
}
// 再进行移动窗口判断
if (windowsSum >= sum) {
windowsSum -= left++;// 窗口值不小于目标值，扩大窗口值=left前移1位
} else {
windowsSum += ++right;// 窗口值大于目标值，缩小窗口值=right后移1位
}
}
return res;
}
public static void main(String[] args) {
JZ41 jz41 = new JZ41();
int sum = 9;
System.out.println(jz41.FindContinuousSequence(sum));
}
} 剑指61 扑克牌中的顺子
题目:从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
示例 1:
输入: [1,2,3,4,5]输出: True
示例 2:
输入: [0,0,1,2,5]输出: True
分析：
- 高效判断是够是顺子的方式：
- 由于大小王是0，遇到大小王就跳过
- 除去大小王外，所有数不能有重复，利用set存放每个数组元素，以此来判断重复
- 除去大小王外，max-min<5；因为就算有2个大小王，max-min只会更小
public class Solution {
// 从一幅扑克牌中抽出5张牌,判断是否是顺子
public boolean isStraight(int[] nums) {
// set判断是否有重复的数
Set<Integer> set = new HashSet<>();
// 扑克牌顺子大小从大小王为0,A=1到K=13,范围[0,13]
int min = 13, max = 0;
// 遍历数组中每一个数字
for (int num : nums) {
// 如果是大小王,这一轮循环跳过
if (num == 0) {
continue;
} else {
// 不是大小王,
// 若有重复数字,必不可能构成顺子
if (set.contains(num)) {
return false;
} else {
// 若没有重复数字,找到当前的max,min
// 每一轮为必须满足判断顺子的条件:max-min<5
min = Math.min(min, num);
max = Math.max(max, num);
// 当前元素放进set中,给之后的遍历重复元素做铺垫
set.add(num);
}
}
}
// 返回整个数组中的max-min<5的布尔值
return max - min < 5;
}
} 牛客JZ45
- 牛客不能使用Set，所以定义两个函数判断是否包含和添加num
public class JZ45 {
public boolean IsContinuous(int[] numbers) {
// set判断是否有重复的数
boolean[] set = new boolean[14];
// 扑克牌顺子大小从大小王为0,A=1到K=13,范围[0,A,2...10,J,Q,K]
int min = 13, max = 0;
// 遍历数组中每一个数字
for (int num : numbers) {
// 如果是大小王,这一轮循环跳过
if (num == 0) {
continue;
} else {
// 不是大小王,
// 若有重复数字,必不可能构成顺子
if (contains(set, num)) {
return false;
} else {
// 若没有重复数字,找到当前的max,min
// 每一轮为必须满足判断顺子的条件:max-min<5
min = Math.min(min, num);
max = Math.max(max, num);
// 当前元素放进set中,给之后的遍历重复元素做铺垫
add(set, num);
}
}
}
// 返回整个数组中的max-min<5的布尔值
return max - min < 5;
}
private boolean contains(boolean[] set, int index) {
return set[index];
}
private void add(boolean[] set, int index) {
set[index] = true;
}
} 链表
剑指06 从头到尾打印链表
题目：输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]输出：[2,3,1]
分析：
- 辅助栈：最容易想到的方法，重点利用本题学习递归常见写法
- 遍历链表，用栈记录节点值
- 遍历栈，用一个数组记录栈顶的值，栈顶元素一次出栈
// 法1:辅助栈
public int[] reversePrint(ListNode head) {
// LinkedList继承了队列、栈,可以使用栈的push,pop的API
LinkedList<Integer> stack = new LinkedList<>();
while (head != null) {
stack.push(head.val);
head = head.next;
}
int[] res = new int[stack.size()];
for (int i = 0; i < res.length; i++) {
res[i] = stack.pop();
}
return res;
} - 递归法：先理解辅助栈法,体会递归本质这种先进后出的思想
- 递归第一次到，不记录值，因为我们从尾到头打印
- 递归第二次到，记录该节点值，放进一个List中
- 遍历List大小的res数组，依次将值放入res中
// 法2:递归法,先理解辅助栈法,体会递归本质这种先进后出的思想
public int[] reversePrint1(ListNode head) {
// 存放递归逆序后的值
List<Integer> temp = new ArrayList<>();
// 递归:本质上是一个先进后出的栈,temp中存放了逆序后的val
reverse(head, temp);
// 将List中的val遍历进一个返回值数组中即可
int[] res = new int[temp.size()];
for (int i = 0; i < temp.size(); i++) {
res[i] = temp.get(i);
}
return res;
}
private void reverse(ListNode node, List<Integer> temp) {
if (node == null) {
return;
}
reverse(node.next, temp);
// 下一层递归结束,接受这一层的node.val
temp.add(node.val);
} 牛客JZ3
public class JZ3 {
// 牛客此题返回值是List，比力扣的返回值是int[]要方便很多
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if (listNode == null) {
return new ArrayList<>();
}
ArrayList<Integer> res = new ArrayList<>();
process(listNode, res);
return res;
}
private void process(ListNode node, ArrayList<Integer> res) {
if (node == null) {
return;
}
process(node.next, res);
res.add(node.val);
}
} 剑指18 删除链表结点
题目：给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。
示例 1:
输入: head = [4,5,1,9], val = 5输出: [4,1,9]解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], val = 1输出: [4,5,9]解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明：
题目保证链表中节点的值互不相同
若使用 C 或 C++ 语言，你不需要
free或delete被删除的节点
分析：
- 法1：双指针版，pre和cur
// 法1:双指针版
public ListNode deleteNode1(ListNode head, int val) {
// 1.判断head是否为待删除结点,不是就初始化cur和pre
if (head == null) {
return null;
}
if (head.val == val) {
return head.next;
}
// 2.初始化pre和cur
ListNode pre = head;
ListNode cur = head.next;
// 3.cur遍历直到cur.val==val结点
while (cur != null && cur.val != val) {
pre = cur;
// 由于cur指向了下一个结点,while条件增加cur!=null
cur = cur.next;
}
// 4.循环跳出,当cur!=null时,肯定指向待删除结点
if (cur != null) {
pre.next = cur.next;
}
return head;
} - 法2：单指针版，cur遍历到待删除结点的前一个位置
// 法2:单指针版
public ListNode deleteNode2(ListNode head, int val) {
if (head == null) {
return null;
}
if (head.val == val) {
return head.next;
}
ListNode cur = head;
// cur遍历到待删除结点的前一个位置
while (cur.next != null && cur.next.val != val) {
cur = cur.next;
}
if (cur.next != null) {
cur.next = cur.next.next;
}
return head;
} JZ56 删除重复结点
题目：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针
示例：
输入：{1,2,3,3,4,4,5}返回值：{1,2,5} 分析：
- NC24 删除有序链表中重复的元素II同题，注意是删除重复结点不保留
public class JZ56 {
// 升序链表删除重复结点
public ListNode deleteDuplication(ListNode pHead) {
if (pHead == null || pHead.next == null) {
return pHead;
}
ListNode dummy = new ListNode(-1);
ListNode pre = dummy;
ListNode cur = pHead;
while (cur != null) {
// 没有后继||前后不一致，就加入pre后继
if (cur.next == null || cur.val != cur.next.val) {
pre.next = cur;
pre = cur;
}
// 否则，就一直后移cur，让cur指向相同节点的最后一个节点
while (cur.next != null && cur.val == cur.next.val) {
cur = cur.next;
}
// 本题不保留重复结点，这里不用pre.next = cur
// 相同节点的最后一个结点不保留，后移cur
cur = cur.next;
}
pre.next = null;
return dummy.next;
}
} 剑指22 链表倒数第k个结点
题目:输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.返回链表 4->5.
分析：
第一反应是先遍历一遍链表，记录链表长度
n，然后n-k+1就是要返回的链表，但是这样时间复杂度较高使用双指针就只用遍历一遍数组
- 初始化：fast,slow都指向head
- fast先走k步，保证fast和slow距离k个单位
- 然后fast和slow同时移动，当fast移动到null时，slow指向倒数第k个节点
- 返回slow
public class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
// 1.快指针先走k步
while (k > 0) {
// 快指针每次都要判断是否为null,注意边界问题
if (fast == null) {
return null;
}
fast = fast.next;
k--;
}
// 2.当快指针走到末尾节点的下一个节点=null时,slow走到倒数第K个节点
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
} 牛客JZ14
public class JZ14 {
public ListNode FindKthToTail(ListNode pHead, int k) {
ListNode fast = pHead, slow = pHead;
while (k > 0) {
if (fast == null) {
return null;
}
fast = fast.next;
k--;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
} 剑指24 反转链表
题目:定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL
分析：
- 迭代法
// 法1:迭代法
public ListNode reverseList1(ListNode head) {
ListNode cur = head;
// pre只是记录cur的前一个结点,不会使用到任何next结点
ListNode pre = null;
while (cur != null) {
// 一定是先记录cur后一个节点
ListNode next = cur.next;
// 从cur开始改变指向
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
} - 递归法
// 法2:递归法
public ListNode reverseList2(ListNode head) {
// base case：参数head为null，或者此时递归的head无下一个结点
if (head == null || head.next == null) {
return head;
}
// 开始递归，head.next为下一轮的head1，当head1.next=null递归停止
// 此时head1位整个链表的末尾节点（反转链表后的头结点），这一轮的head为倒数第二个节点
ListNode ret = reverseList2(head.next);
// head为倒数第二个节点，开始反转最后的两个链表
head.next.next = head;
// 倒数第二个节点next判空,供上一层调用
head.next = null;
return ret;
} 牛客JZ15
public class Solution {
public ListNode ReverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode ret = ReverseList(head.next);
head.next.next = head;
head.next = null;
return ret;
}
} 剑指25 合并两个有序链表
题目：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1：
输入：1->2->4, 1->3->4输出：1->1->2->3->4->4
限制：
0 <= 链表长度 <= 1000
分析：
- 两个有序链表的合并，和合并两个有序数组非常相似，对比代码学习+两项归并排序merge过程
public class Solution {
// 法1:迭代法
public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
// 设定一个哑结点,方便返回值
ListNode dummyNode = new ListNode(-1);
// cur指针指向每次比较的较小值结点
ListNode cur = dummyNode;
while (l1 != null && l2 != null) {
// 判断较小值,cur指向它
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
// 判断完后移cur
cur = cur.next;
}
// 循环结束,cur指向非空链表头部
cur.next = (l1 == null) ? l2 : l1;
return dummyNode.next;
}
// 法2:递归法
public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
// 递归结束情况1:某个链表遍历到了末尾
if (l1 == null || l2 == null) {
return l1 == null ? l2 : l1;
}
// 递归判断，每一次都返回最小值结点进递归栈
if (l1.val <= l2.val) {
l1.next = mergeTwoLists2(l1.next, l2);
// 递归结束条件2:返回某个链表的最小值结点
return l1;
} else {
l2.next = mergeTwoLists2(l1, l2.next);
// 递归结束条件2:返回某个链表的最小值结点
return l2;
}
}
} 力扣88 合并两个有序数组
public class Solution {
// 方法1:双指针,从前往后遍历两个数组,需要辅助数组
public static void merge1(int[] nums1, int m, int[] nums2, int n) {
// temp存储每次排序好的数组
int[] temp = new int[m + n];
// p遍历nums1,q遍历nums2,i遍历temp
int p = 0, q = 0, i = 0;
while (p < m && q < n) {
temp[i++] = nums1[p] < nums2[q] ? nums1[p++] : nums2[q++];
}
while (p < m) {
temp[i++] = nums1[p++];
}
while (q < n) {
temp[i++] = nums2[q++];
}
// 将temp数组遍历回nums1
System.arraycopy(temp, 0, nums1, 0, m + n);
}
// 方法2:双指针,从后往前遍历两个数组,放最大,不需要辅助数组
public static void merge2(int[] nums1, int m, int[] nums2, int n) {
int p = m - 1, q = n - 1, i = m + n - 1;
// 从后往前找大的放入nums1中
while (p >= 0 && q >= 0) {
nums1[i--] = nums1[p] < nums2[q] ? nums2[q--] : nums1[p--];
}
// p<0上面遍历结束,此时q还没遍历到0,将nums2从[0,q+1)复制到nums1中
System.arraycopy(nums2, 0, nums1, 0, q + 1);
}
} 牛客JZ16
public class JZ16 {
public ListNode Merge(ListNode list1, ListNode list2) {
ListNode p = list1, q = list2;
ListNode dummy = new ListNode(-1);
ListNode pre = dummy;
// 是与的关系
while (p != null && q != null) {
if (p.val < q.val) {
pre.next = p;
pre = p;
p = p.next;
} else {
pre.next = q;
pre = q;
q = q.next;
}
}
// 最后谁不为空，指向谁
pre.next = p != null ? p : q;
return dummy.next;
}
} 剑指35 复制链表的复制
题目：请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
分析：难点是怎么记录random指针
常用方法是map,但是牛客禁用了Map包，所以我们不用Map，使用有线几个变量即可
原链表每个结点后接上一个复制val的新结点
更新复制链表的random结点
原链表和复制链表分开
public class Solution {
// 复制含有random结点的链表，常用方法是map,但是牛客禁用了Map包
// 不用Map，用有限几个变量完成复制
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
Node cur = head;
Node curNext;
// 原链表结点后接上一个复制val的结点
while (cur != null) {
curNext = cur.next;
cur.next = new Node(cur.val);// 复制的是cur.val的值
cur.next.next = curNext;
cur = curNext;
}
// 更新复制链表的random结点
cur = head;
Node copyCur;
while (cur != null) {
curNext = cur.next.next;
copyCur = cur.next;
// 复制random指针时先判null
copyCur.random = (cur.random != null) ? cur.random.next : null;
cur = curNext;
}
cur = head;
Node copyHead = cur.next;
while (cur != null) {
curNext = cur.next.next;
copyCur = cur.next;
cur.next = curNext;// cur连接会原来的next
// copy结点连接时先判next是否null
copyCur.next = (curNext != null) ? curNext.next : null;
cur = curNext;
}
return copyHead;
}
} 牛客JZ35
public class JZ35 {
// 牛客不能用map传统解法，
public RandomListNode Clone(RandomListNode pHead) {
if (pHead == null) {
return null;
}
RandomListNode cur = pHead;
RandomListNode next;
// 原链表结点后接上一个复制label的新结点
while (cur != null) {
next = cur.next;
cur.next = new RandomListNode(cur.label);
cur.next.next = next;
cur = next;
}
cur = pHead;
RandomListNode curCopy;
// 更新复制链表的random结点
while (cur != null) {
next = cur.next.next;
curCopy = cur.next;
curCopy.random = (cur.random != null) ? cur.random.next : null;
cur = next;
}
RandomListNode copyHead = pHead.next;
cur = pHead;
// 断开原结点和复制结点
while (cur != null) {
next = cur.next.next;
curCopy = cur.next;
cur.next = next;
curCopy.next = (next != null) ? next.next : null;
cur = next;
}
return copyHead;
}
public static void main(String[] args) {
JZ35 jz35 = new JZ35();
RandomListNode n1 = new RandomListNode(1);
RandomListNode n2 = new RandomListNode(2);
RandomListNode n3 = new RandomListNode(3);
RandomListNode n4 = new RandomListNode(4);
RandomListNode n5 = new RandomListNode(5);
n1.next = n2;
n1.random = n3;
n2.next = n3;
n2.random = n5;
n3.next = n4;
n3.random = n5.next;
n4.next = n5;
n4.random = n2;
RandomListNode copyHead = jz35.Clone(n1);
System.out.println(copyHead.label);
}
} 剑指52 两个链表的第一个相交结点
题目：输入两个链表，找出它们的第一个公共节点。
注意：
如果两个链表没有交点，返回 null.在返回结果后，两个链表仍须保持原有的结构可假定整个链表结构中没有循环。程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
分析：
定义一个
len来记录链表差值，cur1先遍历链表A，len+1；cur2再遍历链表B，len-1判断不相交：两个链表的遍历指针，遍历到链表末尾，最后不相等就是不相交
len取绝对值，因为差值可能为负cur1指向较长的头结点，cur2指向较短的头结点，让指向较长头结点的cur1先走len步cur1、cur2后移直到cur1==cur2，此时必相交，返回cur1 || cur2即可
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode cur1 = headA;
ListNode cur2 = headB;
// len记录两个链表长度差值
int len = 0;
while (cur1.next != null) {
len++;
cur1 = cur1.next;
}
while (cur2.next != null) {
len--;
cur2 = cur2.next;
}
// 如果两个遍历指针遍历到末尾不相等,两个链表必不交
if (cur1 != cur2) {
return null;
}
// cur1指向较长的链表
cur1 = (len > 0 ? headA : headB);
// cur2指向较短的链表
cur2 = (cur1 == headA ? headB : headA);
// 长度差可能为负,len取绝对值
len = Math.abs(len);
// 由于cur1指向长的，先走len步
while (len > 0) {
cur1 = cur1.next;
len--;
}
// cur1和cur2再一起走
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
} 牛客JZ36
public class JZ36 {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if (pHead1 == null || pHead2 == null) {
return null;
}
ListNode cur1 = pHead1;
ListNode cur2 = pHead2;
int len = 0;
while (cur1 != null) {
cur1 = cur1.next;
len++;
}
while (cur2 != null) {
cur2 = cur2.next;
len--;
}
if (cur1 != cur2) {
return null;
}
cur1 = len > 0 ? pHead1 : pHead2;
cur2 = cur1 == pHead1 ? pHead2 : pHead1;
len = Math.abs(len);
while (len > 0) {
cur1 = cur1.next;
len--;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
} 字符串
剑指05 替换空格
题目:请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = "We are happy."输出："We%20are%20happy."
分析：
因为要改变字符串,单线程使用
StringBuilder来append()方便字符串定位字符：
s.charAt(i)
- 匹配到就改变
public class Solution {
// 替换空格
public String replaceSpace(String s) {
// 单线程用StringBuilder更快
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) != ' ') {
sb.append(s.charAt(i));
} else {
sb.append("%20");
}
}
return sb.toString();
}
} 牛客JZ02
public class JZ02 {
public String replaceSpace(String s) {
if (s == null || s.length() == 0) {
return "";
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ' ') {
sb.append("%20");
} else {
sb.append(s.charAt(i));
}
}
return sb.toString();
}
} 剑指20 表示数值的字符串
题目：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
数值（按顺序）可以分成以下几个部分：
若干空格
一个 小数 或者 整数
（可选）一个 'e' 或 'E' ，后面跟着一个 整数
若干空格
小数（按顺序）可以分成以下几个部分：
（可选）一个符号字符（'+' 或 '-'）
下述格式之一：
1. 至少一位数字，后面跟着一个点 '.'
2. 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
3. 一个点 '.' ，后面跟着至少一位数字
整数（按顺序）可以分成以下几个部分：
（可选）一个符号字符（'+' 或 '-'）
至少一位数字
部分数值列举如下：
["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]
部分非数值列举如下：
["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]
示例 1：
输入：s = "0"输出：true
示例 2：
输入：s = "e"输出：false
示例 3：
输入：s = "."输出：false
示例 4：
输入：s = " .1 "输出：true
提示：
1 <= s.length <= 20s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，空格 ' ' 或者点 '.' 。
分析：
- 判断
true情况太多，我们思考判断false情况，定义四种布尔值
- hasNum，hasSign，hasE，hasDot
遍历指针：
index清除字符串前面空格，
index++while(index<n)判断
- 先判断数字部分，直到遇到非数字 or 直接到达字符串末尾，返回ture
- 再判断非数字部分
- 判断E：如果之前有E or 之前无数字，返回false；否则hasE=true，其余三个重置false
- 判断+，-：如果之前有+，- or 有数字 or 有.，返回false；否则hasSign=true
- 判断.：如果之前有. or 有E，返回false；否则hasDot=true
- 遇到空格，直接结束循环，因为此时index不可能再等于n，结果也为false
- index++
清除字符串后面空格，
index++返回：
hasNum && index == n
public class Solution {
public boolean isNumber(String s) {
int n = s.length();
int index = 0;
boolean hasNum = false;
boolean hasE = false;
boolean hasSign = false;
boolean hasDot = false;
// 清除前面的空格
while (index < n && s.charAt(index) == ' ') {
index++;
}
while (index < n) {
// 1.先判断数字
while (index < n && s.charAt(index) >= '0' && s.charAt(index) <= '9') {
hasNum = true;
index++;
}
// 如果此时循环已到字符串末尾
if (index == n) {
break;
}
// 2.判断非数字部分
if (s.charAt(index) == 'E' || s.charAt(index) == 'e') {
if (hasE || !hasNum) {
return false;
}
hasE = true;
// E出现后,需要重新判断四个情况=重新置空
hasNum = false;
hasDot = false;
hasSign = false;
} else if (s.charAt(index) == '+' || s.charAt(index) == '-') {
if (hasSign || hasNum || hasDot) {
return false;
}
hasSign = true;
} else if (s.charAt(index) == '.') {
if (hasDot || hasE) {
return false;
}
hasDot = true;
} else if (s.charAt(index) == ' ') {// 遇到中间的空格,循环结束,判断index长度
break;
} else {
return false;
}
// 3.指针后移
index++;
}
// 清除后面的空格
while (index < n && s.charAt(index) == ' ') {
index++;
}
// 判断条件:有数字且index遍历到n
return hasNum && index == n;
}
} 剑指38 字符串的排列
题目：输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"输出：["abc","acb","bac","bca","cab","cba"]
分析：
当字符串存在重复字符时，排列方案中也存在重复的排列方案。为排除重复方案，需在固定某位字符时，保证 “每种字符只在此位固定一次"=剪枝
定义一个递归函数
dfs，剪枝+回溯模版如下：
private void dfs(int pos) {
// base case：固定位置来到最后一个字符
if (pos == cs.length - 1) {
res.add(String.valueOf(cs));
return;
}
// ...
// 从固定位置pos往后开始递归其他分支
for (int i = pos; i < cs.length; i++) {
// 判断去重，剪枝
// 交换,将cs[i]固定在pos位置
swap(i, pos);
// 递归固定后续index+1的位置
dfs(pos + 1);
// 回溯：交换回原数组顺序
swap(i, pos);
}
} public class Solution {
private char[] cs;
private List<String> res;
public String[] permutation(String s) {
if (s == null || s.length() == 0) {
return new String[]{};
}
res = new ArrayList<>();
cs = s.toCharArray();
dfs(0);
// 结果列表转换为字符串数组list.toArray(目标数组构造器)
return res.toArray(new String[0]);
}
// dfs：将cs中pos位置固定，然后开始递归后面数组组成排列
private void dfs(int pos) {
// base case：固定位置来到最后一个字符
if (pos == cs.length - 1) {
res.add(String.valueOf(cs));
return;
}
// 力扣可用各种API，牛客只能用ArrayList
HashSet<Character> set = new HashSet<>();
// 从固定位置pos往后开始递归其他分支
for (int i = pos; i < cs.length; i++) {
// 先判断i位置上之前递归是否出现过
// ≠return，因为i+1...还要继续递归
if (set.contains(cs[i])) {
continue;
}
set.add(cs[i]);
// 交换,将cs[i]固定在pos位置
swap(i, pos);
// 递归固定后续index+1的位置
dfs(pos + 1);
// 回溯：交换回原数组顺序
swap(i, pos);
}
}
private void swap(int a, int b) {
char temp = cs[a];
cs[a] = cs[b];
cs[b] = temp;
}
public static void main(String[] args) {
Solution solution = new Solution();
String s = "aab";
System.out.println(Arrays.toString(solution.permutation(s)));
}
} 牛客JZ27
public class JZ27 {
private char[] cs;
private ArrayList<String> res;
public ArrayList<String> Permutation(String str) {
if (str == null || str.length() == 0) {
return new ArrayList<>();
}
res = new ArrayList<>();
cs = str.toCharArray();
dfs(0);
return res;
}
private void dfs(int pos) {
if (pos == cs.length - 1) {
res.add(new String(cs));
return;
}
// 牛客题判断重复，导包只能用ArrayList，将就用
ArrayList<Character> set = new ArrayList<>();
for (int i = pos; i < cs.length; i++) {
if (set.contains(cs[i])) {
continue;
}
set.add(cs[i]);
swap(cs, i, pos);
dfs(pos + 1);
swap(cs, i, pos);
}
}
private void swap(char[] cs, int i, int j) {
char t = cs[i];
cs[i] = cs[j];
cs[j] = t;
}
} 剑指48 最长无重复子串长度
题目:请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
分析：
- 初始化：
- HashMap<Character, Integer>记录：当前元素，当前元素最近出现的下标
- pre = -1：str[i-1]为结尾的无重复子串的起始位置的前一个位置,初试值为-1，也就是说str[i-1]的无重复子串是从它的左边到pre截止的
- res = 0：记录每轮无重复子串的最大长度，初始为0
- len= 0：记录每轮无重复子串的长度，初始为0
- 遍历字符数组
- 假设map.get(chars[i])=i'
- 如果i'在pre右边,说明[i'+1,i]一定是chars[i]结尾的无重复子串
- pre每次指向i’和pre最右边的值，作为下一轮遍历chars[i-1]的pre值
- 所以这里就需要更新pre为i‘
- 如果i'在pre左边,说明[pre+1,i]一定是chars[i]结尾的无重复子串
- pre每次指向i’和pre最右边的值，作为下一轮遍历chars[i-1]的pre值
- 这里由于pre已经比i'大了，无需更新
- 记录len记录[此时的pre,i]的距离，res记录每轮的最大值
- 返回：
res即可
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.equals("")) {
return 0;
}
char[] cs = s.toCharArray();// s转化为字符数组，便于遍历和put
// map<该字符,该字符上次出现的位置下标>,初始化value全为-1
HashMap<Character, Integer> map = new HashMap<>();
for (char c : cs) {
map.put(c, -1);
}
int pre = -1;// pre:str[i-1]为结尾的无重复子串的起始位置的前一个位置,初试值为-1
int res = 0;// 记录区间最大的len
int len;// len记录每次max(pre,map.get(cs[i]))
for (int i = 0; i < cs.length; i++) {
if (map.get(cs[i]) >= pre) {// 假设map.get(chars[i])=i‘,如果i‘在pre右边,说明[i’+1,i]一定是chars[i]结尾的无重复子串
pre = map.get(cs[i]);// pre和i‘谁在右边,更新谁=作为下一轮chars[i-1]的起始位置前一位
len = i - map.get(cs[i]);
} else {// 如果i‘在pre左边,说明[pre+1,i]一定是chars[i]结尾的无重复子串
len = i - pre;
}
// 以上几句，可以统一为以下2句：记得住那句就写那句
// pre = Math.max(map.get(cs[i]), pre);
// len = i - pre;
res = Math.max(res, len);
// 更新map,记录元素与它最近出现的位置
map.put(cs[i], i);
}
return res;
}
public static void main(String[] args) {
Solution solution = new Solution();
String str = "aabcd";
int len1 = solution.lengthOfLongestSubstring(str);
System.out.println(len1);
}
} 剑指50 第一个只出现一次的字符
题目:在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例:
s = "abaccdeff"返回 "b"s = "" 返回 " "
限制：
0 <= s 的长度 <= 50000
分析：
- 尽量不使用特殊数据结构，只使用数组
public class Solution {
public char firstUniqChar(String s) {
if (s == null || "".equals(s)) {
return ' ';
}
// 尽量不使用特殊的数据结构，用数组存次数比较快
int[] map = new int[256];
for (int i = 0; i < s.length(); i++) {
map[s.charAt(i)]++;
}
for (int i = 0; i < s.length(); i++) {
if (map[s.charAt(i)] == 1) {
return s.charAt(i);
}
}
return ' ';
}
} 牛客JZ34
public class JZ34 {
public int FirstNotRepeatingChar(String str) {
if (str == null || "".equals(str)) {
return -1;
}
// 牛客不能用Map等数据结构，我们就想数组
int[] map = new int[256];
for (int i = 0; i < str.length(); i++) {
map[str.charAt(i)]++;
}
for (int i = 0; i < str.length(); i++) {
if (map[str.charAt(i)] == 1) {
return i;
}
}
return -1;
}
} 剑指58-I 反转单词顺序
题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
示例 1：
输入: "the sky is blue"输出: "blue is sky the"
示例 2：
输入: " hello world! "输出: "world! hello"解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: "a good example"输出: "example good a"解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
说明：
无空格字符构成一个单词。输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
分析：
先去掉首尾空格，调用
s.trim()index从后往前遍历原串s，last每次都记录非空单词的最后位置
- sb.append(trim, index + 1, last + 1).append(" ")最后要记得加空格" "
- 去掉每个单词后的空格
- while最后记得更新last=index，作为下一个单词的末尾位置
- 返回结果去掉末尾的空格
public class Solution {
// 双指针法,倒序遍历字符串
public String reverseWords(String s) {
// 去掉首尾空格
String trim = s.trim();
int last = trim.length() - 1;// 每个非空单词的末尾指针
int index = last;// 从后往前遍历字符串
StringBuilder sb = new StringBuilder();
while (index >= 0) {
// 获得非空单词起始位置的前一个位置
while (index >= 0 && trim.charAt(index) != ' ') {
index--;
}
// 添加：将这个单词添加进结果字符串中
// 注意：还要加” “
sb.append(trim, index + 1, last + 1).append(" ");
// 去掉每个单词后的空格
while (index >= 0 && trim.charAt(index) == ' ') {
index--;
}
// 更新每个单词的末尾指针
last = index;
}
// 返回结果去掉末尾的空格
return sb.toString().trim();
}
} 牛客 JZ44
public class JZ44 {
public String ReverseSentence(String str) {
String trim = str.trim();
int last = trim.length() - 1;
int index = last;
StringBuilder sb = new StringBuilder();
while (index >= 0) {
while (index >= 0 && trim.charAt(index) != ' ') {
index--;
}
sb.append(trim, index + 1, last + 1).append(" ");
while (index >= 0 && trim.charAt(index) == ' ') {
index--;
}
last = index;
}
return sb.toString().trim();
}
} 剑指58-II 左旋转字符串
题目:字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
示例 1：
输入: s = "abcdefg", k = 2输出: "cdefgab"
示例 2：
输入: s = "lrloseumgh", k = 6输出: "umghlrlose"
限制：
1 <= k < s.length <= 10000
分析：
如何一次遍历，将
[n,len-1]遍历加入结果字符中，然后[0,n-1]再加入结果字符中答：从
index =n开始取余计算i%len
public class Solution {
public String reverseLeftWords(String s, int n) {
int len = s.length();
StringBuilder sb = new StringBuilder();
// 原s:[0,n-1,n,...,len-1]
// 新sb:[n,...,len-1,len,...,n+len-1]
for (int i = n; i < n + len; i++) {
sb.append(s.charAt(i % len));
}
return sb.toString();
}
} 牛客JZ43
public class JZ43 {
public String LeftRotateString(String str, int n) {
if (str == null || "".equals(str)) {
return "";
}
int len = str.length();
StringBuilder sb = new StringBuilder();
// 原s:[0,n-1,n,...,len-1]
// 新sb:[n,...,len-1,len,...,n+len-1]
for (int i = n; i < n + len; i++) {
sb.append(str.charAt(i % len));
}
return sb.toString();
}
} 剑指67 字符串转换为整数
题目：写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:
输入: "42"输出: 42
示例 2:
输入: " -42"输出: -42解释: 第一个非空白字符为 '-', 它是一个负号。我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: "4193 with words"输出: 4193解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"输出: 0解释: 第一个非空字符是 'w', 但它不是数字或正、负号。因此无法执行有效的转换。
示例 5:
输入: "-91283472332"输出: -2147483648解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 因此返回 INT_MIN (−231) 。
分析：
可以正常转换的字符串分为整型的情况：首尾空格 + 符号位 + 数字拼接的字符串 + 非数字部门
数字部分是难点，
num接收数字部分拼接的字符串，有两种情况会越界：
- num>int最大值/10
- num=int最大值且当前拼接的数字是7（因为int类型最大值的个位数字是7）
遇到越界情况，直接返回当前符号位的最大值
没有越界，数字部分：
num = num * 10 + 当前字符代表的数字
public class Solution {
public int strToInt(String str) {
// 去掉首尾空格:原数组去首位空格后转换为字符数组
char[] c = str.trim().toCharArray();
if (c.length == 0) {
return 0;
}
int num = 0;
// num越界的两种情况:int型最大值21474836472147483647,末尾数为7,/10后为boundary
int maxBoundary = Integer.MAX_VALUE / 10;
// sign:负号标记,1正号,-1负号
int initIndex = 1, sign = 1;
// 第一个部分有三种情况:+/-/数字
if (c[0] == '-') {// -:遇到负号就sign成-1
sign = -1;
} else if (c[0] != '+') {// 剩下非数字,初始化指针=0
initIndex = 0;
}
for (int i = initIndex; i < c.length; i++) {
// 力扣：遇到非数字部分，可以忽略，直接当前得到的整数
if (c[i] < '0' || c[i] > '9') {
break;
}
// num越界的两种情况:int型最大值21474836472147483647,末尾数为7,/10后为boundary
// 1.num=最大值/10 且 c[i]>'7',乘积后必越界
// 2.num>最大值/10 乘积后必越界
if (num > maxBoundary || num == maxBoundary && c[i] > '7') {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
// 拼接数字部分
num = num * 10 + (c[i] - '0');
}
// 返回符号*数字
return sign * num;
}
} 牛客JZ49
- 牛客规定：不是合法数字或0都返回0
public class JZ49 {
public int StrToInt(String str) {
char[] c = str.trim().toCharArray();// 去掉
if (c.length == 0) {
return 0;
}
int num = 0;
// int型最大值21474836472147483647,末尾数为7,/10后为boundary
int maxBoundary = Integer.MAX_VALUE / 10;
int index = 1, sign = 1;
if (c[0] == '-') {
sign = -1;
} else if (c[0] != '+') {
index = 0;
}
for (int i = index; i < c.length; i++) {
// 牛客：遇到非数字部分，就返回0
if (c[i] < '0' || c[i] > '9') {
return 0;
}
// num越界的两种情况:int型最大值21474836472147483647,末尾数为7,/10后为boundary
// 1.num=最大值/10 且 c[i]>'7',乘积后必越界
// 2.num>最大值/10 乘积后必越界
if (num > maxBoundary || num == maxBoundary && c[i] > '7') {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
// 拼接数字部分
num = num * 10 + (c[i] - '0');
}
// 返回符号*数字
return sign * num;
}
} 栈与队列
剑指09 两个栈实现队列
题目：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
示例 1：
输入：["CQueue","appendTail","deleteHead","deleteHead"][[],[3],[],[]]输出：[null,null,3,-1]
示例 2：
输入：["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"][[],[],[5],[2],[],[]]输出：[null,-1,null,null,5,2]
提示：
1 <= values <= 10000最多会对 appendTail、deleteHead 进行 10000 次调用
分析：
- 定义一个
push栈向pop栈压入的步骤（摊还时间复杂度），满足两个原则pop栈为空，必须向pop栈压入足够多的数据- 一旦要向
pop栈压入数据，当时push栈里面的数据必须全部压入
public class CQueue {
private LinkedList<Integer> pushStack;
private LinkedList<Integer> popStack;
public CQueue() {
pushStack = new LinkedList<>();
popStack = new LinkedList<>();
}
public void appendTail(int value) {
// 添加:先push再倒入popStack
pushStack.push(value);
pushToPop(pushStack, popStack);
}
public int deleteHead() {
// 判断两个栈非空才出队
if (popStack.isEmpty() && pushStack.isEmpty()) {
return -1;
}
// 删除:先倒入,再删除
pushToPop(pushStack, popStack);
return popStack.pop();
}
// push栈只压入,pop栈只压出
private void pushToPop(LinkedList<Integer> pushStack, LinkedList<Integer> popStack) {
// 只有pop栈空,才从push栈导入数据进pop栈
if (popStack.isEmpty()) {
while (!pushStack.isEmpty()) {
popStack.push(pushStack.pop());
}
}
}
} 牛客JZ5
public class JZ5 {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
push2Pop();
stack1.push(node);
push2Pop();
}
public int pop() {
if (stack1.isEmpty() && stack2.isEmpty()) {
return -1;
}
push2Pop();
int pop = stack2.pop();
push2Pop();
return pop;
}
private void push2Pop() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
}
} 剑指30 包含min功能的栈
题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.min(); --> 返回 -2.
提示：
各函数的调用总次数不超过 20000 次
分析：
- 准备两个栈：
dataStack记录数据，minStack记录最小值 - push：这里的push为非同步入栈，数据栈和最小值栈元素不用保持同一水平线，这样书写代码量最小
- 数据栈每次都加入数据，最小值栈只有栈顶元数>待加入的值 or 最小值栈为空才入栈
- pop：记录出栈元素，如果和最小值栈顶元素相同，最小值栈顶也出栈
- top、min()正常判空，然后操作即可
public class MinStack {
// 方案:data栈入数据,min栈每次只存入<=min栈顶的元素
private LinkedList<Integer> stack1;
private LinkedList<Integer> stack2;
public MinStack() {
stack1 = new LinkedList<>();
stack2 = new LinkedList<>();
}
// s1和s2非同步压入
public void push(int x) {
if (stack2.isEmpty() || x <= stack2.peek()) {
stack2.push(x);
}
stack1.push(x);
}
public void pop() {
if (stack1.isEmpty()) {
throw new RuntimeException("MinStack is null,not pop()");
}
int pop = stack1.pop();
if (pop == min()) {
stack2.pop();
}
}
public int top() {
if (stack1.isEmpty()) {
throw new RuntimeException("MinStack is null,not top()");
}
return stack1.peek();
}
public int min() {
if (stack2.isEmpty()) {
throw new RuntimeException("MinStack is null,not min()");
}
return stack2.peek();
}
} 牛客JZ20
public class JZ20 {
private Stack<Integer> stack1 = new Stack<>();
private Stack<Integer> stack2 = new Stack<>();
// s1和s2同步压入
public void push(int node) {
// s2压入node规则：s2一开始为空||新的值更小
if (stack2.isEmpty() || node <= min()) {
stack2.push(node);
} else {// 新的值更大，s2压入原先的最小值
stack2.push(min());
}
stack1.push(node);
}
public void pop() {
if (stack1.isEmpty()) {
return;
}
stack1.pop();
stack2.pop();
}
public int top() {
if (stack1.isEmpty()) {
return -1;
}
return stack1.peek();
}
public int min() {
if (stack2.isEmpty()) {
return -1;
}
// 最小值也是peek，不是pop
return stack2.peek();
}
} 剑指31 栈的压入弹出序列
题目:输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]输出：true解释：我们可以按以下顺序执行：push(1), push(2), push(3), push(4), pop() -> 4,push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]输出：false解释：1 不能在 2 之前弹出。
提示：
0 <= pushed.length == popped.length <= 10000 <= pushed[i], popped[i] < 1000pushed 是 popped 的排列。
分析：
- 使用一个栈模拟push和pop过程
- 遍历pushed数组，往栈中加入元素，直到栈顶元素和poped[i]数组元素相同就停止
- 遇到相同，就出栈直到不同，所以内层是
while循环，不是if判断
- 遇到相同，就出栈直到不同，所以内层是
- 返回值：模拟栈是否为空，为空就代表
true匹配成功
public class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
// 力扣题可以用LinkedList，但牛客不能用，简单题手写栈比较巩固知识
int[] stack = new int[pushed.length];
int stackIndex = 0;
int popAIndex = 0;
for (int numA : pushed) {
stack[stackIndex++] = numA;
while (stackIndex != 0 && stack[stackIndex - 1] == popped[popAIndex]) {
stackIndex--;
popAIndex++;
}
}
return stackIndex == 0;
}
} 牛客JZ21
public class JZ21 {
public boolean IsPopOrder(int[] pushA, int[] popA) {
// 牛客bug：导包只能用ArrayList，还不如用int[]方便
int[] stack = new int[pushA.length];
int stackIndex = 0;
int popAIndex = 0;
for (int numA : pushA) {
stack[stackIndex++] = numA;
while (stackIndex != 0 && stack[stackIndex - 1] == popA[popAIndex]) {
stackIndex--;
popAIndex++;
}
}
return stackIndex == 0;
}
} 剑指40 最小的k个数
题目：输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1输出：[0]
限制：
0 <= k <= arr.length <= 100000 <= arr[i] <= 10000
分析：
- 快速排序思想法：最小k个数升序的查找，可以使用快速排序基准的思想，如果i==k，表示前k个数已经排好序，返回这k个数即可，但是有2个大坑需要注意一下
- 大坑1：
arr[L]作为基准，只能先移动j后移动i- 比如：
arr={3,1,2,4,5},arr[L]=3,如果先i++,再j- -，再交换swap(ar,i,L),就变成了arr=[4,1,2,3,5],不符合基准量表左小右大的要求 - 原因：
arr[L]作为基准，必须先找到<区域的最后一个数位置，才能交换基准与该位置
- 比如：
- 大坑2：
swap中i与j可能越界arr = {4,5,1,6,2,7,3,8}，k=8，i最后只能=8来划分区间，此时是不能swap(arr,i,L)- 解决办法：
swap函数中加如果i==j，就停止交换即可
public class Solution {
// 快速排序法:只用返回坐标k左边的数即可
public int[] getLeastNumbers(int[] arr, int k) {
if (k < 0 || k > arr.length) {
return new int[]{};
}
return quickSortK(arr, 0, arr.length - 1, k);
}
private int[] quickSortK(int[] arr, int L, int R, int k) {
int i = L;
int j = R;
// while循环,将arr划分为[l,i]<arr[l],arr[l],arr[i+1,r]>arr[l]
while (i < j) {
// 注意：arr[L]作为基准，先移动j后移动i
// 因为我只能和<区域最后一个交换才能保证左小右大，先移动j才能找到第一个<的数
// 找到第一个arr[j]<arr[l]
while (i < j && arr[j] >= arr[L]) {
j--;
}
// 找到第一个arr[i]>arr[l]
while (i < j && arr[i] <= arr[L]) {
i++;
}
swap(arr, i, j);
}
// 交换基准arr[l]和arr[i],保证划分区间
swap(arr, i, L);
// 若i>k ，说明小于k个数的边界在左边，移动右边界
if (i > k) {
quickSortK(arr, L, i - 1, k);
} else if (i < k) {// i<k，移动左边界
quickSortK(arr, i + 1, R, k);
}
// 若i==k,前k个数就是k下标前面的所有数
return Arrays.copyOf(arr, k);
}
private void swap(int[] arr, int i, int j) {
if (i == j) {// 防止i = j = len，越过了len-1长度无法交换
return;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
} 牛客JZ29
public class JZ29 {
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
if (k < 0 || k > input.length) {
return new ArrayList<>();
}
return quickSortK(input, 0, input.length - 1, k);
}
private ArrayList<Integer> quickSortK(int[] arr, int L, int R, int k) {
int i = L;
int j = R;
// while循环,将arr划分为[l,i]<arr[l],arr[l],arr[i+1,r]>arr[l]
while (i < j) {
// 注意：arr[L]作为基准，先移动j后移动i
// 因为我只能和<区域最后一个交换才能保证左小右大，先移动j才能找到第一个<的数
// 找到第一个arr[j]<arr[l]
while (i < j && arr[j] >= arr[L]) {
j--;
}
// 找到第一个arr[i]>arr[l]
while (i < j && arr[i] <= arr[L]) {
i++;
}
swap(arr, i, j);
}
// 交换基准arr[l]和arr[i],保证划分区间
// 注意：swap里，防止i与L都约界，加上i==L就停止交换
swap(arr, i, L);
// 若i>k ，说明小于k个数的边界在左边，移动右边界
if (i > k) {
quickSortK(arr, L, i - 1, k);
} else if (i < k) {// i<k，移动左边界
quickSortK(arr, i + 1, R, k);
}
ArrayList<Integer> res = new ArrayList<>();
for (int m = 0; m < k; m++) {
res.add(arr[m]);
}
return res;
}
private void swap(int[] nums, int i, int j) {
if (i == j) {// 防止i = j = len，越过了len-1长度无法交换
return;
}
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
public static void main(String[] args) {
JZ29 jz29 = new JZ29();
int[] arr = {4, 5, 1, 6, 2, 7, 3, 8};
int k = 8;
jz29.GetLeastNumbers_Solution(arr, k);
}
} 剑指41 数据流中的中位数
题目：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。double findMedian() - 返回目前所有元素的中位数。
例1：
输入：["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"][[],[1],[2],[],[3],[]]输出：[null,null,null,1.50000,null,2.00000]
分析：
- 如果是一个排序后的数组求中位数，可以直接计算出来，但是这里是流动的数据流，想降低时间复杂度，可以使用两个堆维持数据
- 大根堆存较小的N/2个数，小根堆存较大的N/2个数
- 第一个出现的数先加入大根堆，以后每次加入的数≤大根堆堆顶也加入大根堆。否则加入小根堆
- 每次加入一个数后，如果两个堆长度差达到2，就将大的出一个数加入小的堆里
- 任何时候，数据流的中位数就可以由两个堆顶获得
public class MedianFinder {
private Queue<Integer> maxHeap;// 大根堆存较小的N/2个数
private Queue<Integer> minHeap;// 小根堆存较大的N/2个数
public MedianFinder() {
this.maxHeap = new PriorityQueue<>((a, b) -> b - a);
this.minHeap = new PriorityQueue<>();
}
public void addNum(int num) {
if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
maxHeap.add(num);
} else {
minHeap.add(num);
}
modifyHeap();
}
public double findMedian() {
if (maxHeap.isEmpty()) {
return -1.0;
}
if (maxHeap.si***Heap.size()) {
return (maxHeap.peek() + minHeap.peek()) / 2.00000;
} else {
return maxHeap.size() > minHeap.size() ? maxHeap.peek() : minHeap.peek();
}
}
private void modifyHeap() {
// 差距达到2才会发生调整
if (maxHeap.si***Heap.size() + 2) {
minHeap.add(maxHeap.poll());
}
if (minHeap.size() == maxHeap.size() + 2) {
maxHeap.add(minHeap.poll());
}
}
public static void main(String[] args) {
MedianFinder solution = new MedianFinder();
solution.addNum(2);
solution.addNum(3);
System.out.println(solution.findMedian());
solution.addNum(4);
System.out.println(solution.findMedian());
}
} 牛客JZ63
public class JZ63 {
private PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);// 大根堆存较小的N/2个数
private PriorityQueue<Integer> minHeap = new PriorityQueue<>();// 小根堆存较大的N/2个数
public void Insert(Integer num) {
if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
maxHeap.add(num);
} else {
minHeap.add(num);
}
modifyHeap();
}
public double GetMedian() {
if (maxHeap.isEmpty()) {
return -1.0;
}
if (maxHeap.si***Heap.size()) {
return (maxHeap.peek() + minHeap.peek()) / 2.00000;
} else {
return maxHeap.size() > minHeap.size() ? maxHeap.peek() : minHeap.peek();
}
}
private void modifyHeap() {
// 差距达到2才会发生调整
if (maxHeap.si***Heap.size() + 2) {
minHeap.add(maxHeap.poll());
}
if (minHeap.size() == maxHeap.size() + 2) {
maxHeap.add(minHeap.poll());
}
}
} 牛客NC131
public class NC131 {
private PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);// 大根堆存较小的N/2个数
private PriorityQueue<Integer> minHeap = new PriorityQueue<>();// 小根堆存较大的N/2个数
public double[] flowmedian(int[][] operations) {
ArrayList<Double> tempList = new ArrayList<>();
for (int i = 0; i < operations.length; i++) {
if (operations[i][0] == 1) {
Insert(operations[i][1]);
} else if (operations[i][0] == 2) {
tempList.add(GetMedian());
}
}
double[] res = new double[tempList.size()];
for (int i = 0; i < tempList.size(); i++) {
res[i] = tempList.get(i);
}
return res;
}
public void Insert(Integer num) {
if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
maxHeap.add(num);
} else {
minHeap.add(num);
}
modifyHeap();
}
public double GetMedian() {
if (maxHeap.isEmpty()) {
return -1.0;
}
if (maxHeap.si***Heap.size()) {
return (maxHeap.peek() + minHeap.peek()) / 2.00000;
} else {
return maxHeap.size() > minHeap.size() ? maxHeap.peek() : minHeap.peek();
}
}
private void modifyHeap() {
// 差距达到2才会发生调整
if (maxHeap.si***Heap.size() + 2) {
minHeap.add(maxHeap.poll());
}
if (minHeap.size() == maxHeap.size() + 2) {
maxHeap.add(minHeap.poll());
}
}
public static void main(String[] args) {
int[][] opt = {{1, 5}, {2}, {1, 3}, {2}, {1, 6}, {2}, {1, 7}, {2}};
NC131 solution = new NC131();
double[] res = solution.flowmedian(opt);
System.out.println(Arrays.toString(res));
}
} 剑指59-I 滑动窗口最大值
题目：给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3输出: [3,3,5,5,6,7]
提示：
你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
分析：
- 双端队列
qmax队头存区间最大值下标 qmax弹出规则：qmax[尾]<=num[i]就弹出；qmax放入规则；qmax[尾]>num[i]才放- 过期出队：
qmax队头下标是i-size，表示队头元素已过期，队头出队 - 开始记录：遍历指针超过窗口长度就记录返回值，返回值存数组元素
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length < k || k < 1) {
return new int[]{};
}
// num=[2, 3, 4, 2, 6, 2, 5, 1]
// res=[4, 4, 6, 6, 6, 5]
// 双端队列队头存区间最大值下标
LinkedList<Integer> qmax = new LinkedList<>();
int[] res = new int[nums.length - k + 1];
int index = 0;
for (int i = 0; i < nums.length; i++) {
// qmax弹出规则：qmax[尾]<=num[i]就弹出
while (!qmax.isEmpty() && nums[qmax.peekLast()] <= nums[i]) {
qmax.pollLast();
}
qmax.addLast(i);
// 过期出队：qmax队头下标是i-size，表示队头元素已过期，队头出队
if (qmax.peekFirst() == i - k) {
qmax.pollFirst();
}
// 开始记录：遍历指针超过窗口长度就记录返回值
if (i >= k - 1) {
res[index++] = nums[qmax.peekFirst()];
}
}
return res;
}
public static void main(String[] args) {
int[] nums = {2, 3, 4, 2, 6, 2, 5, 1};
int k = 3;
Solution solution = new Solution();
int[] res = solution.maxSlidingWindow(nums, k);
System.out.println(Arrays.toString(res));
}
} 牛客JZ64
public class JZ64 {
public ArrayList<Integer> maxInWindows(int[] num, int size) {
if (num == null || size > num.length || size < 1) {
return new ArrayList<>();
}
// num=[2, 3, 4, 2, 6, 2, 5, 1]
// res=[4, 4, 6, 6, 6, 5]
// 双端队列队头存区间最大值
LinkedList<Integer> qmax = new LinkedList<>();
ArrayList<Integer> res = new ArrayList<>();
for (int i = 0; i < num.length; i++) {
// qmax弹出规则：qmax[尾]<=num[i]就弹出
while (!qmax.isEmpty() && num[qmax.peekLast()] <= num[i]) {
qmax.pollLast();
}
// qmax放入规则：qmax[尾]>num[i]才放
qmax.addLast(i);
// 过期出队：qmax队头下标是i-size，表示队头元素已过期，队头出队
if (qmax.peekFirst() == i - size) {
qmax.pollFirst();
}
// 开始记录：遍历指针超过窗口长度就记录返回值
if (i >= size - 1) {
res.add(num[qmax.peekFirst()]);
}
}
return res;
}
} 剑指59-II 队列最大值
题目：请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
示例 1：
输入: ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"][[],[1],[2],[],[],[]]输出: [null,null,null,2,1,2]
示例 2：
输入: ["MaxQueue","pop_front","max_value"][[],[],[]]输出: [null,-1,-1]
分析：
- 剑指30 包含min功能的栈思路一抹一样
- 定义两个队列：
queue执行正常的操作；deque保存最大值 push_back：为了保证均摊时间复杂度为O(1)，双端队列队头存最大值，待加入元素>=/>队尾元素，队尾元素就全部出队pop_front：如果出队元素就是最大值元素，那deque队列也要出队头元素；否则，queue出队头元素即可max_value：获取deque队头元素即可
public class MaxQueue {
// 普通队列:正常的push、pop
private Queue<Integer> queue;
// 双端队列:队头保证是最大值
private Deque<Integer> deque;
public MaxQueue() {
queue = new LinkedList<>();
deque = new LinkedList<>();
}
// 两个队列非同步入队列，deque中一直维持最大值在队头
public void push_back(int value) {
// 待加元素>双端队列队尾元素,双端队列队尾就一直出队
while (!deque.isEmpty() && value > deque.peekLast()) {
deque.pollLast();
}
deque.offerLast(value);
queue.offer(value);
}
public int pop_front() {
if (queue.isEmpty()) {
return -1;
}
int value = queue.poll();
// 待出队元素,和最大值相同,双端队列队头出队
if (value == max_value()) {
deque.pollFirst();
}
return value;
}
public int max_value() {
if (deque.isEmpty()) {
// 条件规定:max栈为空,返回-1
return -1;
}
return deque.peekFirst();
}
public static void main(String[] args) {
LinkedList<Integer> queue = new LinkedList<>();
queue.addLast(1);
queue.addLast(2);
queue.addLast(3);
queue.addLast(4);
System.out.println(queue.peekFirst());// 1
System.out.println(queue.peekLast());// 4
}
} 树问题
剑指07 重建二叉树
题目：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例子：
前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7]
返回：
3/ \9 20 / \15 7
分析：
- 初始化：
root=0为前序遍历根节点索引，left=0为中序中左子树的左边界，right=中序长度-1为中序中右子树的右边界. - 确定左右子树索引范围和左右子树根节点索引
- 根据
root在preOder中的值，去inOrder中推出该值的索引i - 左子树边界范围：
[left,i-1]。左子树根节点root+1- 左子树根节点显然就是
root在前序遍历中的下一位
- 左子树根节点显然就是
- 右子树边界范围：
[i+1,right]。右子树根节点root+i-left+1- 右子树根节点就不容易想到，联想已知左子树节点范围，可以推出左子树长度，那么
左子树长度+root索引+1就是右子树根节点索引
- 右子树根节点就不容易想到，联想已知左子树节点范围，可以推出左子树长度，那么
- 根据
- 建立递归
- 结束条件：left越过right=
left>right，表示没有结点存在，递归结束 - node为i当前指向的根节点，递归每次都返回
node作为上一层的左右子树
- 结束条件：left越过right=
public class Solution {
private int[] pre;
private Map<Integer, Integer> inMap;// 查找root在中序遍历中的下标
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.pre = preorder;
this.inMap = new HashMap<>();
// map存中序遍历元素值和索引，提高查找效率
// 但是牛客不能使用map，力扣可以用，牛客使用普通查找即可
for (int i = 0; i < inorder.length; i++) {
inMap.put(inorder[i], i);
}
return recur(0, 0, inorder.length - 1);
}
/**
* 根据前序和中序，递归生成二叉树
*
* @param root 在pre中根节点的坐标
* @param left 在in中左孩子左边界下标
* @param right 在in中右孩子右边界下标
* @return 根节点
*/
private TreeNode recur(int root, int left, int right) {
// base case：左子树索引越过右子树索引，代表没法形成结点，递归返回null
if (left > right) {
return null;
}
TreeNode node = new TreeNode(pre[root]);// 建立当前层的根节点:node
int i = inMap.get(pre[root]);// node在中序中的索引值
// node的左子树递归:左子树根节点root+1,左子树范围[left,i-1]
node.left = recur(root + 1, left, i - 1);
// node的右子树递归:右子树根节点root+i-left+1,右子树范围[i+1,right]
node.right = recur(root + i - left + 1, i + 1, right);
// 递归回溯,当前node作为上一层的左or右节点
return node;
}
} 牛客JZ4
public class JZ4 {
private int[] preArr;
private int[] inArr;// 牛客不能用Map
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
this.preArr = pre;
this.inArr = in;
return recur(0, 0, in.length - 1);
}
private TreeNode recur(int root, int left, int right) {
if (left > right) {
return null;
}
TreeNode node = new TreeNode(preArr[root]);
int i = getIndexOfInArr(root);
node.left = recur(root + 1, left, i - 1);
node.right = recur(root + i - left + 1, i + 1, right);
return node;
}
private int getIndexOfInArr(int root) {
for (int i = 0; i < inArr.length; i++) {
if (preArr[root] == inArr[i]) {
return i;
}
}
return -1;
}
} 剑指26 树的子结构
题目：输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
示例：
输入：A = [1,2,3], B = [3,1]输出：false输入：A = [3,4,5,1,2], B = [4,1]输出：true
分析：
- 先序遍历判断A中是否有B，如果有，再判断此时的子树能否完全匹配上B
- 定义一个函数
isContainB判断以node为根结点的子树是否包含B- B若null，说明越过叶子节点也没有匹配上，返回false
- A若null或者A值不等于B值，同样返回false
- 否则递归再次判断左左和右右是否是子结构
- 主函数判断
- 题目规定空树不是任意一个树的子结构，所以A或者B其中一个为null,返回false
- 否则：
isContainB(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)这三个条件满足一个即为子结构- 注意理解：
isContainB(A, B)只是判断A及其子树是否是B的子结构
- 注意理解：
public boolean isSubStructure(TreeNode A, TreeNode B) {
// base case:空节点，返回false
if (A == null || B == null) {
return false;
}
// 先判断A的先序序列中是否用B || 如A中先序有B，则isContainB判断左右子树能否一一对应
return isSubStructure(A.left, B) || isSubStructure(A.right, B) || isContainB(A, B);
}
// 判断A中以root为根节点的树，是否能匹配上match
private boolean isContainB(TreeNode root, TreeNode match) {
// base1：match越过叶子，说明匹配完成，返回true
if (match == null) {
return true;
}
// base2：root为null或者两者值不相同，未匹配成功，返回false
if (root == null || root.val != match.val) {
return false;
}
// 子结构:必须是左左对应，右右对应。不能是左右分开对应
return isContainB(root.left, match.left) && isContainB(root.right, match.right);
} JZ17
public class JZ17 {
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
if (root1 == null || root2 == null) {
return false;
}
return HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2) || isContainB(root1, root2);
}
private boolean isContainB(TreeNode root, TreeNode match) {
if (match == null) {
return true;
}
if (root == null || root.val != match.val) {
return false;
}
return isContainB(root.left, match.left) && isContainB(root.right, match.right);
}
} 剑指27 二叉树的镜像
题目:请完成一个函数，输入一个二叉树，该函数输出它的镜像。
示例 1：
输入：root = [4,2,7,1,3,6,9]输出：[4,7,2,9,6,3,1]
分析：此题就是翻转二叉树
- 递归法：前序遍历依次进行交换左右子树
// 递归法:前序遍历依次进行交换左右子树
public TreeNode mirrorTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
mirrorTree(root.left);
mirrorTree(root.right);
return root;
} - 辅助栈：将上述递归法改成手写的辅助栈
// 将递归改成辅助栈法
public TreeNode mirrorTree1(TreeNode root) {
if (root == null) {
return null;
}
LinkedList<TreeNode> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()) {
// 栈顶元素出队
TreeNode top = stack.pop();
// 使用栈就要先入栈,再交换
if (top.left != null) {
stack.push(top.left);
}
if (top.right != null) {
stack.push(top.right);
}
// 出队结点的左右孩子节点交换
TreeNode temp = top.left;
top.left = top.right;
top.right = temp;
}
return root;
} JZ18
public class JZ18 {
public TreeNode Mirror(TreeNode pRoot) {
if (pRoot == null) {
return null;
}
TreeNode temp = pRoot.left;
pRoot.left = pRoot.right;
pRoot.right = temp;
Mirror(pRoot.left);
Mirror(pRoot.right);
return pRoot;
}
} 剑指28 对称二叉树
题目：请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
分析：这道题对递归会有深刻的认识
- 传入一个
root，若为null，肯定是对称的，返回false - 否则，递归判断
root的左右孩子，对称条件：left.val=right.valleft.left=right.rightleft.right=right.left
root的左右孩子有一个不满足上面的条件，就不是对称二叉树，不满足情况如下：left.val!=right.val左右一个为空,另一个不为空
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return recur(root.left, root.right);
}
private boolean recur(TreeNode left, TreeNode right) {
// 递归成功:左右结点同时到达null
if (left == null && right == null) {
return true;
}
// 递归失败:左右结点一个到达null,另一个不到达,或者左右结点值不相同
if (left == null || right == null || left.val != right.val) {
return false;
}
// 递归:(左左,右右) && (左右,右左)
return recur(left.left, right.right) && recur(left.right, right.left);
}
} JZ58
public class JZ58 {
boolean isSymmetrical(TreeNode pRoot) {
if (pRoot == null) {
return true;
}
return recur(pRoot.left, pRoot.right);
}
private boolean recur(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if (left == null || right == null || left.val != right.val) {
return false;
}
return recur(left.left, right.right) && recur(left.right, right.left);
}
} 剑指32-I 从左到右打印二叉树
题目：从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
示例：
输入：
3
/ \
9 20
/ \
15 7
返回值：
[3,9,20,15,7] 分析：
- 使用队列，左孩子先进右孩子后进
public class Solution {
// 题目:从左到右打印二叉树，输出int[]
// 使用LinkedList
public int[] levelOrder(TreeNode root) {
if (root == null) {
return new int[]{};
}
// 方法:从上到下打印二叉树,利用队列的先进先出的特性
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
// 由于res数组长度未知,先用链表结构存打印结果
ArrayList<Integer> temp = new ArrayList<>();
while (!queue.isEmpty()) {
TreeNode pop = queue.poll();
// 先序遍历,每次遍历到当前元素,就出队
temp.add(pop.val);
if (pop.left != null) {
queue.add(pop.left);
}
if (pop.right != null) {
queue.add(pop.right);
}
}
// 生成链表长度的res数组,重新赋值即可
int[] res = new int[temp.size()];
for (int i = 0; i < res.length; i++) {
res[i] = temp.get(i);
}
return res;
}
} JZ22
- 牛客只能用
ArrayList,用index=0维护队列头部即可
public class JZ22 {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
// 牛客只能用ArrayList
ArrayList<TreeNode> queue = new ArrayList<>();
queue.add(root);
int index = 0;// 用指针=0来维护队列头部
ArrayList<Integer> res = new ArrayList<>();
while (!queue.isEmpty()) {
TreeNode node = queue.get(index);
queue.remove(index);
res.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
return res;
}
} 剑指32-II 二叉树层次遍历
题目：从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。（=二叉树层序遍历）
示例：
3
/ \
9 20
/ \
15 7
返回：
[
[3],
[9,20],
[15,7]
] 分析：
public class Solution {
// 题目：从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。（=二叉树层序遍历）
// 难点: i = queue.size(); i > 0
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
List<List<Integer>> res = new ArrayList<>();
while (!queue.isEmpty()) {
// temp存每一行的数据
List<Integer> temp = new ArrayList<>();
// 层次遍历，需要从确定每层的长度
for (int i = queue.size(); i > 0; i--) {
// 因为queue的长度每次循环内部都在改变,所以不能以size为遍历结束条件
TreeNode node = queue.poll();
temp.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
res.add(temp);
}
return res;
}
} 牛客JZ60
public class JZ60 {
ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
if (pRoot == null) {
return new ArrayList<>();
}
ArrayList<TreeNode> queue = new ArrayList<>();
queue.add(pRoot);
int index = 0;
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
while (!queue.isEmpty()) {
ArrayList<Integer> temp = new ArrayList<>();
// 层次遍历，需要从确定每层的长度
for (int i = queue.size(); i > 0; i--) {
TreeNode node = queue.get(index);
queue.remove(index);
temp.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
res.add(temp);
}
return res;
}
} 剑指32-II 之字型打印二叉树
题目：请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。（之字型打印二叉树）
示例：
输入：{8,6,10,5,7,9,11}返回值：[[8],[10,6],[5,7,9,11]] 分析：
public class Solution {
// 题目：实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，其他行以此类推。
// LinkedList作为数据结构
public List<List<Integer>> levelOrder2(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<List<Integer>> res = new LinkedList<>();
// LinkedList作为queue数据结构
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
// temp双端队列存这一层的打印结点值
LinkedList<Integer> temp = new LinkedList<>();
for (int i = queue.size(); i > 0; i--) {
// 辅助链表存每一层的结点
TreeNode node = queue.poll();
// List<List>的长度=层数，≠全部元素个数
// res.size从0开始=第一层，尾插法
if (res.size() % 2 == 0) {
temp.addLast(node.val);
} else {
temp.addFirst(node.val);
}
// queue存左右孩子节点
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
res.add(temp);
}
return res;
}
} 牛客JZ59
public class JZ59 {
public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
if (pRoot == null) {
return new ArrayList<>();
}
// 牛客NC14，限定死只能用ArrayList这个数据结构作为队列
ArrayList<TreeNode> queue = new ArrayList<>();
queue.add(pRoot);
int index = 0;
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
while (!queue.isEmpty()) {
ArrayList<Integer> temp = new ArrayList<>();
for (int i = queue.size(); i > 0; i--) {
TreeNode node = queue.get(index);
queue.remove(index);
// 层数假设从0开始，偶数层=从左到右打印
if (res.size() % 2 == 0) {
temp.add(node.val);
} else {
temp.add(0, node.val);//层数假设从1开始，奇数层=从右往左打印
}
// 以下是正常层次遍历存结点
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
res.add(temp);
}
return res;
}
} 剑指33 二叉搜索树的后序遍历
题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/ \
2 6
/ \
1 3
输入: [1,6,3,2,5]
输出: false
输入: [1,3,2,6,5]
输出: true 分析：
- 后序遍历将二叉搜索树分为：后序
[左孩子区间|右孩子区间|根节点]+二叉搜素性质 =[小于根节点区间|大于根节点区间|根节点] - 递归结束：
- 只有一个元素或没有元素，停止递归
- 分区间：若根节点为
postorder[right]，则利用上面的性质去找第一个大于跟节点区间的下标j，可以将数组分为小于根节点[left,j-1]、大于根节点[j,right-1]、根节点[right] - 判断区间满足二叉搜索树性质：
小于根节点[left,j-1]是否满足小于根节点的性质，这里在分区间步骤中遍历后序数组就实现了大于根节点[j,right-1]是否满足大于根节点的性质，这里通过遍历j后序元素，是否<=postorder[right]，如果遍历停止当时遍历的指针 = right位置，那性质满足继续下一层递归，否则返回false
- 递归返回：以下3个条件同时满足
- 如果遍历停止当时遍历的指针 是否 = right位置
- 左子树区间判断是否是后序遍历
- 右子树区间判断是否是后序遍历
public class Solution {
public boolean verifyPostorder(int[] postorder) {
if (postorder == null || postorder.length == 0) {
return true;
}
return recur(postorder, 0, postorder.length - 1);
}
// 二叉搜索树后续遍历把数组= [左子树|右子树|根节点],并且左子树<根节点，右子树>根节点
private boolean recur(int[] post, int left, int right) {
// base case:左指针越过右指针，说明子树数量<=1无法判断是否是二叉搜索树
if (left >= right) {
return true;
}
// i指向右子树的第一个结点
// 数组分为[0...i-1|i...right-1|right]，其中根节点=post[right]
int i = left;
while (post[i] < post[right]) {
i++;
}
// j遍历[右子树部分]，其中每个值都应该>根节点，如果没有遍历到right不是BST
int j = i;
while (post[j] > post[right]) {
j++;
}
// 后续匹配成功如下:
// 1.遍历指针j是否到达根节点right，判断是否是二叉搜索树
// 2.左孩子区间满足分治
// 3.右孩子区间满足分治
return j == right
&& recur(post, left, i - 1)
&& recur(post, i, right - 1);
}
} 牛客JZ23
public class JZ23 {
public boolean VerifySquenceOfBST(int[] sequence) {
// 题目规定：空树不是二叉搜索树
if (sequence == null || sequence.length == 0) {
return false;
}
return recur(sequence, 0, sequence.length - 1);
}
private boolean recur(int[] post, int left, int right) {
if (left >= right) {
return true;
}
int i = left;
while (post[i] < post[right]) {
i++;
}
int j = i;
while (post[j] > post[right]) {
j++;
}
return j == right && recur(post, left, i - 1) && recur(post, i, right - 1);
}
} 剑指34 二叉树和为某一值的路径
题目：输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
示例： 给定如下二叉树，以及目标和 target = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1 返回:
[[5,4,11,2], [5,8,4,5]]
分析：
- 利用中序遍历，使用
path链表记录每一条路径，如果满足元素和为target则加入结果集 - 若满足以下三个条件：则将当前
path加入结果集target == 0root.left == nullroot.right == null
- 回溯：需要移除
path末尾元素
public class Solution {
private List<List<Integer>> res;
private ArrayList<Integer> path;
public List<List<Integer>> pathSum(TreeNode root, int target) {
res = new ArrayList<>();
path = new ArrayList<>();
recur(root, target);
return res;
}
private void recur(TreeNode root, int target) {
if (root == null) {
return;
}
// 先序遍历:先记录当前节点值进path
path.add(root.val);
target -= root.val;
// 加入结果集条件:target == 0 && root.left == null && root.right == null
if (target == 0 && root.left == null && root.right == null) {
// new ArrayList<>(path)形成新链表放入结果集
res.add(new ArrayList<>(path));
}
if (root.left != null) {
recur(root.left, target);
}
if (root.right != null) {
recur(root.right, target);
}
// 回溯需要移除path末尾元素
path.remove(path.size() - 1);
}
} 牛客JZ24
public class JZ24 {
private ArrayList<ArrayList<Integer>> res;
private ArrayList<Integer> temp;
// 路径定义:树的根结点到叶结点所经过的结点
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
if (root == null) {
return new ArrayList<>();
}
res = new ArrayList<>();
temp = new ArrayList<>();
backtrack(root, target);
return res;
}
private void backtrack(TreeNode root, int target) {
if (root == null) {
return;
}
temp.add(root.val);
target -= root.val;// target每次递减
// 路径定义:树的根结点到叶结点所经过的结点
if (target == 0 && root.left == null && root.right == null) {
// 难点：再new一个ArrayList(temp)
res.add(new ArrayList<>(temp));
}
if (root.left != null) {
backtrack(root.left, target);
}
if (root.right != null) {
backtrack(root.right, target);
}
// 回溯，移除temp末尾元素值
temp.remove(temp.size() - 1);
}
} 剑指36 二叉搜索树和双向链表
题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
分析：看上去很难，实际很简单，二叉搜索树转化成从小到大排列好的循环双向链表，从小到大提示我们使用中序遍历二叉搜索树
- 由于root形成双向链表后，头指针发生变化，所以定义两个全局变量，
pre和head - 定义一个中序遍历的
dfs，将二叉搜索树转换为双向链表 - 更改
pre和head，将双向链表转换为循环链表 - 返回
head
public class Solution {
private Node pre;
private Node head;
public Node treeToDoublyList(Node root) {
if (root == null) {
return null;
}
// 中序遍历形成双向链表
dfs(root);
// 更新首尾指针,形成循环链表
head.left = pre;
pre.right = head;
return head;
}
private void dfs(Node root) {
if (root == null) {
return;
}
dfs(root.left);
// 二叉搜索树中序遍历:保证从小到大
if (pre == null) {// pre=null,说明是第一次来到最左结点，head记录未来双向链表的头结点
head = root;
} else {// pre!=null，更新pre的后继
pre.right = root;
}
root.left = pre;// 更新cur的前驱
pre = root;// pre后移
dfs(root.right);
}
} 牛客JZ26
public class JZ26 {
private TreeNode pre;
private TreeNode head;
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree == null) {
return null;
}
dfs(pRootOfTree);
return head;
}
private void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
if (pre == null) {
head = root;
} else {
pre.right = root;
}
root.left = pre;
pre = root;
dfs(root.right);
}
} 剑指37 二叉树的序列化和反序列化
你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
分析：
序列化：指定格式是[x,x,x,x]形式，用字符串拼接成这种形式[]
- 层次遍历，初始化结果字符串
[，根节点非空就入队列 - 遍历队列，队头元素出队，记
nodenode!=null，结果字符串添加node.val+,，并且node的左右孩子都入队列node==null，字符串条件添加node,
- 遍历结束，删除末尾逗号，结果字符串
],返回结果字符串
反序列化：
- 字符串删除首尾
[]（如果只有[],直接返回null），并且按照,分割成字符数组 - 形成根节点，根节点值为字符数组首位
- 层次遍历字符数组，根节点先入队列；遍历字符数组指针
index从1开始，因为根节点已生成无需遍历- 队列元素出队记
node - 如果字符数组元素不为null，则
node.left/node.right存在，并按照当前字符数组值生成；同时，队列添加node.left/node.right - 字符数组元素为null，遍历指针
index++
- 队列元素出队记
- 返回根节点
public class Solution {
// 序列化二叉树,按照力扣指定格式返回
public String serialize(TreeNode root) {
if (root == null) {
return "[]";
}
StringBuilder sb = new StringBuilder("[");
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
// node值不为null
if (node != null) {
sb.append(node.val).append(",");
// 队列每次放出队结点的左右结点即可,因为root已经是二叉树
queue.add(node.left);
queue.add(node.right);
} else { // node值为null,结果字符串加null+,
sb.append("null,");
}
}
// 删除最后一个逗号
sb.deleteCharAt(sb.length() - 1);
sb.append("]");
return sb.toString();
}
// 反序列化二叉树
public TreeNode deserialize(String data) {
if (data.equals("[]")) {
return null;
}
// 去掉头尾的"[]"，并根据逗号分离成字符串数组
String[] split = data.substring(1, data.length() - 1).split(",");
// 生产根节点
TreeNode root = new TreeNode(Integer.parseInt(split[0]));
// 队列维持左右孩子
Queue<TreeNode> queue = new LinkedList<TreeNode>() {{
add(root);
}};
// 根节点已生成,遍历指针从1下标开始
int index = 1;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (!split[index].equals("null")) {
node.left = new TreeNode(Integer.parseInt(split[index]));
queue.add(node.left);
}
index++;
if (!split[index].equals("null")) {
node.right = new TreeNode(Integer.parseInt(split[index]));
queue.add(node.right);
}
index++;
}
return root;
}
public static void main(String[] args) {
Solution solution = new Solution();
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
n1.left = n2;
n1.right = n3;
String res = solution.serialize(n1);
System.out.println(res);
}
} 牛客JZ61
public class JZ61 {
String Serialize(TreeNode root) {
if (root == null) {
return "[]";
}
StringBuilder sb = new StringBuilder("[");
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
// node值不为null
if (node != null) {
sb.append(node.val).append(",");
// 队列每次放出队结点的左右结点即可,因为root已经是二叉树
queue.add(node.left);
queue.add(node.right);
} else { // node值为null,结果字符串加null+,
sb.append("null,");
}
}
// 删除最后一个逗号
sb.deleteCharAt(sb.length() - 1);
sb.append("]");
return sb.toString();
}
TreeNode Deserialize(String str) {
if (str.equals("[]")) {
return null;
}
// 去掉头尾的"[]"，并根据逗号分离成字符串数组
String[] split = str.substring(1, str.length() - 1).split(",");
// 生产根节点
TreeNode root = new TreeNode(Integer.parseInt(split[0]));
// 队列维持左右孩子
Queue<TreeNode> queue = new LinkedList<TreeNode>() {{
add(root);
}};
// 根节点已生成,遍历指针从1下标开始
int index = 1;
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (!split[index].equals("null")) {
node.left = new TreeNode(Integer.parseInt(split[index]));
queue.add(node.left);
}
index++;
if (!split[index].equals("null")) {
node.right = new TreeNode(Integer.parseInt(split[index]));
queue.add(node.right);
}
index++;
}
return root;
}
} 剑指54 二叉搜索树的第k个节点
题目：给定一棵二叉搜索树，请找出其中第k大的节点。
例子：
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 4 限制：
1 ≤ k ≤ 二叉搜索树元素个数
分析：看到二叉搜索树，想到中序遍历就是递增数组
- 二叉搜索树的中序遍历，使用list记录每个中序遍历的值，返回
size()-k就是第k大的数
public class Solution {
// 二叉搜索树的中序遍历,用链表存数值,返回第size-k个元素就是第k大的元素
public int kthLargest(TreeNode root, int k) {
ArrayList<Integer> list = new ArrayList<>();
inOrderByLR(root, list);
// 第1大的数->排序后第size-1个数
// 第k大的数->排序后第size-k个数
return list.get(list.size() - k);
}
private void inOrderByLR(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
inOrderByLR(root.left, list);
list.add(root.val);
inOrderByLR(root.right, list);
}
} 牛客JZ62
- 牛客求是的第k小的数，并且不能用List等包
public class JZ62 {
private int[] arr;
private int index;
private int len;
TreeNode KthNode(TreeNode pRoot, int k) {
getNodeCount(pRoot);
if (k == 0 || k > len) {// 判断k越界
return null;
}
arr = new int[len];
index = 0;
inOrder(pRoot);
// 牛客返回的是第k小的数
// 第1小的数，下标为0
// 第k小的数，小标为k
return new TreeNode(arr[k - 1]);
}
private void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
arr[index++] = root.val;
inOrder(root.right);
}
private void getNodeCount(TreeNode root) {
if (root == null) {
return;
}
len++;
getNodeCount(root.left);
getNodeCount(root.right);
}
} 剑指55-I 二叉树深度
题目：输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：
给定二叉树 [3,9,20,null,null,15,7]，返回深度为3
分析：
- 递归，越过叶子节点，高度为0
- 否则，返回当前左右孩子深度的最大值+1，就是二叉树的深度
public class Solution {
// 法:递归法
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
// 二叉树深度:左右子树深度最大值+1
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
} 牛客JZ38
public class JZ38 {
public int TreeDepth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1;
}
} 剑指55-II 平衡二叉树
题目：输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
分析：
- 法1：定义一个函数
process(TreeNode head)，对树进行后续遍历，可以获得左右子树全部信息 - 遇到结点为null，说明越过叶子节点，返回高度0
- 递归左子树，获得左子树高度信息；若是-1，整体返回-1
- 递归右子树，获得右子树高度信息；若是-1，整体返回-1
- 递归返回：
Math.abs(leftHeight - rightHeight) <= 1 ? Math.max(leftHeight, rightHeight) + 1 : -1
public class Solution {
public boolean isBalanced(TreeNode root) {
return process(root) != -1;
}
// 左右子树高度差<=1,返回真实高度;左右子树高度差>1,返回-1
private int process(TreeNode head) {
if (head == null) {
return 0;
}
int leftHeight = process(head.left);
if (leftHeight == -1) {
return -1;
}
int rightHeight = process(head.right);
if (rightHeight == -1) {
return -1;
}
return Math.abs(leftHeight - rightHeight) <= 1 ? Math.max(leftHeight, rightHeight) + 1 : -1;
}
} 法2：左神书上提到了一种树形dp的思路如下：
- 树形 dp 套路第一步：以某个节点 X 为头节点的子树中，分析答案有哪些可能性，并且这种分析是以 X 的左子树、X 的右子树和 X 整棵树的角度来考虑可能性的。
- 可能性一：如果 X 的左子树不是平衡的，则以 X 为头节点的树就是不平衡的。
- 可能性二：如果 X 的右子树不是平衡的，则以 X 为头节点的树就是不平衡的。
- 可能性三：如果 X 的左子树和右子树高度差超过 1，则以 X 为头节点的树就是不平衡的。
- 可能性四：如果上面可能性都没中，那么以 X 为头节点的树是平衡的。
- 树形 dp 套路第二步：根据第一步的可能性分析，列出所有需要的信息。左子树和右子树都需要知道各自是否平衡，以及高度这两个信息。
- 树形 dp 套路第三步：根据第二步信息汇总。定义信息如 ReturnType 类所示。
- 树形 dp 套路第四步：设计递归函数。递归函数是处理以 X 为头节点的情况下的***括设计递归的 base case，默认直接得到左树和右树所有的信息
public class Solution {
public boolean isBalanced(TreeNode root) {
return process(root).isBalanced;
}
private ReturnType process(TreeNode head) {
if (head == null) {
return new ReturnType(true, 0);
}
// 获取左右子树的情况
ReturnType leftType = process(head.left);
ReturnType rightType = process(head.right);
// 整体平衡:左子树平衡、右子树平衡、高度差<=1
boolean isBalanced = leftType.isBalanced && rightType.isBalanced
&& Math.abs(leftType.height - rightType.height) <= 1;
// 整体高度:左右子树最大高度+1
int height = Math.max(leftType.height, rightType.height) + 1;
return new ReturnType(isBalanced, height);
}
}
// 树形dp套路:考虑左右子树情况,定义一个情况类接收
class ReturnType {
boolean isBalanced;
int height;
ReturnType(boolean isBalanced, int height) {
this.isBalanced = isBalanced;
this.height = height;
}
} 牛客JZ39
public class JZ39 {
public boolean IsBalanced_Solution(TreeNode root) {
return process(root) != -1;
}
// 左右子树高度差<=1,返回真实高度;左右子树高度差>1,返回-1
private int process(TreeNode head) {
if (head == null) {
return 0;
}
// 获取左子树高度信息
int leftHeight = process(head.left);
if (leftHeight == -1) {
return -1;
}
// 获取右子树高度信息
int rightHeight = process(head.right);
if (rightHeight == -1) {
return -1;
}
// 左右子树高度差<=1,返回子树最大高度+1;左右子树高度差>1,返回-1
return Math.abs(leftHeight - rightHeight) <= 1 ? Math.max(leftHeight, rightHeight) + 1 : -1;
}
} 剑指68-I 二叉搜索树的最近公共祖先
题目：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
分析：
- 条件：1.二叉搜索树，保证左小右大；2.结点值不重复；3.p,q分别对应两个不同结点
- 迭代法：
- 遍历二叉搜索树，如果p,q一左一右，那么最近公共祖先就是root，停止循环，直接递归
- p,q都在root的右边，root指向它的右孩子
- p,q都在root的左边，root指向它的左孩子
public class Solution {
// BST特性左小右大+无重复结点，自己画图明确三种情况
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 保证左小右大
if (p.val > q.val) {
TreeNode temp = p;
p = q;
q = temp;
}
while (root != null) {
// root比最小的还小,说明root出现在了p,q的左边,那么公共祖先在root的右边
if (root.val < p.val) {
root = root.right;
} else if (root.val > q.val) {
// root比最大的还大,说明root出现在了p,q的右边,那么公共祖先在root的左边
root = root.left;
} else {
// root.val=p.val||root.val=q.val,root此时指向的就是最近公共祖先
break;
}
}
return root;
}
} 剑指68-II 二叉树的最近公共祖先
题目：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
分析：
- 由于普通二叉树没有特别的性质，但后序遍历可以使用先记录左右孩子节点的信息后再操作，所以使用后续遍历
- 递归结束条件：
- 遍历指针越过叶子节点，返回
null - 遍历指针=
p或q，返回遍历指针
- 遍历指针越过叶子节点，返回
- 开始递归：
- 递归左子树，用
left接收 - 递归右子树，用
right接收
- 递归左子树，用
- 返回值：
- 当
left和right同时不为空:说明p,q在root异侧,root就是最近公共祖先 - 当
left和right同时为空:说明root左右子树不包含p,q,无公共祖先 - 当
left和right一个空,一个不空，最近公共祖先肯定在root非空的那个子树里
- 当
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 递归结束条件
// root越过叶子节点,返回null
// root = p/q,最近公共祖先就是root本身，返回root
if (root == null || root == p || root == q) {
return root;
}
// 设当前节点为cur,使用后序遍历记录当前节点的左右子树情况,用left和right接收
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 当left和right同时不为空:说明p,q在root异侧,root就是最近公共祖先
if (left != null && right != null) {
return root;
}
// 当left和right同时为空:说明root左右子树不包含p,q,无公共祖先
// 当left和right一个空,一个不空，最近公共祖先肯定在root非空的那个子树里
return left != null ? left : right;
}
} 动态规划
剑指10-I 斐波那契数列
题目：写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例：
输入：n = 2输出：1
分析：
- 剑指Offer的斐波拉契要取模，其余一样
public class Solution {
// 法1:迭代法
public int fib1(int n) {
if (n < 2) {
return n;
}
int a = 0;
int b = 1;
int sum = 0;
for (int i = 2; i <= n; i++) {
sum = (a + b) % 1000000007;// 剑指Offer的斐波拉契要取模
a = b;
b = sum;
}
return sum;
}
// 法2:动态规划法
public int fib2(int n) {
if (n < 2) {
return n;
}
// dp[0]表示第0个斐波那契数，需要返回第n个斐波拉契数，所以需要长度n+1
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
}
return dp[n];
}
} JZ7
public class JZ7 {
public int Fibonacci(int n) {
if (n < 2) {
return n;
}
int a = 0;
int b = 1;
int sum = 0;
for (int i = 2; i <= n; i++) {
sum = a + b;
a = b;
b = sum;
}
return sum;
}
} 剑指10-II 跳台阶
题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
分析：和NC68是一样的
public class Solution {
// 一次可以跳1个台阶或者2个台阶
public int numWays(int n) {
if (n == 0 || n == 1) {
return 1;
}
int a = 1;
int b = 1;
int sum = 0;
for (int i = 2; i <= n; i++) {
sum = (a + b) % 1000000007;
a = b;
b = sum;
}
return sum;
}
} 牛客JZ9 跳台阶扩展问题
题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
示例：
输入：3返回值：4
分析：
- 此题和前面2道题完全不一样，
f(n)=f(n-1)+f(n-2)+...+f(0) - 变态跳台阶问题：规律从
n=1开始,f(n)=2^(n-1)
public class JZ9 {
// f(n)=f(n-1)+f(n-2)+...+f(0)
// f(0)=1,f(1)=1,f(2)=2,f(3)=4
// 变态跳台阶问题：规律从n=1开始,f(n)=2^(n-1)
public int jumpFloorII(int target) {
if (target == 0 || target == 1) {
return 1;
}
return (int) Math.pow(2, target - 1);
}
} 剑指19 正则表达式匹配
题目：请实现一个函数用来匹配包 ' . '和' * '的正则表达式。模式中的字符'.'表示任意一个字符，而' * '表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab* a c * a"匹配，但与"aa.a"和"ab*a"均不匹配。
示例 1:
输入:s = "aa"p = "a"输出: false解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:s = "aa"p = "a*"输出: true解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:
输入:s = "ab"p = ".*"输出: true解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:
输入:s = "aab"p = "c*a*b"输出: true解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入:s = "mississippi"p = "mis*is*p*."输出: falses 可能为空，且只包含从 a-z 的小写字母。p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。
分析：
- 得去看K神题解：地址如下
- 状态数组：设二维数组
dp[m+1][n+1]，m和n是s、p的长度- 特殊说明：
dp[i][j]表示s下标为s[i-1]的字符，p下标为p[j-1]字符
- 特殊说明：
- 初始化：
dp[i][j]表示 s的前i个字符和p的前j个字符是否匹配dp[0][0]=true，表示s和p的前0个字符均为空串肯定匹配- 若s是空串且p 的偶数次下标为∗*∗,那也是匹配的
- 状态转移：
p.charAt(j - 1) == '*',有三种情况匹配dp[i][j - 2]，既是p[j-2]出现0次(dp[i - 1][j] && s.charAt(i - 1) == p.charAt(j - 2)，p[j-2]出现1次 且 当前i-1和j-2指向的字符相同dp[i - 1][j] && p.charAt(j - 2) == '.'，最特殊情况:p[j-2]=. p[j-1]=*时，根据条件知是万能匹配
p.charAt(j - 1) != '*',有两种情况匹配dp[i - 1][j - 1] && s.charAt(i - 1) == p.charAt(j - 1)，前面元素之前都匹配 且 当前元素也相同dp[i - 1][j - 1] && p.charAt(j - 1) == '.'，前面元素之前都匹配 且 p的当期元素是.
- 返回值：
dp[m][n]
public class Solution {
// 动态规划
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
// dp[i][j]表示s前i-1个字符,p前j-1个字符是否匹配
// 所以二维数组长度为(m+1)*(n+1)
boolean[][] dp = new boolean[m + 1][n + 1];
// 分析动态转移：dp[i][j]需要dp[i][j-1]等状态
// 所以需要先初始化dp[0][0]和首行
// 初始化dp[0][0] :两个空串是匹配的
dp[0][0] = true;
// 初始化首行:i=0,将s为看为空串;j=2开始遍历,步长为2
for (int j = 2; j < n + 1; j += 2) {
// p[j-1]为*,则dp[0][j]=dp[0][j-2]
dp[0][j] = p.charAt(j - 1) == '*' && dp[0][j - 2];
}
for (int i = 1; i < m + 1; i++) {
for (int j = 1; j < n + 1; j++) {
// 当p[j-1]=*时,有三种情况
if (p.charAt(j - 1) == '*') {
if (dp[i][j - 2]) {// p[j-2]出现0次
dp[i][j] = true;
} else if (dp[i - 1][j] && s.charAt(i - 1) == p.charAt(j - 2)) {// p[j-2]出现1次 且 当前i-1和j-2指向的字符相同
dp[i][j] = true;
} else if (dp[i - 1][j] && p.charAt(j - 2) == '.') {// 最特殊情况:p[j-2]=. p[j-1]=*时 根据条件知是万能匹配
dp[i][j] = true;
}
} else {// 当p[j-1]!=*时,有两种情况
if (dp[i - 1][j - 1] && s.charAt(i - 1) == p.charAt(j - 1)) {// 前面元素之前都匹配 且 当前元素也相同
dp[i][j] = true;
} else if (dp[i - 1][j - 1] && p.charAt(j - 1) == '.') { // 前面元素之前都匹配 且 p的当期元素是.
dp[i][j] = true;
}
}
}
}
return dp[m][n];
}
} 牛客JZ52
public class JZ52 {
public boolean match(String str, String pattern) {
int m = str.length();
int n = pattern.length();
// dp[i][j]表示s前i-1个字符,p前j-1个字符是否匹配
// 所以二维数组长度为(m+1)*(n+1)
boolean[][] dp = new boolean[m + 1][n + 1];
// 分析动态转移：dp[i][j]需要dp[i][j-1]等状态
// 所以需要先初始化dp[0][0]和首行
// 初始化dp[0][0] :两个空串是匹配的
dp[0][0] = true;
// 初始化首行:i=0,将s为看为空串;j=2开始遍历,步长为2
for (int j = 2; j < n + 1; j += 2) {
// p[j-1]为*,则dp[0][j]=dp[0][j-2]
dp[0][j] = pattern.charAt(j - 1) == '*' && dp[0][j - 2];
}
for (int i = 1; i < m + 1; i++) {
for (int j = 1; j < n + 1; j++) {
// 当p[j-1]=*时,有三种情况
if (pattern.charAt(j - 1) == '*') {
if (dp[i][j - 2]) {// p[j-2]出现0次
dp[i][j] = true;
} else if (dp[i - 1][j] && str.charAt(i - 1) == pattern.charAt(j - 2)) {// p[j-2]出现1次 且 当前i-1和j-2指向的字符相同
dp[i][j] = true;
} else if (dp[i - 1][j] && pattern.charAt(j - 2) == '.') {// 最特殊情况:p[j-2]=. p[j-1]=*时 根据条件知是万能匹配
dp[i][j] = true;
}
} else {// 当p[j-1]!=*时,有两种情况
if (dp[i - 1][j - 1] && str.charAt(i - 1) == pattern.charAt(j - 1)) {// 前面元素之前都匹配 且 当前元素也相同
dp[i][j] = true;
} else if (dp[i - 1][j - 1] && pattern.charAt(j - 1) == '.') { // 前面元素之前都匹配 且 p的当期元素是.
dp[i][j] = true;
}
}
}
}
return dp[m][n];
}
} 剑指42 连续子数组最大值
题目：输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
补充：遇到正数，就加；遇到负数，会对当前子数组和产生负效应，就不加负数！
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
提示：
1 <= arr.length <= 10^5-100 <= arr[i] <= 100
分析：
- 这题适合初学动态规划，连续子数组的最大和：遇到前i-1的和>0，就加上；遇到i-1的和<=0，就舍弃
- 初始化：一个
dp数组，长度为原数组长度dp[i]表示前i个元素的子数组最大和，dp[0]=nums[0]- 同时定义一个
max=nums[0]，记录dp数组中的最大值
- 状态转移：从
i=1开始遍历原数组dp[i-1]<=0，产生负影响，就舍弃，dp[i]=nums[i]dp[i-1]>0，产生正影响，dp[i]=dp[i-1]+nums[i]- 更新
max为当前dp[i]和max的最大值
- 返回：
max
public class Solution {
// 动态规划
public int maxSubArray(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
// 初始化dp:dp[i]表示nums中前i个元素的最大和
int[] dp = new int[nums.length];
// 根据动态转移dp[i]与dp[i-1]有关，思考初始化dp[0]
dp[0] = nums[0];
// 初始化max=nums[0],千万别是0或者整型最小值
int max = nums[0];
for (int i = 1; i < nums.length; i++) {// 从第二个数开始遍历
// 前i-1元素的最大和<=0,产生负影响,舍弃
if (dp[i - 1] <= 0) {
dp[i] = nums[i];
} else {// 前i-1元素的最大和>0,产生正影响
dp[i] = dp[i - 1] + nums[i];
}
// 更新最大值
max = Math.max(max, dp[i]);
}
return max;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.println(solution.maxSubArray(arr));
}
} 牛客JZ30
public class JZ30 {
public int FindGreatestSumOfSubArray(int[] array) {
if (array.length == 1) {
return array[0];
}
int[] dp = new int[array.length];
dp[0] = array[0];
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (dp[i - 1] <= 0) {
dp[i] = array[i];
} else {
dp[i] = dp[i - 1] + array[i];
}
max = Math.max(dp[i], max);
}
return max;
}
} 剑指46 把数字翻译成字符
题目：给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258输出: 5解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
提示：
0 <= num < 231
分析：
力扣K神题解，地址如下:
初始化：动态数组
dp[i]代表以xi为结尾的翻译数量,dp长度为n+1，理由见注释状态转移：
- 将
num转换为字符串 - 从第三位数开始遍历字符串
- 如果
subStr可以整体翻译,dp[i]=dp[i-1]+dp[i-2] - 如果
subStr不能整体翻译,dp[i]=dp[i-1] - 整体翻译判断：
(subStr.compareTo("10") >= 0 && subStr.compareTo("25") <= 0)
- 如果
- 将
返回值：返回
dp[n]即可
public class Solution {
// 注意:0-a,1-b,...,25-z
// 动态规划:dp[i]=dp[i-2]+dp[i-1] or dp[i-1]
public int translateNum(int num) {
// 将num转换为字符串
String str = String.valueOf(num);
int n = str.length();
// dp[i]代表以xi为结尾的翻译数量,dp长度为n+1
int[] dp = new int[n + 1];
// 初始化dp[0]=dp[1]=1,表示“无数字”和"str第一位的翻译数量"
// dp[0]=1怎么推?因为dp[1]=1,dp[2]要么=1,要么=2,当dp[2]=2时,dp[0]必为1
dp[0] = dp[1] = 1;
// 从第三位数开始遍历dp
for (int i = 2; i <= n; i++) {
// 原串str中拆分xi-1+xi组成的字符串subStr，注意下标变换
String subStr = str.substring(i - 2, i);
// 如果subStr可以整体翻译,说明subStr值需要[10,25]
if (subStr.compareTo("10") >= 0 && subStr.compareTo("25") <= 0) {
dp[i] = dp[i - 2] + dp[i - 1];
} else {// 否则sub不能被翻译
dp[i] = dp[i - 1];
}
}
return dp[n];
}
} 剑指47 礼物的最大值
题目：在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:
输入: [ [1,3,1], [1,5,1], [4,2,1]]输出: 12解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
提示：
0 < grid.length <= 2000 < grid[0].length <= 200
分析：
- 理解题目含义：当前坐标的礼物最大值来自它左边或上边的最大值+它本身，显然就是动态规划，搞清楚状态转移就行
- 初始化：
dp[m][n],m和n分别为grid的行数和列数dp[0][0]=grid[0][0],因为原点的最大礼物值就是它本身- 第一行：
dp[i][j] = dp[i][j - 1] + grid[i][j]; - 第一列：
dp[i][j] = dp[i - 1][j] + grid[i][j];
- 状态转移：
dp[i][j]=max{左边，上边}+grid[i][j] - 返回值：
dp最后一个元素即可
public class Solution {
// 动态规划:最容易理解的写法
public int maxValue(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
// dp[i][j]表示到达grid[i][j]时的礼物最大值
int[][] dp = new int[m][n];
// 状态转移:dp[i][j]=Max{dp[i-1][j],dp[i][j-1]}+grid[i][j]
// 根据状态转移，初始化dp[0][0]、第一行、第一列
dp[0][0] = grid[0][0];
for (int i = 1; i < n; i++) {
dp[0][i] = dp[0][i - 1] + grid[0][i];
}
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
// 常规情况
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
// 左边或上边的最大值+grid[i][j]
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
} 剑指49 丑数
题目：我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10输出: 12解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1 是丑数。n 不超过1690。
分析：
- 丑数=较小的一个丑数 ×（2,3,5）中的某个数 ：
- 假设丑数Xi = (Xa × 2 或者 Xb × 3 或者Xc × 5)
- 由于
Xa，Xb，Xc均为较小的丑数，如果一直往前推到最初，条件给了第一个丑数是1，第二个丑数一定是较小的某个丑数×（2,3,5）某一个得来的，由于已知第二丑数是2，显然是取（2,3,5）*1的最小值才等于2，后面的丑数递推也是如此
- 推出公式：
- 通用公式：
dp[i]=min{dp[a-1]*2,dp[b-1]*3,dp[c-1]*5} - 指针后移：
dp[a-1]*2<=dp[i]<dp[a]*2 - 指针后移：
dp[b-1]*3<=dp[i]<dp[b]*3 - 指针后移：
dp[c-1]*5<=dp[i]<dp[c]*5 - 注意：最小值都相同的时候，指针都必须同时后移
- 通用公式：
- 初始化：
dp[i]表示第i+1个丑数，dp[]长度显然是参数n，初始化dp[0]=1- 初始化三个指针,
a指向2倍数,b指向3倍数,c指向5倍数
- 状态转移：从第二个数开始遍历
dp数组- 由于
dp[i]=min{dp[a-1]*2,dp[b-1]*3,dp[c-1]*5},先算出每个指针可能会指向的下一个数的值，选出最小值，就是这一轮的dp[i] - 后移指针，利用
dp[a-1]*2<=dp[i]<dp[a]*2性质，dp[i]等于哪个ni，哪个ni对应的指针就要后移一位，多个都相同，多个指针都后移一位
- 由于
- 返回值：
dp[n-1]
public class Solution {
// 返回第n个丑数,丑数是只含2,3,5的因数
public int nthUglyNumber(int n) {
// 初始化:三个指针,a指向2倍数,b指向3倍数,c指向5倍数
int a = 0, b = 0, c = 0;
// dp[i]表示第i+1个丑数
int[] dp = new int[n];
// 初始化dp:dp[0]=1,第一个丑数是1
dp[0] = 1;
for (int i = 1; i < n; i++) {
// 公式:dp[i]=min{dp[a-1]*2,dp[b-1]*3,dp[c-1]*5}
int n1 = dp[a] * 2;
int n2 = dp[b] * 3;
int n3 = dp[c] * 5;
dp[i] = Math.min(Math.min(n1, n2), n3);
// 接下来移动指针
// dp[a-1]*2<=dp[i]<dp[a]*2
if (dp[i] == n1) {
a++;
}
// dp[b-1]*3<=dp[i]<dp[b]*3
if (dp[i] == n2) {
b++;
}
// dp[c-1]*5<=dp[i]<dp[c]*5
if (dp[i] == n3) {
c++;
}
}
return dp[n - 1];
}
} 牛客JZ23
public class JZ23 {
public int GetUglyNumber_Solution(int index) {
if (index == 0) {
return 0;
}
int a = 0, b = 0, c = 0;
int[] dp = new int[index];
dp[0] = 1;
for (int i = 1; i < index; i++) {
int n1 = dp[a] * 2;
int n2 = dp[b] * 3;
int n3 = dp[c] * 5;
dp[i] = Math.min(Math.min(n1, n2), n3);
if (dp[i] == n1) {
a++;
}
if (dp[i] == n2) {
b++;
}
if (dp[i] == n3) {
c++;
}
}
return dp[index - 1];
}
} 剑指60 n个骰子的点数
题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
示例 1:
输入: 1输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例 2:
输入: 2输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]1 <= n <= 11
分析：
- 力扣K神题解，地址如下：
- 为了降低时间复杂度，定义两个一位数组：
dp和next数组dp数组：保存第i个筛子的点数和概率，初始化6个大小，初始化元素概率1.0/6.0next：记录下一轮dp数组，最后让dp指向next
- 明确概念：第
n个骰子的点数和总数：5*n+1，因为1个骰子:6种点数和;2个骰子:6+5种点数和 - 初始化第
1个骰子:点数和总数为6个,概率都为1.0/6.0 - 计算第
2个到第n个骰子的点数和概率- 每一轮生成该论的点数和总数长度的
next数组 - 遍历上一轮的
dp数组，每6个数遍历这一轮的next数组 - 上一轮的
dp[j]对它之后的每6个数都产生了dp[j]/6.0的影响 - 这一轮的
dp指向下一轮的next
- 每一轮生成该论的点数和总数长度的
- 返回：
dp即可
public class Solution {
public double[] dicesProbability(int n) {
// 初始化第1个骰子:点数和总数为6个,概率都为1.0/6.0
double[] dp = new double[6];
Arrays.fill(dp, 1.0 / 6.0);
// 计算第2个到第n个骰子的点数和概率
for (int i = 2; i <= n; i++) {
// 1个骰子:6种点数和;2个骰子:6+5种点数和
// n个骰子:6+(n-1)*5=5n+1种点数和
double[] next = new double[5 * i + 1];
// 遍历上一轮的dp数组
for (int j = 0; j < dp.length; j++) {
// 每6个数,遍历这一轮的next数组
for (int k = 0; k < 6; k++) {
// 上一轮的dp[j]对它之后的每6个数都产生了dp[j]/6.0的影响
next[j + k] += dp[j] / 6.0;
}
}
// 上一轮的dp数组更新为这一轮的next数组
dp = next;
}
return dp;
}
} 剑指62 圆圈中最后剩下的数字
题目：0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
示例 1：
输入: n = 5, m = 3输出: 3
示例 2：
输入: n = 10, m = 17输出: 2
限制：
1 <= n <= 10^51 <= m <= 10^6
分析：
- 约瑟夫回环问题推导：
- 数组为[0,n-1]，删除第m个数，对应删除m-1下标的数，由于是循环，所以是删除(m-1)%n下标的数，剩下第m%n的数开始重新计算
- 记一轮删除后，从t=m%n下标的元素开始重新计数，那么t位置就是上一轮删除t-1位置后留下来的第一个数，也就是解f(n)问题的解！！
- 设n=5，m=3，最后剩下的数字是3
- [n,m]问题：[0,1,2,3,4]，不关心这一层，去关心上一层怎么得到解的
- [n-1,m]问题：[0,1,2,3]，先假设我们知道[n-1,m]的解是数字0(为了与初始数组的0下标对齐)，那么[n,m]的解就是（0+m）%n = (0+3)%5=3
- 递推出公式：
f(n，m)=[ f(n-1，m)+ m ] %n，且指定f(1,m) =0
public class Solution {
// 动态规划:最容易理解的版本
public int lastRemaining1(int n, int m) {
int[] dp = new int[n];
// f(1,m)解恒为0
dp[0] = 0;
for (int i = 1; i < n; i++) {
// 动态转移方程:f(n,m)=[f(n-1,m)+m]%n
// 注意:dp[i]时,数组长度为i+1
dp[i] = (dp[i - 1] + m) % (i + 1);
}
return dp[n - 1];
}
// 动态规划:无需开辟dp数组
public int lastRemaining2(int n, int m) {
// n代表数组长度,n=长度1时,res=0
int res = 0;
for (int i = 2; i <= n; i++) {
// res = (res +m) % n
res = (res + m) % i;
}
return res;
}
} 剑指63 股票最大利润
题目：假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
示例 1:
输入: [7,1,5,3,6,4]输出: 5解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]输出: 0解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
分析：
- 理解题意：
[7,1,5,3,6,4]代表股票价格，每一个数字都可以是买入\卖出（买卖只能各一次），并且卖出价格需要大于买入价格 - 公式推导：
- 最大利润 =max（之前的最大利润，今天的利润）
- 之前的最大利润，初始化：
dp[0]=0，因为第一天是没有利润的 - 今天的利润 = 今天的价格 - 之前的最低价格
- 动态规划：
- 定义
dp[i]：表示从第1天到第i+1天以来的最大利润，=prices[i]之前的最大利润 minPrice变量：记录第1天到第i+1天以来的最小价格
- 定义
- 动态转移：
dp[i]= max(dp[i-1],prices[i]-minPrices(i)) - 返回值：
dp[len-1]
public class Solution {
// 动态规划
public int maxProfit1(int[] prices) {
if (prices.length == 0) {
return 0;
}
int n = prices.length;
// dp[i]:表示prices[i]为结尾的数组最大利润
int[] dp = new int[n];
// 第一日利润为0,因为一天只能买不能卖
dp[0] = 0;
int minPrice = prices[0];
for (int i = 1; i < n; i++) {
// 先计算[0,i]的最小价格作为买入价格
minPrice = Math.min(minPrice, prices[i]);
// dp[i]=max(前一日以来的最大利润,第i日的最大利润=当前价格-最小买入价格)
dp[i] = Math.max(dp[i - 1], prices[i] - minPrice);
}
return dp[n - 1];
}
// 高度概括：当日最大利润 = max(当天价格-截止目前的最小价格)
public int maxProfit2(int[] prices) {
if (prices.length == 0) {
return 0;
}
int minPrice = prices[0];
int maxProfit = 0;// 没有利润，规定为0
for (int i = 1; i < prices.length; i++) {
minPrice = Math.min(minPrice, prices[i]);
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
}
return maxProfit;
}
} 剑指66 构建乘积数组
题目：给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
示例:
输入: [1,2,3,4,5]输出: [120,60,40,30,24]
提示：
所有元素乘积之和不会溢出 32 位整数a.length <= 100000
分析：
- 最简单的方法：先算出所有数的乘积结果，每次遍历到它，再除它本身就能得到其他元素乘积结果，但是题目规定不能用除法
- 维护两个
dp数组：left、right分别计算a[i]左边、右边所有数的乘积结果 - 初始化：两个
dp数组左右两边的乘积为1 left从1到len计算、right从len-2到0计算，最后构建结果集即可
public class Solution {
// 2个dp和1个res
public int[] constructArr(int[] a) {
if (a == null || a.length == 0) {
return new int[]{};
}
int len = a.length;
int[] left = new int[len];// a[i]中每个元素左边所有数的乘积
int[] right = new int[len];// a[i]中每个元素右边所有数的乘积
int[] res = new int[len];
// 初始化，两个dp数组左右两边的乘积为1
left[0] = 1;
right[len - 1] = 1;
for (int i = 1; i < len; i++) {// left从1到len
left[i] = left[i - 1] * a[i - 1];
}
for (int i = len - 2; i >= 0; i--) {// right从len-2到0计算
right[i] = right[i + 1] * a[i + 1];
}
for (int i = 0; i < len; i++) {// 构建结果集
res[i] = left[i] * right[i];
}
return res;
}
} 牛客JZ51
public class JZ51 {
// 1个dp和1个res
public int[] multiply(int[] A) {
if (A == null || A.length == 0) {
return new int[]{};
}
int len = A.length;
int[] left = new int[len];// a[i]中每个元素左边所有数的乘积
int[] res = new int[len];
left[0] = 1;
for (int i = 1; i < len; i++) {// left从1到len
left[i] = left[i - 1] * A[i - 1];
}
int right = 1;// 以1个变量维护a[i]右边乘积结果，初始化为1
for (int i = len - 1; i >= 0; i--) {// 结果集从len-1到0构建
res[i] = left[i] * right;// 每次都为当前数的左边乘积结果*它右边乘积结果
right *= A[i];// 更新迭代arr[i]右边乘积结果
}
return res;
}
} 递归
剑指12 矩阵中的路径
题目:给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"输出：true
示例 2：
输入：board = [["a","b"],["c","d"]], word = "abcd"输出：false
提示：
1 <= board.length <= 2001 <= board[i].length <= 200board 和 word 仅由大小写英文字母组成
分析：
- 遍历二维数组，匹配到满足
word单词的解，就返回，典型的回溯问题，也就是要深度遍历，使用递归 - 定义一个函数
bfs(char[][] board, char[] word, int row, int col, int k)，k是遍历word的指针，函数代表遍历board和word的字符数组，匹配到word末尾都匹配上，就返回true - 递归结束条件：行列指针越界 or 当前字符没有匹配上
- 递推过程：
- 递归未结束，先判断是k是否到达
word末尾，到达就说明这个word都匹配成功，返回true - 暂时重置当前遍历元素为
’\0'，防止重复递归 - 递归上下左右，只要有一个匹配上，赋值给布尔变量
res,体会回溯赋值的过程 - 将暂时重置元素，设置会原值，防止元素改变
- 递归未结束，先判断是k是否到达
- 返回：
res
public class Solution {
public boolean exist(char[][] board, String word) {
char[] words = word.toCharArray();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (dfs(board, words, i, j, 0)) {
return true;
}
}
}
return false;
}
// 递归+剪枝+回溯，当前(i,j)如果匹配，index+1
private boolean dfs(char[][] board, char[] word, int i, int j, int index) {
// 递归失败:越界+匹配失败/剪枝
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word[index]) {
return false;
}
// 递归成功:未越界+board[row][col] = word[k]+k遍历到单词末尾
if (index == word.length - 1) {
return true;
}
// 剪枝:递归未结束,将当前元素设为空字符,防止后面递归重复访问
board[i][j] = '\0';
// 四个方向开始递归，记录结果给res
boolean res = (dfs(board, word, i + 1, j, index + 1) || dfs(board, word, i - 1, j, index + 1)
|| dfs(board, word, i, j + 1, index + 1) || dfs(board, word, i, j - 1, index + 1));
// 回溯:将剪枝原值返回给当前元素
board[i][j] = word[index];
return res;
}
} 牛客JZ65
public class JZ65 {
public boolean hasPath(char[][] matrix, String word) {
char[] cs = word.toCharArray();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (dfs(matrix, cs, i, j, 0)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] matrix, char[] word, int i, int j, int index) {
if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || matrix[i][j] != word[index]) {
return false;
}
if (index == word.length - 1) {
return true;
}
matrix[i][j] = '\0';
boolean res = dfs(matrix, word, i + 1, j, index + 1)
|| dfs(matrix, word, i - 1, j, index + 1)
|| dfs(matrix, word, i, j + 1, index + 1)
|| dfs(matrix, word, i, j - 1, index + 1);
matrix[i][j] = word[index];
return res;
}
} 剑指13 机器人运动返回
题目:地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
示例 1：
输入：m = 2, n = 3, k = 1输出：3
示例 2：
输入：m = 3, n = 1, k = 0输出：1
提示：
1 <= n,m <= 1000 <= k <= 20
分析：
- 行列坐标之和怎么求？查看
digitSum学习怎么求数位和 - 法：
dfs1(boolean[][] visited, int i, int j, int k)- 递归结束条件：
- 定义
digitSum来计算(i,j)的数位和 - 数字下标越界 or 行列数位和>k or 该行列位置已被访问过
- 定义
- 递归工作：标记该位置已被访问
- 递归返回：1+右边递归+下边递归
- 递归结束条件：
public class Solution {
public int movingCount(int m, int n, int k) {
boolean[][] visited = new boolean[m][n];
return dfs(visited, 0, 0, k);
}
// 明确概念:机器人从(0,0)出发,行列数位和<k的坐标,只会在(0,0)的右边或者下边,每次只用递归i+1/j+1
private int dfs(boolean[][] visited, int i, int j, int k) {
// 递归结束，返回0: 坐标越界 or 行列坐标数位和超过k or 已经访问过
if (i >= visited.length || j >= visited[0].length || digitSum(i) + digitSum(j) > k || visited[i][j]) {
return 0;
}
// 未访问过,就设置为true,代表访问过
visited[i][j] = true;
// +1:当前访问位置就是一个可以访问单元格的数量,所以加1
// i+1/j+1:机器人从(0,0)出发,所有可达解均在下边或右边,所以只用递归i+1或j+1
return 1 + dfs(visited, i + 1, j, k) + dfs(visited, i, j + 1, k);
}
// 求一个数的数位和
private int digitSum(int num) {
int sum = 0;
while (num != 0) {
// 加上num的个位数，然后num/10
sum += num % 10;
num = num / 10;
}
return sum;
}
} 牛客JZ66
public class JZ66 {
// 用全局变量res来写，dfs就不用返回int
private int res;
public int movingCount(int threshold, int rows, int cols) {
res = 0;
boolean[][] visited = new boolean[rows][cols];
dfs(visited, 0, 0, threshold);
return res;
}
private void dfs(boolean[][] visited, int i, int j, int k) {
if (i >= visited.length || j >= visited[0].length || digitSum(i) + digitSum(j) > k || visited[i][j]) {
return;
}
visited[i][j] = true;
res++;
dfs(visited, i + 1, j, k);
dfs(visited, i, j + 1, k);
}
private int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
} 位运算
剑指15 二进制1的个数
题目：请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
示例 1：
输入：00000000000000000000000000001011输出：3解释：输入的二进制串 00000000000000000000000000001011 ***有三位为 '1'。
示例 2：
输入：00000000000000000000000010000000输出：1解释：输入的二进制串 00000000000000000000000010000000 ***有一位为 '1'。
示例 3：
输入：11111111111111111111111111111101输出：31解释：输入的二进制串 11111111111111111111111111111101 ***有 31 位为 '1'。说明是无符号右移，最高位不计算
提示：输入必须是长度为 32 的 二进制串 。
分析：
- 方法1：n&1，这是最容易想到的方法
- 注意：示例3告诉我们n是>>>无符号右移；循环条件由于n可能为负数，应该是n≠0
// n & 1 是最容易想到的方法
public int hammingWeight(int n) {
int res = 0;
while (n != 0) {// n可为负数，循环条件是n!=0
res += n & 1;
n >>>= 1;// 无符号位移
}
return res;
} - 方法2：n&(n-1)，每次消除n最右边的1，直到n消除0为止
- 比如：
- n=111，n-1=110，n &= n-1，n=110，res+1
- n=110，n-1=101，n &= n-1，n=100，res+1
- n=100，n-1=010，n &= n-1，n=000，res+1
- n=000，循环结束，返回res
// n & (n - 1)消除n最右边的1,速度更快
public int hammingWeight(int n) {
int res = 0;
while (n != 0) {
n = n & (n - 1);// 消除n最右边的1,一直消除到0结束
res++;
}
return res;
} 牛客JZ11
public class JZ11 {
public int NumberOf1(int n) {
int res = 0;
while (n != 0) {
n = n & (n - 1);// 消除最右边的1，知道n为0为止
res++;
}
return res;
}
} 剑指56-I 数组中1出现的次数I
题目：一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6]输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]输出：[2,10] 或 [10,2]
限制：
2 <= nums.length <= 10000
分析：
- 先学习：“一个数组中，一个数为奇数次，其他数为偶数次”
- 方法是
res ^= num
- 方法是
// 先学习:一个数组中除一个数字外，其余数字出现了两次，找出这个数字
public int oneNumbers(int[] nums) {
// 0与任何数异或都为任何数本身
int res = 0;
for (int num : nums) {
res ^= num;
}
return res;
} - 本题可扩展为“两个数为奇数次，其他数为偶数次”，解法相同
- 遍历原数组，用
a ^= cur异或原数组中每个数，a为2个出现1次数字的异或结果 - 利用
rightOne = a & (~a + 1)，可找出最右边不相等的二进制位，去将原数组分组 - 遍历原数组，如果
(rightOne & cur) == 0，说明其中出现1次的数在这一个分组里；另一个在(rightOne & cur) ！= 0里
- 遍历原数组，用
public class Solution {
public int[] singleNumbers(int[] nums) {
int a = 0, b = 0;
// 第一次遍历,a = 数1^数2
for (int cur : nums) {
a ^= cur;
}
// 找到a中第一个不相同的二进制位=数1和数2不相同的一个二进制位
// 由于是十进制表示，所以rightOne 是2^n的表示形式
int rightOne = a & (~a + 1);
a = 0;// 重置a为0，便于下面^操作
// 第二次遍历,利用不相同的二进制位,将原数组分为独立含数1和数2的两个部分
for (int cur : nums) {
if ((rightOne & cur) == 0) {// 这里只能用！=0或者==0来判断属于哪一个阵营
b ^= cur;
} else {
a ^= cur;
}
}
return new int[]{a, b};
}
} 剑指56-II 数组中1出现的次数II
题目：在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1：
输入：nums = [3,4,3,3]输出：4
示例 2：
输入：nums = [9,1,7,9,7,9,7]输出：1
限制：
1 <= nums.length <= 100001 <= nums[i] < 2^31
分析：
- 法：
- 哈希表<字符，出现次数>，如果kay已经存在过了，value设置为-1；否则为1
- 遍历哈希表，取出value=1的key即可
// 法1:遇事不决,找哈希爸爸
public int singleNumber1(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
if (!map.containsKey(num)) {
map.put(num, 1);
} else {
// 已经包含过的，记为-1,减少get操作
map.put(num, -1);
}
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() == 1) {
return entry.getKey();
}
}
return -1;
} 数学
剑指14-I 剪绳子I
题目：给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问k[0]×k[1]...×k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
示例 1：
输入: 2输出: 1解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10输出: 36解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：n最多只到58
2 <= n <= 58
分析：
- 规律：尽可能将绳子以长度 3 等分为多段时，乘积最大，力扣K神题解证明
- 设
n/3=a，n%3=b- 余数0：说明是刚好整分3段，
res = 3 ^ a - 余数为1：想要最大值，将倒数第二段的3+倒数第一段的1变为2+2，因为3×1<2×2，
res = 3 ^ (a-1)×(2×2) - 余数为2：
res = 3^(a) × 2
- 余数0：说明是刚好整分3段，
public class Solution {
// 将长度为n的绳子等分为m段，使其乘积最大，m、n都是整数，n>1并且m>1，m<=n
// 2 <= n <= 58，pow结果不会越界
public int cuttingRope(int n) {
// n=2，m最小为2，乘积1*1=1，返回1
// n=3，m最小为2，乘积1*2=2，返回2
if (n <= 3) {
return n - 1;
}
// 尽可能将绳子n以3等分时，乘积最大
// 2 <= n <= 58，乘积结果不会越界
int a = n / 3;
// 求n三等分后最后一段3的余数
int b = n % 3;
// 余数有以下三种情况
if (b == 0) {// 余0,直接返回3^a为最大乘积
return (int) Math.pow(3, a);
} else if (b == 1) {// 余1,将三等分后倒数第二段中的3+最后一段的1转换为2乘2,因为3*1<2*2
return (int) Math.pow(3, a - 1) * (2 * 2);
}
// 余2,直接返回3^a*(2),最后一段不需要拆分
return (int) Math.pow(3, a) * (2);
}
} 牛客JZ67
public class JZ67 {
// 将长度为target的绳子等分为m段，使其乘积最大，m、target都是整数，target>1并且m>1，m<=target
public int cutRope(int target) {
if (target <= 3) {
return target - 1;
}
int a = target / 3;
int b = target % 3;
if (b == 0) {
return (int) Math.pow(3, a);
} else if (b == 1) {
return (int) Math.pow(3, a - 1) * (2 * 2);
}
return (int) Math.pow(3, a) * 2;
}
} 剑指14-II 剪绳子II
题目：给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]×k[1]...×k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。这一题答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。这一题和上一题的区别是乘积会越界！
示例 1：
输入: 2输出: 1解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10输出: 36解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：n在这里到1000
2 <= n <= 1000
分析：
- 循环求余解决幂次越界问题
public class Solution {
// 将长度为n的绳子等分为m段，使其乘积最大，m、n都是整数，n>1并且m>1，m<=n
// 2 <= n <= 1000，此题的pow过程会越界
public int cuttingRope(int n) {
if (n <= 3) {
return n - 1;
}
int b = n % 3;
long rem = 1;// 余数,long类型
int x = 3;// 底数为3
int standard = 1000000007;// 题目规定的取余数
// n= 3a + b -> a= n/3 - b/3 -> a= n/3 -1
int a = n / 3 - 1;
// 从1到a开始循环求余
for (int i = 1; i <= a; i++) {
rem = (rem * x) % standard;
}
// 剩下和剪绳子I类似啦，将I中的pow换成rem即可
if (b == 0) {
return (int) (rem * (3) % standard);
} else if (b == 1) {
return (int) (rem * (2 * 2) % standard);
} else {
return (int) (rem * (3 * 2) % standard);
}
}
} 剑指16 数值的整数次方
题目：实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n）。不得使用库函数，同时不需要考虑大数问题。
示例 1：
输入：x = 2.00000, n = 10输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3输出：9.26100
示例 3：
输入：x = 2.00000, n = -2输出：0.25000解释：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0-231 <= n <= 231-1-104 <= xn <= 104
分析：学习快速幂法
- 从二进制角度推导出公式，力扣K神题解有详细推导
public class Solution {
public double myPow(double x, int n) {
if (x == 0) {
return 0.0;
}
if (x == 1) {
return 1.0;
}
// b指向幂次n，由于n=−2147483648时, n=-n会溢出，所以设b是long类型
long b = n;
// n为负数幂时，x取倒数，b=-b变成正数
if (b < 0) {
x = 1 / x;
b = -b;
}
double res = 1.0;
while (b > 0) {// 这里b=|b|,循环条件>0即可；如果b能为负数，循环条件是b!=0
if ((b & 1) == 1) {// bi=1时，res乘xi
res *= x;
} else {// bi=0时,res乘1
res *= 1;
}
// b有多少位二进制数，x就成多少次
x *= x;
// b二进制位右移一位,因为此时b=|b|,有符号右移还是无符号右移都行
b >>= 1;
}
return res;
}
} 牛客JZ12
public class Solution {
public double myPow(double x, int n) {
if (x == 0) {
return 0.0;
}
if (x == 1) {
return 1.0;
}
// b指向幂次n，由于n=−2147483648时, n=-n会溢出，所以设b是long类型
long b = n;
// n为负数幂时，x取倒数，b=-b变成正数
if (b < 0) {
x = 1 / x;
b = -b;
}
double res = 1.0;
while (b > 0) {// 这里b=|b|,循环条件>0即可；如果b能为负数，循环条件是b!=0
if ((b & 1) == 1) {// bi=1时，res乘xi
res *= x;
} else {// bi=0时,res乘1
res *= 1;
}
// b有多少位二进制数，x就乘多少次
x *= x;
// b二进制位右移一位,因为此时b=|b|,有符号右移还是无符号右移都行
b >>= 1;
}
return res;
}
} 剑指43 1-n中1出现的次数
题目：输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
示例 1：
输入：n = 12输出：5
示例 2：
输入：n = 13输出：6
分析：
- 将n看成一个x位数的数，定义
- low表示低位数组成的数
- cur表示当前指向的位的数
- high表示高位数组成的数
- digit表示cur指向的第i位上的数的10^i-1^,初始化为10^0^=1
- res记录每轮遍历
- 遍历数组，显然
high == 0 && cur == 0循环结束，反过来high != 0 || cur != 0就是while循环条件 - 每次遍历，通过上面4个变量可以找出计算1出现次数的规律，推导过程：K神力扣题解
- cur=0，1出现的次数为：
high * digit - cur=1，1出现的次数为：
high * digit + low + 1 - cur>1，1出现的次数为：
(high + 1) * digit - 更新前面的4个变量
- cur=0，1出现的次数为：
- 返回：res即可
public class Solution {
public int countDigitOne(int n) {
// 初始化:low,cur,high,digit
int low = 0;
int cur = n % 10;
int high = n / 10;
int digit = 1;// 10^0=1
int res = 0;
while (high != 0 || cur != 0) {// high和cur同时为0，越过了最后一个高位，循环结束
// cur有三种情况:0,1,>1,自己用纸推出这三种表达式
if (cur == 0) {
res += high * digit;
} else if (cur == 1) {
res += high * digit + low + 1;
} else if (cur > 1) {
res += (high + 1) * digit;
}
// 更新low,cur,high,digit
low += cur * digit;
cur = high % 10;
high = high / 10;
digit *= 10;
}
return res;
}
} JZ31 1到n中1出现的次数
public class JZ31 {
// 从1到n中，含有数字1的出现的次数
// 比如：1~13中包含1的数字有1、10、11、12、13因此共出现6次
// 最笨的方法，从1到n统计，每个数中1出现的次数，但是会超时
// 所以找规律，用low、cur、high、digit、res5个变量找规律
public int NumberOf1Between1AndN_Solution(int n) {
int low = 0;
int cur = n % 10;
int high = n / 10;
int digit = 1;
int res = 0;
while (high != 0 || cur != 0) {
if (cur == 0) {
res += high * digit;
} else if (cur == 1) {
res += high * digit + low + 1;
} else if (cur > 1) {
res += (high + 1) * digit;
}
low = cur * digit + low;
cur = high % 10;
high = high / 10;
digit *= 10;
}
return res;
}
} 剑指44 数字序列中的某一位数字
题目：数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。请写一个函数，求任意第n位对应的数字。
示例 1：
输入：n = 3输出：3
示例 2：
输入：n = 11输出：0
限制：
0 <= n < 2^31
分析：力扣K神题解学习
- 看k神题解，画表格，明确
start、digit、count三个概念 - 初始化：
start=1，digit=1，count=(9×start)×digit=9 - 根据
count = 9×start×digit,算出n所在的start和digit- 使用循环,n每次都减去数位区间的数字总数,直到差值<区间总数，就跳出
- 计算n属于该digit下的第几个num
- 公式：
start + (n - 1) / digit
- 公式：
- 计算n属于该digit下的第几个num
- 公式：
(n - 1) % digit
- 公式：
- 返回：
String.valueOf(num).charAt(index) - '0'，因为题目要求返回int
public class Solution {
public int findNthDigit(int n) {
// 明确以下概念:数字num,数位digit,该数位下起始位置start，数位总数count
// 条件给的序列：0123456789101112...,每一位记为数位
// num:我们常见的数字10,11,12，称为数字num
// digit:每个数字的所属的位数，比如数字10是一个两位数,记为digit=2
// start:每位digit表示的位数起始值(即1,10,100),记为start
// count：截止到返回值的数位总数，=9×start×digit,显然初始化为9
long start = 1;
int digit = 1;
long count = 9;
// 根据count = 9×start×digit,算出n所在的start和digit
while (n > count) {// n<count时，代表n是该数位下的某个num
n -= count;
digit++;
start *= 10;
count = 9 * start * digit;
}
// 上面while循环结束,n变为从该数位下的第一个数开始，此时n为[1,2,3...count]
// 计算n属于该digit下的第几个num
long num = start + (n - 1) / digit;
// 计算n是该digit下的第几个num的第几位
int index = (n - 1) % digit;
// 返回值规定为int,定位到char再-'0'即可
return String.valueOf(num).charAt(index) - '0';
}
public static void main(String[] args) {
Solution solution = new Solution();
int n = 11;
System.out.println(solution.findNthDigit(n));
}
} 剑指64 求1+2+...+n
题目：求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
示例 1：
输入: n = 3输出: 6
示例 2：
输入: n = 9输出: 45
限制：
1 <= n <= 10000
分析：
- 先学习
sumN()，明白常见的求和函数递归写法，最终答案是通过它推出来的
private int sumN(int n) {
// 当n=1时停止递归
if (n == 1) {
return 1;
}
// n>1时,开始递归
// sum=n+fun(n-1)=n+n-1+fun(n-2)...
n += sumN(n - 1);
return n;
} - 题目要求不能用乘除、判断等条件语句,就使用&&辅助完成判断
- 修改
sumN()，利用逻辑与的短路效应，完成递归：- 短路效用：前一个条件不满足，后面条件不执行，想到递归结束条件
n=1,改为&&前的条件是n>1
- 短路效用：前一个条件不满足，后面条件不执行，想到递归结束条件
- 特殊说明：Java&&语法注意事项
boolean x =...,因为A&&B整体需要一个返回值接受,否则单独返回会报错A&&B,两边都需要布尔值,A的n>1比较容易想到,B中的>0利用1+...+n>0来凑布尔值
public class Solution {
// 不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句
public int sumNums(int n) {
// n>1时开始递归,不能用条件判断语句,就使用&&辅助完成判断
// boolean x =...,A&&B整体需要一个返回值接受,否则单独返回会报错
// A&&B,两边都需要布尔值,A的n>1比较容易想到,B中的>0利用1+...+n>0来凑布尔值
boolean x = (n > 1) && (n += sumNums(n - 1)) > 0;
// 返回n
return n;
}
} 牛客JZ47
public class JZ47 {
public int Sum_Solution(int n) {
boolean x = n > 1 && (n += Sum_Solution(n - 1)) > 0;
return n;
}
} 剑指65 不用加减乘除做加法
题目：写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
示例:
输入: a = 1, b = 1输出: 2
提示：
a, b 均可能是负数或 0结果不会溢出 32 位整数
分析：
- 观察0与0，0与1，1与0，1与1二进制相加，无进位和 = 异或的结果，进位值=与的结果
- 推出：
a+b= a与b的进位+a与b的无进位和
public class Solution {
// a+b = 两数无进位和+进位值
public int add(int a, int b) {
// 如果b=0，直接返回a,所以sum初始化为a
int sum = a;
while (b != 0) {// 进位信息为0才停止
sum = a ^ b;// a+b不能用+，那就sum用^先算无进位相加的结果
b = (a & b) << 1;// b每次获取成当前两数的进位值结果
a = sum; // a迭代作为下轮的sum
}
return sum;
}
} 牛客JZ28
public class JZ48 {
public int Add(int num1, int num2) {
int sum = num1;
while (num2 != 0) {
sum = num1 ^ num2;
num2 = (num1 & num2) << 1;
num1 = sum;
}
return sum;
}
} 加减乘除不用四则运算
public class AddMinusMultiDivideByBit {
// Q:不能使用算术运算符，分别实现a和b的加、减、乘、除,不用考虑溢出
// 加法:无进位相加(^)+进位的结果(&<<1)
public static int add(int a, int b) {
int sum = a;
while (b != 0) {// 当进位为0时,返回此时的sum
sum = a ^ b;// sum:记录^的结果
b = (a & b) << 1;// b:进位的结果
// 下一轮 a=sum
a = sum;
}
return sum;
}
// 减法:a+(b的相反数)
public static int minus(int a, int b) {
return add(a, negNum(b));
}
// 获得一个数相反数
public static int negNum(int n) {
// 取反+1=该数的相反数
return add(~n, 1);
}
// 乘法:左移a,无符号右移b
public static int multi(int a, int b) {
int res = 0;
while (b != 0) {
// b末尾是1,说明要加1个a
if ((b & 1) != 0) {
res = add(res, a);
}
// a有符号左移一位
a <<= 1;
// b无符号右移一位,因为需要将b磨成0,所以是无符号右移缩小
b >>>= 1;
}
return res;
}
// 判断是否是负数
public static boolean isNeg(int n) {
return n < 0;
}
// 除法:只用考虑a和b是正数的情况
public static int div(int a, int b) {
// 将a、b转换成正数
int x = isNeg(a) ? negNum(a) : a;
int y = isNeg(b) ? negNum(b) : b;
int res = 0;
for (int i = 31; i >= 0; i = minus(i, 1)) {
// 让x右移去够到y
if ((x >> i) >= y) {
res |= (1 << i);
x = minus(x, y << i);
}
}
return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
}
public static int divide(int a, int b) {
if (b == 0) {
throw new RuntimeException("divisor is 0");
}
if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
return 1;
} else if (b == Integer.MIN_VALUE) {
return 0;
} else if (a == Integer.MIN_VALUE) {
int res = div(add(a, 1), b);
return add(res, div(minus(a, multi(res, b)), b));
} else {
return div(a, b);
}
}
} 
投递去哪儿等公司10个岗位 >
