头像

heiyou


访客:877

在线 


活动打卡代码 LeetCode 38. Count and Say

heiyou
7小时前
class Solution {
public:
    string countAndSay(int n) {
        string s = "1";
        string ans;
        if(n == 1) return s;
        for(int i = 1; i < n; i ++)
        {
            ans = transform(s);
            s = ans;
        }

        return s;
    }

    string transform(string s)
    {
        string res;
        for(int i = 0; i < s.size(); )
        {
            char t = s[i];
            int k = 0;
            while(k + i < s.size() && s[i + k] == t) k ++;
            res += to_string(k) + t;
            i = k + i;
        }
        return res;
    }
};


活动打卡代码 LeetCode 52. N-Queens II

heiyou
8小时前
class Solution {
public:
    vector<bool> row, col, diag, anti_diag;
    int ans = 0;
    int totalNQueens(int n) { 
        row = vector<bool>(n, false);
        col = vector<bool>(n, false);
        diag = vector<bool>(2 * n, false);
        anti_diag = vector<bool>(2 * n, false);

        dfs(0, 0, 0, n);  //从0 0 开始填皇后, 最后一个参数表示填了几个皇后
        return ans;
    }
    void dfs(int x, int y, int k, int n)
    {
        if(y == n) y = 0, x ++;
        if(x == n)
        {
            if(k == n) ans ++;
            return ;
        }

        dfs(x, y + 1, k, n);
        if(!row[x] && !col[y] && !diag[x + y] && !anti_diag[y - x + n])
        {
            row[x] = col[y] = diag[x + y] = anti_diag[y - x + n] = true;
            dfs(x, y + 1, k + 1, n);
            row[x] = col[y] = diag[x + y] = anti_diag[y - x + n] = false;
        }
    }
};



heiyou
19小时前
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k, n, 1); //k表示还需要填几个数, 1表示从1开始枚举
        return ans;
    }

    void dfs(int k, int n, int u)
    {
        if(k == 0)
        {
            if(n == 0) ans.push_back(path);
            return;
        }

        for(int i = u; i <= 9; i ++)
        {
            if(n >= i + k - 1) 
            {
                path.push_back(i);
                dfs(k - 1, n - i, i + 1);
                path.pop_back();
            }
        }
    }
};


活动打卡代码 LeetCode 90. Subsets II

heiyou
20小时前
class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        if(nums.empty()) return vector<vector<int>>(0);

        unordered_map<int, int> times;
        unordered_set<int> val;
        for(int i = 0; i < nums.size(); i ++)
        {
            val.insert(nums[i]);
            if(times.count(nums[i])) times[nums[i]] ++;
            if(!times.count(nums[i])) times[nums[i]] = 1;
        }

        ans.push_back(vector<int>(0));
        for(auto c : val)   //c是枚举的数字
        {
            vector<vector<int>> now;
            for(auto x : ans)  //枚举的的是上一次的集合
            {
                for(int i = 0; i <= times[c]; i ++)
                {
                    vector<int> cur = x;
                    for(int j = 0; j < i; j ++)
                        cur.push_back(c);
                    now.push_back(cur);
                }
            }
            ans = now;
        }

        return ans;
    }
};


活动打卡代码 LeetCode 78. Subsets

heiyou
1天前
class Solution {
public:
    //考察点  二进制
    vector<vector<int>> ans;
    vector<vector<int>> subsets(vector<int>& nums) {
        for(int i = 0; i < 1 << nums.size(); i ++)
        {
            vector<int> res;
            for(int j = 0; j < nums.size(); j ++)
            {
                if(i >> j & 1)
                    res.push_back(nums[j]);
            }
            ans.push_back(res);
        }
        return ans;
    }
};


活动打卡代码 LeetCode 47. Permutations II

heiyou
1天前
第一种:枚举每一个数字放置的位置
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> st;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        if(nums.empty()) return vector<vector<int>>(0);
        sort(nums.begin(), nums.end());

        for(int i = 0; i < nums.size(); i ++)
        {
            st.push_back(false);
            path.push_back(0);             //初始化
        }
        dfs(nums, 0, 0);
        return ans;
    }

    void dfs(vector<int>& nums, int u, int start)
    {
        if(u == nums.size())
        {
            ans.push_back(path);
            return;
        }

        for(int i = start; i < nums.size(); i ++)
        {
            if(!st[i])
            {
                st[i] = true;
                path[i] = nums[u];
                dfs(nums, u + 1, u + 1 < nums.size() && nums[u + 1] == nums[u] ? i + 1 : 0);
                st[i] = false;
            } 
        }
    }
};

第二种:枚举每个位置上放的数字
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> st;
    int n;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        if(nums.empty()) return vector<vector<int>>(0);

        n = nums.size();
        for(int i = 0; i < n; i ++)
        {
            path.push_back(0);
            st.push_back(false);
        }

        dfs(nums, 0);
        return ans;
    }

    void dfs(vector<int>& nums, int u)  //u表示当前枚举的位置
    {
        if(u == n)
        {
            ans.push_back(path);
            return ;
        }

        unordered_set<int> val;
        for(int i = 0; i < n; i ++)
        {
            if(!st[i] && (val.count(nums[i]) == 0 || val.empty()))
            {
                st[i] = true;
                path[u] = nums[i];
                val.insert(nums[i]);
                dfs(nums, u + 1);
                st[i] = false;
            }
        }
    }
};



活动打卡代码 LeetCode 46. Permutations

heiyou
1天前
class Solution {
public:
    //全排列问题
    vector<vector<int>> ans;
    vector<int> path;
    vector<bool> st;

    vector<vector<int>> permute(vector<int>& nums) {
        if(nums.empty()) return vector<vector<int>>(0);
        for(int i = 0; i < nums.size(); i ++) st.push_back(false);
        dfs(0, nums);
        return ans;
    }

    void dfs(int u, vector<int>& nums)
    {
        if(u == nums.size())
        {
            ans.push_back(path);
            return;
        }

        for(int i = 0; i < nums.size(); i ++)
        {
            if(!st[i])
            {
                st[i] = true;
                path.push_back(nums[i]);
                dfs(u + 1, nums);
                st[i] = false;
                path.pop_back();
            }
        }
    }
};


活动打卡代码 LeetCode 79. Word Search

heiyou
1天前
回溯需要注意保存现场和恢复现场
class Solution {
public:
    int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
    bool exist(vector<vector<char>>& board, string word) {
        if(board.empty() || word.empty()) return false;
        for(int i = 0; i < board.size(); i ++)
            for(int j = 0; j < board[i].size(); j ++)
                if(dfs(board, word, 0, i, j)) return true;
        return false;
    }

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

        char t = board[row][col];
        board[row][col] = '-';
        for(int i = 0; i < 4; i ++)
        {
            int a = row + dx[i], b = col + dy[i];
            if(a >= 0 && a < board.size() && b >= 0 && b < board[a].size())
                if(dfs(board, word, cnt + 1, a, b)) return true;
        }
        board[row][col] = t;
        return false;
    }
};



heiyou
1天前
class Solution {
public:
    string chars[8] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return vector<string>();
        vector<string> ans(1, "");
        int n = digits.size();

        for(int i = 0; i < n; i ++)
        {
            vector<string> now;
            string number = chars[digits[i] - '2'];
            for(auto c : number)
                for(auto x : ans)
                    now.push_back(x + c);
            ans = now;
        }
        return ans;
    }
};


活动打卡代码 LeetCode 278. First Bad Version

heiyou
1天前
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1, r = n;
        while(l < r)
        {
            int mid = (long long)l + r >> 1;
            if(isBadVersion(mid)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};