《剑指Offer》打卡活动 Week 7《剑指Offer》第67-76题
79. 滑动窗口的最大值
思路 单调队列O(N)
1. 队列里存放的是下标
2. 遍历所有元素
2.1 先检查队列底部的下标是否过期了，也就是是否已经滑出窗口while (!q.isEmpty() && q.peekFirst() <= i - k + 1) q.pollFirst()
2.2 再检查队列顶部的元素和要加入元素之间的大小关系，也就是保持单调性 while (!q.isEmpty() && nums[i] >= nums[q.peekLast()]) q.pollLast()
2.3 窗口进行滑动，也就是将当前元素入队列 q.offerLast(i) 无论与否窗口的滑动是必然的
2.4 检查是否满足输出条件，也就是窗口的大小是否是k if (i - k + 1 >= 0) res.add(nums[q.peekFirst()]
3. 返回结果
Java代码
class Solution {
public int[] maxInWindows(int[] nums, int k ) {
int n = nums.length;
int[] res = new int[n - k + 1];
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i ++ ) {
while (!q.isEmpty() && q.peekFirst() < i - k + 1) q.pollFirst();
// i + 1 > q.peekFirst + k q.peekFirst已经滑出窗口了 peek取值在区间[i + 1 - k, i]之间
while (!q.isEmpty() && nums[i] >= nums[q.peekLast()]) q.pollLast();
q.offerLast(i);
if (i - k + 1 >= 0) res[i - k + 1] = nums[q.peekFirst()]; // i + 1 >= k 窗口已经形成
}
return res;
}
}
80. 骰子的点数
思路1 DFS
DFS问题需要注意两点：
1. 状态表示（一般从题目里找，问什么，什么就是状态）
2. 递归的顺序
此题中
状态投掷n次, 点数之和为sum的方案数即 dfs(int n, int sum)
顺序 以最后一次投掷为例，我们枚举投掷一次的点数 也就是从1 - 6本次的方案数更新和上一次有关 res += dfs(n - 1, sum - i)
Java代码
class Solution {
public int[] numberOfDice(int n) {
int[] res = new int[6 * n - n + 1];
for (int i = n; i <= 6 * n; i ++ ) {
res[i - n] = dfs(n, i);
}
return res;
}
public int dfs(int n, int sum) {
// 边界条件
if (sum < 0) return 0;
if (n == 0 && sum == 0) return 1; // 找到了一个合法方案
// 递归顺序
int res = 0;
for (int i = 1; i <= 6; i ++ ) {
res += dfs(n - 1, sum - i);
}
return res;
}
}
思路2 动态规划
动态规划是每个状态只遍历一遍，而dfs是存在重复遍历的情况，dp是记忆化搜索了
f[i][j] 投掷i次总和为j的方案数
集合划分中以最后一次投掷的点数划分有 1 2 3 4 5 6个集合
其实是分组背包
n组物品，每组物品的体积分布是1-6，每组之选一个，求体积总和为n-6n的方案数
循环物品组——循环体积——循环决策
Java代码
class Solution {
public int[] numberOfDice(int n) {
int[][] f = new int[n + 1][6 * n + 1];
f[0][0] = 1;
for (int i = 1; i <= n; i ++ ) { // 枚举次数
for (int j = 1; j <= 6 * i; j ++ ) { // 枚举总和
for (int k = 1; k <= Math.min(6, j); k ++ ) { // 枚举最后一次的点数
f[i][j] += f[i - 1][j - k];
}
}
}
int[] res = new int[6 * n - n + 1];
for (int i = n; i <= 6 * n; i ++ ) res[i - n] = f[n][i];
return res;
}
}
按照分组背包优化到一维
class Solution {
public int[] numberOfDice(int n) {
int[] f = new int[6 * n + 1];
for (int i = 1; i <= 6; i ++ ) f[i] = 1; // /动归数组初始值，表示1个骰子扔出1-6的可能数都为1
for (int i = 2; i <= n; i ++ ) { // 枚举次数
for (int j = 6 * n; j >= 0; j -- ) { // 枚举总和
f[j] = 0;
for (int k = 1; k <= 6; k ++ ) { // 枚举最后一次的点数
if(j - k >= 0) f[j] += f[j - k];
}
}
}
int[] res = new int[6 * n - n + 1];
for (int i = n; i <= 6 * n; i ++ ) res[i - n] = f[i];
return res;
}
}
81. 扑克牌的顺子
思路 模拟问题
排序后把除零以外的拿出来
如果有相同的值 不是顺子
看最大最小值直接的差距是不是4以内,如果在，那么中间空缺的数字可以用0来补
Java代码
class Solution {
public boolean isContinuous(int [] numbers) {
if (numbers == null || numbers.length == 0) return false;
Arrays.sort(numbers);
int k = 0;
while (numbers[k] == 0) k ++ ;
for (int i = k + 1; i < numbers.length; i ++ ) {
if (numbers[i] == numbers[i - 1]) return false;
}
return numbers[numbers.length - 1] - numbers[k] <= 4;
}
}
82. 圆圈中最后剩下的数字
思路 约瑟夫环问题
- 递推问题——总结相邻两项之间的关系
f(n, m) = (f(n - 1, m) + m) % n - 边界
f(1, m) = 0
推到过程：
在f(n, m)时，假设编号为x的被选中了，下一轮就从x + 1开始编号, 第m个会被选中，那么可以知道是在原本的f(n, m)轮里的第x + m的会被选中
Java代码
class Solution {
public int lastRemaining(int n, int m) {
if (n == 1) return 0;
return (lastRemaining(n - 1, m) + m) % n;
}
}
83. 股票的最大利润
思路 枚举模拟
如何枚举所有情况，直接枚举在哪一天卖
从第二天开始遍历，用minPrice记录截至第i天前的最小价值，然后看要不要在这一天卖来更新最大利润
Java代码
class Solution {
public int maxDiff(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int minPrice = nums[0];
int res = 0;
for (int i = 1; i < nums.length; i ++ ) {
res = Math.max(res, nums[i] - minPrice);
minPrice = Math.min(minPrice, nums[i]);
}
return res;
}
}
84. 求1+2+…+n
思路 语法问题
通项公式求和
for循环
dfs(判断边界)
class Solution {
public int getSum(int n) {
int res = n;
if (n > 0) res += getSum(n - 1);
return res;
}
}
短路问题 A && B和 A || B用这个来代替if判断
class Solution {
public int getSum(int n) {
int res = n;
boolean flag = n > 0 && (res += getSum(n - 1)) > 0;
return res;
}
}
85. 不用加减乘除做加法
思路 数电加法器
先计算不进位加法 num1 异或 num2
再加上进位
什么时候有进位呢 在两位都是1的时候进位也就是num1 & num2 进位是向前进位，所以要左移一位
Java代码
class Solution {
public int add(int num1, int num2) {
while (num2 != 0) {
int sum = num1 ^ num2;
int carry = (num1 & num2) << 1;
num1 = sum;
num2 = carry;
}
return num1;
}
}
86. 构建乘积数组
题目理解
Bi = A的乘积 / Ai
要求在常数空间内解决，且不能用除法
思路 找一个循环的顺序
扫一遍不行，因为不能用除法
Bi的计算分成两部分 Bi1 = A0 * ... * Ai-1 第二部分 Bi2 = Ai+1 * ... * An-1
Bi = Bi1 * Bi2
Java代码
class Solution {
public int[] multiply(int[] A) {
if (A == null || A.length == 0) return new int[0];
int n = A.length;
int[] B = new int[n];
for (int i = 0, p = 1; i < n; i ++ ) {
B[i] = p;
p *= A[i];
}
for (int i = n - 1, p = 1; i >= 0; i --) {
B[i] *= p;
p *= A[i];
}
return B;
}
}
87. 把字符串转换成整数
思路 模拟
要把所有情况都考虑到
- 前缀空格
- 正负号
- 中间非数字字符
- 是否超出int范围
Java代码
class Solution {
public int strToInt(String str) {
if (str == null || str.length() == 0) return 0;
int k = 0;
while (k < str.length() && str.charAt(k) == ' ') k ++ ; // 处理前缀空格
long number = 0;
boolean is_minus = false;
if (str.charAt(k) == '+') k ++ ;
else if (str.charAt(k) == '-') {
k ++ ;
is_minus = true;
}
while (k < str.length() && str.charAt(k) >= '0' && str.charAt(k) <= '9') { // 只处理数字
number = number * 10 + str.charAt(k) - '0';
k ++ ;
}
if (is_minus) number *= -1; // 正负号
if (number > Integer.MAX_VALUE) number = Integer.MAX_VALUE;
if (number < Integer.MIN_VALUE) number = Integer.MIN_VALUE;
return (int) number;
}
}
87. 把字符串转换成整数
思路 模拟
要把所有情况都考虑到
- 前缀空格
- 正负号
- 中间非数字字符
- 是否超出int范围
Java代码
class Solution {
public int strToInt(String str) {
char[] s = str.toCharArray();
int n = s.length;
int k = 0;
while (k < n && s[k] == ' ') k++;
if (k == n) return 0;
boolean isMinus = false;
if (s[k] == '+') k ++ ;
else if (s[k] == '-') {
isMinus = true;
k ++ ;
}
long res = 0;
while (k < n && Character.isDigit(s[k])) {
res = res * 10 + (s[k ++ ] - '0');
if (!isMinus && res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
if (isMinus && -res < Integer.MIN_VALUE) return Integer.MIN_VALUE;
}
if (isMinus) return (int) -res;
return (int) res;
}
}
88. 树中两个结点的最低公共祖先
Java代码
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
if (root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) return root;
if (left == null) return right;
return left;
}
}
