PHP网站建设计划书,室内设计联盟官方网站入口,wordpress 匿名投票,南充做网站的46. 全排列 给定一个不含重复数字的数组 nums #xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1#xff1a; 输入#xff1a;nums [1,2,3]
输出#xff1a;[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2#xff1a; 输入#xff…46. 全排列 给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1 输入nums [1,2,3]
输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2 输入nums [0,1]
输出[[0,1],[1,0]]示例 3 输入nums [1]
输出[[1]]提示 1 nums.length 6-10 nums[i] 10nums 中的所有整数 互不相同 vectorvectorint ans;
vectorint path;
vectorbool vis;vectorvectorint permute(vectorint nums) {int n nums.size();vis vectorbool(n, false);dfs(nums);return ans;
}void dfs(vectorint nums) {int n nums.size();if (path.size() n) {ans.push_back(path);return;}for (int i 0; i n; i) {if (vis[i] false) {path.push_back(nums[i]);vis[i] true;dfs(nums);path.pop_back();vis[i] false;}}
}78. 子集 给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1 输入nums [1,2,3]
输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例 2 输入nums [0]
输出[[],[0]]提示 1 nums.length 10-10 nums[i] 10nums 中的所有元素 互不相同 vectorvectorint ans;
vectorint path;vectorvectorint subsets(vectorint nums) {dfs(nums, 0);return ans;
}void dfs(vectorint nums, int pos) {if (pos nums.size()) {ans.push_back(path);return;}dfs(nums, pos 1);path.push_back(nums[pos]);dfs(nums, pos 1);path.pop_back();
}另一种方法
vectorvectorint ans;
vectorint path;vectorvectorint subsets(vectorint nums) {dfs(nums, 0);return ans;
}void dfs(vectorint nums, int pos) {ans.push_back(path);for (int i pos; i nums.size(); i) {path.push_back(nums[i]);dfs(nums, i 1);path.pop_back();}
}17. 电话号码的字母组合 给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 示例 1 输入digits 23
输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2 输入digits
输出[]示例 3 输入digits 2
输出[a,b,c]提示 0 digits.length 4digits[i] 是范围 [2, 9] 的一个数字。 vectorstring ans;
string path;
vectorstring nums {, , abc, def,ghi, jkl, mno,pqrs, tuv, wxyz
};vectorstring letterCombinations(string digits) {if (digits.size() 0) {return ans;}dfs(digits, 0);return ans;
}void dfs(string digits, int pos) {if (path.size() digits.size()) {ans.push_back(path);return;}int n digits[pos] - 0;string str nums[n];for (int i 0; i str.size(); i) {path.push_back(str[i]);dfs(digits, pos 1);path.pop_back();}
}39. 组合总和 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。 对于给定的输入保证和为 target 的不同组合数少于 150 个。 示例 1 输入candidates [2,3,6,7], target 7
输出[[2,2,3],[7]]
解释
2 和 3 可以形成一组候选2 2 3 7 。注意 2 可以使用多次。
7 也是一个候选 7 7 。
仅有这两种组合。示例 2 输入: candidates [2,3,5], target 8
输出: [[2,2,2,2],[2,3,3],[3,5]]示例 3 输入: candidates [2], target 1
输出: []提示 1 candidates.length 302 candidates[i] 40candidates 的所有元素 互不相同1 target 40 vectorvectorint ans;
vectorint path;vectorvectorint combinationSum(vectorint candidates, int target) {dfs(candidates, target, 0, 0);return ans;
}void dfs(vectorint candidates, int target, int sum, int pos) {if (sum target) {return;}if (sum target) {ans.push_back(path);return;}for (int i pos; i candidates.size(); i) {path.push_back(candidates[i]);dfs(candidates, target, sum candidates[i], i);path.pop_back();}
}22. 括号生成 数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。 示例 1 输入n 3
输出[((())),(()()),(())(),()(()),()()()]示例 2 输入n 1
输出[()]提示 1 n 8 vectorstring ans;
string path;vectorstring generateParenthesis(int n) {dfs(n, 0, 0);return ans;
}void dfs(int n, int left, int right) {if (left right 2 * n) {ans.push_back(path);return;}if (left n) {path.push_back(();dfs(n, left 1, right);path.pop_back();}if (right left) {path.push_back());dfs(n, left, right 1);path.pop_back();}
}79. 单词搜索 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中返回 true 否则返回 false 。 单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示例 1 输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word ABCCED
输出true示例 2 输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word SEE
输出true示例 3 输入board [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word ABCB
输出false提示 m board.lengthn board[i].length1 m, n 61 word.length 15board 和 word 仅由大小写英文字母组成 vectorvectorbool vis;
const int dx[4] {0, 0, 1, -1};
const int dy[4] {1, -1, 0, 0};bool exist(vectorvectorchar board, string word) {int n board.size(), m board[0].size();vis vectorvectorbool(n, vectorbool(m, false));for (int i 0; i n; i) {for (int j 0; j m; j) {if (board[i][j] word[0]) {vis[i][j] true;if (dfs(board, word, i, j, 1) true) {return true;}vis[i][j] false;}}}return false;
}bool dfs(vectorvectorchar board, const string word, int x, int y, int pos) {if (pos word.size()) {return true;}int n board.size(), m board[0].size();for (int k 0; k 4; k) {int nx x dx[k], ny y dy[k];if (nx 0 nx n ny 0 ny m board[nx][ny] word[pos] vis[nx][ny] false) {vis[nx][ny] true;if (dfs(board, word, nx, ny, pos 1) true) {return true;}vis[nx][ny] false;}}return false;
}131. 分割回文串 给你一个字符串 s请你将 s 分割成一些 子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。 示例 1 输入s aab
输出[[a,a,b],[aa,b]]示例 2 输入s a
输出[[a]]提示 1 s.length 16s 仅由小写英文字母组成 vectorvectorstring ans;
vectorstring path;
unordered_setstring hash;
unordered_setstring nonhash;vectorvectorstring partition(string s) {dfs(s, 0);return ans;
}void dfs(const string s, int pos) {if (pos s.size()) {ans.push_back(path);return;}// pos开始i结尾for (int i pos; i s.size(); i) {string str s.substr(pos, i - pos 1);if (isPalindrome(str)) {path.push_back(str);dfs(s, i 1);path.pop_back();}}
}bool isPalindrome(const string s) {if (hash.count(s)) {return true;}if (nonhash.count(s)) {return false;}int left 0, right s.size() - 1;while (left right) {if (s[left] ! s[right]) {nonhash.insert(s);return false;}left, right--;}hash.insert(s);return true;
}51. N 皇后 按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。 给你一个整数 n 返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 Q 和 . 分别代表了皇后和空位。 示例 1 输入n 4
输出[[.Q..,...Q,Q...,..Q.],[..Q.,Q...,...Q,.Q..]]
解释如上图所示4 皇后问题存在两个不同的解法。示例 2 输入n 1
输出[[Q]]提示 1 n 9 通过x 0时y b来判断是否当前斜线上有无皇后。
vectorvectorstring ans;
vectorstring path;
bool vis[10];
bool vis1[20]; // y - x b
bool vis2[20]; // y x bvectorvectorstring solveNQueens(int n) {path.resize(n);for (int i 0; i n; i) {path[i].append(n, .);}dfs(n, 0);return ans;
}void dfs(int n, int y) {if (y n) {ans.push_back(path);return;}for (int x 0; x n; x) {if (!vis[x] !vis1[y - x 10] !vis2[y x]) {path[y][x] Q;vis[x] vis1[y - x 10] vis2[y x] true;dfs(n, y 1);path[y][x] .;vis[x] vis1[y - x 10] vis2[y x] false;}}
}
