万人千题计划
前言
前面的是今天英雄哥给的题解，后面的二叉树是自己的内容，你们按自己的需求来看就行
推荐社区：万人千题
今日题解
统计位数为偶数的数字
思路：
依据除10法可以得到数字相应的位数（代码中的while方块）
每个数字遍历之前需要初始化count
是否为偶数：%2是否为0，为0：偶数；不为0：奇数
class Solution {
public:
int findNumbers(vector<int>& nums) {
int count, res = 0;
for(int i =0; i<nums.size(); ++i) {
count = 0;
while(nums[i]!=0) {
++count;
nums[i] /= 10;
}
if(count % 2 == 0) {
++res;
}
}
return res;
}
};
有序数组中的单一元素
思路：二分查找，对所有偶数索引进行搜索，直到遇到第一个其后元素不相同的索引
如果是无序的话，其实可以用位运算来解决，算是最优解，懒得贴代码了，之前的题解有
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int left = 0, right = nums.size()-1;
while(left < right) {
int mid = left + (right-left)/2;
if(mid %2 == 1) {
--mid;
}
if(nums[mid] == nums[mid + 1]) {
left = mid + 2;
}else right = mid;
}
return nums[left];
}
};
调整数组顺序使奇数位于偶数前面
思路：代码注释里
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
// 一个数不能既为奇数又为偶数，所以推出循环的终止条件是 left == right
// 排好序的数组，left 指针前都是奇数，right 指针后都是偶数
while(left < right) {
// left 找偶数
while(left < right && nums[left] % 2 != 0) {
++left;
}
// right 找奇数
while(left < right && nums[right] % 2 == 0) {
--right;
}
// 将 left 左边的偶数 和 right 右边的奇数 互换
if(left < right) {
swap(nums[left], nums[right]);
}
}
// left 和 right 重合时，数组排序完成
return nums;
}
};
有效的字母异位词
思路：新开一个26大小的数组，用来存储字母的种类
for循环遍历两个字符串，看它们的字母出现的次数是否相等
class Solution {
public:
bool isAnagram(string s, string t) {
int record[26] = {0};
for(int i=0; i<s.size(); i++) {
record[s[i] - 'a']++;
}
for(int i=0; i<t.size(); i++) {
record[t[i] - 'a']--;
}
for(int i=0; i<26; i++) {
if(record[i] != 0) {
return false;
}
}
return true;
}
};
思路：本题要求我们的是返回数组排序之后的倒数第 k个位置
1、使用堆或者优先队列 priority_queue
2、维护一个 k 大小的小顶堆，堆顶就是第 k 个最大的数
3、当堆的大小已经是 k 个的时候，需要直接与堆顶判断决定是否加入堆中
目前我不会手写实现堆或者优先队列
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> pq;
for (auto n : nums) {
if (pq.size() == k && pq.top() >= n) continue;
if (pq.size() == k) {
pq.pop();
}
pq.push(n);
}
return pq.top();
}
};
丢失的数字
思路：用哈希集合，将nums[i] 中的数据插入set集合里，看0~n的数字是否在set集合中出现过，没出现过则它就是丢失的数字
class Solution {
public:
int missingNumber(vector<int>& nums) {
unordered_set<int> Set;
int n = nums.size();
for(int i=0; i<n; i++) {
Set.insert(nums[i]);
}
int missing = -1;
for(int i=0; i<=n; i++) {
if(Set.count(i) == 0) {
missing = i;
break;
}
}
return missing;
}
};
找不同
思路：字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
class Solution {
public:
char findTheDifference(string s, string t) {
int res = 0;
for(auto &i : t) {
res += i;
for(auto &i : s) {
res -= i;
}
return res;
}
};
平衡二叉树
思路：使用栈和迭代法
class Solution {
public:
int getDepth(TreeNode* cur) {
stack<TreeNode*> sk;
if(cur != nullptr) sk.push(cur);
int res = 0;
int depth = 0;
while(!sk.empty()) {
TreeNode* node = sk.top();
if(node != nullptr) {
//sk.top();
sk.pop();
sk.push(node);
sk.push(nullptr);
++depth;
if(node->left) sk.push(node->left);
if(node->right) sk.push(node->right);
}else {
sk.pop();
node = sk.top();
sk.pop();
--depth;
}
res = res > depth ? res : depth;
}
return res;
}
bool isBalanced(TreeNode* root) {
stack<TreeNode*> sk;
if(root == nullptr) return true;
sk.push(root);
while(!sk.empty()) {
TreeNode* node = sk.top();
sk.pop();
if(abs(getDepth(node->left) - getDepth(node->right)) > 1) {
return false;
}
if(node->left) sk.push(node->left);
if(node->right) sk.push(node->right);
}
return true;
}
};
二叉树的所有路径
class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
stack<TreeNode*> treeSk;
stack<string> pathSk;
vector<string> res;
if(root == nullptr) return res;
treeSk.push(root);
pathSk.push(to_string(root->val));
while(!treeSk.empty()) {
TreeNode* node = treeSk.top();
treeSk.pop();
string path = pathSk.top();
pathSk.pop();
if(node->left == nullptr && node->right == nullptr) {
res.push_back(path);
}
if(node->left) {
treeSk.push(node->left);
pathSk.push(path + "->" + to_string(node->left->val));
}
if(node->right) {
treeSk.push(node->right);
pathSk.push(path + "->" + to_string(node->right->val));
}
}
return res;
}
};
左叶子之和
思路：递归和迭代法都能做，但主要的是读懂题目
这题的意思是：如果左节点不为空，且左节点没有左右孩子，那么这个节点就是左叶子，而判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
stack<TreeNode*> sk;
if(root == nullptr) return 0;
sk.push(root);
int res = 0;
while(!sk.empty()) {
TreeNode* node = sk.top();
sk.pop();
if(node->left != nullptr && node->left->left == nullptr && node->left->right == nullptr) {
res += node->left->val;
}
if(node->left) sk.push(node->left);
if(node->right) sk.push(node->right);
}
return res;
}
};
找树左下角的值
思路：用层序遍历，找出最后一行首个叶子节点的值
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> que;
if(root == nullptr) return 0;
que.push(root);
int res = 0;
while(!que.empty()) {
int size = que.size();
for(int i=0; i<size; ++i) {
TreeNode* node = que.front();
que.pop();
if(i == 0) res = node->val;
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
}
return res;
}
};
路径总和
思路：都在注释里
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
//用pair结构来存储节点指针和路径总和
stack<pair<TreeNode*, int>> sk;
if(root == nullptr) return false;
sk.push(pair<TreeNode*, int> (root, root->val));
while(!sk.empty()) {
pair<TreeNode*, int> node = sk.top();
sk.pop();
//如果找到叶子节点，且路径总和与目标总和相等
//if(pair<TreeNode*, int> (node, node->val))
if(!node.first->left && !node.first->right && node.second == targetSum) {
return true;
}
//压入左节点，记录路径和
if(node.first->left) {
sk.push(pair<TreeNode*, int> (node.first->left, node.second + node.first->left->val));
}
//压入右节点，记录路径和
if(node.first->right) {
sk.push(pair<TreeNode*, int> (node.first->right, node.second + node.first->right->val));
}
}
return false;
}
};