目录
给定一个链表（链表结点包含一个整型值）的头结点 head。
同时给定列表 G，该列表是上述链表中整型值的一个子集。
返回列表 G 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 G 中）构成的集合。
示例 1：
输入:
head: 0->1->2->3
G = [0, 1, 3]
输出: 2
解释:
链表中,0 和 1 是相连接的，且 G 中不包含 2，所以 [0, 1] 是 G 的一个组件，同理 [3] 也是一个组件，故返回 2。
示例 2：
输入:
head: 0->1->2->3->4
G = [0, 3, 1, 4]
输出: 2
解释:
链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。
注意:
如果 N 是给定链表 head 的长度，1 <= N <= 10000。
链表中每个结点的值所在范围为 [0, N - 1]。
1 <= G.length <= 10000
G 是链表中所有结点的值的一个子集.
代码：
class Solution {
public:
bool has(vector<int>& G, int k)
{
return (lower_bound(G.begin(), G.end(), k) != upper_bound(G.begin(), G.end(), k));
}
int numComponents(ListNode* head, vector<int>& G) {
int ans = 0, num = 0;
ListNode* p = head;
sort(G.begin(), G.end());
while (p)
{
if(has(G, p->val))num++;
else if (num > 0)ans++, num = 0;
p = p->next;
}
if (num > 0)ans++;
return ans;
}
};在桌子上有 n 张卡片，每张卡片的正面和背面都写着一个正数（正面与背面上的数有可能不一样）。
我们可以先翻转任意张卡片，然后选择其中一张卡片。
如果选中的那张卡片背面的数字 x 与任意一张卡片的正面的数字都不同，那么这个数字是我们想要的数字。
哪个数是这些想要的数字中最小的数（找到这些数中的最小值）呢？如果没有一个数字符合要求的，输出 0 。
其中, fronts[i] 和 backs[i] 分别代表第 i 张卡片的正面和背面的数字。
如果我们通过翻转卡片来交换正面与背面上的数，那么当初在正面的数就变成背面的数，背面的数就变成正面的数。
示例 1：
输入：fronts = [1,2,4,4,7], backs = [1,3,4,1,3] 输出：2解释：假设我们翻转第二张卡片，那么在正面的数变成了[1,3,4,4,7]， 背面的数变成了[1,2,4,1,3]。接着我们选择第二张卡片，因为现在该卡片的背面的数是 2，2 与任意卡片上正面的数都不同，所以 2 就是我们想要的数字。
示例 2：
输入：fronts = [1], backs = [1] 输出：0 解释： 无论如何翻转都无法得到想要的数字，所以返回 0 。
提示：
n == fronts.length == backs.length1 <= n <= 10001 <= fronts[i], backs[i] <= 2000class Solution {
public:
int flipgame(vector<int>& fronts, vector<int>& backs) {
map<int,int>m;
vector<int>v;
for(int i=0;i<fronts.size();i++){
if(fronts[i]==backs[i])m[backs[i]]++;
v.push_back(fronts[i]);
v.push_back(backs[i]);
}
sort(v.begin(),v.end());
for(auto vi:v)if(m[vi]==0)return vi;
return 0;
}
};给你一个数组 seats 表示一排座位，其中 seats[i] = 1 代表有人坐在第 i 个座位上，seats[i] = 0 代表座位 i 上是空的（下标从 0 开始）。
至少有一个空座位，且至少有一人已经坐在座位上。
亚历克斯希望坐在一个能够使他与离他最近的人之间的距离达到最大化的座位上。
返回他到离他最近的人的最大距离。
示例 1：
输入：seats = [1,0,0,0,1,0,1] 输出：2 解释： 如果亚历克斯坐在第二个空位（seats[2]）上，他到离他最近的人的距离为 2 。 如果亚历克斯坐在其它任何一个空位上，他到离他最近的人的距离为 1 。 因此，他到离他最近的人的最大距离是 2 。
示例 2：
输入：seats = [1,0,0,0] 输出：3 解释： 如果亚历克斯坐在最后一个座位上，他离最近的人有 3 个座位远。 这是可能的最大距离，所以答案是 3 。
示例 3：
输入：seats = [0,1] 输出：1
提示：
2 <= seats.length <= 2 * 104seats[i] 为 0 或 1
class Solution {
public:
int maxDistToClosest(vector<int>& seats) {
int a = -1, ans = 0, last = 0;
for (int i = 0; i < seats.size(); i++) {
if (seats[i]) {
if (a == -1)ans = i;
else ans = max(ans, (i - a)/2);
a = i;
last = i;
}
}
return max(ans, int(seats.size() - 1 - last));
}
};题目：
N 辆车沿着一条车道驶向位于 target 英里之外的共同目的地。
每辆车 i 以恒定的速度 speed[i] （英里/小时），从初始位置 position[i] （英里） 沿车道驶向目的地。
一辆车永远不会超过前面的另一辆车，但它可以追上去，并与前车以相同的速度紧接着行驶。
此时，我们会忽略这两辆车之间的距离，也就是说，它们被假定处于相同的位置。
车队 是一些由行驶在相同位置、具有相同速度的车组成的非空集合。注意，一辆车也可以是一个车队。
即便一辆车在目的地才赶上了一个车队，它们仍然会被视作是同一个车队。
会有多少车队到达目的地?
示例：
输入：target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
输出：3
解释：
从 10 和 8 开始的车会组成一个车队，它们在 12 处相遇。
从 0 处开始的车无法追上其它车，所以它自己就是一个车队。
从 5 和 3 开始的车会组成一个车队，它们在 6 处相遇。
请注意，在到达目的地之前没有其它车会遇到这些车队，所以答案是 3。
提示：
0 <= N <= 10 ^ 4
0 < target <= 10 ^ 6
0 < speed[i] <= 10 ^ 6
0 <= position[i] < target
所有车的初始位置各不相同。
代码：
bool cmp(pair<int, int>a, pair<int, int>b)
{
return a.first > b.first;
}
class Solution {
public:
int carFleet(int target, vector<int>& position, vector<int>& speed) {
if (position.empty())return 0;
vector<pair<int, int>>pos;
for (int i = 0; i < position.size(); i++)
{
pos.insert(pos.end(), make_pair(position[i], speed[i]));
}
sort(pos.begin(), pos.end(), cmp);
int ans = pos.size(), k = 0;
for (int i = 1; i < pos.size(); i++)
{
long long a = target - pos[k].first, b = target - pos[i].first;
if (a*pos[i].second >= b*pos[k].second)ans--;
else k = i;
}
return ans;
}
};在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例 1：
输入：bills = [5,5,5,10,20] 输出：true 解释： 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。 由于所有客户都得到了正确的找零，所以我们输出 true。
示例 2：
输入：bills = [5,5,10,10,20] 输出：false 解释： 前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。 对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。 对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。 由于不是每位顾客都得到了正确的找零，所以答案是 false。
提示：
1 <= bills.length <= 105bills[i] 不是 5 就是 10 或是 20 class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int x5=0,x10=0,x20=0;
for(auto b:bills){
if(b==5)x5++;
else if(b==10){
if(x5<1)return false;
x10++,x5--;
}else{
if(x10==0){
if(x5<3)return false;
x5-=3;
}else{
if(x5<1)return false;
x10--,x5--;
}
}
}
return true;
}
};题目：
给定正整数 N ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。
如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。
示例 1：
输入：1
输出：true
示例 2：
输入：10
输出：false
示例 3：
输入：16
输出：true
示例 4：
输入：24
输出：false
示例 5：
输入：46
输出：true
提示：
1 <= N <= 10^9
思路：
2的幂非常少，一个个匹配就行了。
列出所有的2的幂，依次判断是不是能对应上即可。
代码：
class Solution {
public:
bool isSame(int a,int b) {
int num[10]={0};
while(a>0){
num[a%10]++;
a/=10;
}
while(b>0){
num[b%10]--;
b/=10;
}
for(int i=0;i<10;i++){
if(num[i]!=0){
return false;
}
}
return true;
}
bool reorderedPowerOf2(int N) {
for(int i=0;i<30;i++){
if(isSame(N,(1<<i))){
return true;
}
}
return false;
}
};贪心 贪心（1）田忌赛马_csuzhucong的博客-CSDN博客_力扣 田忌赛马
题目：
如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：
n >= 3
对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
给定一个严格递增的正整数数组形成序列，找到 A 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。
（回想一下，子序列是从原序列 A 中派生出来的，它从 A 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）
示例 1：
输入: [1,2,3,4,5,6,7,8]
输出: 5
解释:
最长的斐波那契式子序列为：[1,2,3,5,8] 。
示例 2：
输入: [1,3,7,11,12,14,18]
输出: 3
解释:
最长的斐波那契式子序列有：
[1,11,12]，[3,11,14] 以及 [7,11,18] 。
提示：
3 <= A.length <= 1000
1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
（对于以 Java，C，C++，以及 C# 的提交，时间限制被减少了 50%）
思路：
动态规划。DP[x][y]表示以A[x]和A[y]开头的最长斐波那契子数列的长度。
代码一：
备忘录写法
#define MAX 1000
int ans[MAX][MAX];
int dp(int x,int y,vector<int>& A)
{
if(ans[x][y]){
return ans[x][y];
}
auto it= lower_bound(A.begin(),A.end(),A[x]+A[y]);
ans[x][y]=((it!=A.end() && *it==A[x]+A[y])?(dp(y,it-A.begin(),A)+1):2);
return ans[x][y];
}
class Solution {
public:
int lenLongestFibSubseq(vector<int>& A) {
int res=0;
for(int i=0;i<A.size();i++){
memset(ans[i],0,sizeof(ans[0][0])*A.size());
}
for(int i=0;i<A.size();i++){
for(int j=i+1;j<A.size();j++){
if(res<dp(i,j,A)){
res=dp(i,j,A);
}
}
}
if(res<3)res=0;
return res;
}
};结果：AC 820ms
代码二：
非备忘录方法，控制计算顺序，省略初始化步骤
#define MAX 1000
int ans[MAX][MAX];
class Solution {
public:
int lenLongestFibSubseq(vector<int>& A) {
int res=0;
for(int j=A.size()-1;j>=0;j--){
for(int i=j-1;i>=0;i--){
auto it= lower_bound(A.begin(),A.end(),A[i]+A[j]);
ans[i][j]=((it!=A.end() && *it==A[i]+A[j])?(ans[j][it-A.begin()]+1):2);
res=max(res,ans[i][j]);
}
}
if(res<3)res=0;
return res;
}
};结果：AC 436ms
改进思路：
上述算法时间复杂度O（n* n * lg n）
利用双指针代替lower_bound完成查找工作，算法时间复杂度可以降为O（n* n）
珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。
珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。
示例 1：
输入: piles = [3,6,7,11], H = 8
输出: 4
示例 2：
输入: piles = [30,11,23,4,20], H = 5
输出: 30
示例 3：
输入: piles = [30,11,23,4,20], H = 6
输出: 23
提示：
1 <= piles.length <= 10^4
piles.length <= H <= 10^9
1 <= piles[i] <= 10^9
bool ok(vector<int>&b, int m,int ans)
{
int s=0;
for(int i=0;i<b.size();i++)
{
m-=(b[i]%ans>0)+b[i]/ans;
}
return m>=0;
}
class Solution {
public:
int minEatingSpeed(vector<int>& piles, int H) {
int low=0,high=1000000000;
while (low < high-1)
{
int mid = (low + high) / 2;
if(ok(piles,H,mid))high = mid;
else low = mid;
}
return high;
}
};高维DP 高维DP_csuzhucong的博客-CSDN博客
二叉树 二叉树_csuzhucong的博客-CSDN博客_二叉树csdn
写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请你实现 RecentCounter 类：
RecentCounter() 初始化计数器，请求数为 0 。int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。保证 每次对 ping 的调用都使用比之前更大的 t 值。
示例 1：
输入： ["RecentCounter", "ping", "ping", "ping", "ping"] [[], [1], [100], [3001], [3002]] 输出： [null, 1, 2, 3, 3] 解释： RecentCounter recentCounter = new RecentCounter(); recentCounter.ping(1); // requests = [1]，范围是 [-2999,1]，返回 1 recentCounter.ping(100); // requests = [1, 100]，范围是 [-2900,100]，返回 2 recentCounter.ping(3001); // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3 recentCounter.ping(3002); // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3
提示：
1 <= t <= 109ping 调用所使用的 t 值都 严格递增
ping 方法 104 次class RecentCounter {
public:
int ping(int t) {
v.push_back(t);
while(v[0]<v.back()-3000)v.erase(v.begin());
return v.size();
}
vector<int>v;
};贪心 贪心（4）选取问题_csuzhucong的博客-CSDN博客
给定一个有 N 个节点的二叉树，每个节点都有一个不同于其他节点且处于 {1, ..., N} 中的值。
通过交换节点的左子节点和右子节点，可以翻转该二叉树中的节点。
考虑从根节点开始的先序遍历报告的 N 值序列。将这一 N 值序列称为树的行程。
（回想一下，节点的先序遍历意味着我们报告当前节点的值，然后先序遍历左子节点，再先序遍历右子节点。）
我们的目标是翻转最少的树中节点，以便树的行程与给定的行程 voyage 相匹配。
如果可以，则返回翻转的所有节点的值的列表。你可以按任何顺序返回答案。
如果不能，则返回列表 [-1]。
示例 1：
输入：root = [1,2], voyage = [2,1]
输出：[-1]
示例 2：
输入：root = [1,2,3], voyage = [1,3,2]
输出：[1]
示例 3：
输入：root = [1,2,3], voyage = [1,2,3]
输出：[]
提示：
1 <= N <= 100
第一次AC的代码：
class Solution {
public:
map<int,int>m;
vector<int>ans;
int fin(vector<int>& voyage,int low,int high,int k)
{
if(m[k]>=low && m[k]<high)return m[k];
return high;
}
bool f(TreeNode* root, vector<int>& voyage,int low,int high){
if(!root)return low==high;
if(high<=low || voyage[low]!=root->val)return false;
if(!root->left && !root->right)return high==low+1;
if(high<=low+1)return false;
if(root->left && root->left->val==voyage[low+1])
{
if(root->right)return f(root->left,voyage,low+1,fin(voyage,low,high,root->right->val)) && f(root->right,voyage,fin(voyage,low,high,root->right->val),high);
return f(root->left,voyage,low+1,high);
}
if(root->right && root->right->val==voyage[low+1])
{
if(root->left)
{
ans.push_back(root->val);
return f(root->left,voyage,fin(voyage,low,high,root->left->val),high) && f(root->right,voyage,low+1,fin(voyage,low,high,root->left->val));
}
return f(root->right,voyage,low+1,high);
}
return false;
}
vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
m.clear();
ans.clear();
for(int i=0;i<voyage.size();i++)m[voyage[i]]=i;
if(f(root,voyage,0,voyage.size()))return ans;
ans.clear();
ans.push_back(-1);
return ans;
}
};然后感觉写的太繁琐，fin函数是不需要的，优化代码：
class Solution {
public:
map<int,int>m;
vector<int>ans;
bool f(TreeNode* root, vector<int>& voyage,int low,int high){
if(!root)return low==high;
if(high<=low || voyage[low]!=root->val)return false;
if(high==low+1)return !root->left && !root->right;
if(root->left && root->left->val==voyage[low+1])
{
if(root->right)return f(root->left,voyage,low+1,m[root->right->val]) && f(root->right,voyage,m[root->right->val],high);
return f(root->left,voyage,low+1,high);
}
if(root->right && root->right->val==voyage[low+1])
{
if(root->left)
{
ans.push_back(root->val);
return f(root->left,voyage,m[root->left->val],high) && f(root->right,voyage,low+1,m[root->left->val]);
}
return f(root->right,voyage,low+1,high);
}
return false;
}
vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
m.clear();
ans.clear();
for(int i=0;i<voyage.size();i++)m[voyage[i]]=i;
if(f(root,voyage,0,voyage.size()))return ans;
ans.clear();
ans.push_back(-1);
return ans;
}
};因为这题没有要求说不能改变二叉树的结构，所以我还试了一下改变二叉树结构的写法，使得代码更简洁：
class Solution {
public:
map<int,int>m;
vector<int>ans;
bool f(TreeNode* root, vector<int>& voyage,int low,int high){
if(!root)return low==high;
if(high<=low || voyage[low]!=root->val)return false;
if(high==low+1)return !root->left && !root->right;
if(root->right && root->right->val==voyage[low+1])
{
if(root->left)ans.push_back(root->val);
TreeNode* p=root->left;
root->left=root->right,root->right=p;
}
if(!root->left || root->left->val!=voyage[low+1])return false;
if(!root->right)return f(root->left,voyage,low+1,high);
return f(root->left,voyage,low+1,m[root->right->val]) && f(root->right,voyage,m[root->right->val],high);
}
vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
ans.clear();
for(int i=0;i<voyage.size();i++)m[voyage[i]]=i;
if(f(root,voyage,0,voyage.size()))return ans;
ans.clear();
ans.push_back(-1);
return ans;
}
};给定一个有 N 个结点的二叉树的根结点 root，树中的每个结点上都对应有 node.val 枚硬币，并且总共有 N 枚硬币。
在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点，或者从子结点移动到父结点。)。
返回使每个结点上只有一枚硬币所需的移动次数。
示例 1：
输入：[3,0,0]
输出：2
解释：从树的根结点开始，我们将一枚硬币移到它的左子结点上，一枚硬币移到它的右子结点上。
示例 2：
输入：[0,3,0]
输出：3
解释：从根结点的左子结点开始，我们将两枚硬币移到根结点上 [移动两次]。然后，我们把一枚硬币从根结点移到右子结点上。
示例 3：
输入：[1,0,2]
输出：2
示例 4：
输入：[1,0,0,null,3]
输出：4
提示：
1<= N <= 100
0 <= node.val <= N
class Solution {
public:
int distributeCoins(TreeNode* root,long &dif) {
if(!root)
{
dif=0;
return 0;
}
long dif1,dif2;
int ans1=distributeCoins(root->left,dif1),ans2=distributeCoins(root->right,dif2);
dif=dif1+dif2+root->val-1;
return ans1+ans2+abs(dif);
}
int distributeCoins(TreeNode* root) {
long dif=0;
return distributeCoins(root,dif);
}
};给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个从 0 到 25 的值，分别代表字母 'a' 到 'z'：值 0 代表 'a'，值 1 代表 'b'，依此类推。
找出按字典序最小的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。
（小贴士：字符串中任何较短的前缀在字典序上都是较小的：例如，在字典序上 "ab" 比 "aba" 要小。叶结点是指没有子结点的结点。）
示例 1：
输入：[0,1,2,3,4,3,4]
输出："dba"
示例 2：
输入：[25,1,3,1,3,0,2]
输出："adz"
示例 3：
输入：[2,2,1,null,1,0,null,0]
输出："abc"
提示：
给定树的结点数介于 1 和 8500 之间。
树中的每个结点都有一个介于 0 和 25 之间的值。
class Solution {
public:
void smallestFromLeaf(TreeNode* root, string cur, string &ans)
{
if (!root)return;
cur.insert(0, 1, char(int('a') + root->val));
if (!root->left && !root->right)
{
ans = min(ans, cur);
return;
}
smallestFromLeaf(root->left, cur, ans);
smallestFromLeaf(root->right, cur, ans);
}
string smallestFromLeaf(TreeNode* root) {
string ans = " ";
ans[0] = char(int('z') + 1);
smallestFromLeaf(root, "", ans);
return ans;
}
};