heiyou

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;
}
};


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();
}
}
}
};


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;
}
};


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;
}
};


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;
}
}
}
};



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();
}
}
}
};


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;
}
};


heiyou
1天前
// The API isBadVersion is defined for you.

class Solution {
public: