最近决定巩固一下算法，开始刷leetcode每日一题，具体刷多久还不知道，刚开始是有点吃力，慢慢来。
【Day01】938.二叉搜索树的范围和
题目：
给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
示例1：
输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
输出：32示例 2：
输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输出：23提示：
- 树中节点数目在范围 [1, 2 * 104] 内
- 1 <= Node.val <= 105
- 1 <= low <= high <= 105
- 所有 Node.val 互不相同
题解：
递归
class Solution {
public:
int rangeSumBST(TreeNode* root, int low, int high) {
if (!root) return 0;
int sum = 0;
sum += rangeSumBST(root->left, low, high);
if (root->val >= low && root->val <= high) sum += root->val;
sum += rangeSumBST(root->right, low, high);
return sum;
}
};非递归
class Solution {
public:
int rangeSumBST(TreeNode* root, int low, int high) {
if (!root) return 0;
queue q;
TreeNode* p = root;
int sum = 0;
while (p || q.size()) {
while (p) {
q.push(p);
p = p->left;
}
if (q.size()) {
p = q.front();
q.pop();
if (p->val >= low && p->val <= high) {
sum += p->val;
}
p = p->right;
}
}
return sum;
}
}; 【Day02】633.平方数之和
题目：
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。
示例 1：
输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5示例 2：
输入：c = 3
输出：false示例 3：
输入：c = 4
输出：true示例 4：
输入：c = 2
输出：true示例 5：
输入：c = 1
输出：true枚举
对 a 从 0 开始到 n√n 枚举，然后判断是否存在 b。
class Solution {
public:
bool judgeSquareSum(int c) {
for (int i = 0; (long long)(i) * i <= c; i++) {
int j = sqrt(c - i * i);
if (i * i + j * j == c)
return true;
}
return false;
}
};预处理+查询
如果存在符合条件的a，b，那么a和b一定在1和sqrt(c)之间。
class Solution {
public:
typedef unsigned long long ULL;
bool judgeSquareSum(int c) {
if (c == 0) return true;
unordered_map um;
for (int i = 1; i <= sqrt(c); i++) {
um[i*i]++;
}
for (int i = 1; i <= sqrt(c); i++) {
if (i*i == c || um.count(c - i*i)) return true;
}
return false;
}
}; 双指针
class Solution {
public:
bool judgeSquareSum(int c) {
int j = sqrt(c);
int i = 0;
while (i <= j) {
if (i*i > c - j*j) {
j--;
} else if (i*i < c - j*j) {
i++;
} else {
return true;
}
}
return false;
}
};【Day03】403.青蛙过河
403. 青蛙过河
题目描述：
一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。
给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。
开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格 1 跳至单元格 2 ）。
如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。
示例 1：
输入：stones = [0,1,3,5,6,8,12,17]
输出：true
解释：青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。示例 2：
输入：stones = [0,1,2,3,4,8,9,11]
输出：false
解释：这是因为第 5 和第 6 个石子之间的间距太大，没有可选的方案供青蛙跳跃过去。提示：
- 2 <= stones.length <= 2000
- 0 <= stones[i] <= 231 - 1
- stones[0] == 0
题解：
递归:
class Solution {
public:
unordered_map um;
bool canCross(vector& stones) {
for (int i = 0; i < stones.size(); i++) {
um[stones[i]] = i; // key:石子值 value是第几块石子
}
if (!um.count(1)) return false;
return dfs(stones, stones.size(), 1, 1);
}
bool dfs(vector& stones, int n, int cur, int k) {
if (cur == n - 1) return true;
for (int i = -1; i <= 1; i++) {
if (k + i == 0) continue;
int next = stones[cur] + k + i;
if (um.count(next)) { // 存在
bool choose = dfs(stones, n, um[next], k + i);
if (choose) return true;
}
}
return false;
}
}; dfs记忆化搜索:
class Solution {
public:
unordered_map um;
vector> memo;
bool canCross(vector& stones) {
for (int i = 0; i < stones.size(); i++) {
um[stones[i]] = i; // key:石子值 value是第几块石子
}
if (!um.count(1)) return false;
memo = vector>(stones.size(), vector(stones.size(), -1));
return dfs(stones, stones.size(), 1, 1);
}
bool dfs(vector& stones, int n, int cur, int k) {
if (memo[cur][k] != -1) return memo[cur][k];
if (cur == n - 1) return memo[cur][k] = true;
for (int i = -1; i <= 1; i++) {
if (k + i == 0) continue; // 原地跳过
int next = stones[cur] + k + i;
if (um.count(next)) { // 存在
bool choose = dfs(stones, n, um[next], k + i);
if (choose) return memo[cur][k] = true;
}
}
return memo[cur][k] = false;
}
}; 动态规划：
class Solution {
public:
bool canCross(vector& stones) {
int n = stones.size();
if (stones[1] != 1) return false;
vector> dp(n, vector(n));
// dp[i][k] 表示在第i个位置且跳k个单位到第i块石子。
dp[1][1] = true;
for (int i = 2; i < n; i++) {
for (int j = 1; j < i; j++) {
int k = stones[i] - stones[j];
if (k > j + 1) continue;
// 因为题目要求 青蛙第一次只能跳1步，那么第二次至多跳2步，以此类推，青蛙在第i块（i从0开始）石头上至多只能跳i+1步。在第j块石头上至多只能跳 j+1 步 ，如果k > j+1，说明石头 i 隔石头 j 太远了，远到不满足题目的隐藏规则，所以青蛙必定跳不过去。
dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k+1];
}
}
for (int i = 1; i < n; i++) {
if (dp[n-1][i]) return true;
}
return false;
}
}; 另一种动态规划:
class Solution {
public:
bool canCross(vector& stones) {
// dp[i][j] 表示 第 i 个石头是否可以跳 j 步
int n = stones.size();
vector> dp(n, vector(n));
dp[0][1] = true;
for (int i = 1; i < n; i++) {
bool flag = false;
for (int j = i - 1; j >= 0; j--) {
int k = stones[i] - stones[j];
if (k > i) break;
if (dp[j][k]) {
dp[i][k - 1] = dp[i][k] = dp[i][k + 1] = true;
flag = true;
}
}
if (i == n - 1 && !flag) {
return false;
}
}
return true;
}
}; 【Day04】137.只出现一次的数字II
137. 只出现一次的数字 II
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
示例1：
输入：nums = [2,2,3,2]
输出：3示例2：
输入：nums = [0,1,0,1,0,1,99]
输出：99提示：
- 1 <= nums.length <= 3 * 104
- -231 <= nums[i] <= 231 - 1
- nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
题解：
有限状态自动机：
使用二进制表示每个元素，对应二进制位的1相加，最后相加对3取余
对于所有数字中的某二进制位 1 的个数，存在 3 种状态，即对 3 余数为 0,1,2 。由于二进制只能表示 0, 10,1 ，因此需要使用两个二进制位来表示 3 个状态。设此两位分别为 one，two.
计算 one方法：
设当前状态为 one ，two 此时输入二进制位 nn 。如下图所示，通过对状态表的情况拆分，可推出 one的计算方法为：
if two == 0:
if n == 0:
one = one
if n == 1:
one = ~one
if two == 1:
one = 0引入 异或运算 ，可将以上拆分简化为：
if two == 0:
one = one ^ n
if two == 1:
one = 0引入 与运算 ，可继续简化为：
one = one ^ n & ~two同理：
two = two ^ n & ~one代码：
class Solution {
public:
int singleNumber(vector& nums) {
int two = 0, one = 0;
for (auto x: nums) {
one = (one ^ x) & ~two;
two = (two ^ x) & ~one;
}
return one;
}
}; 哈希表：
class Solution {
public:
int singleNumber(vector& nums) {
unordered_map um;
for (auto x : nums) {
um[x]++;
}
for (auto x : um) {
if (x.second == 1) return x.first;
}
return -1;
}
}; 【Day05】690.员工的重要性
690. 员工的重要性
给定一个保存员工信息的数据结构，它包含了员工 唯一的 id ，重要度 和 直系下属的 id 。
比如，员工 1 是员工 2 的领导，员工 2 是员工 3 的领导。他们相应的重要度为 15 , 10 , 5 。那么员工 1 的数据结构是 [1, 15, [2]] ，员工 2的 数据结构是 [2, 10, [3]] ，员工 3 的数据结构是 [3, 5, []] 。注意虽然员工 3 也是员工 1 的一个下属，但是由于 并不是直系 下属，因此没有体现在员工 1 的数据结构中。
现在输入一个公司的所有员工信息，以及单个员工 id ，返回这个员工和他所有下属的重要度之和。
示例：
输入：[[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
输出：11
解释：
员工 1 自身的重要度是 5 ，他有两个直系下属 2 和 3 ，而且 2 和 3 的重要度均为 3 。因此员工 1 的总重要度是 5 + 3 + 3 = 11 。提示：
- 一个员工最多有一个 直系 领导，但是可以有多个 直系 下属
- 员工数量不超过 2000 。
题解：
今天的题不是很难，直接遍历所有节点相加就行了，使用哈希表将id指向映射到指针，遍历一遍。
dfs
class Solution {
public:
unordered_map hash;
int getImportance(vector employees, int id) {
for (auto& p: employees) hash[p->id] = p;
return dfs(id);
}
int dfs(int id) {
auto p = hash[id];
int res = p->importance;
for (auto son: p->subordinates)
res += dfs(son);
return res;
}
};
【Day06】554.砖墙
554. 砖墙
你的面前有一堵矩形的、由 n 行砖块组成的砖墙。这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和应该相等。
你现在要画一条 自顶向下 的、穿过 最少 砖块的垂线。如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。
给你一个二维数组 wall ，该数组包含这堵墙的相关信息。其中，wall[i] 是一个代表从左至右每块砖的宽度的数组。你需要找出怎样画才能使这条线 穿过的砖块数量最少 ，并且返回 穿过的砖块数量 。
示例 1：
输入：wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
输出：2示例 2：
输入：wall = [[1],[1],[1]]
输出：3提示：
- n == wall.length
- 1 <= n <= 104
- 1 <= wall[i].length <= 104
- 1 <= sum(wall[i].length) <= 2 * 104
- 对于每一行 i ，sum(wall[i]) 应当是相同的
- 1 <= wall[i][j] <= 231 - 1
题解：
贪心，哈希表
显然最优的线一定是沿某个块砖的边缘穿过的。
统计每一行的砖可以从左到右可以构成的长度值，用 unordered_map 哈希表统计长度值出现的次数。出现次数最多的值就应该是这条线所在的位置。
class Solution {
public:
int leastBricks(vector>& wall) {
unordered_map cnt;
for (auto& line: wall) {
for (int i = 0, s = 0; i + 1 < line.size(); i ++ ) {
s += line[i];
cnt[s] ++ ;
}
}
int res = 0;
for (auto [k, v]: cnt) res = max(res, v);
return wall.size() - res;
}
};
【Day07】7.整数反转7. 整数反转
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1：
输入：x = 123
输出：321示例 2：
输入：x = -123
输出：-321示例 3：
输入：x = 120
输出：21示例 4：
输入：x = 0
输出：0提示：
- -231 <= x <= 231 - 1
题解：
(循环) O(logn)
依次从右往左计算出每位数字，然后逆序累加在一个整数中。
另外，这题有两点需要注意：
因为int型整数逆序后可能会溢出，所以我们要用long long记录中间结果；
在C++中，负数的取模运算和数学意义上的取模运算不同，结果还是负数，比如 −12%10=−2−12%10=−2，所以我们不需要对负数进行额外处理。
时间复杂度分析：一共有 O(logn) 位，对于每一位的计算量是常数级的，所以总时间复杂度是 O(logn)
class Solution {
public:
int reverse(int x) {
int res = 0;
while (x) {
if (x > 0 && res > (INT_MAX - x % 10) / 10) return 0;
if (x < 0 && res < (INT_MIN - x % 10) / 10) return 0;
res = res * 10 + x % 10;
x /= 10;
}
return res;
}
};
【Day08】1473.粉刷房子III
1473. 粉刷房子 III
在一个小城市里，有 m 个房子排成一排，你需要给每个房子涂上 n 种颜色之一（颜色编号为 1 到 n ）。有的房子去年夏天已经涂过颜色了，所以这些房子不需要被重新涂色。
我们将连续相同颜色尽可能多的房子称为一个街区。（比方说 houses = [1,2,2,3,3,2,1,1] ，它包含 5 个街区 [{1}, {2,2}, {3,3}, {2}, {1,1}] 。）
给你一个数组 houses ，一个 m * n 的矩阵 cost 和一个整数 target ，其中：
- houses[i]：是第 i 个房子的颜色，0 表示这个房子还没有被涂色。
- cost[i][j]：是将第 i 个房子涂成颜色 j+1 的花费。
请你返回房子涂色方案的最小总花费，使得每个房子都被涂色后，恰好组成 target 个街区。如果没有可用的涂色方案，请返回 -1 。
示例 1：
输入：houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
输出：9
解释：房子涂色方案为 [1,2,2,1,1]
此方案包含 target = 3 个街区，分别是 [{1}, {2,2}, {1,1}]。
涂色的总花费为 (1 + 1 + 1 + 1 + 5) = 9。示例 2：
输入：houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
输出：11
解释：有的房子已经被涂色了，在此基础上涂色方案为 [2,2,1,2,2]
此方案包含 target = 3 个街区，分别是 [{2,2}, {1}, {2,2}]。
给第一个和最后一个房子涂色的花费为 (10 + 1) = 11。示例 3：
输入：houses = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5
输出：5示例 4：
输入：houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
输出：-1
解释：房子已经被涂色并组成了 4 个街区，分别是 [{3},{1},{2},{3}] ，无法形成 target = 3 个街区。提示：
- m == houses.length == cost.length
- n == cost[i].length
- 1 <= m <= 100
- 1 <= n <= 20
- 1 <= target <= m
- 0 <= houses[i] <= n
- 1 <= cost[i][j] <= 10^4
题解·：
很明显的DP
设状态 f(i,j,k) 表示处理了前 i 个房屋，有 j 个社区，最后一个房屋的颜色为 k 的最小花费，其中房屋的有效下标从 1 开始。建立辅助数组 g(i,j,k) 表示同样含义下，最后一个房屋颜色 不是 k 的最小花费。
初始时，f(0,0,k)=g(0,0,k)=0，其余为正无穷或者待定。
转移时，分两种情况如果第 i 个房屋已经有了颜色 c，则有两种选择，上一个房屋颜色为 c 或者不为 c，转移
$$
f(i, j, c)=\min (f(i-1, j, c), g(i-1, j-1, c))
$$如果第 i 个房屋没有颜色，则枚举一个颜色 k，然后同样根据上一个房屋的颜色，转移
$$
f(i, j, k)=\min (f(i-1, j, k), g(i-1, j-1, k))+\operatorname{cost}(i, k-1)_{\text {。 }}
$$对于 g 数组的维护如下，假设当前需要维护前 i 个房屋且有 j 个社区下的 g 数组，则我们找 f(i,j,k) 中的最小值 m1 和次小值 m2。如果 m1=m2，则说明对于所有 k， g(i,j,k)=m1；否则，对于 f(i,j,k0)=m1 的那个 k0，其 g(i,j,k0)=m2g，其余 k≠k0都有 g(i,j,k)=m1。
最终答案为
$$
\min (f(m, \text { target }, k)
$$
class Solution {
public:
int minCost(vector& houses, vector>& cost, int m, int n, int target) {
const int MAX = 0x3f3f3f3f;
const int M = 110;
const int N = 30;
int f[M][M][N], g[M][M][N];
memset(f, 0x3f, sizeof(f));
memset(g, 0x3f, sizeof(g));
for (int k = 1; k <= n; k++)
f[0][0][k] = g[0][0][k] = 0;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= min(i, target); j++) {
if (houses[i - 1] > 0) {
int c = houses[i - 1];
f[i][j][c] = min(f[i - 1][j][c], g[i - 1][j - 1][c]);
} else {
for (int k = 1; k <= n; k++)
f[i][j][k] = min(f[i - 1][j][k], g[i - 1][j - 1][k])
+ cost[i - 1][k - 1];
}
int m1 = MAX, m2 = MAX;
for (int k = 1; k <= n; k++)
if (m1 > f[i][j][k]) {
m2 = m1;
m1 = f[i][j][k];
} else if (m2 > f[i][j][k])
m2 = f[i][j][k];
if (m1 == m2) {
for (int k = 1; k <= n; k++)
g[i][j][k] = m1;
} else {
for (int k = 1; k <= n; k++)
if (f[i][j][k] == m1) g[i][j][k] = m2;
else g[i][j][k] = m1;
}
}
int ans = MAX;
for (int k = 1; k <= n; k++)
ans = min(ans, f[m][target][k]);
if (ans == MAX)
ans = -1;
return ans;
}
};
【Day09】740.删除并获得点数
740. 删除并获得点数](https://leetcode-cn.com/problems/delete-and-earn/)
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1：
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。示例 2：
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。提示：
- 1 <= nums.length <= 2 * 104
- 1 <= nums[i] <= 104
题解：
首先，我们先明确一个概念，就是每个位置上的数字是可以在两种前结果之上进行选择的：
如果你不删除当前位置的数字，那么你得到就是前一个数字的位置的最优结果。
如果你觉得当前的位置数字i需要被删，那么你就会得到i - 2位置的那个最优结果加上当前位置的数字乘以个数。
以上两个结果，你每次取最大的，记录下来，然后答案就是最后那个数字了。
如果你看到现在有点迷糊，那么我们先把数字进行整理一下。
我们在原来的 nums 的基础上构造一个临时的数组 all，这个数组，以元素的值来做下标，下标对应的元素是原来的元素的个数。
举个例子：
nums = [2, 2, 3, 3, 3, 4]构造后：
all=[0, 0, 2, 3, 1];就是代表着 22 的个数有两个，33 的个数有 33 个，44 的个数有 11 个。
其实这样就可以变成打家劫舍的问题了呗。
我们来看看，打家劫舍的最优子结构的公式：
$$
\mathrm{dp}[\mathrm{i}]=\text { Math.max }(\mathrm{d} \mathrm{p}[\mathrm{i}-1], \mathrm{dp}[\mathrm{i}-2]+\mathrm{nums}[\mathrm{i}])
$$
再来看看现在对这个问题的最优子结构公式：
$$
\mathrm{dp}[\mathrm{i}]=\text { Math.max }\left(\mathrm{dp}[\mathrm{i}-1], \mathrm{dp}[\mathrm{i}-2]+\mathrm{i}^{\star} \mathrm{all}[\mathrm{i}]\right)
$$
class Solution {
public:
int deleteAndEarn(vector& nums) {
if(nums.size() < 1) return 0;
int maxn = 0;
for(int it : nums)
maxn = max(maxn, it);
vector cnt(maxn+1), dp(maxn+1);
for(int it : nums)
cnt[it]++;
dp[1] = cnt[1];
for(int i = 2; i <= maxn; i++)
dp[i] = max(dp[i-1], dp[i-2] + cnt[i] * i);
return dp[maxn];
}
}; 【Day10】1720. 解码异或后的数组
1720. 解码异或后的数组
未知 整数数组 arr 由 n 个非负整数组成。
经编码后变为长度为 n - 1 的另一个整数数组 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如，arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3] 。
给你编码后的数组 encoded 和原数组 arr 的第一个元素 first（arr[0]）。
请解码返回原数组 arr 。可以证明答案存在并且是唯一的。
示例 1：
输入：encoded = [1,2,3], first = 1
输出：[1,0,2,1]
解释：若 arr = [1,0,2,1] ，那么 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]示例 2：
输入：encoded = [6,2,7,3], first = 4
输出：[4,2,0,7,4]提示：
- 2 <= n <= 104
- encoded.length == n - 1
- 0 <= encoded[i] <= 105
- 0 <= first <= 105
题解：
异或运算满足交换律和结合律；
任意整数和自身做异或运算的结果都等于 0，即 x⊕x=0；
任意整数和 0 做异或运算的结果都等于其自身，即 x⊕0=0⊕x=x。
在等号两边同时异或 arr[i]
class Solution {
public:
vector decode(vector& encoded, int first) {
int n = encoded.size();
vector arr(n + 1);
arr[0] = first;
for (int i = 0; i < n; i ++)
arr[i + 1] = arr[i] ^ encoded[i];
return arr;
}
};
【Day11】1486.数组异或操作
1486. 数组异或操作
给你两个整数，n 和 start 。
数组 nums 定义为：nums[i] = start + 2*i（下标从 0 开始）且 n == nums.length 。
请返回 nums 中所有元素按位异或（XOR）后得到的结果。
示例 1：
输入：n = 5, start = 0
输出：8
解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。
"^" 为按位异或 XOR 运算符。示例 2：
输入：n = 4, start = 3
输出：8
解释：数组 nums 为 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) = 8.示例 3：
输入：n = 1, start = 7
输出：7示例 4：
输入：n = 10, start = 5
输出：2提示：
- 1 <= n <= 1000
- 0 <= start <= 1000
- n == nums.length
题解：
class Solution {
public:
int xorOperation(int n, int start)
{
int result = start, i;
for (i = 1; i < n; i++)
{
result = result ^ (start + i * 2);
}
return result;
}
};【Day12】1723.完成所有工作的最短时间
1723. 完成所有工作的最短时间
给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。
请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化 。
返回分配方案中尽可能 最小 的 最大工作时间 。
示例 1：
输入：jobs = [3,2,3], k = 3
输出：3
解释：给每位工人分配一项工作，最大工作时间是 3 。示例 2：
输入：jobs = [1,2,4,7,8], k = 2
输出：11
解释：按下述方式分配工作：
1 号工人：1、2、8（工作时间 = 1 + 2 + 8 = 11）
2 号工人：4、7（工作时间 = 4 + 7 = 11）
最大工作时间是 11 。提示：
- 1 <= k <= jobs.length <= 12
- 1 <= jobs[i] <= 107
题解：
回溯法+剪枝
用一个 vector
递归深度为 n=jobs.length 工作数量，每次递归需要检测范围为 k 员工数量并开启分支，最坏情况下走满树时间复杂度为 O(k^n)
题设 1 <= k <= jobs.length <= 12，最坏情况下 12^12 = 8.9E12，外面还套了一个二分，还要再乘 log12 = 3.xxxx，远超1s极限算量1E8
因此我们需要考虑一些剪枝的方法，首先我们可以 sort 一下 jobs ，时长从大到小开始分配，进而能够更快的超出限制，被剪枝掉，其次是朴素写法中存在很多重复的路径
例如对于第一份工作的分配，所有人工作时长全部是0，我们只需要分配一次
[t1,0,0,0,0]
之后的
[0,t1,0,0,0]
...都是重复操作。
56号测试用例：
[5,5,4,4,4]
2如果先将 5h 分配给两个人block [5,5]，之后分配4时，只需要走一次 [9,5]，后面的[5,9] 是重复操作
由于jobs已排序，因此我们每次枚举到的 block[i] 应当和上一次不一样，才是没走过的路径，进而排除全0时的重复放置，或是出现相同工作时长分配时的重复放置
class Solution {
public:
int k;
vector block;
bool backtracking(vector& jobs,int id,int lim) {
if(id==-1) return true; //出口 全部放完了
bool res=false;
int last=INT_MIN;
for(int i=0;i& jobs, int k) {
this->k = k;
int s=0; //区间左端点（最小）
int e=0; //区间右端点（最大）
int m;//中间
int n = jobs.size()-1;//起手下标
block = vector(k,0); // 拷贝初始化
sort(jobs.begin(),jobs.end());
s=jobs[n];//结果最小应是 jobs[i] 的最大值
for(auto i : jobs) { //最大应是 sum(jobs.begin(),jobs.end()) 小心越界
if(e<=INT_MAX-i) e+=i;
else e=INT_MAX;
}
while(s!=e) {
int m = (s+e)/2;
if(backtracking(jobs,n,m)) { //成功 尝试缩减区间
e=m;//m无法排除
}else {//失败 扩大
s=m+1;//m肯定不对最少加1
}
}
return s;
}
}; 【Day13】1482.制作m束花所需的最少天数
1482. 制作 m 束花所需的最少天数
给你一个整数数组 bloomDay，以及两个整数 m 和 k 。
现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。
花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。
请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。
示例 1：
输入：bloomDay = [1,10,3,10,2], m = 3, k = 1
输出：3
解释：让我们一起观察这三天的花开过程，x 表示花开，而 _ 表示花还未开。
现在需要制作 3 束花，每束只需要 1 朵。
1 天后：[x, _, _, _, _] // 只能制作 1 束花
2 天后：[x, _, _, _, x] // 只能制作 2 束花
3 天后：[x, _, x, _, x] // 可以制作 3 束花，答案为 3示例 2：
输入：bloomDay = [1,10,3,10,2], m = 3, k = 2
输出：-1
解释：要制作 3 束花，每束需要 2 朵花，也就是一共需要 6 朵花。而花园中只有 5 朵花，无法满足制作要求，返回 -1 。示例 3：
输入：bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
输出：12
解释：要制作 2 束花，每束需要 3 朵。
花园在 7 天后和 12 天后的情况如下：
7 天后：[x, x, x, x, _, x, x]
可以用前 3 朵盛开的花制作第一束花。但不能使用后 3 朵盛开的花，因为它们不相邻。
12 天后：[x, x, x, x, x, x, x]
显然，我们可以用不同的方式制作两束花。示例 4：
输入：bloomDay = [1000000000,1000000000], m = 1, k = 1
输出：1000000000
解释：需要等 1000000000 天才能采到花来制作花束示例 5：
输入：bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
输出：9提示：
- bloomDay.length == n
- 1 <= n <= 10^5
- 1 <= bloomDay[i] <= 10^9
- 1 <= m <= 10^6
- 1 <= k <= n
题解：
假设制作m束花需要等待的最少天数是x天，那么有：
- [0, x)天无法制作出来m束
- [x,maxDay]可以制作出m束
求出给定花开数组中最大值，进行二分计算即可。
class Solution {
public:
int minDays(vector& bloomDay, int m, int k) {
int n = bloomDay.size();
if (m * k > n) return -1;
int l = 0, r = 0;
for (auto x : bloomDay) {
r = max(r, x);
}
while(l < r) {
int mid = l + r >> 1;
if (check(bloomDay, mid, m, k)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
bool check(vector& bloomDay, int mid, int m, int k) {
int sum = 0;
// 计算是否满足m束花且每一束都有相邻的k个
for (int i = 0; i < bloomDay.size() && sum < m; i++) {
int cur_sum = 0;
if (bloomDay[i] <= mid) { // 可以开
cur_sum++;
int j = i + 1;
while (j < bloomDay.size() && bloomDay[j] <= mid && cur_sum < k) {
j++;
cur_sum++;
}
if (cur_sum == k) sum++;
i = j - 1;
}
}
return sum >= m;
}
}; 【Day14】872.叶子相似的树
872. 叶子相似的树
请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。
示例 1：
输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
输出：true示例 2：
输入：root1 = [1], root2 = [1]
输出：true示例 3：
输入：root1 = [1], root2 = [2]
输出：false示例 4：
输入：root1 = [1,2], root2 = [2,2]
输出：true示例 5：
输入：root1 = [1,2,3], root2 = [1,3,2]
输出：false提示：
- 给定的两棵树可能会有 1 到 200 个结点。
- 给定的两棵树上的值介于 0 到 200 之间。
题解：
将第一次的结果存储下来后，后面直接比较并返回结果。
class Solution {
public:
int index = 0;
bool leafSimilar(TreeNode* root1, TreeNode* root2) {
vector r1;
dfs1(root1, r1);
return dfs2(root2, r1) && index == r1.size();
}
void dfs1(TreeNode* root, vector& res) {
if (!root) return;
if (!root->left && !root->right) {
res.push_back(root->val);
return;
}
dfs1(root->left, res);
dfs1(root->right, res);
}
bool dfs2(TreeNode* root, vector& res) {
if (!root) return true;
if (!root->left && !root->right) {
if (index >= res.size()) return false;
if (root->val != res[index]) return false;
index++;
return true;
}
return dfs2(root->left, res) && dfs2(root->right, res);
}
}; 【Day15】1734.解码异或后的排列
1734. 解码异或后的排列
给你一个整数数组 perm ，它是前 n 个正整数的排列，且 n 是个 奇数 。
它被加密成另一个长度为 n - 1 的整数数组 encoded ，满足 encoded[i] = perm[i] XOR perm[i + 1] 。比方说，如果 perm = [1,3,2] ，那么 encoded = [2,1] 。
给你 encoded 数组，请你返回原始数组 perm 。题目保证答案存在且唯一。
示例 1：
输入：encoded = [3,1]
输出：[1,2,3]
解释：如果 perm = [1,2,3] ，那么 encoded = [1 XOR 2,2 XOR 3] = [3,1]示例 2：
输入：encoded = [6,5,4,6]
输出：[2,4,1,5,3]提示：
- 3 <= n < 105
- n 是奇数。
- encoded.length == n - 1
题解：
perm = [A,B,C,D,E]
encoded = [A^B, B^C, C^D, D^E]
而B^C^D^E = encoded[1] ^ encode[3]
A^B^C^D^E = total
total ^ (B^C^D^E) = first
class Solution {
public:
vector decode(vector& encoded) {
int n = encoded.size() + 1;
int total = 0;
for (int i = 1; i <= n; i++) {
total ^= i;
}
int e = 0;
for (int i = 1; i < n - 1; i += 2) {
e ^= encoded[i];
}
vector ans(n);
ans[0] = total ^ e;
for (int i = 1; i < n; i++) {
ans[i] = ans[i-1] ^ encoded[i-1];
}
return ans;
}
}; 【Day16】1310.子数组异或查询
1310. 子数组异或查询
有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [Li, Ri]。
对于每个查询 i，请你计算从 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor … xor arr[Ri]）作为本次查询的结果。
并返回一个包含给定查询 queries 所有结果的数组。
示例 1：
输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
输出：[2,7,14,8]
解释：
数组中元素的二进制表示形式是：
1 = 0001
3 = 0011
4 = 0100
8 = 1000
查询的 XOR 值为：
[0,1] = 1 xor 3 = 2
[1,2] = 3 xor 4 = 7
[0,3] = 1 xor 3 xor 4 xor 8 = 14
[3,3] = 8示例 2：
输入：arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
输出：[8,0,4,4]提示：
- 1 <= arr.length <= 3 * 10^4
- 1 <= arr[i] <= 10^9
- 1 <= queries.length <= 3 * 10^4
- queries[i].length == 2
- 0 <= queries[i][0] <= queries[i][1] < arr.length
题解：
利用前缀和思想：sum(i,j) = sum(j) - sum(i-1);
class Solution {
public:
vector xorQueries(vector& arr, vector>& queries) {
vector ans;
int sum[arr.size() + 1];
for (int i = 1; i <= arr.size(); i++) {
sum[i] = sum[i - 1] ^ arr[i - 1];
}
for (auto q : queries) {
ans.push_back(sum[q[1] + 1] ^ sum[q[0]]);
}
return ans;
} 【Day17】1269.停在原地的方案数
1269. 停在原地的方案数
有一个长度为 arrLen 的数组，开始有一个指针在索引 0 处。
每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地（指针不能被移动到数组范围外）。
给你两个整数 steps 和 arrLen ，请你计算并返回：在恰好执行 steps 次操作以后，指针仍然指向索引 0 处的方案数。
由于答案可能会很大，请返回方案数 模 10^9 + 7 后的结果。
示例 1：
输入：steps = 3, arrLen = 2
输出：4
解释：3 步后，总共有 4 种不同的方法可以停在索引 0 处。
向右，向左，不动
不动，向右，向左
向右，不动，向左
不动，不动，不动示例 2：
输入：steps = 2, arrLen = 4
输出：2
解释：2 步后，总共有 2 种不同的方法可以停在索引 0 处。
向右，向左
不动，不动示例 3：
输入：steps = 4, arrLen = 2
输出：8提示：
1 <= steps <= 500
1 <= arrLen <= 10^6题解：
暴力递归
pos表示移动的index,st表示当前还剩步数。结果超时- _ -
class Solution {
public:
const int N = 1000000007;
int numWays(int steps, int arrLen) {
int res = dfs(steps, arrLen, 0);
return res % N;
}
int dfs(int st, int arrLen, int pos) {
if (st < 0 || pos < 0 || pos >= arrLen) return 0;
if (st == 0 && pos == 0) {
return 1;
}
int ans = 0;
if (pos >= 0 && pos <= arrLen - 1)
// 不动
ans = dfs(st - 1, arrLen, pos);
if (pos >= 1)
// 向左
ans += dfs(st - 1, arrLen, pos - 1);
if (pos <= arrLen - 2)
// 向右
ans += dfs(st- 1, arrLen, pos + 1);
return ans;
}
};记忆化搜索
一开始开辟空间太大，过不了，发现开辟很大空间后，使用map性能比vector好，而实际只需要开辟steps*steps即可。
int memo[505][505];
// vector> memo;
class Solution {
public:
static const int N = 1000000007;
int numWays(int steps, int arrLen) {
memset(memo, -1, sizeof(memo));
// memo = vector>(505, vector(505,-1));
int res = dfs(steps, arrLen, 0);
return res % N;
}
int dfs(int st, int arrLen, int pos) {
if (st < 0 || pos < 0 || pos >= arrLen) return 0;
if (memo[st][pos] != -1) return memo[st][pos];
if (st == 0 && pos == 0) {
return memo[st][pos] = 1;
}
int ans = 0;
if (pos >= 0 && pos <= arrLen - 1)
// 不动
ans = dfs(st - 1, arrLen, pos) % N;
if (pos >= 1)
// 向左
ans = ans % N + dfs(st - 1, arrLen, pos - 1) % N;
if (pos <= arrLen - 2)
// 向右
ans = ans % N + dfs(st- 1, arrLen, pos + 1) % N;
return memo[st][pos] = ans;
}
}; 动态规划
class Solution {
public:
static const int N = 1000000007;
int numWays(int steps, int arrLen) {
int maxLen = min(steps, arrLen);
long long dp[steps + 1][maxLen + 1];
memset(dp, 0, sizeof dp);
dp[1][0] = 1;
dp[1][1] = 1; // step=1 pos=1
for (int s = 1; s <= steps; s++) {
for (int l = 0; l < maxLen; l++) {
// 原地
dp[s][l] = dp[s][l] + dp[s - 1][l];
// 右
dp[s][l] = dp[s][l] + dp[s - 1][l + 1];
// 左
if (l - 1 >= 0)
dp[s][l] = dp[s][l] + dp[s - 1][l - 1];
dp[s][l] %= N;
}
}
return dp[steps][0];
}
};【Day18】12.整数转罗马数字
12. 整数转罗马数字
罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
- I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
- X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
- C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给你一个整数，将其转为罗马数字。
示例 1:
输入: num = 3
输出: "III"示例 2:
输入: num = 4
输出: "IV"示例 3:
输入: num = 9
输出: "IX"示例 4:
输入: num = 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.示例 5:
输入: num = 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.提示：
- 1 <= num <= 3999
题解：
第一想到贪心，使用哈希表排序罗马数字并遍历，从高到低进行匹配。暴力匹配也可以的，
class Solution {
public:
string intToRoman(int num) {
int values[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
string reps[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
string ans;
int
for (int i = 0; i < 13; i ++ )
while(num >= values[i])
{
num -= values[i];
ans += reps[i];
}
return ans;
}
};【Day19】13.罗马数字转整数
13. 罗马数字转整数
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
- I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
- X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
- C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1:
输入: "III"
输出: 3示例 2:
输入: "IV"
输出: 4示例 3:
输入: "IX"
输出: 9示例 4:
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.示例 5:
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.提示：
- 1 <= s.length <= 15
- s 仅含字符 (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’)
- 题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
- 题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
- IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
- 关于罗马数字的详尽书写规则，可以参考 罗马数字 - Mathematics 。
题解：
当小值在大值的左边，则减小值，如 IV=5-1=4；
当小值在大值的右边，则加小值，如 VI=5+1=6；
小值放在大值的左边，就是做减法，否则为加法。
class Solution {
public:
int romanToInt(string s) {
int r=0;
for(int i=0;i【Day20】421.数组中两个数的最大异或值
421. 数组中两个数的最大异或值
给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。
进阶：你可以在 O(n) 的时间解决这个问题吗？
示例 1：
输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.示例 2：
输入：nums = [0]
输出：0示例 3：
输入：nums = [2,4]
输出：6示例 4：
输入：nums = [8,10,2]
输出：10示例 5：
输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127提示：
- 1 <= nums.length <= 2 * 104
- 0 <= nums[i] <= 231 - 1
题解：
前缀树
将所有数据从最高位开始取每一个bit，构建出树形结构，尽可能保证最高位为1，也就是说当循环到当前数的时候，如果当前数的bit与当前数中某一个数的某一位是相反的，那么可以保证为1，也就是最大，否则向低位继续循环。
struct Node{
Node* next[2] = {nullptr};
};
class Solution {
public:
void insert(int num, Node* root) {
for (int i = 30; i >= 0; --i) {
int t = (num >> i & 1);
if (!root->next[t]) {
root->next[t] = new Node();
}
root = root->next[t];
}
}
int findMaximumXOR(vector& nums) {
Node* root = new Node();
for (auto val : nums) {
insert(val, root);
}
int res = 0, tmp = 0;
Node* p = root;
for (auto val : nums) {
p = root; tmp = 0;
for (int i = 30; i >= 0; --i) {
int t = (val >> i) & 1;
if (p->next[!t]) {
p = p->next[!t];
tmp += (1 << i);
}else p = p->next[t];
}
res = max(res, tmp);
}
return res;
}
}; 暴力+剪枝
剪枝策略两数异或最大不超过两数之和，先排序再剪枝。
class Solution {
public:
int findMaximumXOR(vector& nums) {
sort(nums.begin(), nums.end(), [](auto a, auto b) {return a > b;});
int ans = 0;
for (int i = 0; i < nums.size() - 1; i++) {
for (int j = i + 1; j < nums.size(); j++) {
long long x = (long long)nums[i] + nums[j];
if (ans > x) break;
ans = max(ans, nums[i] ^ nums[j]);
}
}
return ans;
}
}; 【Day21】993.二叉树的堂兄弟节点
993. 二叉树的堂兄弟节点
在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。
我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。
只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。
示例 1：
输入：root = [1,2,3,4], x = 4, y = 3
输出：false示例 2：
输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
输出：true示例 3：
输入：root = [1,2,3,null,4], x = 2, y = 3
输出：false提示：
- 二叉树的节点数介于 2 到 100 之间。
- 每个节点的值都是唯一的、范围为 1 到 100 的整数。
题解：
假设从根节点开始编号1，依次往后编号，其两个孩子是2*n与2*n+1。反过来便是根据两个孩子节点判断是否是同一个父亲，那便是直接除以2，向下取整，看两者是否一样即可。
例如：2、3是同一父亲，2、4不是。
在BFS过程中记录节点编号以及x、y节点，最后判断即可。
class Solution {
public:
bool isCousins(TreeNode* root, int x, int y) {
queue q;
q.push(root);
int cnt = 1;
while (q.size()) {
int sz = q.size();
bool xt = false, yt = false;
int xcnt, ycnt;
while (sz--) {
auto p = q.front();
q.pop();
if (p) {
if (x == p->val) {
xt = true;
xcnt = cnt;
}
if (y == p->val) {
yt = true;
ycnt = cnt;
}
if (xt && yt && int(xcnt / 2) != int(ycnt / 2) ) {
return true;
}
q.push(p->left); q.push(p->right);
}
cnt++;
}
}
return false;
}
}; 【Day22】1442.形成两个异或相等数组的三元组数目
1442. 形成两个异或相等数组的三元组数目
给你一个整数数组 arr 。
现需要从数组中取三个下标 i、j 和 k ，其中 (0 <= i < j <= k < arr.length) 。
a 和 b 定义如下：
- a = arr[i] ^ arr[i + 1] ^ … ^ arr[j - 1]
- b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]
注意：^ 表示 按位异或 操作。
请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。
示例 1：
输入：arr = [2,3,1,6,7]
输出：4
解释：满足题意的三元组分别是 (0,1,2), (0,2,2), (2,3,4) 以及 (2,4,4)示例 2：
输入：arr = [1,1,1,1,1]
输出：10示例 3：
输入：arr = [2,3]
输出：0示例 4：
输入：arr = [1,3,5,7,9]
输出：3示例 5：
输入：arr = [7,11,12,9,5,2,7,17,22]
输出：8提示：
- 1 <= arr.length <= 300
- 1 <= arr[i] <= 10^8
题解：
∵ a = arr[i] ^ arr[i + 1] ^ … ^ arr[j - 1]
b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]
∴ arr[i] ^ arr[i + 1] ^ … ^ arr[k] = a ^ b = 0;
a^b=0得到区间[i,k]中有k-i个元组，全部累加即可。区间内三元组的个数为 k - i（因为区间内的任意一个j，都和i，k组成满足题目的一个三元组）。
class Solution {
public:
int countTriplets(vector& arr) {
int ans = 0;
for (int i = 0; i < arr.size(); i++) {
int s = arr[i];
for (int k = i + 1; k < arr.size(); k++) {
s ^= arr[k];
if (s == 0) ans += k - i;
}
}
return ans;
}
}; 【Day23】1738.找出第 K 大的异或坐标值
1738. 找出第 K 大的异或坐标值
给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。
矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j]（下标从 0 开始计数）执行异或运算得到。
请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。
示例 1：
输入：matrix = [[5,2],[1,6]], k = 1
输出：7
解释：坐标 (0,1) 的值是 5 XOR 2 = 7 ，为最大的值。示例 2：
输入：matrix = [[5,2],[1,6]], k = 2
输出：5
解释：坐标 (0,0) 的值是 5 = 5 ，为第 2 大的值。示例 3：
输入：matrix = [[5,2],[1,6]], k = 3
输出：4
解释：坐标 (1,0) 的值是 5 XOR 1 = 4 ，为第 3 大的值。示例 4：
输入：matrix = [[5,2],[1,6]], k = 4
输出：0
解释：坐标 (1,1) 的值是 5 XOR 2 XOR 1 XOR 6 = 0 ，为第 4 大的值。提示：
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 1000
- 0 <= matrix[i][j] <= 106
- 1 <= k <= m * n
题解：
二维差分+最小堆
前缀和模板+维护k个元素的最小堆
class Solution {
public:
int prefix[1000][1000];
int kthLargestValue(vector>& matrix, int k) {
int m = matrix.size();
int n = matrix[0].size();
prefix[0][0] = matrix[0][0];
// 处理第一行
for (int i = 1; i < n; i++) {
prefix[0][i] = prefix[0][i - 1] ^ matrix[0][i];
}
// 处理第一列
for (int i = 1; i < m; i++) {
prefix[i][0] = prefix[i - 1][0] ^ matrix[i][0];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
prefix[i][j] = prefix[i - 1][j] ^ prefix[i][j - 1] ^ matrix[i][j] ^ prefix[i - 1][j - 1];
}
}
priority_queue, std::greater> pq;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
pq.push(prefix[i][j]);
if (pq.size() > k) pq.pop();
}
}
return pq.top();
}
}; 二分搜值
每次猜测一个值x，然后遍历前缀和矩阵，统计有多少个元素大于等于x，如果count小于k，那么x肯定不可能是答案，我们将猜测的上界下调至x-1；否则，我们就将猜测的下界调整至x。可以看到问题可以转换为查找最后一个小于等于target的数。因为当查找到大于等于target时要往上不断压缩区间，直到小于等于k为止。
class Solution {
public:
int prefix[1000][1000];
int m, n;
int kthLargestValue(vector>& matrix, int k) {
m = matrix.size();
n = matrix[0].size();
prefix[0][0] = matrix[0][0];
// 处理第一行
for (int i = 1; i < n; i++) {
prefix[0][i] = prefix[0][i - 1] ^ matrix[0][i];
}
// 处理第一列
for (int i = 1; i < m; i++) {
prefix[i][0] = prefix[i - 1][0] ^ matrix[i][0];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
prefix[i][j] = prefix[i - 1][j] ^ prefix[i][j - 1] ^ matrix[i][j] ^ prefix[i - 1][j - 1];
}
}
int left = 0, right = 1e6;
while (left < right) {
int mid = right - (right - left - 1) / 2;
if (count(mid) < k) { // 缩小值
right = mid - 1;
} else {
left = mid;
}
}
return left;
}
int count (int mid) {
int cnt = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (prefix[i][j] >= mid) cnt++;
}
}
return cnt;
}
}; 【Day24】692.前K个高频单词
692. 前K个高频单词
给一非空的单词列表，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
示例 1：
输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 "i" 在 "love" 之前。示例 2：
输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
出现次数依次为 4, 3, 2 和 1 次。注意：
- 假定 k 总为有效值， 1 ≤ k ≤ 集合元素数。
- 输入的单词均由小写字母组成。
扩展练习：
尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。
题解：
struct Cmp {
bool operator()(const pair& p1, const pair& p2) {
if(p1.second != p2.second) return p1.second > p2.second;
else return p1.first < p2.first;
}
};
class Solution {
public:
vector topKFrequent(vector& words, int k) {
unordered_map m;
for(string& word : words) m[word]++;
vector> sorted_list(m.begin(), m.end());
sort(sorted_list.begin(), sorted_list.end(), Cmp());
vector res;
for(int i = 0; i < k; i++) res.push_back(sorted_list[i].first);
return res;
}
}; 【Day25】1035.不相交的线
1035. 不相交的线
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：
- nums1[i] == nums2[j]
- 且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。
示例 1：
输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。示例 2：
输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出：3示例 3：
输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出：2提示：
- 1 <= nums1.length <= 500
- 1 <= nums2.length <= 500
- 1 <= nums1[i], nums2[i] <= 2000
题解：
class Solution {
public:
vector> dp;
int maxUncrossedLines(vector& nums1, vector& nums2) {
int n = nums1.size(), m = nums2.size();
dp = vector>(n + 1, vector(m + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[n][m];
}
}; 【Day26】810.黑板异或游戏
810. 黑板异或游戏
黑板上写着一个非负整数数组 nums[i] 。Alice 和 Bob 轮流从黑板上擦掉一个数字，Alice 先手。如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。 (另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为 0。）
换种说法就是，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于 0，这个玩家获胜。
假设两个玩家每步都使用最优解，当且仅当 Alice 获胜时返回 true。
示例：
输入: nums = [1, 1, 2]
输出: false
解释:
Alice 有两个选择: 擦掉数字 1 或 2。
如果擦掉 1, 数组变成 [1, 2]。剩余数字按位异或得到 1 XOR 2 = 3。那么 Bob 可以擦掉任意数字，因为 Alice 会成为擦掉最后一个数字的人，她总是会输。
如果 Alice 擦掉 2，那么数组变成[1, 1]。剩余数字按位异或得到 1 XOR 1 = 0。Alice 仍然会输掉游戏。提示：
- 1 <= N <= 1000
- 0 <= nums[i] <= 2^16
题解：
class Solution {
public:
bool xorGame(vector& nums) {
//数组元素个数是奇数/偶数，有决定性作用：
//如果是偶数，先手必胜；
//如果是奇数，只有当一上来所有元素异或的结果为0，先手才获胜，
//否则，接下来轮到后手，此时元素个数为偶数，则后手必胜，先手必败！
int len = nums.size(), t = 0;
if(len % 2)
{
for(auto& x:nums) t ^= x; //所有元素异或的结果
if(t) return false;
else return true;
}
else return true;
}
}; 【Day27】1707.与数组中元素的最大异或值
1707. 与数组中元素的最大异或值
给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 queries[i] = [xi, mi] 。
第 i 个查询的答案是 xi 和任何 nums 数组中不超过 mi 的元素按位异或（XOR）得到的最大值。换句话说，答案是 max(nums[j] XOR xi) ，其中所有 j 均满足 nums[j] <= mi 。如果 nums 中的所有元素都大于 mi，最终答案就是 -1 。
返回一个整数数组 answer 作为查询的答案，其中 answer.length == queries.length 且 answer[i] 是第 i 个查询的答案。
示例 1：
输入：nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
输出：[3,3,7]
解释：
1) 0 和 1 是仅有的两个不超过 1 的整数。0 XOR 3 = 3 而 1 XOR 3 = 2 。二者中的更大值是 3 。
2) 1 XOR 2 = 3.
3) 5 XOR 2 = 7.示例 2：
输入：nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
输出：[15,-1,5]提示：
- 1 <= nums.length, queries.length <= 105
- queries[i].length == 2
- 0 <= nums[j], xi, mi <= 109
题解：
const int N = 1e5 + 50, M = 32 * N;
int son[M][2];
int idx;
void insert(int x){
int p = 0;
for(int i = 31; i >= 0; i--){
int u = (x >> i) & 1;
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
}
int query(int x){
int ans = 0, p = 0;
for(int i = 31; i >= 0; i--){
int u = (x >> i) & 1;
if(son[p][!u]) {
ans += (1 << i);
p = son[p][!u];
}
else p = son[p][u];
}
return ans;
}
class Solution {
public:
vector maximizeXor(vector& nums, vector>& queries) {
memset(son,0,sizeof son);
idx = 0;
sort(nums.begin(),nums.end());
//离线思想，因此需要对queries加一个pos，因为回答是乱序的
int pos = 0;
for(auto& q: queries){
q.push_back(pos++);
}
sort(queries.begin(),queries.end(),[](const auto& a,const auto& b){
return a[1] < b[1];
});
vector ans(queries.size());
int cur = 0;
for(const auto& q : queries){
int xi = q[0], mi = q[1],id = q[2];
while(cur < nums.size() and nums[cur] <= mi){
insert(nums[cur]);
cur++;
}
if(cur == 0) ans[id] = -1;
else ans[id] = query(xi);
}
return ans;
}
}; 【Day28】664.奇怪的打印机
664. 奇怪的打印机
有台奇怪的打印机有以下两个特殊要求：
- 打印机每次只能打印由 同一个字符 组成的序列。
- 每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。
给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。
示例 1：
输入：s = "aaabbb"
输出：2
解释：首先打印 "aaa" 然后打印 "bbb"。示例 2：
输入：s = "aba"
输出：2
解释：首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。提示：
- 1 <= s.length <= 100
- s 由小写英文字母组成
题解：
区间dp问题，对于[i,j]区间i<j，如果s[i] == s[j]，那么dp[i][j] = dp[i - 1][j] 或者dp[i + 1][j]，例如：aba 等于 ab或者 ba
如果s[i]!=s[j]，那么对于区间[i,j]的所有组合，进行累加求min即可。
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])
目标是求dp[0][n - 1]，因此，对于这道题有两种遍历方式。
第一种：从下往上，从左到右。
class Solution {
public:
int strangePrinter(string s) {
// aba
// aaabbb
int n = s.size();
int dp[n][n];
memset(dp, 0x3f3f3f3f, sizeof(dp));
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
if (s[i] == s[j]) {
dp[i][j] = dp[i][j - 1];
} else {
for (int k = i; k < j; k++) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
}
}
}
return dp[0][n - 1];
}
};第二种：斜着遍历。
class Solution {
public:
int strangePrinter(string s) {
// aba
// aaabbb
int n = s.size();
int dp[n][n];
memset(dp, 0x3f3f3f3f, sizeof(dp));
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
for (int l = 2; l <= n; l++) {
for (int i = 0; i < n - l + 1; i++) {
int j = l + i - 1;
if (s[i] == s[j]) {
dp[i][j] = dp[i][j - 1];
} else {
for (int k = i; k < j; k++) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
}
}
}
return dp[0][n - 1];
}
};【Day29】1787.使所有区间的异或结果为零
1787. 使所有区间的异或结果为零
给你一个整数数组 nums 和一个整数 k 。区间 [left, right]（left <= right）的 异或结果 是对下标位于 left 和 right（包括 left 和 right ）之间所有元素进行 XOR 运算的结果：nums[left] XOR nums[left+1] XOR … XOR nums[right] 。
返回数组中 要更改的最小元素数 ，以使所有长度为 k 的区间异或结果等于零。
示例 1：
输入：nums = [1,2,0,3,0], k = 1
输出：3
解释：将数组 [1,2,0,3,0] 修改为 [0,0,0,0,0]示例 2：
输入：nums = [3,4,5,2,1,7,3,4,7], k = 3
输出：3
解释：将数组 [3,4,5,2,1,7,3,4,7] 修改为 [3,4,7,3,4,7,3,4,7]示例 3：
输入：nums = [1,2,4,1,2,5,1,2,6], k = 3
输出：3
解释：将数组[1,2,4,1,2,5,1,2,6] 修改为 [1,2,3,1,2,3,1,2,3]提示：
1 <= k <= nums.length <= 2000
0 <= nums[i] < 210
题解：
第一种情况采用贪心的方法求得最优解。因为修改后的元素可能是原序列中没有出现过的元素。如果修改的某一列的元素是原序列中没有出现过的元素，那么这种情况下一定可以用贪心的办法求出最优解，做法是将众数最小的一列中的每个数变成一个全新的，该列中没有出现的，使得每个周期内的元素的异或和为0的数。
第二种情况采用dp的方法求得最优解在这种情况下，由于没有最终修改后的元素是原数组中存在的数，因此可以从前往后枚举每一列，然后枚举选择第几行的数作为这列元素修改后的元素，由于异或具有交换性质，因此不具有顺序的问题，所以可以采用dp的方法递推出将序列变成数组中本来存在的某个数的情况。边界，f[0] [0] = 0，目标状态是f[k] [0]，状态表示f[i] [j]为前i列异或和为j的情况下的最小值。
class Solution {
public:
// 1.某一列用了一个全新的数
// 2.每一列用了原来的数
const int N = 1024, INF = 1e8;
int s[1024]; // 求众数
int minChanges(vector& nums, int k) {
int n = nums.size(), m = (n + k - 1) / k;
vector> f(k + 1, vector(N, INF));
int cnt = 0, minv = INF; // 每一列代价
// f[i][j] 第i列的异或和为j
f[0][0] = 0;
for (int i = 1; i <= k; i++) {
int len = m;
memset(s, 0 , sizeof s);
if (n % k && n % k < i) len--;
for (int j = 0; j < len; j ++) {
s[nums[j * k + i - 1]]++;
}
int maxv = 0;
for (int j = 0; j < N; j++) {
maxv = max(maxv, s[j]);
}
cnt += len - maxv;
minv = min(minv, maxv); // 众数最少的那一列 不用众数 而用全新的数
for (int j = 0; j < N; j++) { // 异或和为j
for (int u = 0; u < len; u++) { // 每一行
int x = nums[u * k + i - 1], cost = len - s[x];
f[i][j] = min(f[i][j], f[i - 1][j ^ x] + cost);
}
}
}
// cnt: 每一列的代价
// minv表示 某一列不用众数时的代价 si - maxv -> si 变成全新的数代价
return min(cnt + minv, f[k][0]);
}
}; 【Day30】1190.反转每对括号间的子串
1190. 反转每对括号间的子串
给出一个字符串 s（仅含有小写英文字母和括号）。
请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。
注意，您的结果中 不应 包含任何括号。
示例 1：
输入：s = "(abcd)"
输出："dcba"示例 2：
输入：s = "(u(love)i)"
输出："iloveu"示例 3：
输入：s = "(ed(et(oc))el)"
输出："leetcode"示例 4：
输入：s = "a(bcdefghijkl(mno)p)q"
输出："apmnolkjihgfedcbq"提示：
- 0 <= s.length <= 2000
- s 中只有小写英文字母和括号
- 我们确保所有括号都是成对出现的
题解：
挨个遍历， 左括号和普通字符直接入栈；遇到右括号 ，就依次出栈直到栈顶为左括号 ，出栈的这些字符按出栈顺序链接自然也就是逆序的，然后栈顶左括号出栈 把组合成的逆序串重新压入栈。
遍历完字符串 栈中从栈底到栈顶 自然也就想要的结果，如果依次出栈 要注意连接顺序，还需要一次整体反转。
代码：
class Solution {
public:
string reverseParentheses(string s) {
stack st;
for (auto c : s) {
if (c != ')') {
st.push(c);
} else {
string tmp;
while (st.top() != '(') {
tmp += st.top();
st.pop();
}
st.pop();
for (auto s : tmp) {
st.push(s);
}
}
}
string ans;
while (!st.empty()) {
ans = st.top() + ans; st.pop();
}
return ans;
}
};
几天刚好一个月结束啦，收获还是很多的，困难我唯唯诺诺，简单重拳出击！！！hhh~
