51. 加法
不使用+、-，计算两数字之和
class Solution {
public:
int getSum(int a, int b) {
while(b){
int carry = ((unsigned int)a&b)<<1;
a ^= b;
b = carry;
}
return a;
}
};
52. 至少有K个重复字符的最长子串
找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。
- 示例 1:
输入:
s = "aaabb", k = 3
输出:
3解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。
- 示例 2:
输入:
s = "ababbc", k = 2
输出:
5解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
思路：先统计出现在字符串中的字符出现频率，出现次数小于k的字符一定不会出现在期望的最长子串中。因此，可以将字符串分成若干个不包含出现次数小于k的符号的子串，分而治之，直到当前字符串中不包含出现次数小于k的字符。
class Solution {
public:
int longestSubstring(string s, int k) {
unordered_map<char, int> umap;
for(auto ch : s){
umap[ch]++;
}
vector<int> split;
for(int i =0; i < s.size(); ++i){
if(umap[s[i]] < k){
split.push_back(i);
}
}
if(split.empty()){return s.size();}
int prev = 0;
int res = 0;
split.push_back(s.size());
for(auto end : split){
int len = end - prev;
if(len > res){ // tips，剪枝，不考虑比当前出现的结果更短的串
res = max(res, longestSubstring(s.substr(prev,end),k));
}
prev = end+1;
}
return res;
}
};
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。
- 示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
思路：使用双指针，注意边界处的处理
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int res = INT_MAX;
if(nums.empty()){
return 0;
}
int l = 0, r = 0;
int sum = 0;
while(r < nums.size()){
if(sum < s){
sum += nums[r];
r++;
} else {
res = min(res, r-l);
sum -= nums[l];
l++;
}
}
while(sum >= s){
res = min(res, r-l);
sum -= nums[l];
l++;
}
return res==INT_MAX? 0:res;
}
};
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
思路：单调栈
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
int len = T.size();
vector<int> res(len,0);
stack<int> s;
for(int i =0; i < T.size(); ++i){
while(!s.empty()&&T[s.top()] < T[i]){
int prev = s.top();
s.pop();
res[prev] = i-prev;
}
s.push(i);
}
return res;
}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
unordered_map<int, int> m;//节点的值 -> inorder下标
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int len = preorder.size();
if(len==0){
return nullptr;
}
for(int i = 0; i < len; ++i){
m[inorder[i]]= i;
}
return build(preorder, 0, len-1,inorder, 0, len-1);
}
TreeNode* build(vector<int>& preorder, int pl, int pr, vector<int> &inorder, int il, int ir){//左闭右闭，访问数组的时候不要左闭右开
if(pl >pr || il > ir ){
return nullptr;
}
TreeNode* root = new TreeNode;
root->val = preorder[pl];
int inRootIndex = m[preorder[pl]];
int leftLen = inRootIndex - il;
TreeNode* left = build(preorder, pl+1, pl+leftLen,inorder,il,inRootIndex-1);
TreeNode* right = build(preorder, pl+leftLen+1,pr,inorder,inRootIndex+1, ir);
root->left = left;
root->right = right;
return root;
}
};
106. 从中序与后序遍历序列构造二叉树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
unordered_map<int, int> m;//节点的值 -> inorder下标
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int len = inorder.size();
if(len==0){
return nullptr;
}
for(int i = 0; i < len; ++i){
m[inorder[i]]= i;
}
return build(inorder, 0, len-1, postorder, 0, len-1);
}
TreeNode* build(vector<int>& inorder, int il, int ir, vector<int> &postorder, int pl, int pr){
if(il > ir){
return nullptr;
}
TreeNode* root = new TreeNode;
root->val = postorder[pr];
int inRootIndex = m[postorder[pr]];
int rightLen = inRootIndex - il;
TreeNode* left = build(inorder, il, inRootIndex-1,postorder,pl,pl+rightLen-1);
TreeNode* right = build(inorder,inRootIndex+1,ir,postorder,pl+rightLen, pr-1);
root->left = left;
root->right = right;
return root;
}
};
- 课程表（拓扑排序）
你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
示例 1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> m(numCourses, vector<int>());
vector<int> inDegree(numCourses, 0);
for(vector<int> v : prerequisites){
m[v[0]].push_back(v[1]);
inDegree[v[1]]++;
}
queue<int> q;
for(int i = 0; i < numCourses;++i){
if(inDegree[i] == 0){
q.push(i);
}
}
int n = numCourses;
while(!q.empty()){
int start = q.front();
q.pop();
n--;
for(int end : m[start]){
if(--inDegree[end]==0){
q.push(end);
}
}
}
return n==0;
}
现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
示例 1:
输入: 2, [[1,0]]
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2:
输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> to(numCourses, vector<int>());
vector<int> inDegree(numCourses,0);
vector<int> res;
for(vector<int> v : prerequisites){
inDegree[v[0]]++;
to[v[1]].push_back(v[0]);
}
queue<int> q;
for(int i = 0; i < numCourses; ++i){
if(inDegree[i]==0){
q.push(i);
res.push_back(i);
}
}
while(!q.empty()){
int fr = q.front();
q.pop();
for(int end: to[fr]){
inDegree[end]--;
if(inDegree[end]==0){
q.push(end);
res.push_back(end);
}
}
}
return res.size()==numCourses ? res : vector<int>();
}
};
- 课程表III
. 课程表 III
这里有 n 门不同的在线课程，他们按从 1 到 n 编号。每一门课程有一定的持续上课时间（课程时间）t 以及关闭时间第 d天。一门课要持续学习 t 天直到第 d 天时要完成，你将会从第 1 天开始。
给出 n 个在线课程用 (t, d) 对表示。你的任务是找出最多可以修几门课。
示例：
[[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出: 3
解释:
这里一共有 4 门课程, 但是你最多可以修 3 门:
首先, 修第一门课时, 它要耗费 100 天，你会在第 100 天完成, 在第 101 天准备下门课。
第二, 修第三门课时, 它会耗费 1000 天，所以你将在第 1100 天的时候完成它, 以及在第 1101 天开始准备下门课程。
第三, 修第二门课时, 它会耗时 200 天，所以你将会在第 1300 天时完成它。
第四门课现在不能修，因为你将会在第 3300 天完成它，这已经超出了关闭日期。
思路：贪心
贪心主要有两点：
当两门课的结束时间 d1 < d2 时，在允许的情况下，总是优先将课1排上。
假设当前的时间是x，前者需x+ t1 < d1 && x + t1 + t2 < d2 ，后者x+ t2 < d2 && x + t1 + t2 < d2，如果满足x+ t2 < d2 先学习后者，那么再学习前者时的要求从 x + t1 + t2 < d2 变成了更严格的 x + t1 + t2 < d1，有可能就少安排了一节课。如果当前无法满足 x+t < d 时，设当前已经安排的课中时间最长的课是t_max, 且当前的 t 小于 t_max，可以将t_max 这门课换成当前课程，（以寻求排更多的课）
算法：根据结束时间排序，如果满足 x + t < d，将t加入优先级队列，如果不满足，找到优先级
队列中的时间最长的课程替换。
class Solution {
public:
static bool cmp(vector<int> a, vector<int> b){
return b[1] > a[1];
}
int scheduleCourse(vector<vector<int>>& courses) {
sort(courses.begin(), courses.end(),cmp);
priority_queue<int> q;
int t = 0;
for(vector<int> v : courses){
if(v[0] + t <= v[1]){
q.push(v[0]);
t+=v[0];
} else if(!q.empty() && v[0] <q.top() ){
int m = q.top();
q.pop();
t+=v[0]-m;
q.push(v[0]);
}
}
return q.size();
}
};
- 婴儿名字
每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成了两个名字公布出来。给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。设计一个算法打印出每个真实名字的实际频率。注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。
在结果列表中，选择字典序最小的名字作为真实名字。
示例：
输入：names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"], synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
输出：["John(27)","Chris(36)"]
思路：具有传递和对称性的题目优先考虑使用并查集。
对于题目中出现过的每一个名字，用一个int来表示。
class FindUnion{
public:
vector<int> parent;//记录所在并查集的根结点
vector<string> name;
vector<int> rank;//记录出现的次数
FindUnion(vector<int>& rank,vector<string>& name, int len){
this->rank = rank;
this->name = name;
parent.resize(len);
for(int i = 0;i < len; ++i){
parent[i] = i;
}
}
//返回序号所在的根结点
int find(int idx){
int t = idx;
while(idx!=parent[idx]){
idx = parent[idx];
}
while(t!=idx){//将路径上的所有节点的parent更新为根结点，减少树的深度。
int tmp = parent[t];
parent[t] = idx;
t = tmp;
}
return idx;
}
void merge(int idx1, int idx2){
int parent1 = find(idx1);
int parent2 = find(idx2);
if(parent1 == parent2){//如果已经是在同一棵树上，就不用merge了
return;
}
string a = name[parent1];
string b = name[parent2];
if(a <= b){
parent[parent2] = parent1;
rank[parent1] =rank[parent1] + rank[parent2]; //是parent不是idx
} else {
parent[parent1] = parent2;
rank[parent2] = rank[parent1] + rank[parent2]; // 真正的merge操作
}
}
};
class Solution {
public:
vector<string> trulyMostPopular(vector<string>& names, vector<string>& synonyms) {
vector<string> name;
vector<int> rank;
unordered_map<string,int> m;
vector<string> res;
for(int i = 0; i < names.size(); ++i){
string n = names[i];
int p = n.find("(");
string str = n.substr(0,p);
int freq = atoi(n.substr(p+1,n.size()-p-2).c_str());
name.push_back(str);
rank.push_back(freq);
m[str] = i;
}
FindUnion fu(rank, name, names.size());
for(string synonym : synonyms){
int p = synonym.find(",");
string a = synonym.substr(1,p-1);
string b = synonym.substr(p+1,synonym.size()-2-p);
fu.merge(m[a],m[b]);
}
for(int i = 0; i < rank.size(); ++i){
if(fu.find(i)==i){
res.push_back(name[i] + "(" + to_string(fu.rank[i]) + ")");
}
}
return res;
}
};
- 最长有效括号
学习力扣的解法，很巧妙
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> stk;//stk里面可能有多个'(', 也有可能只有一个-1，也有可能只有一个‘)’:用来表示合法串前面的右括号下标
stk.push(-1);//处理边界条件，初始的时候假设栈中有一个右括号（不影响结果）
int m = 0;
for(int i = 0; i < s.length(); ++i){
if(s[i]=='('){//遇到左括号时，栈顶中无论时左括号还是右括号都push进去
stk.push(i);
} else {
stk.pop();
if(stk.empty()){//栈中只记录最新的右括号下标（此时栈中只有右括号）
stk.push(i);
} else { //匹配到了左括号，更新最大有效括号长度。
m = max(m, i-stk.top());
}
}
}
return m;
}
};
在显示着数字的坏计算器上，我们可以执行以下两种操作：
双倍（Double）：将显示屏上的数字乘 2；
递减（Decrement）：将显示屏上的数字减 1 。
最初，计算器显示数字 X。
返回显示数字 Y 所需的最小操作数。
示例 1：
输入：X = 2, Y = 3
输出：2
解释：先进行双倍运算，然后再进行递减运算 {2 -> 4 -> 3}.
示例 2：
输入：X = 5, Y = 8
输出：2
解释：先递减，再双倍 {5 -> 4 -> 8}.
示例 3：
输入：X = 3, Y = 10
输出：3
解释：先双倍，然后递减，再双倍 {3 -> 6 -> 5 -> 10}.
示例 4：
输入：X = 1024, Y = 1
输出：1023
解释：执行递减运算 1023 次
思路：
使用贪心算法+逆向思维，将题目变成Y->X，只能除二和加一。
当前如果是奇数，总是加一（因为奇数没有办法除2）
如果当前是偶数，总是除二（因为只有两次加一操作后才能再除二，总是不如一次除二一次加一）
class Solution {
public:
int brokenCalc(int X, int Y) {
int step=0;
while(Y>X){
step++;
if(Y%2==1){
Y++;
} else {
Y/=2;
}
}
return step + X - Y;
}
};
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
示例 1:
输入: [1,7,4,9,2,5]
输出: 6
解释: 整个序列均为摆动序列。
</pre>
示例 2:
输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
输入: [1,2,3,4,5,6,7,8,9]
输出: 2
思路：贪心
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if(nums.size()==0){
return 0;
}
bool init = true, dir = false;//dir=true时，当前方向为递增
int i = 1;
stack<int> s;
s.push(nums[0]);
while(i < nums.size()){
if(nums[i]==s.top()){ // 处理 [1,1,1,1,1] 这样的特殊例子
i++;
} else if(init){ //处理一下初始的情况
dir = nums[i] > s.top();
s.push(nums[i]);
init = false;
} else {
if(cmp(s.top(),nums[i],dir)){ // 贪心，将序列分为n个单调递增且长度大于等于1的序列，每次都取序列的最后一个元素入栈
s.pop();
s.push(nums[i]);
} else {
s.push(nums[i]);
dir = !dir;
}
}
}
return s.size();
}
bool cmp(int a,int b,bool c){
return c ? b>a:b<a;
}
};
- 分汤
有 A 和 B 两种类型的汤。一开始每种类型的汤有 N 毫升。有四种分配操作：
提供 100ml 的汤A 和 0ml 的汤B。
提供 75ml 的汤A 和 25ml 的汤B。
提供 50ml 的汤A 和 50ml 的汤B。
提供 25ml 的汤A 和 75ml 的汤B。
当我们把汤分配给某人之后，汤就没有了。每个回合，我们将从四种概率同为0.25的操作中进行分配选择。如果汤的剩余量不足以完成某次操作，我们将尽可能分配。当两种类型的汤都分配完时，停止操作。
注意不存在先分配100 ml汤B的操作。
需要返回的值： 汤A先分配完的概率 + 汤A和汤B同时分配完的概率 / 2。
示例:
输入: N = 50
输出: 0.625
解释:
如果我们选择前两个操作，A将首先变为空。对于第三个操作，A和B会同时变为空。对于第四个操作，B将首先变为空。
所以A变为空的总概率加上A和B同时变为空的概率的一半是 0.25 *(1 + 1 + 0.5 + 0)= 0.625。
思路：动态规划，dp[i][j] = (dp[i-4][j] + dp[i-3][j-1] + dp[i-2][j-2] + dp[i-1][j-3])
其中dp[0][0] = 0.5，dp[0][i] = 1 （i>0）
class Solution {
public:
double soupServings(int N) {
//坑，三元运算符要用（）包起来，因为优先级很低...
int len = N/25 + (N%25 == 0 ? 0 : 1) ;//当小于25的时候当25算， 注意这里可能会有 远小于25的N，有可能没有办法floor
if(len > 500){
return 1;
}
vector<vector<double>> dp(len+1, vector<double>(len+1));
dp[0][0] = 0.5;
for(int i = 1; i <= len; ++i){
dp[i][0] = 0.0;
}
for(int j = 1; j <= len; ++j){
dp[0][j] = 1.0;
}
for(int i = 1; i <= len; ++i){
for(int j = 1; j <= len; ++j){
dp[i][j] = 0.25*(dp[m(i-4)][j] + dp[m(i-3)][m(j-1)] + dp[m(i-2)][m(j-2)]
+ dp[m(i-1)][m(j-3)]);
}
}
return dp[len][len];
}
int m(int num){
return num>0? num : 0;
}
};
给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。
进阶:
如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？
示例:
// 初始化一个单链表 [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);
// getRandom()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。
solution.getRandom();
思路：蓄水池取样算法
最后返回的值为res，res 等于第 0 个节点。
从头向后遍历一个流（链表），设当前正在被遍历的是第i个节点(i从0开始)，从前向后遍历，每一个节点有1/i+1的几率替换之前的res。
第i个节点替换res 的可能性为 1/i+1，不被后面的节点替换的可能性 i+1/i+2* 1+2/i+3* ... * n-1/n
所以最后为 i 的可能为 1/n;
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
/** @param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node. */
Solution(ListNode* head) {
this->head = head;
}
/** Returns a random node's value. */
int getRandom() {
ListNode* tmp = this->head;
int i = 1;
int res = tmp->val;
while(tmp){
if((rand()% i++) ==0){
res = tmp->val;
}
tmp = tmp->next;
}
return res;
}
private:
ListNode* head;
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(head);
* int param_1 = obj->getRandom();
*/
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。要求空间复杂度不超过O(1)
示例 1:
输入: [1,2,0]
输出: 3
示例 2:输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
思路1:使用原地映射
设数组nums的总长度是N，那么nums中缺失的正整数范围为[1, N+1]。
在O(N)的空间复杂度要求下，可能我们会直接新建一个长度为n的bool类型数组，将nums中出现的正整数标记为true。最后遍历数组，第一个false就是没有出现的正整数（如果没有false，就是N+1）。
在O(1)的空间复杂度要求下，我们进行原地的哈希，规定如果nums[i]<0时，i+1在数组中出现过，实现这样的原地哈希需要先进行如下处理：
- 先把数组中所有小于等于0的数字换成大于N的数字。（保证数组中无负数和0）
- 再遍历数组，如果abs(nums[i])在[1,N]之间，将nums[abs(nums[i])-1]设置为负数。
- 最后遍历数组，缺失的第一个正数是nums中第一个负数的下标+1或者N+1
public:
int firstMissingPositive(vector<int>& nums) {
int len = nums.size();
for(int i = 0; i < nums.size(); ++i){
if(nums[i]<=0){
nums[i] = len+1;
}
}
for(int i = 0; i < nums.size(); ++i){
int idx = abs(nums[i]);
if(idx!=0&&idx <= len && nums[idx-1]>0){
nums[idx-1] = -nums[idx-1];
}
}
for(int i = 0; i<nums.size();++i){
if(nums[i]>0){return i+1;}
}
return len+1;
}
}
思路2: 原地置换
可以将置于区间[1,N]的元素i置换到nums[i-1]上。
实现：遍历整个数组，如果nums[i] 属于 [1,N] 这个区间，那么将nums[i] 与 nums[i-1] 交换位置，直到nums[i] 不属于这个区间。注意，由于有可能nums[i] == nums[x-1]，需要防止死循环，应加上nums[i]!=nums[x-1]
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
for(int i = 0; i < nums.size(); ++i){
int x = nums[i];
while(x<=nums.size()&&x > 0&&i != x-1&&nums[i]!=nums[x-1]){
swap(nums[x-1],nums[i]);
x = nums[i];
}
}
for(int i = 0; i < nums.size(); ++i){
if(i+1 != nums[i]){
return i+1;
}
}
return nums.size()+1;
}
};
- 一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快到达公主，骑士决定每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。
-2 (K) -3 3
-5 -10 1
10 30 -5 (P)
思路，动态规划
方法一：动态规划
思路及算法
几个要素：「M \times NM×N 的网格」「每次只能向右或者向下移动一步」。让人很容易想到该题使用动态规划的方法。
但是我们发现，如果按照从左上往右下的顺序进行动态规划，对于每一条路径，我们需要同时记录两个值。第一个是「从出发点到当前点的路径和」，第二个是「从出发点到当前点所需的最小初始值」。而这两个值的重要程度相同，参看下面的示例：
从 (0,0)(0,0) 到 (1,2)(1,2) 有多条路径，我们取其中最有代表性的两条：
绿色路径「从出发点到当前点的路径和」为 11，「从出发点到当前点所需的最小初始值」为 33。
蓝色路径「从出发点到当前点的路径和」为 -1−1，「从出发点到当前点所需的最小初始值」为 22。
我们希望「从出发点到当前点的路径和」尽可能大，而「从出发点到当前点所需的最小初始值」尽可能小。这两条路径各有优劣。
在上图中，我们知道应该选取绿色路径，因为蓝色路径的路径和太小，使得蓝色路径需要增大初始值到 44 才能走到终点，而绿色路径只要 33 点初始值就可以直接走到终点。但是如果把终点的 -2−2 换为 00，蓝色路径只需要初始值 22，绿色路径仍然需要初始值 33，最优决策就变成蓝色路径了。
因此，如果按照从左上往右下的顺序进行动态规划，我们无法直接确定到达 (1,2)(1,2) 的方案，因为有两个重要程度相同的参数同时影响后续的决策。也就是说，这样的动态规划是不满足「无后效性」的。
于是我们考虑从右下往左上进行动态规划。令 dp[i][j]dp[i][j] 表示从坐标 (i,j)(i,j) 到终点所需的最小初始值。换句话说，当我们到达坐标 (i,j)(i,j) 时，如果此时我们的路径和不小于 dp[i][j]dp[i][j]，我们就能到达终点。
这样一来，我们就无需担心路径和的问题，只需要关注最小初始值。对于 dp[i][j]dp[i][j]，我们只要关心 dp[i][j+1]dp[i][j+1] 和 dp[i+1][j]dp[i+1][j] 的最小值 \textit{minn}minn。记当前格子的值为 \textit{dungeon}(i,j)dungeon(i,j)，那么在坐标 (i,j)(i,j) 的初始值只要达到 \textit{minn}-\textit{dungeon}(i,j)minn−dungeon(i,j) 即可。同时，初始值还必须大于等于 11。这样我们就可以得到状态转移方程：
dp[i][j] = \max(\min(dp[i+1][j], dp[i][j + 1]) - \textit{dungeon}(i, j), 1)
dp[i][j]=max(min(dp[i+1][j],dp[i][j+1])−dungeon(i,j),1)
最终答案即为 dp[0][0]dp[0][0]。
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int m = dungeon.size();
if(m==0){
return 1;
}
int n = dungeon[0].size();
vector<vector<int>> dp(m+1, vector<int>(n+1,INT_MAX));
dp[m][n-1] = dp[m-1][n] = 1;
for(int i = m-1; i >=0 ; --i){
for(int j = n-1; j>=0; --j){
dp[i][j] = max(min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j],1);
}
}
return dp[0][0];
}
};
- 三角形最小路径和
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
例如，给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
思路：动态规划，dp[i][j] = min(dp[i-1][j-1] + dp[i-1][j])+val[i][j]
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int len = triangle.size();
if(len==0){
return 0;
}
vector<vector<int>> dp(len,vector<int>(len));
dp[0][0] = triangle[0][0];
for(int i = 1; i < len; ++i){
dp[i][0] = dp[i-1][0] + triangle[i][0];
for(int j = 1; j <i; ++j){
dp[i][j] = min(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j];
}
dp[i][i] = dp[i-1][i-1] + triangle[i][i];
}
int res = dp[len-1][0];
for(int j=1; j<len; ++j){
res = min(res,dp[len-1][j]);
}
return res;
}
};
优化：上面的空间复杂度是O(n^2)，可以优化到O(n)：
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int len = triangle.size();
if(len==0){
return 0;
}
vector<int> dp(len);
dp[0] = triangle[0][0];
for(int i = 1; i < len; ++i){
int prev = dp[0];
dp[0] = prev + triangle[i][0];
for(int j = 1; j <i; ++j){
int tmp = prev;
prev = dp[j];
dp[j] = min(tmp,dp[j]) + triangle[i][j];
}
dp[i] = prev + triangle[i][i];
}
int res = dp[0];
for(int j=1; j<len; ++j){
res = min(res,dp[j]);
}
return res;
}
};
- 判断二分图：
给定一个无向图graph，当这个图为二分图时返回true。
如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。
graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。
示例 1:
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释:
无向图如下:
0----1
| |
| |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。
示例 2:
输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
输出: false
解释:
无向图如下:
0----1
| \ |
| \ |
3----2
我们不能将节点分割成两个独立的子集。
思路：如果只用两种颜色就能将所有的节点上色，且任意一个边的两个节点颜色不同，则这个图是二分图。可以使用BFS或者DFS
#define UNCOLORED 0
#define RED 1
#define BLUE 2
class Solution {
public:
bool isBipartite(vector<vector<int>>& graph) {
int len = graph.size();
if(len==0){
return true;
}
vector<int> colors(len, UNCOLORED);
for(int i = 0; i < len; ++i){ //有可能提供的是多个图而不是一个图
if(colors[i]==UNCOLORED){
queue<int> q;
q.push(i);
while(!q.empty()){
int prevNode = q.front();
q.pop();
int prevColor = colors[prevNode];
for(int num : graph[prevNode]){
if(colors[num]==UNCOLORED){
colors[num] = prevColor == RED? BLUE:RED;
q.push(num);
} else {
if(prevColor == colors[num]){
return false;
}
}
}
}
}
}
return true;
}
};
- 整数拆分
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
思路：
数学推导，详见https://leetcode-cn.com/problems/integer-break/solution/343-zheng-shu-chai-fen-tan-xin-by-jyd/
class Solution {
public:
int integerBreak(int n) {
if(n<2){
return 0;
}
if(n==2){
return 1;
}
if(n==3){
return 2;
}
int a = n/3;
int b = n%3;
if(b==0){
return (int)pow(3,a);
} else if(b==1){
return (int)pow(3,a-1) * 4;
} else {
return (int)pow(3,a) * 2;
}
}
};
69.#### 两数之和 II - 输入有序数组
给定一个已按照**升序排列 **的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值index1 和 index2，其中 index1 必须小于 index2。
说明:
- 返回的下标值（index1 和 index2）不是从零开始的。
- 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
思路，由于数组是有序的，所以只需要使用双指针就可以。
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int i = 0, j = numbers.size()-1;
while(i<j){
int t = numbers[i] + numbers[j];
if(t==target){
return {i+1,j+1};
} else if( t>target ){
j--;
} else {
i++;
}
}
return {-1,-1};
}
//mid search 这里，需要注意low<=high不是low<high,不然两个边界都不行
// int midSearch(vector<int>& numbers,int low,int high, int target){
// int mid = (low+high)/2;
// while(low<=high){
// if(numbers[mid] < target){
// low = mid +1;
// } else if(numbers[mid] == target){
// return mid;
// } else {
// high = mid-1;
// }
// mid = (low+high)/2;
// }
// return -1;
// }
};
- 找零钱
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
输入: amount = 10, coins = [10]
输出: 1
思路：动态规划+逆向思维
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount+1);
dp[0] = 1;
for(int coin : coins){
for(int i = 0; i <= amount-coin; ++i){
dp[i+coin] += dp[i];
}
}
return dp[amount];
}
};
- 汉明距离
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
思路，位置不同可以考虑异或，计算异或结果中1的数量。
class Solution {
public:
int hammingDistance(int x, int y) {
int res = 0;
int t = x ^ y;
// while(t){
// if(t % 2==1){
// res++;
// }
// t = t>>1;
// }
//布赖恩·克尼根算法
while(t){
res++;
t = t & (t-1); //这个操作会把最右面的 1 去掉
}
return res;
}
};
- 子串出现的最大次数
给你一个字符串 s ，请你返回满足以下条件且出现次数最大的 任意 子串的出现次数：
子串中不同字母的数目必须小于等于 maxLetters 。
子串的长度必须大于等于 minSize 且小于等于 maxSize 。
示例 1：
输入：s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
输出：2
解释：子串 "aab" 在原字符串中出现了 2 次。
它满足所有的要求：2 个不同的字母，长度为 3 （在 minSize 和 maxSize 范围内）。
思路：如果出现的长度为3，
class Solution {
public:
int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
// maxSize没有用，因为如果最后长度为minSize+x的字串有重复了n次，那么一定有minSize的串重复了n次
unordered_map<string ,int> occ;// 子串哈希->出现次数
int res = 0;
for(int i = 0; i < s.size()-minSize+1; ++i){
string str = s.substr(i,minSize);
unordered_set<char> strSet(str.begin(), str.end());
if(strSet.size()<=maxLetters){
string str = s.substr(i,minSize);
occ[str]++;
res = max(res,occ[str]);
}
}
return res;
}
};
- 和为k的数组：
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int len = nums.size();
if(len==0){
return 0;
}
int res= 0;
for(int j = 0; j< len; ++ j){
int sum = 0;
for(int i = j; i>=0; --i){
sum += nums[i];
if(sum == k){
res++;
}
}
}
return res;
}
};
给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
输入:
nums = [7,2,5,10,8]
m = 2
输出:
18
解释:
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
思路：分析得知，对于一个非负整数数组，其子数组和的最大值处于[数组中元素的最大值，数组中所有的值] ，对于这样的一个离散的递增序列，我们可以使用二分查找解决。另外还需要实现判定是否满足m个子数组各自的和的最大值为不超过目标值x，可以使用贪心的算法：每次分子数组时，尽量使子数组的和接近但不超过目标值x，这样分的组最少，如果这样的分组个数小于等于m的话，表示可以满足分成m个子数组各自的和的最大值为不超过目标值x。
class Solution {
public:
bool check(vector<int> &nums, int x, int m){
int cnt = 0;
int sum = 0;
for(int i =0; i<nums.size(); ++i){
if(sum + nums[i] <= x){
sum +=nums[i];
} else {
sum = nums[i];
cnt++;
}
}
return cnt <= m;
}
int splitArray(vector<int>& nums, int m) {
if(nums.size()==0){
return 0;
}
int lower = nums[0];
int higher = nums[0];
for(int i = 1; i<nums.size(); ++i){
lower = max(lower, nums[i]);
higher+ = nums[i];
}
while(lower < higher){
long long mid = (mid + gi)
if(check(nums,mid,m)){
higher = mid;
} else {
lower = mid + 1;
}
}
return lower;
}
};
思路1:
dfs + 记忆
如果本题规定起点为{0,0}，那么这道题是一道很明显的DFS问题。现在这道题的起点有m*n个，这给我们带来了一定的优化空间-当一个节点DFS访问过的时候，我们会计算出来从这个节点开始的最长递增路径，把他缓存下来。当下一次重新DFS到这个节点的时候，无需继续递归，直接返回记忆值即可。
（注：起名不好，dp应该叫memo）
class Solution {
public:
vector<vector<int>> dir = {{0,1}, {1,0}, {0,-1},{-1,0}};
int m,n;
int longestIncreasingPath(vector<vector<int>>& matrix) {
m = matrix.size();
if(m==0){
return 0;
}
n = matrix[0].size();
vector<vector<int>> dp(m,vector<int>(n));
int res = 1;
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
res = max(res,longestPath(matrix,i,j,dp));
}
}
return res;
}
int longestPath(vector<vector<int>> & matrix, int li, int lj, vector<vector<int>>& dp){
if(dp[li][lj]!=0){
return dp[li][lj];
}
dp[li][lj]++;//自增序列至少是1，
for(int i = 0 ; i < 4; ++i){
int newI = li + dir[i][0];
int newJ = lj + dir[i][1];
//没有visited数组，因为matrix[newI][newJ] > matrix[li][lj]会确保不会访问之前的节点。
if(newI>=0&&newI < m&&newJ>=0 &&newJ < n && matrix[newI][newJ] > matrix[li][lj]){
dp[li][lj] = max(dp[li][lj], longestPath(matrix,newI,newJ,dp)+1);
}
}
return dp[li][lj];
}
};
思路2： 动态规划+拓扑排序
我们不难发现，一个节点的最长递增序列只与其上下左右四个节点（如果有的话）相关，可以使用动态规划进行计算。使用动态规划时，应使用拓扑序列进行——将整个矩阵看为一张图，其中每个元素是一个节点，当一个元素小于另一个元素时，有一条较小的元素到较大的元素的边。这样入度为0的节点就是最递增序列中最小的节点。
class Solution {
public:
vector<vector<int>> dir = {{0,1}, {1,0}, {0,-1},{-1,0}};
int m,n;
int longestIncreasingPath(vector<vector<int>>& matrix) {
m = matrix.size();
if(m==0){
return 0;
}
n = matrix[0].size();
vector<vector<int>> inDegree(m,vector<int>(n));
for(int i = 0 ; i < m; i++){
for(int j = 0; j < n; j++){
for(vector<int> v: dir){
int newI = i+v[0];
int newJ = j+v[1];
if(newI>=0&&newI<m&&newJ>=0&&newJ<n&&matrix[i][j]<matrix[newI][newJ]){
inDegree[newI][newJ]++;
}
}
}
}
queue<pair<int,int>> q;
vector<vector<int>> dp(m,vector<int>(n));
for(int i = 0; i < m; ++i){
for(int j = 0; j<n; ++j){
if(inDegree[i][j] ==0){
q.push(pair<int,int>(i,j));
dp[i][j]=1;
}
}
}
while(!q.empty()){
auto [li,lj] = q.front();
q.pop();
for(vector<int> v : dir){
int newI = li+v[0];
int newJ = lj+v[1];
if(newI<m&&newI >=0&&newJ>=0&&newJ<n&&matrix[newI][newJ]>matrix[li][lj]){
//有两种可能，一种是newI，newJ没有被DFS过，直接等于dp[li][lj]+1
// 另一种是被DFS过，取两者之间的最大
dp[newI][newJ] =max(dp[newI][newJ], dp[li][lj]+1);
inDegree[newI][newJ]--;
if(inDegree[newI][newJ]==0){
q.push(pair<int,int>(newI,newJ));
}
}
}
}
int res = 1;
for(int i = 0 ; i< m; ++i){
for(int j = 0 ; j<n; ++j){
res = max(res,dp[i][j]);
}
}
return res;
}
};
- 字符串转换整数
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。
思路：字符串处理，如果单纯的用逻辑判断，会被复杂的条件逼疯，看了力扣题解之后知道应该使用FSM实现：
class Solution {
public:
int myAtoi(string str) {
/*
*｜-------------------------------------------------------
*｜status\ symbol ｜ '-'/'+' ｜ '0'-'9' ｜ ' ' ｜ other
*｜-------------------------------------------------------
*｜ init ｜ signed ｜ num ｜ init ｜ end
*｜---------------｜------------｜---------｜------｜-------
*｜ singed ｜ end ｜ num ｜ end ｜ end
*｜---------------｜------------｜---------｜------｜-------
*｜ num ｜ end ｜ num ｜ end ｜ end
*｜---------------｜------------｜---------｜------｜-------
*｜ end ｜ end ｜ end ｜ end ｜ end
*｜--------------------------------------------------------
*/
vector<vector<int>> statusMachine = {
{1,2,0,3},
{3,2,3,3},
{3,2,3,3}
};
bool neg = false;
int curState = 0;
long long res = 0;
for(int i = 0; i < str.size()&&curState!=3; ++i){
int code = getCode(str[i]);
curState = statusMachine[curState][code];
if(ch == '-'){
neg == true;
}
if(curState==2){
res = res*10+str[i]-'0';
if(res > INT)
}
}
}
int getCode(char ch){
if(ch =='+' || ch =='-'){
return 0;
}
if(ch<='9'&&ch>='0'){
return 1;
}
if(ch ==' '){
return 2;
}
return 3;
}
};
- 最长递增子序列
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
思路：如果这个序列是有序的，我们很容易就可以求出长度，因此可以使用排序，虽然违背了力扣O(n)的要求，但是时间上击败了94%的用户
给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。
示例 1:
输入: [10,2]
输出: 210
示例 2:
输入: [3,30,34,5,9]
输出: 9534330
说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。
思路：我们总希望数值最大的排在前面，可以先简单考虑两个数字之前的排序，如果toString(num1) + toString(num2) > toString(num2) + toString(num1)，我们肯定会选择方案1。我们将字符串进行排序，如果满足上述条件，我们认为num1 > num2。这样排序后的数组按序拼接可以保证得到最优解。
class Solution {
static bool cmp(string a, string b){
return a+b>b+a;
}
public:
string largestNumber(vector<int>& nums) {
vector<string> strs(nums.size());
long long sum=0;
for(int i= 0; i < nums.size(); ++i){
strs[i] = to_string(nums[i]);
}
sort(strs.begin(),strs.end(),cmp);
if(strs[0]=="0"){//注意数组中有可能是全0，如果排序后的最大元素是
return "0";
}
string res = "";
for(string str:strs){
res = res + str;
}
return res;
}
};
- 超级丑数
编写一个程序，找出第 n 个丑数。
丑数就是质因数只包含 2, 3, 5 的正整数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
思路：可以看到数组中除了第一个数，其他的数都是2，3，5和数组中数字的乘积，可以使动态规划进行求解。由于丑数数组是一个增序排列，数组中对2的除数也一定是增序排列且在数组中下标连续的，3，5同理。我们可以记录2，3，5已经乘积的数组下标，每次取最小值放在结果的最后。其中需要注意的是，有可能2的乘积和3的乘积会一样（比如12 = 26 = 34）需要去重。
81. 分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
- 每个数组中的元素不会超过 100
- 数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
思路：题目可以换一种说法，叫，找出集合中的自数组，使其和为原来数组和的一半。然后就是一个典型的背包问题
class Solution {
public:
bool canPartition(vector<int>& nums) {
vector<int> freq(101);
int sum = 0;
for(int num: nums){
sum+=num;
}
if(sum&1==1){
return false;
}
vector<vector<bool>> dp(nums.size(), vector<bool>(sum/2+1));
for(int i = 0; i<nums.size(); ++i){
dp[i][0] = true;
}
if(nums[0]<sum/2+1){
dp[0][nums[0]] = true;
}
for(int i = 1; i < nums.size(); ++i){
for(int j = 1; j < sum/2+1; ++j){
if(j-nums[i]>=0 &&( dp[i-1][j-nums[i]]||dp[i-1][j]) ){
dp[i][j]=true;
}
}
}
return dp[nums.size()-1][sum/2];
}
};
82. h 指数
给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。
h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数 不超过 h 次。）
例如：某人的 h 指数是 20，这表示他已发表的论文中，每篇被引用了至少 20 次的论文总共有 20 篇。
示例：
输入：citations = [3,0,6,1,5]
输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。
排序以后十分简单
class Solution {
public:
int hIndex(vector<int>& citations) {
sort(citations.begin(),citations.end());
int i = 0;
int len = citations.size();
for(; i < len; ++i){
if(citations[i]<len-i){
} else {
break;
}
}
return len-i;
}
};
83. 下一个最大元素II
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
示例 1:
输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
思路1：暴力解法
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int len=nums.size();
vector<int> res(len);
for(int i = 0; i < len; i++){
int index = i;
while(true){
index++;
if(index == len){
index = 0;
}
if(index == i){
res[i] = -1;
break;
}
if(nums[index] > nums[i]){
res[i] = nums[index];
break;
}
}
}
return res;
}
};
思路2：单调栈
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int len=nums.size();
vector<int> res(len,-1);
stack<int> s;
for(int i = 0; i < 2*len; i++){
int realI = i <len ? i : i-len;
if(s.empty()){
s.push(realI);
} else {
int x = s.top();
while(!s.empty()&&nums[s.top()]<nums[realI]){
res[s.top()] = nums[realI];
s.pop();
}
s.push(realI);
}
}
return res;
}
};
84. 最小和的k个元素
给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。
定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2。
找到和最小的 k 对数字 (u1,v1), (u2,v2) ... (uk,vk)。
示例 1:
输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
示例 2:
输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数：
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
示例 3:
输入: nums1 = [1,2], nums2 = [3], k = 3
输出: [1,3],[2,3]
解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]
思路：堆排序，如果我们将所有的可能的数对加起来并排序会导致超时。这时候可以使用堆排序/插入排序，且当堆中的元素个数要超过k时，比较堆中的最大元素和当前元素，如果当前元素小于堆中的最大元素，使用当前的元素替换堆中元素，这样可以将复杂度从O(nlogn) （n是nums1.size()nums2.size()）降到 O(n*logk) 也就是O(n)。除此之外，还可以把nums1和nums2进行一次排序，这样nums1和nums2的加和也是整体相对有序，可以减少排序时间
class Solution {
public:
struct cmp{
bool operator ()(pair<int, int> &a, pair<int, int> &b) {
return a.first+a.second<b.first+b.second;
}
};
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
priority_queue<pair<int,int>,vector<pair<int,int>>,cmp>q;
vector<vector<int>>res;
sort(nums1.begin(),nums1.end());
sort(nums2.begin(),nums2.end());
for(int i=0;i<nums1.size();i++){
for(int j=0;j<nums2.size();j++){
if(q.size()<k)
q.push({nums1[i],nums2[j]});
else if(nums1[i]+nums2[j]<q.top().first+q.top().second){
q.pop();
q.push({nums1[i],nums2[j]});
}
}
}
while(!q.empty()){
pair<int,int> top=q.top();
res.push_back({top.first,top.second});
q.pop();
}
return res;
}
};
85. #### Minimum Genetic Mutation
A gene string can be represented by an 8-character long string, with choices from "A", "C", "G", "T".
Suppose we need to investigate about a mutation (mutation from "start" to "end"), where ONE mutation is defined as ONE single character changed in the gene string.
For example, "AACCGGTT" -> "AACCGGTA" is 1 mutation.
Also, there is a given gene "bank", which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.
Now, given 3 things - start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from "start" to "end". If there is no such a mutation, return -1.
Note:
Starting point is assumed to be valid, so it might not be included in the bank.
If multiple mutations are needed, all mutations during in the sequence must be valid.
You may assume start and end string is not the same.
Example 1:
start: "AACCGGTT"
end: "AACCGGTA"
bank: ["AACCGGTA"]
return: 1
Example 2:
start: "AACCGGTT"
end: "AAACGGTA"
bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]
return: 2
Example 3:
start: "AAAAACCC"
end: "AACCCCCC"
bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]
return: 3
思路：要求变异后的基因序列一定要在bank中，且每次只能变异一个位置。所以在每一次变异时，结果是从所有bank，中和当前基因比较变异距离为1的基因中选择，如果可以到达最终的end，认为可以变异。这里可以使用广度优先的遍历方式，找到最少变异次数。
class Solution {
public:
int diffNum(string a, string b){
int cnt = 0;
for(int i = 0; i<8; ++i){
if (a[i] != b[i]){
cnt++;
}
}
return cnt;
}
int minMutation(string start, string end, vector<string>& bank) {
int len = bank.size();
vector<bool> visited(len);
queue<pair<string,int>> q;
q.push(pair<string,int>(start,0));
while(!q.empty()){
auto [cur, step] = q.front();
q.pop();
for(int i = 0; i < len; ++i){
if(!visited[i]&&diffNum(cur, bank[i])==1){
visited[i] =true;
if(bank[i]==end){
return step+1;
}
q.push(pair<string,int>(bank[i], step+1));
}
}
}
return -1;
}
};
86. Alignment (POJ1836)
Description
In the army, a platoon is composed by n soldiers. During the morning inspection, the soldiers are aligned in a straight line in front of the captain. The captain is not satisfied with the way his soldiers are aligned; it is true that the soldiers are aligned in order by their code number: 1 , 2 , 3 , . . . , n , but they are not aligned by their height. The captain asks some soldiers to get out of the line, as the soldiers that remain in the line, without changing their places, but getting closer, to form a new line, where each soldier can see by looking lengthwise the line at least one of the line's extremity (left or right). A soldier see an extremity if there isn't any soldiers with a higher or equal height than his height between him and that extremity.
Write a program that, knowing the height of each soldier, determines the minimum number of soldiers which have to get out of line.
Input
On the first line of the input is written the number of the soldiers n. On the second line is written a series of n floating numbers with at most 5 digits precision and separated by a space character. The k-th number from this line represents the height of the soldier who has the code k (1 <= k <= n).
There are some restrictions:
• 2 <= n <= 1000
• the height are floating numbers from the interval [0.5, 2.5]
Output
The only line of output will contain the number of the soldiers who have to get out of the line.
Sample Input
8
1.86 1.86 1.30621 2 1.4 1 1.97 2.2
Sample Output
4
在oj上过的第一道认为不算太水的题，哭了，OJ是真的不如力扣。OJ上的题以过为目标，不追求效率。
思路：题目大意为：去掉最少的人数，使当前队中所有的人可以看到左端点或者是右端点，即中间高，两边矮。可以求出来从左到右和从右到左的最长递增子序列的dp、dp2数组，然后在所有的 dp[i] + dp2[j] (i<j) 中找到最大的ans，最后的结果就是 总人数 - ans
int main(){
int n ;
while(cin >>n) {
double heights[n];
for (int i = 0; i < n; ++i) {
cin >> heights[i];
}
vector<int> dp(n, 1);
vector<int> dp2(n, 1);
for (int i = 1; i < n; ++i) {
for (int j = i - 1; j >= 0; --j) {
if (heights[j] < heights[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
for (int i = n - 2; i >= 0; --i) {
for (int j = i+1; j < n; ++j) {
if (heights[j] < heights[i]) {
dp2[i] = max(dp2[i], dp2[j] + 1);
}
}
}
int ans = 0;
for(int i = 0; i < n; ++i){
for(int j = i+1; j < n; ++j){
ans = max(ans, dp[i] + dp2[j]);
}
}
cout << n - ans << endl;
}
return 0;
}
87. Power of Cryptography
Given an integer n>=1 and an integer p>= 1 you have to write a program that determines the n th positive root of p. In this problem, given such integers n and p, p will always be of the form k to the nth. power, for an integer k (this integer is what your program must find).
Input
The input consists of a sequence of integer pairs n and p with each integer on a line by itself. For all such pairs 1<=n<= 200, 1<=p<10^101 and there exists an integer k, 1<=k<=10^9 such that kn = p.
Output
For each integer pair n and p the value k should be printed, i.e., the number k such that k^n =p.
Sample Input
2 16
3 27
7 4357186184021382204544
Sample Output
4
3
1234
思路：double 完全可以hold住10^101
int m;
double n;
while(cin >>m >>n){
cout << pow(n, 1.0/m) << endl;
}
88.POJ2586
易证得全年盈利只与12个月中盈利月总数和亏损月总数相关，与各月具体盈利或亏损无关。
分析可知，欲满足每5个月总和为亏损，全年又必须盈利，则需要令每五个月内的亏损尽可能少。又为了尽可能多的让亏损月份可以在其他区间中共享，令5个月中的亏损月后置，盈利月前置。
1~5月中盈利亏损分部仅有以下几种可能：
ssssd
sssdd
ssddd
sdddd
确定第一个月的分部后，后面月份可以根据【统计亏损月份数量是否足够，不足则在末尾补上】的策略推出。
只需按亏损月数递增的顺序扫描上述四种方案，直到能使5个月总和为亏损则停止。由选定的方案即可确定全年12个月方案。则可求出全年是否盈利。若全年财务为负值则不可盈利。
（因ddddd的情况为全年亏损，明显无法盈利，故不用考虑。若遇到四个月亏损一个月盈利仍无法使5个月总和为负，则直接输出Deficit）
根据前五个月可推出全年方案只有四种：
ssssdssssdss
sssddsssddss
ssdddssdddss
sddddsddddsd
将四种方案的盈利月数和亏损月数总和直接存储在常数组中，方便计算。
程序样例
include<stdio.h>
int main() {
const int a[4][2] = {3,9,6,6,8,4,10,2};
int s, d, i;
while (scanf("%d%d", & s, & d) == 2) {
for (i = 4; i >= 1; i--)
if (s * i < d * (5 - i)) break;
if (i == 0 || (s * a[i - 1][0] - d * a[i - 1][1]) < 0)
printf("Deficit\n");
else
printf("%d\n", s * a[i - 1][0] - d * a[i - 1][1]);
}
return 0;
}
88. Supermarket
Description
A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral number of time units starting from the moment the sale begins. Each product takes precisely one unit of time for being sold. A selling schedule is an ordered subset of products Sell ≤ Prod such that the selling of each product x∈Sell, according to the ordering of Sell, completes before the deadline dx or just when dx expires. The profit of the selling schedule is Profit(Sell)=Σx∈Sellpx. An optimal selling schedule is a schedule with a maximum profit.
For example, consider the products Prod={a,b,c,d} with (pa,da)=(50,2), (pb,db)=(10,1), (pc,dc)=(20,2), and (pd,dd)=(30,1). The possible selling schedules are listed in table 1. For instance, the schedule Sell={d,a} shows that the selling of product d starts at time 0 and ends at time 1, while the selling of product a starts at time 1 and ends at time 2. Each of these products is sold by its deadline. Sell is the optimal schedule and its profit is 80.
Write a program that reads sets of products from an input text file and computes the profit of an optimal selling schedule for each set of products.
Input
A set of products starts with an integer 0 <= n <= 10000, which is the number of products in the set, and continues with n pairs pi di of integers, 1 <= pi <= 10000 and 1 <= di <= 10000, that designate the profit and the selling deadline of the i-th product. White spaces can occur freely in input. Input data terminate with an end of file and are guaranteed correct.
Output
For each set of products, the program prints on the standard output the profit of an optimal selling schedule for the set. Each result is printed from the beginning of a separate line.
Sample Input
4 50 2 10 1 20 2 30 1
7 20 1 2 1 10 3 100 2 8 2
5 20 50 10
Sample Output
80
185
Hint
The sample input contains two product sets. The first set encodes the products from table 1. The second set is for 7 products. The profit of an optimal schedule for these products is 185.
思路：贪心
ddl从后往前，总是选择满足ddl当前中价值最高的商品售卖出去。
void poj1456() {
int n;
while (cin >> n) {
vector<vector<int> > goods(10001);
for (int i = 0; i < n; ++i) {
int pr, dl;
cin >> pr >> dl;
goods[dl].push_back(pr);
}
priority_queue<int> q;
int res = 0;
for (int i = 10000; i > 0; --i){
for(int j = 0; j< goods[i].size(); ++j){
q.push(goods[i][j]);
}
if(!q.empty()) {
res += q.top();
q.pop();
}
}
cout << res << endl;
}
}
89. POJ1080
Description
It is well known that a human gene can be considered as a sequence, consisting of four nucleotides, which are simply denoted by four letters, A, C, G, and T. Biologists have been interested in identifying human genes and determining their functions, because these can be used to diagnose human diseases and to design new drugs for them.
A human gene can be identified through a series of time-consuming biological experiments, often with the help of computer programs. Once a sequence of a gene is obtained, the next job is to determine its function.
One of the methods for biologists to use in determining the function of a new gene sequence that they have just identified is to search a database with the new gene as a query. The database to be searched stores many gene sequences and their functions – many researchers have been submitting their genes and functions to the database and the database is freely accessible through the Internet.
A database search will return a list of gene sequences from the database that are similar to the query gene.
Biologists assume that sequence similarity often implies functional similarity. So, the function of the new gene might be one of the functions that the genes from the list have. To exactly determine which one is the right one another series of biological experiments will be needed.
Your job is to make a program that compares two genes and determines their similarity as explained below. Your program may be used as a part of the database search if you can provide an efficient one.
Given two genes AGTGATG and GTTAG, how similar are they? One of the methods to measure the similarity
of two genes is called alignment. In an alignment, spaces are inserted, if necessary, in appropriate positions of
the genes to make them equally long and score the resulting genes according to a scoring matrix.
For example, one space is inserted into AGTGATG to result in AGTGAT-G, and three spaces are inserted into GTTAG to result in –GT--TAG. A space is denoted by a minus sign (-). The two genes are now of equal
length. These two strings are aligned:
AGTGAT-G
-GT--TAG
In this alignment, there are four matches, namely, G in the second position, T in the third, T in the sixth, and G in the eighth. Each pair of aligned characters is assigned a score according to the following scoring matrix.
<center>
</center>
denotes that a space-space match is not allowed. The score of the alignment above is (-3)+5+5+(-2)+(-3)+5+(-3)+5=9.
Of course, many other alignments are possible. One is shown below (a different number of spaces are inserted into different positions):
AGTGATG
-GTTA-G
This alignment gives a score of (-3)+5+5+(-2)+5+(-1) +5=14. So, this one is better than the previous one. As a matter of fact, this one is optimal since no other alignment can have a higher score. So, it is said that the
similarity of the two genes is 14.
Input
The input consists of T test cases. The number of test cases ) (T is given in the first line of the input file. Each test case consists of two lines: each line contains an integer, the length of a gene, followed by a gene sequence. The length of each gene sequence is at least one and does not exceed 100.
Output
The output should print the similarity of each test case, one per line.
Sample Input
2
7 AGTGATG
5 GTTAG
7 AGCTATT
9 AGCTTTAAA </pre>
Sample Output
14
21
思路：可以使用动态规划，
初始 - 两个空串的最大距离是0
递推 - 两个非空串的最大距离需要通过三种计算结果比较得知，例如当前的串1是 ACGT... 和 串2是 A-GA...，其中前三个已经是最佳匹配，有以下3种可能 ——
- 串1 = ACG- 串2 = A-GA
- 串1 = ACGT 串2 = A-G-
- 串1 = ACGT 串2 = A-GA
选择其中最大的。
const int matr[5][5] = {
{ 5, -1, -2, -1, -3},
{-1, 5, -3, -2, -4},
{-2, -3, 5, -2, -2},
{-1, -2, -2, 5, -1},
{-3, -4, -2, -1, 5}
};
int get(char ch) {
switch (ch) {
case 'A': {
return 0;
}
case 'C': {
return 1;
}
case 'G': {
return 2;
}
case 'T': {
return 3;
}
}
return 4;
}
void poj1080() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
string a, b;
int m, n;
cin >> m >> a >> n >> b;
vector<vector<int> > dp(m + 1, vector<int>(n + 1));
dp[0][0] = 0;
for (int i = 1; i <= m; ++i) {
dp[i][0] = dp[i - 1][0] + matr[get(a[i - 1])][4];
}
for (int i = 1; i <= n; ++i) {
dp[0][i] = dp[0][i - 1] + matr[get(b[i - 1])][4];
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
dp[i][j] = max(dp[i][j], dp[i][j - 1] + matr[4][get(b[j - 1])]);
dp[i][j] = max(dp[i][j], dp[i - 1][j] + matr[get(a[i - 1])][4]);
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + matr[get(a[i - 1])][get(b[j - 1])]);
}
}
cout << dp[m][n] << endl;
}
}
90. POJ1068
Description
Let S = s1 s2...s2n be a well-formed string of parentheses. S can be encoded in two different ways:
q By an integer sequence P = p1 p2...pn where pi is the number of left parentheses before the ith right parenthesis in S (P-sequence).
q By an integer sequence W = w1 w2...wn where for each right parenthesis, say a in S, we associate an integer which is the number of right parentheses counting from the matched left parenthesis of a up to a. (W-sequence).
Following is an example of the above encodings:
S (((()()())))
P-sequence 4 5 6666
W-sequence 1 1 1456
Write a program to convert P-sequence of a well-formed string to the W-sequence of the same string.
Input
The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case is an integer n (1 <= n <= 20), and the second line is the P-sequence of a well-formed string. It contains n positive integers, separated with blanks, representing the P-sequence.
Output
The output file consists of exactly t lines corresponding to test cases. For each test case, the output line should contain n integers describing the W-sequence of the string corresponding to its given P-sequence.
Sample Input
2
6
4 5 6 6 6 6
9
4 6 6 6 6 8 9 9 9
Sample Output
1 1 1 4 5 6
1 1 2 4 5 1 1 3 9
思路：使用栈记录左括号下标，每次在匹配的左括号和右括号之间寻找做括号的个数
#include <stack>
#include <queue>
void poj1068(){
int n;
cin >> n;
while(n--){
int num;
cin >> num;
vector<int> rights(num+1);
stack<int> s;
string str = "";
for(int i = 1 ; i <= num; ++i){
cin >> rights[i];
for (int j = 0; j < rights[i]-rights[i-1]; ++j) {
str += "(";
}
str += ")";
}
vector<int> res;
for (int i = 0; i < 2*num; ++i) {
if(str[i] == '('){
s.push(i);
} else {
int prevLeft = s.top();
s.pop();
int cnt = 0;
for (int j = prevLeft; j < i; ++j) {
if(str[j] == '('){
cnt++;
}
}
res.push_back(cnt);
}
}
for(int i = 0 ; i< res.size(); ++i){
cout << res[i] << " " ;
}
cout << endl;
}
}
91. 打家劫舍系列：
I
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
思路：动态规划，设 dp[i] 为前 i 家能抢到的最大值，那么
dp[i] = max(dp[i-2]+nums[i], dp[i-1)
class Solution {
public:
int rob(vector<int>& nums) {
int pre=0, tmp=0, cur = 0;
for(int num:nums){
tmp = cur;
cur = max(pre+num, cur);
pre = tmp;
}
return cur;
}
};
II
在I的基础上，房子按照圆形排列，即第一家和最后一家不能一块偷
思路：既然第一家和最后一家不能同事偷，那么答案就是偷前n-1家和偷后n-1家中的最大值/
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size()==1){
return nums[0];
}
return max(myRob(nums, 1,nums.size()), myRob(nums,0,nums.size()-1));
}
int myRob(vector<int> &nums, int start, int end){
int len = end-start;
int cur = 0, tmp = 0, pre = 0;
for(int i = start; i< end; ++i){
tmp = cur;
cur = max(pre + nums[i], cur);
pre = tmp;
}
return cur;
}
};
92. 恢复搜索二叉树
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
思路：搜索二叉树的中序遍历是有序的，可以通过中序找到需要交换的两个元素的值，将他们交换回来：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void recoverTree(TreeNode* root) {
inorder(root);
vector<int> two = findSwappedVal();
recover(root,two[0],two[1]);
}
vector<int> nums;
void inorder(TreeNode* root){
if(!root){
return;
}
inorder(root->left);
nums.push_back(root->val);
inorder(root->right);
}
vector<int> findSwappedVal(){
int x = -1, y = -1;
for(int i = 1; i<nums.size(); ++i){
if(nums[i-1]>nums[i]){
if(x==-1){
x = nums[i-1];
}
y = nums[i];
}
}
return {x,y};
}
void recover(TreeNode* node,int val1,int val2){
if(!node){
return;
}
if(node ->val == val1||node->val ==val2){
node->val = node->val==val1? val2:val1;
}
recover(node->left, val1,val2);
recover(node->right,val1,val2);
}
};
93. Sorting It All Out
scription
An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.
Input
Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.
Output
For each problem instance, output consists of one line. This line should be one of the following three:
Sorted sequence determined after xxx relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.
where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.
Sample Input
4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0
Sample Output
Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.
思路：
拓扑排序，使用队列来保存当前度为0的节点。当队列中的元素数字永远只有一个的时候，拓扑排序的顺序是肯定的。
int n,m,num,ok;
vector<int> G[maxn];
vector<int> ans;
queue<int> q;
char s[10];
int inDeg[maxn], tmp[maxn];
int topSort()
{
while(!q.empty()) q.pop();
for(int i=0;i<n;i++) ans.clear();
ok=0;
memcpy(tmp,inDeg,sizeof(inDeg));
for(int i=0;i<n;i++) if(!inDeg[i]) q.push(i);
while(!q.empty())
{
if(q.size()>1) ok = 1; //q中只有始终1个元素，才能保证全序
int now = q.front();
q.pop();
ans.push_back(now);
for(int i=0; i<G[now].size(); i++)
{
int son = G[now][i];
if(--tmp[son] == 0) q.push(son);
}
}
if(ans.size() < n) return 0; //存在环
if(ok) return 1; //无法生成序列/不能确定次序
return 2; //ok
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF,n,m)
{
int ok=0; //必须局部定义标志变量！
ms(inDeg,0);
ms(tmp,0);
for(int i=0;i<n;i++) G[i].clear();
for(int i=0;i<n;i++) ans.clear();
for(int i=1;i<=m;i++)
{
scanf("%s",s);
if(ok) continue;
int u = s[0] - 'A';
int v = s[2] - 'A';
G[u].push_back(v);
inDeg[v]++;
int z = topSort();
if(z==0)
{
printf("Inconsistency found after %d relations.\n",i);
ok=1;
}
if(z==2)
{
printf("Sorted sequence determined after %d relations: ",i);
for(int i=0;i<n;i++)
printf("%c",ans[i]+'A');
printf(".\n");
ok=1;
}
}
if(ok==0)
printf("Sorted sequence cannot be determined.\n");
}
return 0;
}
94. MyCalendarIII
Implement a MyCalendarThree class to store your events. A new event can always be added.
Your class will have one method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.
A K-booking happens when K events have some non-empty intersection (ie., there is some time that is common to all K events.)
For each call to the method MyCalendar.book, return an integer K representing the largest integer such that there exists a K-booking in the calendar.
Your class will be called like this: MyCalendarThree cal = new MyCalendarThree(); MyCalendarThree.book(start, end)
Example 1:
MyCalendarThree();
MyCalendarThree.book(10, 20); // returns 1
MyCalendarThree.book(50, 60); // returns 1
MyCalendarThree.book(10, 40); // returns 2
MyCalendarThree.book(5, 15); // returns 3
MyCalendarThree.book(5, 10); // returns 3
MyCalendarThree.book(25, 55); // returns 3
Explanation:
The first two events can be booked and are disjoint, so the maximum K-booking is a 1-booking.
The third event [10, 40) intersects the first event, and the maximum K-booking is a 2-booking.
The remaining events cause the maximum K-booking to be only a 3-booking.
Note that the last event locally causes a 2-booking, but the answer is still 3 because
eg. [10, 20), [10, 40), and [5, 15) are still triple booked.
Note:
The number of calls to MyCalendarThree.book per test case will be at most 400.
In calls to MyCalendarThree.book(start, end), start and end are integers in the range [0, 10^9].
思路1：
当开始了一个预定的时候，需要增加一个线程，当结束了一个预定，则表明空闲出来了一个线程（这个线程可以接受别的预定）。顺着时间轴来，我们可以得到每次预定后所需的最少线程数。
class MyCalendarThree {
public:
MyCalendarThree() {
}
map<int, int> m;//c++中的map是根据key升序排列的。
int book(int start, int end) {
if(++m[start]==0){
m.erase(start);
}
if(--m[end] == 0){
m.erase(end);
}
int active = 0;
int ans = 0;
for(auto it : m){
active += it.second;
ans = max(active,ans);
}
return ans;
}
};
思路2，线段树
关于线段树的介绍，参考了这篇：知乎文章
结合这道题就是我们其实希望对于区间进行一个离散化，每预定一个区间，就对于区间中离散的元素进行+1操作，最后想找到这些离散化区间元素中的最大值。这时候可以使用线段树。
class MyNode{
public:
int start, end, maxP, mark;
MyNode * left = nullptr;
MyNode * right = nullptr;
MyNode(int start, int end){
this->start = start;
this-> end = end;
maxP = 0;
mark = 0;
}
MyNode* leftChild(){
if(!this->left){
this->left = new MyNode(start,(start + end) >> 1);
}
return this->left;
}
MyNode* rightChild(){
if(!this->right){
this->right = new MyNode((start+end)>>1, end);
}
return this -> right;
}
int insert(int start,int end){
if(start <= this-> start && end >= this->end){ // 当前区间被完全 包含
maxP++;
mark++;
} else if(start < this->end || end > this->start){ //有相交
leftChild()->maxP +=this->mark;
rightChild()->maxP +=this->mark;
leftChild()->mark += this->mark;
rightChild()->mark += this->mark; // 懒更新
mark = 0;
maxP = max(this->maxP,max(leftChild()->insert(start,end),rightChild()->insert(start,end)));
}
return this->maxP;
}
};
class MyCalendarThree {
public:
MyCalendarThree() {
node = new MyNode(0,1000000000);
}
MyNode* node;
int book(int start, int end) {
return node->insert(start,end);
}
};
95. Count Binary SubStrings
Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively.
Substrings that occur multiple times are counted the number of times they occur.
Example 1:
Input: "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".
Notice that some of these substrings repeat and are counted the number of times they occur.
Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.
Example 2:
Input: "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.
Note:
s.length will be between 1 and 50,000.
s will only consist of "0" or "1" characters.
思路：观察得知 0011 和 01 或者是 1100 和 10 一定成立，所以。所以当我们统计字符串中符合要求的子串个数，可以先统计0和1连续出现的次数，比如 000011001111 => {4,2,2,4} 。由于符合要求的子串一定开头全是0或者结尾全是0，且出现1的次数和出现0的次数一样，所以符合子串一定是在相邻的两个序列中0或1出现次数的最小值之和，即min{4,2} + min{2,2}+ min{2,4} = 6。
class Solution {
public:
int countBinarySubstrings(string s) {
int i = 0, prev = 0, res = 0, tmp = 0;
while(i < s.size()){
char ch = s[i];
tmp = 0;
while(s[i] == ch){
i++;
tmp ++;
}
res += min(prev, tmp);
prev = tmp;
}
return res;
}
};
96. Surrounded Region
Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
Example:
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
Explanation:
Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.
思路1:根据题意，我们知道所有和边界上相连的 O 都不会变成 X，像这种连通性问题可以使用并查集来进行解决。可以设立一个虚假的节点dummy，与所有边界上的 O 进行连接。在获取了所有的连通集合之后，我们可以把没有与dummy连通的节点改成X
// 并查集模版
class FindUnion{
public:
vector<int> parents;
FindUnion(int size){
parents = vector<int>(size);
//重要！所有人一开始与自己连通
for(int i = 0 ; i<size; ++i){
parents[i] = i;
}
}
int find(int x){
int t = x;
while(parents[x]!=x){
x = parents[x];
}
while(parents[t]!=x){
int tmp = parents[t];
parents[t] = x;
t = tmp;
}
return x;
}
void unionPoint(int x, int y){
int px = find(x);
int py = find(y);
parents[py] = px;
}
bool connected(int x, int y){
return find(x)==find(y);
}
};
class Solution {
public:
void solve(vector<vector<char>>& board) {
int m = board.size();
if(m ==0){
return;
}
int n = board[0].size();
FindUnion fu(m*n+1);
int dummy = m*n;
for(int i = 0; i < m; i++){
for(int j = 0; j<n; ++j){
if(board[i][j]=='O'){
if(i==0||i==m-1||j==0||j==n-1){ //如果是边界上的O，与dummy连通
fu.unionPoint(i*n+j, dummy);
} else {
if(i>0 && board[i-1][j]=='O'){
fu.unionPoint((i-1)*n+j,i*n+j);
}
if(i<m-1 && board[i+1][j] =='O'){
fu.unionPoint((i+1)*n+j, i*n+j);
}
if(j>0 && board[i][j-1] =='O'){
fu.unionPoint(i*n+j-1,i*n+j);
}
if(j<n-1 && board[i][j+1] == 'O'){
fu.unionPoint(i*n+j+1,i*n+j);
}
}
}
}
}
for(int i = 0; i<m;++i){
for(int j = 0; j<n; ++j){
if(!fu.connected(i*n+j,dummy)){
board[i][j] = 'X';
}
}
}
}
};
思路2:
从边界上的O开始，dfs标记所有可以到达的O，进行标记，所有未标记的O变成X，标记的O不变
class Solution {
public:
void markZero(vector<vector<char>>& board,int x,int y){
int m = board.size();
int n = board[0].size();
if(x<0||x>m-1 || y<0 || y>n-1){
return;
}
if(board[x][y]=='O'){
board[x][y] = '-';
markZero(board,x-1,y);
markZero(board,x+1,y);
markZero(board,x,y-1);
markZero(board,x,y+1);
}
}
void solve(vector<vector<char>>& board) {
int m = board.size();
if(m ==0){
return;
}
int n = board[0].size();
for(int i = 0; i < n; ++i){
markZero(board,0,i);
}
for(int i = 1; i < m; ++i){
markZero(board,i,0);
}
for(int i = 1; i < m; ++i){
markZero(board,i,n-1);
}
for(int i = 1; i< n-1;++i){
markZero(board,m-1,i);
}
for(int i = 0; i<m; ++i){
for(int j = 0; j<n; ++j){
if(board[i][j]=='-'){
board[i][j] = 'O';
}
else if(board[i][j] =='O'){
board[i][j] = 'X';
}
}
}
}
};
97. 大数乘法
class Solution {
public:
string multiply(string num1, string num2) {
if(num1=="0"||num2=="0"){
return "0";
}
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
string res(num1.size()+num2.size(),'0');
for(int i = 0;i < num1.size(); ++i){
int carry = 0;
for(int j = 0; j<num2.size(); ++j){
int tmp = (int)(num1[i]-'0') * (int)(num2[j]-'0') + carry + (int)(res[i+j]-'0');
res[i+j] = (char)(tmp%10 + '0');
carry = tmp/10;
}
if(carry){
res[i+num2.size()] = (char)carry+'0';
}
}
reverse(res.begin(), res.end());
int i = 0;
while(res[i]=='0'){
i++;
}
return res.substr(i, res.size()-i);
}
};
