//这就是一个单纯的排列问题,不要求前面的数必须在前面,要求就是每个数只能出现一次:无重复数字
class Solution {
private:
vector <int> tmp;
vector <vector <int>> res;
int vis[10] = {0};
public:
void dfs (vector<int>&nums, vector<int>& tmp, int k, int len){
if (k >= len){
res.push_back(tmp);
return;
}
for (int i = 0; i < len; i ++){//不要求后面的数必须在后面,每次循环从0开始
if (vis[i] == 0){ //每个数只能出现一次
tmp.push_back(nums[i]);
vis[i] = 1;
dfs(nums, tmp, k + 1, len);
vis[i] = 0;
tmp.pop_back();
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
decltype (nums.size()) len = nums.size();
dfs(nums, tmp, 0, len);
return res;
}
};
//这个是有重复数字,也就是说,按照上面的算法,,肯定有重复
//只需要先排序,然后剪枝
class Solution {
private:
vector <int> tmp;
vector <vector <int>> res;
int vis[10] = {0};
public:
void dfs (vector<int>&nums, vector<int>& tmp, int k, int len){
if (k >= len){
// auto isNull = find(res.begin(), res.end(), tmp);
// if (isNull == res.end()){
res.push_back(tmp);
// }
return;
}
for (int i = 0; i < len; i ++){
if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])continue; //防重复都可以这样写
if (vis[i] == 0){
tmp.push_back(nums[i]);
vis[i] = 1;
dfs(nums, tmp, k + 1, len);
vis[i] = 0;
tmp.pop_back();
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
decltype (nums.size()) len = nums.size();
dfs(nums, tmp, 0, len);
return res;
}
};
//跟第46题思想一模一样
class Solution {
public:
vector <int> nums;
int vis[10] = {0}, cnt = 0, flag = 0;
string str = "";
void getStr(){
for (auto c : nums){
str += to_string(c);
}
}
void dfs (vector <int>& nums, int n, int k, int sum){
if (sum >= n){
cnt ++;
if (cnt == k){
flag = 1;
getStr();
}
return;
}
for (int i = 1; i <= n; i ++){
if (vis[i] == 0 && flag == 0){
nums.push_back(i);
vis[i] = 1;
dfs (nums, n, k, sum + 1);
nums.pop_back();
vis[i] = 0;
}
}
}
string getPermutation(int n, int k) {
dfs (nums, n, k, 0);
return str;
}
};
//这题跟46题一模一样
class Solution {
private:
int nums[16] = {0};
int ans = 0;
public:
void dfs(int n, int cnt){
if (cnt > n){
ans ++;
return;
}
for (int i = 1; i <= n; i ++){
if ((i % cnt == 0 || cnt % i == 0) && nums[i] == 0){
nums[i] = 1;
dfs (n, cnt + 1);
nums[i] = 0;
}
}
}
int countArrangement(int n) {
dfs(n, 1);
return ans;
}
};
//本题其实严格意义上来说,跟47题是一样的,因为除去要判断每对相邻的和为完全平方数,其他的就是47题,
//所以只要加一个这样的判断即可,比如记录前缀,
class Solution {
int ans = 0;
public:
int numSquarefulPerms(vector<int>& A) {
vector<bool> vis(A.size(), false);
sort(A.begin(), A.end());
dfs(A, 0, -1, vis);
return ans;
}
void dfs(vector<int>& A, int count, int prev, vector<bool>& vis)
{
if(count == A.size())
{
ans++;
return;
}
for(int i = 0; i < A.size(); ++i)
{
if(i > 0 && !vis[i-1] && A[i-1]==A[i])//用这个前提,要把初始序列排序
continue;// 剪枝
if(!vis[i] && (prev == -1 || ok(prev, A[i])))//判断是否相邻和为完全平方数。
{
vis[i] = true;
dfs(A, count+1, A[i], vis);
vis[i] = false;
}
}
}
bool ok(int a, int b)
{
int num = sqrt(a+b);
return num*num == a+b;
}
};
//组合问题就是在一个序列中,选出一个或多个能重复或者不能重复的值,然后让其满足一个条件,即为组合问题
//本题就是一个选出一个或多个可重复的值,然后让其结果等于target
//因为前面数的序号,不能大于后面数的序号,所以每次循环不能从0开始,要从上一次开始的地方开始。
class Solution {
private:
vector <vector<int>> res;
vector <int> cnt;
public:
void dfs(vector <int>& candidates, int sum, int target, int s){
if (sum > target)return ;
if (sum == target){
res.push_back(cnt);
return;
}
for (int i = s; i < candidates.size(); i ++){//要从上一次开始的地方开始
cnt.push_back(candidates[i]);
dfs (candidates, sum + candidates[i],target, i);
cnt.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
dfs(candidates, 0, target, 0);
return res;
}
};
//这一题与上一题不同的地方是一个数字只能用一次,加一个vis就好了
class Solution {
private:
vector <vector <int>> res;
vector <int> cnt;
public:
void dfs(vector<int>& candidates, int target, int sum, vector <int>& vis, int s){
if (sum > target)return;
if (sum == target){
// auto iter = find(res.begin(), res.end(), cnt);
// if (iter == res.end())
res.push_back(cnt);
return;
}
for (int i = s; i < candidates.size(); i ++){
if (i > 0 && vis[i - 1] == 0 && candidates[i] == candidates[i - 1])continue; //剪枝
if (vis[i] == 0){//加上这个就好了。
vis[i] = 1;
cnt.push_back(candidates[i]);
dfs(candidates, target, sum + candidates[i], vis, i);
vis[i] = 0;
cnt.pop_back();
}
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector <int> vis(candidates.size(), 0);
dfs (candidates, target, 0, vis, 0);
return res;
}
};
//这题就是单纯的取一定数目的数字了,不能重复用vis,前面的数不能大于后面的数,从上一次结束的地方开始。
class Solution {
private:
vector <int> cnt;
vector <vector<int>> res;
public:
void dfs (int n, int k, int ans, int s, vector <int>& vis){
if (ans >= k){
res.push_back(cnt);
return ;
}
for (int i = s; i <= n; i ++){
if (vis[i] == 0){
cnt.push_back(i);
vis[i] = 1;
dfs (n, k, ans + 1, i, vis);
vis[i] = 0;
cnt.pop_back();
}
}
}
vector<vector<int>> combine(int n, int k) {
vector <int> vis(n + 1, 0);
dfs (n, k, 0, 1, vis);
return res;
}
};
//跟上面一题一模一样
class Solution {
private:
vector <int> cnt;
vector <vector<int>> res;
public:
void dfs (int n, int k, int ans, int s, vector <int>& vis, int sum){
if (ans == k && n == sum){
res.push_back(cnt);
return ;
}
if (ans > k) return;
if (sum > n) return;
for (int i = s; i <= 9; i ++){
if (vis[i] == 0){
cnt.push_back(i);
vis[i] = 1;
dfs (n, k, ans + 1, i, vis, sum + i);
vis[i] = 0;
cnt.pop_back();
}
}
}
vector<vector<int>> combinationSum3(int k, int n) {
vector <int> vis(10, 0);
dfs (n, k, 0, 1, vis, 0);
return res;
}
};
//按照数组顺序遍历数组,如果碰到与单词第一个字母一样的,,继续,并且记录;
class Solution {
private:
int flag = 0;
public:
void backTrack(vector<vector<char>>& board, vector<vector<int>>& vis, int i, int j, int index, string& word){
if (index == word.size() - 1 && board[i][j] == word[index]){
flag = 1;
return;
}
if (board[i][j] != word[index])return;
vector<pair<int, int>> directions{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
for (const auto& dir : directions){
int newi = dir.first + i, newj = dir.second + j;
if (newi >= 0 && newi < board.size() && newj >= 0 && newj < board[0].size() && !vis[newi][newj]){
vis[newi][newj] = 1;
backTrack(board, vis, newi, newj, index + 1, word);
vis[newi][newj] = 0;
if (flag == 1)return;
}
}
}
bool exist(vector<vector<char>>& board, string word) {
int n = board.size(), m = board[0].size();
vector<vector<int>> vis(n, vector<int>(m));
for (int i = 0; i < n; i ++){
for (int j = 0; j < m; j ++){
vis[i][j] = 1;
backTrack(board, vis, i, j, 0, word);
vis[i][j] = 0;
if(flag)return true;
}
}
return false;
}
};
//用字典树来存储单词数组,然后每次遍历与字典树进行比对
struct node{
int id; //记录该node是否为某个单词的结尾字符
int cnt; //记录有几个单词经过该node
node* children[26];
node(){
cnt = 0;
id = -1;
memset(children, 0, sizeof(children));
}
~node(){
for(node* child : children)
delete child;
}
};
int dirs[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int backtrace(vector<vector<char>>& board, vector<string>& words, node* cur, int i, int j, vector<string>& res){
node* child = cur->children[board[i][j]-'a'];
if(!child) return 0;
int ans = 0; //计算经过该node匹配到的单词数量
if(child->id != -1){
res.push_back(words[child->id]);
child->id = -1;
ans++;
}
char c = board[i][j];
board[i][j] = '#';
for(int k = 0; k < 4; k++){
int x = i + dirs[k][0], y = j + dirs[k][1];
if(x >= 0 && x < board.size() && y >= 0 && y < board[0].size() && board[x][y] != '#'){
ans += backtrace(board, words, child, x, y, res);
}
}
board[i][j] = c;
child->cnt -= ans;
if(child->cnt == 0){ //经过该节点的所有单词都匹配到了,回溯回来的路上将其删除
delete child;
cur->children[board[i][j]-'a'] = nullptr;
}
return ans;
}
vector<string> findWords(vector<vector<char>>& board, vector<string>& words){
vector<string> res;
node* root = new node();
for(int i = 0; i < words.size(); i++){
node* cur = root;
for(char c : words[i]){
if(!cur->children[c - 'a']) cur->children[c - 'a'] = new node();
cur = cur->children[c - 'a'];
cur->cnt++;
}
cur->id = i;
}
for(int i = 0; i < board.size(); i++){
for(int j = 0; j < board[0].size(); j++){
backtrace(board, words, root, i, j, res);
}
}
return res;
}
class Trie {
private:
bool is_string = false;
Trie* next[26] = {nullptr};
public:
/** Initialize your data structure here. */
Trie() {
}
/** Inserts a word into the trie. */
void insert(string word) {
Trie* root = this;
for (const auto& u : word){
if (!root->next[u - 'a'])root->next[u - 'a'] = new Trie();
root = root->next[u - 'a'];
}
root->is_string = true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
Trie* root = this;
for (const auto& u : word){
if (!root->next[u - 'a'])return false;
root = root->next[u - 'a'];
}
return root->is_string;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
Trie* root = this;
for (const auto& u : prefix){
if (!root->next[u - 'a'])return false;
root = root->next[u - 'a'];
}
return true;
}
};
class WordDictionary {
private:
WordDictionary* next[27] = {nullptr};
bool is_string = false;
public:
/** Initialize your data structure here. */
WordDictionary() {
}
void addWord(string word) {
WordDictionary* root = this;
for (const auto& u : word){
if (!root->next[u - 'a'])root->next[u - 'a'] = new WordDictionary();
root = root->next[u - 'a'];
}
root->is_string = true;
}
bool findWord(WordDictionary* root, const string& word, int index){
if (index == word.size())return root->is_string;
if (word[index] == '.'){
for (int i = 0; i < 26; i ++){
if (root->next[i] && findWord(root->next[i], word, index + 1)){
return true;
}
}
}else{
int u = word[index] - 'a';
if (root->next[u]){
return findWord(root->next[u], word, index + 1);
}else{
return false;
}
}
return false;
}
bool search(string word) {
WordDictionary* root = this;
return findWord(root, word, 0);
}
};
//n皇后一般进行逐行判断,也就是说第n行要不要放这个问题,需要判断每一列,每一正负对角线符不符合
//正对角线的数的下标满足:i - j + n;副对角线满足i + j;
class Solution {
private:
int cols[10], primary[20], deputy[20];
vector <vector<string>> res;
vector <string> cnt;
public:
void dfs(int n, int ans){
if (ans >= n){
res.push_back(cnt);
return;
}
for (int i = 0; i < n; i ++){
cnt[ans][i] = 'Q';
if (!cols[i] && !primary[ans - i + n] && !deputy[i + ans]){
cols[i] = primary[ans - i + n] = deputy[i + ans] = 1;
dfs(n, ans + 1);
cols[i] = primary[ans - i + n] = deputy[i + ans] = 0;
}
cnt[ans][i] = '.';
}
}
vector<vector<string>> solveNQueens(int n) {
string str = "";
for (int i = 0; i < n; i ++){
str += '.';
}
for (int i = 0; i < n; i ++){
cnt.push_back(str);
}
dfs (n, 0);
return res;
}
};
class Solution {
private:
int cols[10], primary[20], deputy[20];
int num = 0;
public:
void dfs(int n, int ans){
if (ans >= n){
num ++;
return;
}
for (int i = 0; i < n; i ++){
if (!cols[i] && !primary[ans - i + n] && !deputy[i + ans]){
cols[i] = primary[ans - i + n] = deputy[i + ans] = 1;
dfs(n, ans + 1);
cols[i] = primary[ans - i + n] = deputy[i + ans] = 0;
}
}
}
int totalNQueens(int n) {
dfs (n, 0);
return num;
}
};
class Solution {
private:
vector <string> res;
public:
void dfs (const string& tiles, vector <int>& vis, string& str, int sum){
if (sum < tiles.size() && str != ""){
res.push_back(str);
}
if (sum >= tiles.size()){
res.push_back(str);
return ;
}
for (int i = 0; i < tiles.size(); i ++){
if (i > 0 && !vis[i - 1] && tiles[i] == tiles[i - 1])continue;
if (!vis[i]){
vis[i] = 1;
str += tiles[i];
dfs(tiles, vis, str, sum + 1);
str.erase(--str.end());
vis[i] = 0;
}
}
}
int numTilePossibilities(string tiles) {
string str = "";
sort(tiles.begin(), tiles.end());
vector <int> vis(tiles.size(), 0);
dfs (tiles, vis, str, 0);
return res.size();
}
};
//这种题目就是建立一个层次树,以beginword为根结点,每一次取出每一层的最后一个单词看看能不能扩充
//直到最后一个单词与endword一样即可:
class Solution {
vector <vector<string>> res;
public:
vector<vector<string>> BFS(vector<string>& wordList, string beginWord, string endWord){
unordered_set<string> searchWord(wordList.begin(), wordList.end());
deque <vector<string>> level;
level.push_back({beginWord});
while (!level.empty()){
unordered_set <string> visited;
for (int i = level.size(); i > 0; i --){
vector<string> tmp = level.front();
level.pop_front();
string tail = tmp.back();
if (endWord == tail){
res.push_back(tmp);
continue;
}
for (int j = 0; j < tail.size(); j ++){
char temp = tail[j];
for (char c = 'a'; c <= 'z'; c ++){
if (temp == c)continue;
tail[j] = c;
if (searchWord.count(tail) == 0)continue;
tmp.push_back(tail);
visited.insert(tail);
level.push_back(tmp);
tmp.pop_back();
}
tail[j] = temp;
}
}
if (res.size())return res;
for (auto& vis : visited)searchWord.erase(vis);
}
return {};
}
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
if (find(wordList.begin(), wordList.end(), endWord) == wordList.end())return {};
return BFS(wordList, beginWord, endWord);
}
};
class Solution {
public:
int BFS(vector<string>& wordList, string beginWord, string endWord){
unordered_set<string> searchWord(wordList.begin(), wordList.end());
deque <vector<string>> level;
level.push_back({beginWord});
while (!level.empty()){
unordered_set <string> visited;
for (int i = level.size(); i > 0; i --){
vector<string> tmp = level.front();
level.pop_front();
string tail = tmp.back();
if (endWord == tail){
return tmp.size();
}
for (int j = 0; j < tail.size(); j ++){
char temp = tail[j];
for (char c = 'a'; c <= 'z'; c ++){
if (temp == c)continue;
tail[j] = c;
if (searchWord.count(tail) == 0)continue;
tmp.push_back(tail);
visited.insert(tail);
level.push_back(tmp);
tmp.pop_back();
}
tail[j] = temp;
}
}
for (auto& vis : visited)searchWord.erase(vis);
}
return 0;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
if (find(wordList.begin(), wordList.end(), endWord) == wordList.end())return {};
return BFS(wordList, beginWord, endWord);
}
};
class Solution {
public:
bool isVaild(vector<vector<char>>& board, int row, int col, char ch){
for (int i = 0; i < 9; i ++){
if (board[i][col] == ch)return false;
if (board[row][i] == ch)return false;
if(board[(row/3)*3 + i/3][(col/3)*3 + i%3] == ch) return false;
}
return true;
}
bool backTrack(vector<vector<char>>& board, int row, int col){
if (col == 9){
return backTrack(board, row + 1, 0);
}
if (row == 9){
return true;
}
for (int i = row; i < 9; i ++){
for (int j = col; j < 9; j ++){
if (board[i][j] != '.')return backTrack(board, i, j + 1);
for (char c = '1'; c <= '9'; c ++){
if (isVaild(board, i, j, c) == false)continue;
board[i][j] = c;
if (backTrack(board, i, j + 1)){
return true;
}
board[i][j] = '.';
}
return false;
}
}
return false;
}
void solveSudoku(vector<vector<char>>& board) {
backTrack(board, 0, 0);
}
};
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。