头像

ShizhengLee




离线:25天前


最近来访(1458)
用户头像
rsy
用户头像
爱抠鼻屎的
用户头像
喵籽
用户头像
StkOvflow
用户头像
满洲里有象QAQ
用户头像
不高兴的兽奶
用户头像
bre
用户头像
艾伦_0
用户头像
six_one
用户头像
hanwenwang
用户头像
4ppleS
用户头像
hulian425
用户头像
简约之上还有快乐
用户头像
yangdaxian
用户头像
多多_0
用户头像
IF_3
用户头像
lorendw7
用户头像
EdwardNygma
用户头像
shinyruo319
用户头像
Oinng

活动打卡代码 AcWing 62. 丑数

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> q(1, 1);
        int i = 0, j = 0, k = 0;
        while ( -- n) {
            int t = min(q[i] * 2, min(q[j] * 3, q[k] * 5)); // 三路归并的最小值
            q.push_back(t);
            if (t == q[i] * 2) i ++;
            if (t == q[j] * 3) j ++;
            if (t == q[k] * 5) k ++;
        }
        return q.back(); // 返回q序列的最后一个值
    }
};



class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.empty()) return 0;
        if (s.size() == 1) return 1;
        int res = 0, left = -1;
        unordered_map<char, int> hash;
        for (int i = 0; i < s.length(); i ++) {
            if (hash.find(s[i]) != hash.end()) { // s[i]在hash表中,就更新左指针left
                left = max(hash[s[i]], left);
            }
            hash[s[i]] = i; //更新右指针
            res = max(res, i - left);
        }
        return res;
    }
};






class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= m; j ++) {
                f[i][j] = max(f[i -1][j], f[i][j - 1]) + grid[i -1][j - 1];
            }
        }
        return f[n][m];
    }
};




class Solution {
public:
    int getTranslationCount(string s) {
       int n = s.size();
       vector<int> f(n + 1);
       f[0] = 1;
       for (int i = 1; i <= n; i ++) {
           f[i] = f[i - 1];
           int t = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
           if (t >= 10 && t <= 25)  f[i] += f[i- 2];
       }
       return f[n];
    }
};




ShizhengLee
1个月前
class Solution {
public:

    static bool cmp(int a, int b) {
        auto as = to_string(a), bs = to_string(b);
        return as + bs < bs + as; // 字符串拼接后比较: ab < ba; string这里的“+” 就是拼接到一起
    }

    string printMinNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), cmp);
        string res;
        for (auto x: nums) res += to_string(x);
        return res;
    }
};




ShizhengLee
1个月前
class Solution {
public:
    int findNthDigit(int n) {
        if (!n) return 0;

        long long i = 1; // i表示位数,从1位开始枚举
        long long s = 9; // s表示这一位共有多少个数
        long long base = 1; // base表示这位数的第一个数是多少,初始时是1位数,base = 1 

        // 第一步:确定n属于几位数,比如4位数,4位数中可能是1000~9999
        // 当前n大于i位的所有数
        while (n > i * s) {
            n -= i * s;
            i ++;
            s *= 10;
            base *= 10; // 位数 + 1,base 乘10
        }  

        // 第二步:确定是几位数的第几个数,可以确定具体是哪个数字中的某一位,比如1234这个数中的某一位
        // n / i 上取整: 所求的第n位属于第几个i位数
        int number = base + (n + i - 1) / i - 1;

        //第三步:属于那个数的第几位
        // 余数, n % i 
        int r = n % i ? n % i : i;

        // 求number的第r位数字是多少
        for (int j = 0; j < i - r; j ++) number /= 10;

        return number % 10;

    }
};




ShizhengLee
8个月前
class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
        vector<int> a;
        while(n) a.push_back( n % 10), n/= 10;
        int res =0;
        for(int i = a.size()-1; i>=0; i--){
            int d = a[i];
            int left =0, right =0, power =1;
            for(int j = a.size()-1; j>i ;j--) left = left*10 +a[j];
            for(int j= i-1; j>=0; j--){
                right = right * 10 + a[j];
                power *= 10;
            }

            if(d ==0) res += left * power;
            else if(d ==1) res +=   left * power + right +1;
            else  res += (left +1) *power;
        }
        return res;

    }
};





ShizhengLee
8个月前
class Solution {
public:

    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN, s = 0;
        for (auto x : nums) {
            // 如果以前一个数结尾的子数组和的最大值<0, 
            // 则当前数结尾的子数组和的最大值直接为x

            // 否则的话,以当前数结尾的子数组的最大值就等于 
            // s(以前一个数结尾的最大值)  + x(当前数)
            if (s < 0) s = 0;
            s += x;

            res = max(res, s);
        }
        return res;
    }
};





ShizhengLee
8个月前
class Solution {
public:
    priority_queue<int> max_heap;
    priority_queue<int, vector<int>, greater<int>> min_heap;

    void insert(int num){
        max_heap.push(num);
        if (min_heap.size() && max_heap.top() > min_heap.top()) {
            auto minv = min_heap.top(), maxv = max_heap.top();
            max_heap.pop(), min_heap.pop();
            max_heap.push(minv), min_heap.push(maxv);
        }

        if (max_heap.size() > min_heap.size() + 1) {
            min_heap.push(max_heap.top());
            max_heap.pop(); 
        }
    }

    double getMedian(){
        int num = max_heap.size() + min_heap.size();
        if (num & 1)  return max_heap.top();
        else return (min_heap.top() + max_heap.top()) / 2.0;

    }
};




活动打卡代码 AcWing 53. 最小的k个数

ShizhengLee
8个月前
class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        priority_queue<int> heap;
        for (auto x : input) {
            heap.push(x);
            if (heap.size() > k) heap.pop();
        }

        vector<int> res;
        while(heap.size()) {
            res.push_back(heap.top());
            heap.pop();
        }

        reverse(res.begin(), res.end());
        return res;
    }
};