头像

北阪有桑


访客:1519

离线:1天前


活动打卡代码 LeetCode 338. Counting Bits

class Solution {
public:
    vector<int> countBits(int num) {
        if(num==0) return {0};
        if(num==1) return {0,1};
        vector<int> f(num+1,0);
        f[0] = 0,f[1] = 1;
        for(int i = 2;i<=num;i++){
            f[i] = f[i>>1]+(i&1);
        }
        return f;
    }

};



bool cmp(vector<int> a, vector<int> b){
    if(a[0]!=b[0]) return a[0]<b[0];
    else return a[1]>b[1];
}

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), cmp);
        vector<int> f(envelopes.size()+1, 0);
        int res = 0;
        for(int i = 1;i<=envelopes.size();i++){
            int tem = 0;
            for(int j = 1;j<i;j++){
                if(envelopes[j-1][1]<envelopes[i-1][1]){
                    tem = max(tem, f[j]);
                }
            }
            f[i] = tem+1;
            res = max(res, f[i]);
        }

        return res;
    }
};


活动打卡代码 LeetCode 476. Number Complement

class Solution {
public:
    int bitwiseComplement(int N) {
        if(N==0) return 1;
        int i = N,cur=0;
        while(N>0){
            i^=(1<<(cur++));
            N=N>>1;
        }
        return i;
    }
};


活动打卡代码 LeetCode 136. Single Number

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        for(int i = 1;i<nums.size();i++){
            nums[0] = nums[0]^nums[i];
        }
        return nums[0];
    }
};



const int N = 100;

class Solution {
public:
    int primes[N], cnt;
    bool st[N];

    void get_primes(int n)
    {
        st[1] = true;
        for (int i = 2; i <= n; i++)
        {
            if (!st[i]) primes[cnt++] = i;
            for (int j = 0; primes[j] <= n / i; j++)
            {
                st[primes[j] * i] = true;
                if (i % primes[j] == 0) break;
            }
        }
    }

    int countPrimeSetBits(int L, int R) {
        get_primes(30);
        int res = 0;
        for(int i=L;i<=R;i++){
            if(!st[getBit(i)]) res++;
        }
        return res;
    }



    int getBit(int i){
        int res=0;
        while(i>0){
            if(i&1) res++;
            i = i>>1;
        }
        return res;
    }

};



活动打卡代码 LeetCode 79. Word Search

class Solution {
public:
    int col, row;
    int dx[4] = { -1,0,1,0 }, dy[4] = { 0,-1,0,1 };
    bool exist(vector<vector<char>>& board, string word) {
        if (word == "") return true;
        row = board.size(); col = board[0].size();
        for (int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if (dfs(i, j, word, 0, board)) return true;
            }
        }
        return false;
    }

    bool dfs(int i, int j, string word, int a, vector<vector<char>>& board) {
        if (word[a] != board[i][j]) return false;
        if (a == (word.size() - 1)) return true;
        board[i][j] = '.';

        for (int k = 0; k < 4; k++) {
            int xx = i + dx[k], yy = j + dy[k];
            if (xx >= 0&& xx < row && yy >= 0 && yy < col)
                if (dfs(xx, yy, word, a + 1, board))return true;
        }
        board[i][j] = word[a];
        return false;
    }
};



class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        unordered_map<string, vector<string>> hash;
        for (auto i : allowed) {
            if (!hash.count(i.substr(0, 2))) {
                hash[i.substr(0, 2)] = vector<string>();
            }
            hash[i.substr(0, 2)].push_back(i.substr(2,1));
        }
        string tem = "";
        return match(bottom, 0, hash, tem);

    }
    bool match(string bottom, int cur, unordered_map<string, vector<string>> block, string& upLevel) {
        if (bottom.size() == 2) {
            if (block.count(bottom)) return true;
            else return false;
        }
        if (cur == bottom.size() - 1) {
            string tem = "";
            return match(upLevel, 0, block, tem);
        }
        if (block.count(bottom.substr(cur, 2))) {
            auto li = block[bottom.substr(cur, 2)];
            for (auto item : li) {
                upLevel.append(item);
                if (match(bottom, cur + 1, block, upLevel)) {
                    return true;
                }
                upLevel.erase(upLevel.end() - 1);
            }
        }
        return false;
    }
};



class NestedIterator {
public:
    int cur;
    vector<int> cacheList;
    NestedIterator(vector<NestedInteger> &nestedList) {
        cur = 0;
        dfs(nestedList);
    }

    void dfs(vector<NestedInteger> &nestedList){
        for(auto i:nestedList){
            if(i.isInteger()){
                cacheList.push_back(i.getInteger());
            }else{
                dfs(i.getList());
            }
        }
    }

    int next() {
        return cacheList[cur++];
    }

    bool hasNext() {
        return cur<cacheList.size();
    }
};


活动打卡代码 LeetCode 394. Decode String

class Solution {
public:
    string decodeString(string s) {
        if (s == "")return "";
        int braPos = 0;
        int numPos = 0;
        int braLen = 0;
        int numLen = 0;
        int numBegin = 0;
        int braBegin = 0;
        for (int i = 0; i < s.size(); i++) {
            if (numBegin==0) {
                if (s[i] >= '0' && s[i] <= '9') {
                    numBegin = 1;
                    numPos = i;
                    numLen++;
                }
                continue;
            }
            if (numBegin == 1) {
                if (s[i] >= '0' && s[i] <= '9')numLen++;
                else if (s[i] == '[') {
                    numBegin++;
                    braPos = i+1;
                    braBegin++;
                }
                continue;
            }
            if (s[i] == '[') {
                braBegin++;
                braLen++;
            }
            else if (s[i] == ']') {
                braBegin--;
                braLen++;
                if (braBegin == 0) {
                    string res = "";
                    res += s.substr(0, numPos);
                    int times = 0;
                    sscanf(s.substr(numPos, numLen).c_str(), "%d", &times);
                    string dec = decodeString(s.substr(braPos, braLen-1));
                    for (int i = 0; i < times; i++) {
                        res += dec;
                    }
                    res += decodeString(s.substr(i + 1, s.size() - i - 1));
                    return res;
                }
            }
            else {
                braLen++;
            }
        }
        return s;
    }
};



class Solution {
public:

    vector<TreeNode*> generateTrees(int n) {
        if(n==0) return {};
        return dfs(1,n);
    }

    vector<TreeNode*> dfs(int l , int r){
        if(l>r) return {NULL};
        if(l==r) return {new TreeNode(l)};
        vector<TreeNode*> res;
        for(int i =l;i<=r;i++){
            auto left = dfs(l, i-1);
            auto right = dfs(i+1, r);
            for(auto ll:left){
                for(auto rr:right){
                    auto head = new TreeNode(i);
                    head->left = ll;
                    head->right = rr;
                    res.push_back(head);
                }
            }
        }
        return res;
    }

};