力扣Hot100题单个人计划c++版（五）

力扣Hot100题单个人计划c++版（五）

力扣Hot100题单个人计划c++版（一）
力扣Hot100题单个人计划c++版（二）
力扣Hot100题单个人计划c++版（三）
力扣Hot100题单个人计划c++版（四）
力扣Hot100题单个人计划c++版（五）

---

刷题链接：力扣Hot 100
每日一题，每日一更，白板手写。

力扣Hot 100

• 81.打家劫舍 III
• 82.比特位计数
• 83.前 K 个高频元素
• 84.字符串解码
• 85.除法求值
• 86.根据身高重建队列
• 87.分割等和子集
• 88.路径总和 III
• 89.找到字符串中所有字母异位词
• 90.找到所有数组中消失的数字
• 91.汉明距离

---

81.打家劫舍 III

11.22打卡
树形dp，入门题就是没有上司的舞会，本题和入门题类似解法。即对于一个节点，要么选该节点要么不选，将两个状态都返回。

struct selectnode{
    int s0,s1;
};
class Solution {
public:
    selectnode dfs(TreeNode* p){
        if(p==nullptr)return {0,0};
        auto l=dfs(p->left);
        auto r=dfs(p->right);
        int s0=max(l.s0,l.s1)+max(r.s0,r.s1);
        int s1=p->val+l.s0+r.s0;
        return {s0,s1};
    }
    int rob(TreeNode* root) {
        selectnode r=dfs(root);
        return max(r.s0,r.s1);
    }
};

82.比特位计数

11.24打卡
感觉是找规律题，每次过2的n次方就是一个循环。类似数电的8421码。因为每过2的n次方最高位变成了1，0-1的个数是0,1，那么2-3就是再0-1基础加一，4-7就是在0-3基础上加一。这样循环每个周期就可以了。对应题解即方法二，看不懂正常，毕竟官方一直不说人话的，把简单理解术语化。看懂官方题解只需要了解原码二进制表示即可，尽管计算机以补码形式保存和处理数据，但正数的补码和原码是相同的，只需要明白 i & ( i − 1 ) i&(i-1) i&(i−1)其实是数字i二进制中最后一个1改为0的数。

class Solution {
public:
    vector countBits(int n) {
        if(n==0)return {0};
        vector nums(n+1);
        nums[0]=0;nums[1]=1;
        int round=1;
        for(int i=2;i<=n;++i){
           if(i==2*round)round=round<<1;//此处官方写法：if(i&(i-1)==0)round=i;
           								//实际二者相同，i&(i-1)其实是i二进制中最后一个1改为0的数
           nums[i]=1+nums[i-round];
        }
        return nums;
    }
};

还有从位进制的规律dp的解法，偶数的最后一位必然是0，所以偶数1的个数和它除二后的数一样，奇数最后一位是1，所以1的个数是它除二后的数字个数加1。

class Solution {
public:
    vector countBits(int n) {
        vector nums(n+1);
        nums[0]=0;
        for(int i=1;i<=n;++i){
            if(i%2)nums[i]=nums[i>>1]+1;//表示i除2的余数也可以用位运算i&1
            else nums[i]=nums[i>>1];
        }
        return nums;
    }
};

还有一个巧妙解法，对于每个正数，它1的个数等于它的最低位1变成0的数字1的个数加1。

class Solution {
public:
    vector countBits(int n) {
        vector nums(n+1);
        nums[0]=0;
        for(int i=1;i<=n;++i){
            nums[i]=nums[i&(i-1)]+1;
            //cout< 
83.前 K 个高频元素 
11.25打卡
 和63.数组中的第K个最大元素几乎一模一样，区别只在于判断优先度的问题，即把大于号的比较方式改为判断数量大小的大小。这里就不再写了。
 
84.字符串解码 
11.25打卡
 华为一面时被问到该题的变形。当时也是递归写的，但是有些小问题导致递归的数字没执行，时间有限便大致说了思路就草草结束，面试管交流说也可以用栈实现。题目要求很清晰，难点就是得注意递归的一些细节。
 今天重写本题终于知道当时失败的原因，如果用递归的话，只需要判断当前字符是不是数字或者字母就可以了，如果是字母将下一个字符交给下一个递归执行，不要再判断下一个字母是不是’]’，或者是不是数字，这样递归就复杂化了。需要时刻明白定义的递归返回的是当前字符之后已经解码好的字符串，只需要和当前解码好的字符拼接即可。
 
class Solution {
public:
    int cur;
    int getdigit(const string s){
        int num=0;
        while(isdigit(s[cur])){
            num*=10;
            num+=s[cur++]-'0';
        }
        return num;
    }
    string dfs(const string s,const int n){
        if(cur==n||s[cur]==']')return "";
        string ret="";
        if(isdigit(s[cur])){
            int repnum=getdigit(s);
            char c=s[cur];
            ++cur;//跳过左括号
            string tmp=dfs(s,n);
            ++cur;//跳过右括号
            while(repnum--)ret+=tmp;
        }else if(isalpha(s[cur])){
            ret+=s[cur++];
        }
        return ret+dfs(s,n);
    }
    string decodeString(string s) {
        int n=s.size();
        cur=0;
        return dfs(s,n);
    }
};
 
85.除法求值 
11.26打卡
 毫无思路，没想到题解竟是转换为图论构建有向图，妙不可言。查并集算法，包含路径压缩。待补。
 
86.根据身高重建队列 
11.27打卡
 模拟题，身高排序后插入即可。
 
class Solution {
public:
    vector> reconstructQueue(vector>& people) {
        sort(people.begin(),people.end(),[](const vector& a,const vector& b){
            return a[0]>b[0]||(a[0]==b[0]&&a[1]> ans;
        for(vector& p:people){
            ans.insert(ans.begin()+p[1],p);
        }
        return ans;
    }
};
 
87.分割等和子集 
11.28打卡
 一开始想到深搜，存中间能加到的值，记忆化搜索其实就是dp。也就是每次新加入的数，尝试更新加上每个数可以到达的数，最后看一半那个数能不能加到。
 有几个小tricks，比如总和为奇数一定不满足，最大的数超过总和的一半一定不满足。
 
class Solution {
public:
    bool canPartition(vector& nums) {
        int sum=0;
        int len=0;
        int maxnum=-1;
        for(const int& t:nums){
            sum+=t;++len;
            if(t>maxnum)maxnum=t;
        }
        if(sum&1)return false;
        int target=sum>>1;
        if(target=nums[i];--j){
                dp[j]=(dp[j]||dp[j-nums[i]]);
            }
        }
        return dp[target];
    }
};
 
88.路径总和 III 
11.29打卡
 以为题解会用树状数组或者线段树记录节点和。谁知道前序遍历加前缀和这个思路真的太巧妙了。本题中的路径是一棵树，从根往任一节点的路径上(不走回头路)，有且仅有一条路径，因为不存在环，所以我们可以用哈希表记录前序遍历的前缀和，即用哈希表保存从根节点到该节点的一整条路径的所有值的个数，然后查找在前缀和上，有没有前缀和currSum-target的节点，哈希表存的就是满足的节点数量。然后继续遍历左右节点，当回溯时把该节点的路径值从哈希表去掉即可。mark一下反复看。
 
class Solution {
public:
    unordered_map hp;
    int dfs(TreeNode* pos,int cur,const int target){
        if(!pos)return 0;
        int ans=0;
        cur+=pos->val;
        if(hp.count(cur-target))ans+=hp[cur-target];
        hp[cur]++;
        ans+=dfs(pos->left,cur,target);
        ans+=dfs(pos->right,cur,target);
        hp[cur]--;
        return ans;
    }
    int pathSum(TreeNode* root, int targetSum) {
        hp[0]=1;
        return dfs(root,0,targetSum);
    }
};
 
89.找到字符串中所有字母异位词 
12.1打卡
 经典滑动窗口题。每次移动一格修改窗口内各个字符个数。记录每个窗口内的字符个数和目标字符串个数比较，相同就记录起点。当然也可以优化一下，以下为优化后的代码。即用一个变量dif记录窗口内字符个数不相同的个数，只有dif为0时记录起点。
 
class Solution {
public:
    vector findAnagrams(string s, string p) {
        int sl=s.size();
        int pl=p.size();
        if(sl();
        vector ans;
        vector cnt(26,0);
        for(int i=0;i 
90.找到所有数组中消失的数字 
12.1打卡
 力扣的简单题果然套路。思路属于没有见过基本想不到的题解。类似剑指offer里的剑指offer(1) 找出数组中重复的数字。最直接的思路就是，哈希表或者说桶排序来记录每个数的个数，如果某个数的个数为0就返回它。但题意要求空间复杂度O(1)，本题恰好数组大小为n，而且数组元素不超过n，所以可以原地记录，给对应位置元素+n，这样最终找到那些小于n的就可以得到没有出现过的数。
 
class Solution {
public:
    vector findDisappearedNumbers(vector& nums) {
        int n=nums.size();
        for(int i=0;i ans;
        for(int i=0;i 
91.汉明距离 
12.2打卡
 关于求最低位1的小技巧，前面已经提到过x&(x-1)即去掉最低位1的数。本题技巧也很强，记住即可。
 
class Solution {
public:
    int hammingDistance(int x, int y) {
        int t=x^y;
        int ans=0;
        while(t){
            t=t&(t-1);++ans;
        }
        return ans;
    }
};
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5634592.html