@TOC
N皇后
解题思路，利用回溯法，和之前解数独是一样的思想，回溯法主要在于递归时更新状态，然后递归，如果之后不满足条件需要恢复状态。
怎么更新状态，当在棋盘上放上一个棋子的时候，需要更新棋盘，该棋子的横竖斜方向都不能被放。假设，棋子的位置为(x, y);
- 横方向 则更新m[x][i…]
- 竖方向 则更新m[i…][y]
- 斜方向 则需要考虑四个方向，以棋子为原点，分别更新45°，135°，-135°，-45°
AC代码:
class Solution {
public:
vector<vector<string>> r;
void update(vector<vector<string>>& res) {
for(int i = 0; i < res.size(); ++i) {
for(int j = 0; j < res.size(); ++j) {
if(res[i][j] == "Q") write(res, i, j, "1");
}
}
}
void write(vector<vector<string>>& res, int x, int y, string value) {
//横
for(int i = 0; i < res.size(); ++i) {
res[x][i] = value;
}
//竖
for(int i = 0; i < res.size(); ++i) {
res[i][y] = value;
}
//45
for(int i = x + 1, j = y - 1; i < res.size() && j >= 0; ++i,--j) {
res[i][j] = value;
}
//-45
for(int i = x + 1, j = y + 1; i < res.size() && j < res.size(); ++i,++j) {
res[i][j] = value;
}
//-135
for(int i = x - 1, j = y + 1; i >= 0 && j < res.size(); ++j,--i) {
res[i][j] = value;
}
//135
for(int i = x - 1, j = y - 1; i >= 0 && j >= 0; --i,--j) {
res[i][j] = value;
}
if(value == "1") res[x][y] = "Q";
else res[x][y] = "0";
}
void back(vector<vector<string>>& res, int ope) {
if(ope == res.size()) {
vector<string> vtmp;
for(int i = 0; i < res.size(); ++i) {
string tmp;
for(int j = 0; j < res.size(); ++j) {
if(res[i][j] == "1") {
tmp.append(".");
}else {
tmp.append(res[i][j]);
}
}
vtmp.push_back(tmp);
}
r.push_back(vtmp);
return;
}
for(int i = 0; i < res.size(); ++i) {
if(res[ope][i] == "0") {
res[ope][i] = "Q";
write(res, ope, i, "1");
res[ope][i] = "0";
write(res, ope, i, "0");
update(res);
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<string> tmp(n, "0");
vector<vector<string>> res(n, tmp);
back(res, 0);
return r;
}
};
N皇后 II
要求和上一题一模一样，返回解题的方案总数，Are you kidding me?
前一题已经都把答案输出了，加个size就ok了。
过了
最大子序和
解题思路，因为是一个乱序数组，所以找到答案肯定是要遍历完一遍数组的，而要怎么去解题，需要弄清楚怎么获得最大和的连续数组。
简单的来说，在遍历的时候维护两个值，其中一个值记录前面已经遍历的最大子序和res，另一个值来记录前面已经遍历每一个子序列和大于0的值tmp；
- tmp的判断标准就是，如果前面数组的最大值加上当前的值还没有当前的值大，则到当前为止，最大值就是当前值；否则加上当前值；
- res的判断标准就是，和tmp比较，记录最大值
AC代码:
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.size() <= 1) return nums.size()==0? 0 : nums[0];
int res = nums[0];
int tmp = res;
for(int i = 1; i < nums.size(); ++i) {
if(tmp + nums[i] > nums[i]) {
tmp += nums[i];
}else {
tmp = nums[i];
}
res = tmp > res ? tmp : res;
}
return res;
}
};
螺旋矩阵
解题思路:利用递归的思想，也就是把数组一层一层的扒下来，直到数组的个数为1或者数组内的数组个数为1,。
AC代码:
class Solution {
public:
vector<int> res;
void getRes(vector<vector<int>> &ope) {
if(ope.size() == 0 || (*ope.begin()).size() == 0) return;
int n = ope.size();
int m = (*ope.begin()).size();
if(n == 1) {
for(int i = 0; i < m; ++i) {
res.push_back(ope[0][i]);
}
return;
}else if(m == 1) {
for(int i = 0; i < n; ++i) {
res.push_back(ope[i][0]);
}
return;
}else {
//第一行
for(int i = 0; i < m; ++i) {
res.push_back(ope[0][i]);
}
//最后一列
for(int i = 1; i < n-1; ++i) {
res.push_back(ope[i][m-1]);
}
//最后一行
for(int i = m-1; i >= 0; --i) {
res.push_back(ope[n-1][i]);
}
//第一列
for(int i = n-2; i > 0; --i) {
res.push_back(ope[i][0]);
}
}
ope.erase(ope.begin());
ope.erase(ope.end()-1);
for(auto& o : ope) {
o.erase(o.begin());
o.erase(o.end()-1);
}
getRes(ope);
}
vector<int> spiralOrder(vector<vector<int>>& matrix) {
getRes(matrix);
return res;
}
};
ps:看到解题有一个奇妙的解法，思想大概如下:
只需要写一个逆时针旋转数组的函数即可。
跳跃游戏
看到这道题，解题思路还是一下子就是动态规划。
初始化:倒数第二个数，如果是0，则为0，否则为1
状态转移:根据跳跃的距离判断，如果跳跃距离为0，或者跳跃到的位置不超过最后的位置且为0则为0；否则为1，更新跳跃的数组为1；
ps:之前遇到过dp超时用贪心算法的，这道题也可以用贪心算法解决，思路就是从0开始出发，判断能够到达的最远距离是否能够到达最后一位得到答案。
AC代码:
class Solution {
public:
bool dp(vector<int>& nums) {
int n = nums.size();
if(n < 2) return 1;
int dp[n];
dp[n-2] = nums[n-2] > 0 ? 1 : 0;
cout << dp[n-2] << endl;
for(int i = n-3; i >= 0; --i) {
if((nums[i] + i < n - 1 && dp[nums[i]+i] == 0) || (nums[i] == 0)) {
dp[i] = 0;
}else {
for(int j = i; j < nums[i]+i && j <= n-2; ++j) {
dp[j] = 1;
}
}
}
return dp[0];
}
bool tanxin(vector<int>& nums) {
if(nums.size() < 2) return 1;
int rightmost = 0;
for (int i = 0; i <= rightmost; ++i) {
rightmost = max(rightmost, i + nums[i]);
if (rightmost >= n - 1) {
return true;
}
}
return false;
}
bool canJump(vector<int>& nums) {
return dp(nums);
}
};
合并区间
解题思路，把这些集合都放到x轴上，然后从左到右遍历获得正确的区间
看图
AC代码
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> res;
multimap<int, string> m;
multimap<string, int> tmp;
for(auto vi : intervals) {
tmp.insert(make_pair("a", vi[0]));
tmp.insert(make_pair("b", vi[1]));
}
for(auto t : tmp) {
m.insert(make_pair(t.second, t.first));
}
//上面的两个map操作保证相同的数字，a在前面，也就是start在前面
int se = 0, start, end;
for(auto s : m) {
if(s.second == "a") {
if(se == 0) start = s.first;
++se;
}else {
--se;
if(se == 0) end = s.first;
}
if(se == 0) res.push_back({start, end});
}
return res;
}
};
插入区间
和上一道题本质上是一样的，修改了一下对于两个相同的start或者两个相同的end处理方式。
AC代码:
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> res;
multimap<double, string> m;
for(auto vi : intervals) {
m.insert(make_pair(vi[0], "s"));
m.insert(make_pair(vi[1], "e"));
}
if(m.find(newInterval[0]) == m.end()) m.insert(make_pair(newInterval[0], "s"));
else m.insert(make_pair(newInterval[0]-0.1, "s"));
if(m.find(newInterval[1]) == m.end()) m.insert(make_pair(newInterval[1], "e"));
else m.insert(make_pair(newInterval[1]+0.1, "e"));
int se = 0, start, end;
for(auto s : m) {
if(s.second == "s") {
if(se == 0) start = s.first + 0.2;
++se;
}else {
--se;
if(se == 0) end = s.first + 0.2;
}
if(se == 0) res.push_back({start, end});
}
return res;
}
};
提供一个新方法，解题方法如下:
代码:
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> result;
int i;
for (i = 0; i < intervals.size(); ++i) {
if (newInterval[0] > intervals[i][1]) {
result.push_back(intervals[i]);
}
else {
break;
}
}
result.push_back(newInterval);
for (; i < intervals.size(); ++i) {
if (result.back()[1] < intervals[i][0]) {
result.push_back(intervals[i]);
}
else {
result.back()[0] = min(result.back()[0], intervals[i][0]);
result.back()[1] = max(result.back()[1], intervals[i][1]);
}
}
return result;
}
};
最后一个单词的长度
解题思路，最关键的一句话字符串从左向右滚动显示，最后一个单词就是最后出现的单词呢，意思表面，字符串最后可能包含n个空格，这是需要注意的问题。
所以当选择从后面开始计算长度的时候，需要注意从第一个不是空格的开始计数
AC代码:
class Solution {
public:
int lengthOfLastWord(string s) {
if(s.size() == 0) return 0;
int res = 0;
bool flag = false;
for(int i = s.size() - 1; i != -1; --i) {
if(!flag && s[i] == ' ') {
flag = false;
continue;
}else {
flag = true;
}
if(s[i] != ' ') res++;
else break;
}
return res;
}
};
螺旋矩阵 II
解题思路就是模拟螺旋排列，从最上面一行，到最右边一列，再到最下面一行，然后最左边一列。模拟完一层，然后缩小范围继续模拟
AC代码:
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n);
if(n == 0) return res;
int inser = 1;
for (int i = 0; i < res.size(); i++) res[i].resize(n);
int t = 0, b = n-1, l = 0, r = n-1;
while(1) {
if(t == b) {
res[t][l] = inser;
break;
}
//最上面一行
for(int i = l; i <= b; ++i) res [t][i] = inser++;
//最右边一列
for(int i = t+1; i < r; ++i) res[i][r] = inser++;
//最下面一行
for(int i = r; i >= l; --i) res[b][i] = inser++;
//最左边一列
for(int i = b-1; i > t; --i) res[i][l] = inser++;
//范围缩小一层
t++, b--, l++, r--;
if(b <= 0 || t > b) break;
}
return res;
}
};
第k个排列
解题思路，根据下一个排列算法的思想，循环k次得到结果
因为之前已经写过下一个排列的算法了，所以这次就直接用了库函数里面的next_permutation函数。
AC代码:
string getPermutation(int n, int k) {
string res;
for(int i = 1; i <= n; ++i) {
res += to_string(i);
}
for(int i = 0; i < k-1; ++i) next_permutation(res.begin(), res.end());
return res;
}
