头像

SHIJIA


访客:3515

离线:11小时前



SHIJIA
4小时前
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *dummy=new ListNode(-1);
        dummy->next=head;
        for(auto p=dummy;p;p=p->next){
            auto q=p->next;
            while(q && q->val==val)
                q=q->next;
            p->next=q;
        }

        return dummy->next;
    }
};


活动打卡代码 LeetCode 202. 快乐数

SHIJIA
4小时前

快慢指针

  • 最后肯定会进入一个循环
  • 如果最后进入一个没有快乐数的循环,则环的入口一定不是1
  • 如果最后进入快乐数1的自循环,则环的入口一定为1
  • 用快慢指针找环的入口
class Solution {
public:
    int get(int x){     //获取x每一位的平方和
        int res=0;
        while(x){
            res+=(x%10)*(x%10);
            x/=10;
        }
        return res;
    }

    bool isHappy(int n) {
        int slow=n,fast=n;
        do{                             //快慢指针找环入口
            slow=get(slow);
            fast=get(get(fast));
        }while(slow!=fast);

        return slow==1;                 
    }
};



SHIJIA
5小时前

$O(logn)$

  • 找到m和n从高位到低位中第一次出现不一样的位置,答案为该位置之前的二进制的累计和
  • 因为,当从高位往低位遍历到第一次出现不一样的位时,从m上升到n的过程中,必然会经历xxx0111…和xxx1000两个数,这两个数使得第一个不同位之后的所有位与起来结果为0。
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int res=0;
        for(int i=30;i>=0;--i){
            if((m>>i&1)!=(n>>i&1)) break;
            if(m>>i&1)
                res+=1<<i;
        }
        return res;
    }
};
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int offset=0;
        for(;m!=n;++offset){
            m>>=1;
            n>>=1;
        }
        return n<<offset;
    }
};



活动打卡代码 AcWing 200. 岛屿数量

SHIJIA
1天前

DFS

class Solution {
public:
//DFS
    int numIslands(vector<vector<char>>& grid) {
        int n=grid.size();
        if(n==0) return 0;          //特判
        int m=grid[0].size();

        int cnt=0;
        for(int i=0;i<n;++i)
            for(int j=0;j<m;++j)
                if(grid[i][j]=='1')
                {
                    dfs(grid,i,j);
                    cnt++;          //每次DFS表明出现一个岛屿
                } 
        return cnt;
    }

private:
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    void dfs(vector<vector<char>> &grid,int x,int y)
    {
        grid[x][y]='0';             //访问过的节点置为0,防止重复遍历

        int n=grid.size();
        int m=grid[0].size();
        for(int i=0;i<4;++i)
        {
            int a=x+dx[i],b=y+dy[i];
            if(a>=0 && a<n && b>=0 && b<m && grid[a][b]=='1')
                dfs(grid,a,b);
        }
    }
};

BFS

class Solution {
public:

    int numIslands(vector<vector<char>>& grid) {
        int n=grid.size();
        if(n==0) return 0;          //特判
        int m=grid[0].size();

        int cnt=0;
        for(int i=0;i<n;++i)
            for(int j=0;j<m;++j)
                if(grid[i][j]=='1')
                {
                    cnt++;
                    grid[i][j]='0';                 //先标记访问过,再入队
                    queue<pair<int,int>> Q;
                    Q.push({i,j});
                    while(!Q.empty())
                    {
                        auto [x,y]=Q.front();
                        Q.pop();
                        for(int i=0;i<4;++i)
                        {
                            int a=x+dx[i],b=y+dy[i];
                            if(a>=0 && a<n && b>=0 && b<m && grid[a][b]=='1')
                            {
                                grid[a][b]='0';
                                Q.push({a,b});
                            }

                        }
                    }
                }
        return cnt;
    }

};



SHIJIA
1天前

层序遍历

  • 只存每层的最右节点值
class Solution {
public:
//层序遍历
    vector<int> rightSideView(TreeNode* root) {
        if(!root) return {};

        vector<int> res;
        queue<TreeNode*> Q;
        Q.push(root);
        while(!Q.empty())
        {
            res.push_back(Q.back()->val);              //每次只存最右边节点的值
            int size=Q.size();
            while(size--)
            {
                auto p=Q.front();
                Q.pop();
                if(p->left) Q.push(p->left);
                if(p->right) Q.push(p->right);
            }
        }
        return res;
    }
};


活动打卡代码 LeetCode 198. 打家劫舍

SHIJIA
1天前
class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n==0) return 0;
        if(n==1) return nums[0];
        vector<int> dp(n);
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);
        for(int i=2;i<n;++i){
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);     //第i家店铺有偷与不偷两种选择
        }
        return dp[n-1];
        /*              状态机做法
        int f[n][2];
        f[0][0]=0;
        f[0][1]=nums[0];

        for(int i=1;i<n;++i)
        {
            f[i][0]=max(f[i-1][0],f[i-1][1]);
            f[i][1]=f[i-1][0]+nums[i];
        }

        return max(f[n-1][0],f[n-1][1]);
        */
    }
};


活动打卡代码 LeetCode 191. 位1的个数

SHIJIA
1天前
class Solution {
public:
//O(1)
    int hammingWeight(uint32_t n) {
        int cnt=0;
        while(n){
            if(n&1)
                cnt++;
            n>>=1;
        }
        return cnt;
    }
};



SHIJIA
1天前

位运算

  • 从小到大取出n的二进制每一位,逆序累加到一个无符号数中
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res=0;
        for(int i=0;i<32;++i){
            res=(res<<1)+(n>>i&1);
        }
        return res;
    }
};


活动打卡代码 LeetCode 189. 旋转数组

SHIJIA
1天前
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k=k%nums.size();
        reverse(nums.begin(),nums.end());
        reverse(nums.begin(),nums.begin()+k);
        reverse(nums.begin()+k,nums.end());
    }
};



SHIJIA
1天前

DP

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n=prices.size();
        if(n<2 || k==0) return 0;
        vector<int> w{0};
        for(auto x:prices) w.push_back(x);

        if(k>=n/2){                      //k超过n/2,相当于可以进行为无限次交易,变成股票问题2,用贪心
            int res=0;
            for(int i=2;i<=n;++i){
                if(w[i]>w[i-1])
                    res+=w[i]-w[i-1];
            }
            return res;
        }

        int f[n+1][k+1][2];     //f[i][k][0]表示第i天不持股,且已完成k次交易时的最大利润
        memset(f,-0x3f,sizeof f);
        for(int i=0;i<=n;++i)   //初始化合法状态
            f[i][0][0]=0;

        int K=k;
        for(int i=1;i<=n;++i){
            for(int k=1;k<=K;++k){
                f[i][k][0]=max(f[i-1][k][0],f[i-1][k][1]+w[i]);
                f[i][k][1]=max(f[i-1][k][1],f[i-1][k-1][0]-w[i]);
            }
        }

        int res=0;
        for(int j=0;j<=k;++j)           //看第n天不持股,且完成了几次交易时利润最大
            res=max(res,f[n][j][0]);
        return res;
    }
};