找树左下角的值
分析：
??层序遍历：如果队列为空说明进行到了最后一层，返回第一个元素即可。
代码：
/**
* 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:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> que;
que.push(root);
while(!que.empty()) {
int n = que.size();
vector<int> temp;
for(int i = 0; i < n; i++) {
TreeNode* fr = que.front();
temp.push_back(fr->val);
que.pop();
if(fr->left) {
que.push(fr->left);
}
if(fr->right) {
que.push(fr->right);
}
}
if(que.empty()) { //最后一层
return temp[0];
}
}
return 0;
}
};
长度最小的子数组
方法一：
??暴力枚举：从0开始枚举左边界，然后逐个累加判断。
代码：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
if(n == 0) {
return 0;
}
int res = INT_MAX;
for(int i = 0; i < n; i++) {
int sum = 0;
for(int j = i; j < n; j++) {
sum += nums[j];
if(sum >= target) {
res = min(res, j - i + 1);
break;
}
}
}
return res == INT_MAX ? 0 : res;
}
};
方法二：
??滑动窗口：初始left和right都指向0处，然后移动right，移动过程中求和，如果当前[left, right]区间和满足要求，则更新区间长度。随后left右移，移动过程中可能还是满足条件，也需要更新结果。当移动到当前区间不满足条件时left停止移动，right开始继续移动。
代码：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
if(n == 0) {
return 0;
}
int res = INT_MAX;
int left = 0, right = 0;
int sum = 0;
while(right < n) {
while(right < n && sum < target) {
sum += nums[right];
right++;
}
right--;
if(sum >= target) {
while(sum >= target) {
res = min(res, right - left + 1);
sum -= nums[left];
left++;
}
}else {
break;
}
right++;
}
return res == INT_MAX ? 0 : res;
}
};
组合总和 III
分析：
??回溯。
代码：
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(int targetSum, int k, int sum, int startIndex) {
if (path.size() == k) {
if (sum == targetSum) {
result.push_back(path);
return;
}
}
for (int i = startIndex; i <= 9; i++) {
sum += i;
path.push_back(i);
backtracking(targetSum, k, sum, i + 1);
sum -= i; // 回溯
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum3(int k, int n) {
backtracking(n, k, 0, 1);
return result;
}
};
只出现一次的数字 III
方法一：
??哈希表。
代码：
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
unordered_map<int, int> mp;
vector<int> res;
for(int x : nums) {
mp[x]++;
}
for(auto& [x, y] : mp) {
if(y == 1) {
res.push_back(x);
}
}
return res;
}
};
位运算：
??设结果为a b，由于两个相同数异或为0，而任何数异或0为本身，所以我们将数组中所有数进行异或操作，最终结果就为a ^ b，记为ret。我们可以将所有数分成两组，所有相同的数在一组，ab在不同的一组，最终分组结果类似于：{1 1 2 2 3 3 a}和{4 4 7 7 8 8 b}，这样两组异或的结果就分别为a和b。为此，我们可以以ret中某一个不为0的位x(记为00010000)与各个数进行与运算，为0分在一组为1分在另一组：两个相同的数与上0001000，其结果肯定一致所以被分在同一组，对于a b，由于位x处有ai ^ bi == 1，说明ai和bi必然一个为1一个为0，所以a b可以被分在不同组。
代码：
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int a = 0, b = 0;
int ret = 0;
for(int x : nums) {
ret ^= x; //求出所有数的异或，ret = a ^ b
}
int div = 1;
while((div & ret) == 0) {
div <<= 1; //找到ret从低位到高位的第一个1
}
for(int x : nums) {
if(x & div) {
a ^= x; //分组，每一组的异或即为答案
}else {
b ^= x;
}
}
return {a, b};
}
};
丑数
分析：
??将数不断除以2 3 5，如果最后为1说明就是丑数，否则不是。
代码：
class Solution {
public:
bool isUgly(int n) {
if(n == 1) {
return true;
}
if(n <= 0) {
return false;
}
int factors[3] = {2, 3, 5};
for(int x : factors) {
while(n % x == 0) {
n /= x;
}
}
return n == 1;
}
};
丑数 II
分析：
??思路类似于：蓝桥杯第九届【省赛C/C++ A组】T4：第几个幸运数
代码：
class Solution {
public:
int nthUglyNumber(int n) {
int factors[3] = {2, 3, 5};
priority_queue<long long, vector<long long>, greater<long long>> que;
set<long long> s;
que.push(1);
s.insert(1);
int cnt = 0, res = 0;
while(true) {
long long x = que.top(); //取队头
que.pop();
cnt++;
if(cnt == n) {
res = x;
break;
}
for(int y : factors) {
long long m = x * y;
if(s.count(m) == 0) {
s.insert(m);
que.push(m);
}
}
}
return res;
}
};