格雷编码➕旋转
class Solution {
public:
vector<int> circularPermutation(int n, int start)
{
vector<int> ret;
ret.push_back(0);
//初始化
int head=1;
//层数看待
for(int i=0;i<n;i++)
{
for(int j=ret.size()-1;j>=0;j--)
{
ret.push_back(head+ret[j]);
}
head<<=1; //头部+1
}
vector<int> ans;
int m=ret.size();
int i=0;
for(;i<m;i++)
{
if(ret[i]==start)
break;
}
ans.insert(ans.end(),ret.begin()+i,ret.end());
ans.insert(ans.end(),ret.begin(),ret.begin()+i);
return ans;
}
};
lc922.奇偶排序的两种解法
1.奇偶分离
class Solution {
public:
vector<int> sortArrayByParityII(vector<int>& nums) {
vector<int> odds, evens, res(nums.size());
for (auto n : nums) {
if (n & 1) odds.push_back(n);
else evens.push_back(n);
}
for (int i = 0, oI = 1, eI = 0; i < odds.size(); ++i) {
res[eI] = evens[i], eI += 2; // 装偶数
res[oI] = odds[i], oI += 2; // 装厅数
}
return res;
}
};
2.双指针
class Solution {
public:
vector<int> sortArrayByParityII(vector<int>& nums) {
for (int i = 0, j = 1; i < nums.size(); i += 2) {
if (nums[i] % 2) {
while (nums[j] % 2) {
j += 2;
}
swap(nums[i], nums[j]);
}
}
return nums;
}
};
lc1900.模拟比赛
算出两个指定选手最早和最晚能在第几轮碰到。
还是建议dfs捏
模拟比赛，找出两个特定选手（firstPlayer和secondPlayer）最早和最晚相遇的轮次。
1. 定义了一个“选手”结构体，包含两个属性a（战斗力）和b（编号），并规定按b值排序。
2. 主函数里，根据总人数n设置模拟次数（人数越多模拟次数越多）。
3. 每次模拟时：
- 给所有选手随机分配战斗力，让两个特定选手战斗力最高（确保他们能赢到最后相遇）。
- 模拟比赛：每轮让第i名和第rest+1-i名选手对决，赢的留下。
- 检查这一轮是否是两个特定选手相遇，记录最早和最晚的轮次。
4. 最后返回这两个记录的轮次。
简单说就是通过多次模拟比赛，算出两个指定选手最早和最晚能在第几轮碰到。
struct node
{
int a , b;
bool operator <(const node &p)
{
return b < p.b;
}
}player[30];
class Solution {
public:
vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer)
{
srand(time(NULL));
// 根据n的大小设置模拟次数
int N;
if(n <= 10)
N = 800;
else if (n <= 20)
N = 8000;
else N = 38000;
int ans1 = 9999 , ans2 = 0 , rest , now;
while(N--)
{
// 剩余的运动员
rest = n;
// 初始化战斗力
for(int i = 1 ; i <= n ; i++)
{
player[i].a = rand() % 1075943;
player[i].b = i;
}
player[firstPlayer].a = 11000000;
player[secondPlayer].a = 10999999;
// 统计轮次
now = 1;
// 模拟比赛
while(rest > 1)
{
for(int i = 1 ; i <= rest / 2 ; i++)
{
if(player[i].a < player[rest + 1 - i].a)
player[i] = player[rest + 1 - i];
// 统计firstPlayer和secondPlayer相遇轮次的最大值和最小值
if(player[i].b == firstPlayer && player[rest + 1 - i].b == secondPlayer)
ans1 = min(ans1 , now) , ans2 = max(ans2 , now);
}
now++;
rest = (rest + 1) / 2;
sort(player + 1 , player + rest + 1);
}
}
vector<int> ans = {ans1 , ans2};
return ans;
}
};
dfs
class Solution {
bitset<1 << 15> m;
int the_max = 0, the_min = INT_MAX;
void dfs(int serial, int n, int firstPlayer, int secondPlayer) {
int mask = (n << 10) + (firstPlayer << 5) + secondPlayer;
int ff = n - firstPlayer + 1, fs = n - secondPlayer + 1;
if (ff == secondPlayer) {
the_max = max(the_max, serial);
the_min = min(the_min, serial);
return;
}
if (m[mask]) return;
m.set(mask);
int arr[] {firstPlayer, secondPlayer, ff, fs};
sort(arr, arr + 4);
int f_index = lower_bound(arr, arr + 4, firstPlayer) - arr;
int s_index = lower_bound(arr, arr + 4, secondPlayer) - arr;
for (int i = 0; i < arr[0]; ++i) {
for (int j = 0; j < arr[1] - arr[0]; ++j) {
int fi = arr[0] - 1 - i;
int fj = arr[1] - arr[0] - 1 - j;
int mid = (arr[2] - arr[1]) / 2;
int val[] { i, i + j, i + j + mid, i + j + mid + fj };
if (f_index == 0 && s_index == 1) {
dfs(serial + 1, (n + 1) / 2, val[0] + 1, val[1] + 2);
} else if (f_index == 2 && s_index == 3) {
dfs(serial + 1, (n + 1) / 2, val[2] + 1, val[3] + 2);
} else if (f_index == 0 && s_index == 2) {
dfs(serial + 1, (n + 1) / 2, val[0] + 1, val[2] + 2);
} else {
assert(f_index == 1 && s_index == 3);
dfs(serial + 1, (n + 1) / 2, val[1] + 1, val[3] + 2);
}
}
}
}
public:
vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
dfs(1, n,firstPlayer, secondPlayer);
return { the_min, the_max };
}
};
计算两个特定选手（firstPlayer和secondPlayer）在比赛中最早和最晚相遇的轮次。
1. 用深度优先搜索（dfs）模拟比赛过程，不是真的比胜负，而是追踪两个选手的位置变化。
2. 每次递归代表一轮比赛，选手按规则配对后，胜者进入下一轮，位置会重新排列。
3. 代码通过记录状态（当前总人数、两个选手的位置）避免重复计算，高效找出两人相遇的最早和最晚轮次。
简单说，就是用递归模拟每一轮比赛，追踪两个指定选手的位置变化，最终得出他们最早和最晚能碰上的轮次。
找回自信dp
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
//初始化一个dp表
vector<int> dp(n+1,0);
//初始化
dp[0]=dp[1]=0;
//填表
for(int i=2;i<n+1;i++)
//根据状态转移方程得
dp[i]=min(cost[i-1]+dp[i-1],cost[i-2]+dp[i-2]);
//一步两步当中，勇敢取小
return dp[n];
}
};
在 C++ 中， queue 可以存储 vector ，因为 queue 是一种容器适配器，它可以容纳任何符合要求的元素类型，包括标准容器（如 vector ）。
accumulate()累加求和
accumulate 是 C++ 标准库 <numeric> 里的一个实用工具，专门用来做累加求和
accumulate(vec开始位置, vec结束位置, 0);
eg.(nums.begin(),nums.end(),0)
lc2428.沙漏
可以固定左上角的点枚举，也可以用3*3卷积
更完善一点的，可以开辟空间
存储每个3x3区域的计算结果
vector<vector<int>> nums(m - 2, vector<int>(n - 2, 0));
class Solution {
public:
int maxSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int ret=0;
// 定义十字形卷积核, 处理映射
vector<vector<int>> Kernel = {{1,1,1}, {0,1,0}, {1,1,1}};
for (int i = 0; i <= m - 3; ++i) {
for (int j = 0; j <= n - 3; ++j) {
int sum=0;
for (int k = 0; k < 3; ++k) {
for (int l = 0; l < 3; ++l) {
sum += grid[i + k][j + l] * Kernel[k][l];
}
}
ret=max(ret,sum);
}
}
return ret;
}
};
对称二叉树
class Solution {
public:
bool isSymmetric(TreeNode* root)
{
if(!root) return true;
return com(root->left,root->right);
}
bool com(TreeNode* left,TreeNode* right)
{
//对称
if(!left && !right)
return true;
if(!left ||!right)
return false;
return (left->val==right->val)
&& com(left->left,right->right)
&& com(left->right,right->left);
}
};