方法一:c++的next_permutation()封装了全排列的实现,注意使用前先排序。
代码:
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
do {
res.push_back(nums);
}while(next_permutation(nums.begin(), nums.end()));
return res;
}
};
方法二:采用dfs。
代码:
class Solution {
public:
void dfs(int cur, vector<int>& temp, vector<vector<int>>& res, vector<int>& used, vector<int>& nums) {
if(cur == nums.size()) {
res.push_back(temp);
return;
}
for(int i = 0; i < nums.size(); i++) {
if(used[i] == 0) {
used[i] = 1;
temp.push_back(nums[i]);
dfs(cur + 1, temp, res, used, nums);
temp.pop_back();
used[i] = 0;
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
int n = nums.size();
vector<int> temp;
vector<vector<int>> res;
if(n == 0) {
return res;
}
vector<int> used(n, 0);
dfs(0, temp, res, used, nums);
return res;
}
};
分析:简单的模拟题。
代码:
class Solution {
public:
vector<string> letterCasePermutation(string s) {
vector<string> res;
for(int i = 0; i < s.size(); i++) {
if(s[i] >= '0' && s[i] <= '9') {
if(res.empty()) {
string temp = "";
temp += s[i];
res.push_back(temp);
}else {
for(int j = 0; j < res.size(); j++) {
res[j].push_back(s[i]);
}
}
}else {
//复制两份
int n = res.size();
char s1 = tolower(s[i]), s2 = toupper(s[i]);
if(n == 0) {
string temp = "";
res.push_back(temp + s1);
res.push_back(temp + s2);
continue;
}
vector<string> test;
for(int j = 0; j < n; j++) {
string temp = res[j];
test.push_back(temp + s1);
test.push_back(temp + s2);
}
res = test;
}
}
return res;
}
};
分析:动态规划,设dp[i]表示房间数为i时的最优解。边界条件:如果只有一个房间,则只能选择偷窃此房间,即dp[0] = nums[0];如果有两个房间,由于不能偷窃连续房间,则dp[1]为max(nums[0], nums[1]);如果房间数大于2,对于第i个房间,可以选择不偷窃,即dp[i] = dp[i-1],也可以选择偷窃,由于不能偷窃连续房间,则dp[i] = dp[i - 2] + nums[i]。
代码:
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.empty()) {
return 0;
}
int size = nums.size();
if (size == 1) {
return nums[0];
}
vector<int> dp = vector<int>(size, 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < size; i++) {
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[size - 1];
}
};
分析:动态规划,比较简单,不再分析。
代码:
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int m = triangle.size();
vector<vector<int>> f(m, vector<int>(m, 0));
f[0][0] = triangle[0][0];
for(int i = 1; i < m; i++) {
f[i][0] = f[i - 1][0] + triangle[i][0];
f[i][i] = f[i - 1][i - 1] + triangle[i][i];
}
for(int i = 0; i < m; i++) {
for(int j = 0; j < i; j++) {
if(j == 0 || i == j) {
continue;
}else {
f[i][j] = min(f[i - 1][j], f[i - 1][j - 1]) + triangle[i][j];
}
}
}
return *min_element(f[m - 1].begin(), f[m - 1].end());
}
};
分析:层序遍历(与层次遍历不同):采用bfs,每次将同一层中的所有节点取出,然后进行链接。
代码:
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node() : val(0), left(NULL), right(NULL), next(NULL) {}
Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
Node* connect(Node* root) {
if (root == nullptr) {
return root;
}
queue<Node*> Q;
Q.push(root);
while (!Q.empty()) {
// 记录当前队列大小
int size = Q.size();
// 遍历这一层的所有节点
for(int i = 0; i < size; i++) {
Node* node = Q.front();
Q.pop();
// 连接
if (i < size - 1) {
node->next = Q.front();
}
if (node->left != nullptr) {
Q.push(node->left);
}
if (node->right != nullptr) {
Q.push(node->right);
}
}
}
return root;
}
};