Week 06 - Leetcode 51 - 60
51 - N皇后
+ DFS每一行必定且仅会出现一个皇后，所以按行枚举出现的位置，并用col[n], dg[n], udg[n] 记录列， 主对角线， 副对角线是否已经出现过皇后即可；
class Solution {
public:
int n;
vector<vector<string>> res;
vector<string> path;
vector<bool> col, dg, udg;
public:
vector<vector<string>> solveNQueens(int n) {
this->n = n;
// DFS - 回溯 + 剪枝
// 按行枚举 用bool数组记录 列 主斜线 副斜线
col = vector<bool>(n);
dg = vector<bool>(2 * n);
udg = vector<bool>(2 * n);
string p(n, '.');
path = vector<string>(n, p);
dfs(0);
//cout << p << endl;
return res;
}
void dfs(int u)
{
if(u == n)
res.push_back(path);
else
{
for(int i = 0; i < n; i++)
{
if(!col[i] && !dg[i + u] && !udg[n + i - u])
{
col[i] = dg[i + u] = udg[n + i - u] = true;
path[u][i] = 'Q';
dfs(u + 1);
col[i] = dg[i + u] = udg[n + i - u] = false;
path[u][i] = '.';
}
}
}
}
};52 - N皇后II
可以说和上面那个题一模一样了；
class Solution {
public:
int n, res;
vector<string> path;
vector<bool> col, dg, udg;
public:
int totalNQueens(int n) {
this->n = n;
// DFS - 回溯 + 剪枝
// 按行枚举 用bool数组记录 列 主斜线 副斜线
col = vector<bool>(n);
dg = vector<bool>(2 * n);
udg = vector<bool>(2 * n);
string p(n, '.');
path = vector<string>(n, p);
dfs(0);
//cout << p << endl;
return res;
}
void dfs(int u)
{
if(u == n)
res++;
else
{
for(int i = 0; i < n; i++)
{
if(!col[i] && !dg[i + u] && !udg[n + i - u])
{
col[i] = dg[i + u] = udg[n + i - u] = true;
path[u][i] = 'Q';
dfs(u + 1);
col[i] = dg[i + u] = udg[n + i - u] = false;
path[u][i] = '.';
}
}
}
}
};53 - 最大子序和
动态规划 f[i]表示已为结尾的连续子数组的最大和； f[i] = max(f[i - 1] + w[i], w[i]);
仅用到上一个状态 -> 空间优化；
class Solution {
public:
int maxSubArray(vector<int>& nums) {
//vector<int> f(nums.size() + 1, 0);
int res = INT_MIN, f = 0;
for(int i = 1; i <= nums.size(); i++)
{
f = max(f + nums[i - 1], nums[i - 1]);
res = max(res, f);
}
return res;
}
};54 - 螺旋矩阵
+ 模拟 (偏移量)经典问题了 在各种地方都出现过(x)
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
int n = matrix.size();
if(!n) return res;
int m = matrix[0].size();
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
bool st[n][m];
memset(st, false, sizeof st);
for(int i = 0, x = 0, y = 0, d = 0; i < n * m; i++)
{
res.push_back(matrix[x][y]);
st[x][y] = true;
int a = x + dx[d], b = y + dy[d];
if(a < 0 || a >= n || b < 0 | b >= m || st[a][b])
{
d = (d + 1) % 4;
a = x + dx[d], b = y + dy[d];
}
x = a, y = b;
}
return res;
}
};55 - 跳跃游戏
和第四十五题（跳跃游戏ii） 很像， 代码也差不多 无非是从记录步数 到记录能否跳到的bool值
class Solution {
public:
bool canJump(vector<int>& nums) {
vector<bool> f(nums.size());
f[0] = true;
for(int i = 1, j = 0; i < nums.size(); i++)
{
while(j + nums[j] < i) j++;
f[i] = f[i] || f[j];
}
return f[nums.size() - 1];
}
};56 - 合并区间
+ 双指针算法经典题型了。。 又忘记了复习一下
按照start 给所有区间排序
枚举每个区间 比较最开始的end 和下一个区间的start 是否重叠；
重叠就合并
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
// 双指针模板题
// 1. 按照end排序
vector<vector<int>> res;
if(intervals.empty()) return res;
sort(intervals.begin(), intervals.end());
// 2. 双指针遍历；
int st = -2e9, ed = -2e9;
for(vector<int>& interval : intervals)
{
if(ed < interval[0])
{
if(st != -2e9) res.push_back({st, ed});
st = interval[0], ed = interval[1];
}
else
{
ed = max(ed, interval[1]);
}
}
if(st != -2e9) res.push_back({st, ed});
return res;
}
};57 - 插入区间
更像是模拟题：找到有交集的那一小段区间合并，剩下的维持原样；
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int st = newInterval[0], ed = newInterval[1], si = -1, ei = -1;
for(int i = 0; i < intervals.size(); i++)
{
if(intervals[i][1] < st)
continue;
else
{
ei = si = i;
st = min(st, intervals[i][0]);
while(ei < intervals.size() && ed >= intervals[ei][0])
ed = max(ed, intervals[ei][1]), ei++;
break;
}
}
// 注意边界问题
if(si != -1)
{
// 有交集的中间直接删掉
intervals.erase(intervals.begin() + si, intervals.begin() + ei);
// 插入合并后的新区间
intervals.insert(intervals.begin() + si, {st, ed});
}
else
{
// 没找到有交集的 直接插在最后即可
intervals.push_back(newInterval);
}
return intervals;
}
};58 - 最后一个单词的长度
stringstream 的应用： 把字符串变成流 常用于带空格的字符串拆分；
class Solution {
public:
int lengthOfLastWord(string s) {
stringstream ss(s);
string word;
int res = 0;
while(ss >> word)
res = word.size();
return res;
}
};实际上 就是找到最后的字符串就可以了 用一个指针去找: 模拟；
class Solution {
public:
int lengthOfLastWord(string s) {
int i = s.size() - 1, res = 0;
while(i >= 0)
{
if(s[i] == ' ')
{
if(res != 0) break;
} else {
res++;
}
i--;
}
return res;
}
};59 - 螺旋矩阵II
和54 螺旋矩阵 差不多 都是定义偏移量往里写就好了
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n, vector<int>(n, 0));
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
int x = 0, y = 0, d = 0;
for(int i = 1; i <= n * n; i++)
{
int a = x + dx[d], b = y + dy[d];
if(a < 0 || a >= n || b < 0 || b >= n || res[a][b] != 0)
{
d = (d + 1) % 4;
a = x + dx[d], b = y + dy[d];
}
res[x][y] = i;
x = a, y = b;
}
return res;
}
};60 - 排序序列
+ 计数DP利用语法 next_permutation 也能过了 但是复杂度高
class Solution {
public:
string getPermutation(int n, int k) {
vector<int> res;
for(int i = 1; i <= n; i++)
res.push_back(i);
while(--k)
next_permutation(res.begin(), res.end());
stringstream ss;
for(int x : res)
ss << x;
return ss.str();
}
};计数DP
class Solution {
public:
string getPermutation(int n, int k) {
stringstream ss;
vector<int> fact(n + 1, 1);
vector<bool> st(10);
// 计算阶乘
for(int i = 1; i <= n; i++)
fact[i] = fact[i - 1] * i;
for(int i = 0; i < n; i++)
{
int f = fact[n - i - 1];
for(int j = 1; j <= n; j++)
{
if(!st[j])
{
if(f < k) k -= f;
else
{
ss << j;
st[j] = true;
break;
}
}
}
}
return ss.str();
}
};Last updated
