力扣练习题笔记

788. 旋转数字

788. 旋转数字 - 力扣（LeetCode）

代码

class Solution {
public:
    int rotatedDigits(int n) {
        //数中没有3，4，7
        //数中至少出现一次2或5，6或9
        //对于0，1，8无要求
        int ans = 0;
        for(int i = 1; i <= n; i ++) {
            int j = i;
            int flag = 0;
            while(j) {
                int num = j%10;
                if(num==3||num==4||num==7) {flag = 0; break;}
                if(num==2||num==5||num==6||num==9) 
                    flag = 1;
                j /= 10;
            }
            if(flag) ans ++;
        }
        return ans;
    }
};

1185. 一周中的第几天

1185. 一周中的第几天 - 力扣（LeetCode）

代码

class Solution {
public:
    string dayOfTheWeek(int day, int month, int year) {
        //1969.12.31 是星期四,只要看距离这天几天，闰年多一天

        vector<string> week = {"Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"};
        vector<int> monthDays = {31,28,31,30,31,30,31,31,30,31,30}; //最后一个月不用
        // 1073 - 1069 刚好四年，因为1972年闰年多一天
        // 从1971年开始 year-1971  year - 1969因为，1972闰年，1973-1969 = 4
        //年的贡献
        int days = 365*(year - 1971) + (year - 1969)/4;
        //月的贡献
        for(int i = 0; i < month-1; i ++) {
            days += monthDays[i];
        }
        //闰年同时月份>=3
        if((year%400==0 || (year%4==0&&year%100!=0)) && month>=3) {
            days += 1;
        }
        // 天数贡献
        days += day;
        //假设1969，12，13是周一，直接%7 = 0， 右移3到周四
        return week[(days+3)%7];
    }
};

1513. 仅含 1 的子串数

1513. 仅含 1 的子串数 - 力扣（LeetCode）

代码

考虑特殊情况，假设 111 （3个全是1）

那么子集 1 1 1 11 11 111 （3 + 2 + 1，等差数列求和 k*(k+1)/2 )

所以每一段都是这个公式。

class Solution {
public:
    const int P = 1e9 + 7;

    int numSub(string s) {
        //字串连续选取
        int p = 0;
        long long ans = 0;

        while(p < s.size()) {
            if(s[p]=='0') {
                ++p; 
                continue;
            }

            int cnt = 0;
            while(p < s.size() && s[p] == '1') {
                ++ cnt;
                ++ p;
            }
            
            ans = ans + (1 + (long long)cnt)*cnt/2;
            ans = ans%P;
        }
        return ans;
    }
};

代码2 超时

会超时

代码3 超时

精妙之处在于l = r的更新。

遍历寻找每一段连续子集

然后两个for 求个数= 执行次数

int numSub(string ss) {
        int n = ss.size();
        int l = 0,ans=0;
        while (l<n){
            if (ss[l]=='0'){
                l++;
                continue;
            }
            int r=l;
            while (r<n && ss[r]=='1'){
                r++;
            }
            //[l,r]是ss全1的子区间
            for (int s=l;s<r;s++){ // 子区间的连续子集的的左端点
                for (int e=s;e<r;e++){// 子区间的连续子集的的右端点
                    ans++;
                    cout<<ss.substr(s,e-s+1)<<endl;
                }
            }
            l = r;
        }
        return ans;
    }

2126. 摧毁小行星

代码

long long 防爆数据

class Solution {
public:
    bool asteroidsDestroyed(int mass, vector<int>& asteroids) {
        // 每次跟最小的行星碰撞就能让自己不断吃的更大
        sort(asteroids.begin(),asteroids.end());
        long long sum = mass; // 防爆数据
        for(auto x : asteroids) {
            if(sum < x) return false;
            sum += x;
        }
        return true;
    }
};

代码2

只要比所有都大就可以结束了（大于最大）

因为最大也才1e5

class Solution {
public:
    bool asteroidsDestroyed(int mass, vector<int>& asteroids) {
        // 每次跟最小的行星碰撞就能让自己不断吃的更大
        sort(asteroids.begin(),asteroids.end());
        
        int maxx = asteroids.back();
        for(auto x : asteroids) {
            if(mass < x) return false;
            if(mass > maxx) return true;
            mass += x;
        }
        return true;
    }
};