枚举
答案肯定是字符串的某个前缀，然后简单直观的想法是枚举所有前缀来判断，设前缀长度lenz，前缀串的长度必然要是两个字符串长度的约数才能满足条件。
可以枚举长度，再去判断这个前缀串拼接若干次以后是否等于str1和str2。
class Solution {
bool check(string str, string s){
int len = s.length()/str.length();
string ans;
for(int i=0; i<len; i++){
ans += str;
}
return ans == s;
}
public:
string gcdOfStrings(string str1, string str2) {
int len1 = str1.length();
int len2 = str2.length();
for(int i=min(len1,len2); i>=1; i--){
if(len1%i ==0 && len2%i==0){
string str = str1.substr(0,i);
if(check(str, str1) && check(str, str2)){
return str;
}
}
}
return "";
}
};
拥有最多糖果的孩子
给一个数组candies和一个整数extraCandies。
class Solution {
public:
vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
int n = candies.size();
vector<bool> res(n,false);
int max_candy = *max_element(candies.begin(), candies.end());
for(int i=0; i<n; i++){
res[i] = ((candies[i] + extraCandies) >= max_candy);
}
return res;
}
};
除自身以外数组的乘积
不能使用除法，并且需要在O(n)时间复杂度内完成此题。
左右乘积列表
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> leftSum(n,1);
vector<int> rightSum(n,1);
vector<int> res(n,1);
for(int i=1; i<n; i++){
leftSum[i] = nums[i-1]*leftSum[i-1];
}
for(int i=n-2; i>=0; i--){
rightSum[i] = nums[i+1] * rightSum[i+1];
}
for(int i=0; i<n; i++){
res[i] = leftSum[i] * rightSum[i];
}
return res;
}
};
递增的三元子序列
如果在i>=1且i<n-1的范围内，左边存在一个元素小于nums[i]，右边存在一个元素大于nums[i]，则nums中存在递增的三元子序列。
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int n = nums.size();
if(n < 3){
return false;
}
vector<int> minLeft(n);
vector<int> maxRight(n);
minLeft[0] = nums[0];
maxRight[n-1] = nums[n-1];
for(int i=1; i<n-2; i++){
minLeft[i] = min(minLeft[i-1], nums[i]);
}
for(int i=n-2; i>=2; i--){
maxRight[i] = max(maxRight[i+1],nums[i]);
}
for(int i=1; i<n-1; i++){
if(minLeft[i-1] < nums[i] && nums[i] < maxRight[i+1]){
return true;
}
}
return false;
}
};
压缩字符串
压缩字符串
为了实现原地压缩，我们可以使用双指针分别标志我们在字符串中读和写的位置。
当读指针read位于字符串的末尾，或者读指针下一个字符不相同，就认为读指针位于相同字符串的最右侧。用变量left记录左侧的位置，这样长度为right-left+1。
class Solution {
public:
int compress(vector<char>& chars) {
int n = chars.size();
int write = 0;
int left = 0;
int read = 0;
for(; read < n; read++){
if(read == n-1 || chars[read] != chars[read+1]){
chars[write++] = chars[read];
int count = read-left+1;
if(count > 1){
int anchor = write;
while(count){
chars[write++] = count%10 + '0';
count /= 10;
}
reverse(&chars[anchor], &chars[write]);
}
left = read+1;
}
}
return write;
}
};
移动零
原地移动数组，且保持相对顺序不变。
双指针
左指针表示当前已经处理好的序列的尾部，右指针指向待处理序列的头部。
右指针不断向右移动，每次右指针指向非零数，就交换左右指针，左指针向右移动。
左指针左边均是非零数，
右指针左边直到左指针均为零。
每日温度
暴力
对于每个元素tempaerature[i]，需要找到最小的下标j，使得对应值大于它。
温度在[30,100]范围内，可以维护一个数组next记录每个温度第一次出现的下标。
便利温度列表的过程中更新next的值。
电话号码的字母组合
class Solution {
void backtrace(vector<string>& combinations, const unordered_map<char,string>&phoneMap, const string digits, int index, string& combination){
if(index == digits.size()){
combinations.push_back(combination);
}else{
char digit = digits[index];
const string& letters = phoneMap.at(digit);
for(int i=0; i<letters.size(); i++){
combination.push_back(letters[i]);
backtrace(combinations, phoneMap, digits, index+1, combination);
combination.pop_back();
}
}
}
public:
vector<string> letterCombinations(string digits) {
vector<string> combinations;
if(digits.empty()){
return combinations;
}
unordered_map<char, string> phoneMap = {
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
string combination;
backtrace(combinations, phoneMap, digits, 0, combination);
return combinations;
}
};
删除二叉搜索树中的节点
需要保证二叉搜索树的性质不变。
二叉搜索树有以下性质：
- 左子树的所有结点（如果有）的值均小于当前节点的值；
- 右子树的所有节点（如果有）的值均大于当前节点的值；
- 左子树和右子树均为二叉搜索树。
TreeNode *successor = root->right;
while(successor->left){
successor = successor->left;
}
root->right = deleteNode(root->right, successor->val);
successor->left = root->left;
sucessor->right = root->right;
二叉树的最大深度
二叉树的最大深度从根节点到最远叶子结点的最长路径上的节点数。
