最大的收获，不在于怎么做这道题，而在于面对一个递归的题目时，最高效的思维框架是什么。
递推参数、终止条件、递推任务，脑子里要有这个框架
lc3226
抽象思考，统计1的个数差异就好了，无需关心前导0
class Solution {
public:
int cntBits(int x){
int cnt = 0;
while(x){
if(x & 1)cnt++;
x = x >> 1;
}
return cnt;
}
int minChanges(int n, int k)
{
if((n & k) != k)
return -1;
return cntBits(n) - cntBits(n & k);
}
};
lc896
是升序还是降序
class Solution {
public:
bool isMonotonic(vector<int>& nums) {
set<bool>st;
for(int i = 1; i < nums.size(); i++)
{
//如果是元素相同，那么既可以看成是升序也可以看成是降序，因此特殊情况跳过
if(nums[i] == nums[i - 1])
{
continue;
}
//升序加入true；否则加入false
if(nums[i] - nums[i - 1] > 0)
st.insert(true);
else
{
st.insert(false);
}
}
return st.size() == 1 || st.size() == 0 ? true : false;
}
};
lc2042.
cpp string stream + try catch
class Solution {
public:
bool areNumbersAscending(string s) {
const int n = s.length();
istringstream ss(s);
string w;
int curr = 0;
while(ss >> w){
try{
int a = stoi(w);
if(a > curr){
curr = a;
}else return false;
}catch(...){}
}
return true;
}
};
lc437
path+presum+hash
class Solution
{
private:
unordered_map<long long, int> preSumCount;
int dfs(TreeNode* node, int targetSum, long long preSum)
{
if (!node) return 0;
preSum += node->val;
int pathCnt = preSumCount[preSum - targetSum];
preSumCount[preSum] += 1;
pathCnt += dfs(node->left, targetSum, preSum) + dfs(node->right, targetSum, preSum);
preSumCount[preSum] -= 1;
return pathCnt;
}
public:
int pathSum(TreeNode* root, int targetSum)
{
preSumCount[0] = 1;
return dfs(root, targetSum, 0);
}
};
lc105
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
this->preorder = preorder;
for(int i = 0; i < inorder.size(); i++)
dic[inorder[i]] = i;
return recur(0, 0, inorder.size() - 1);
}
private:
vector<int> preorder;
unordered_map<int, int> dic;
TreeNode* recur(int root, int left, int right)
{
if (left > right) return nullptr; // 递归终止
TreeNode* node = new TreeNode(preorder[root]); // 建立根节点
int i = dic[preorder[root]]; // 划分根节点、左子树、右子树
node->left = recur(root + 1, left, i - 1); // 开启左子树递归
node->right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
return node;
}
};
i - left + root + 1
首先对于左子树的变量的左右边界很好理解，
中序遍历左边界为left,另一边是i-1
所以我们可以计算得到左子树的长度为
(i-1) –left+1=i-left
回到前序遍历给出的数组中，从根节点跳过左
子树的长度，就可以找到右子树的根节点：即
为root+(i-left)+1=i - left + root + 1