当前位置:网站首页>Leetcode question brushing (XI) -- sequential questions brushing 51 to 55
Leetcode question brushing (XI) -- sequential questions brushing 51 to 55
2022-07-06 22:14:00 【CAccept】
List of articles
51.N Queen
According to the rules of chess , The queen can attack the pieces on the same row, column or diagonal line .
n queens problem It's about how to make n A queen is placed in n×n On the chessboard , And keep the Queens from attacking each other .
Give you an integer n , Go back to all the different n queens problem Solutions for .
Each solution contains a different n queens problem The chess piece placement scheme of , The scenario ‘Q’ and ‘.’ They represent the queen and the vacant seat .
Example 1:
Input :n = 4
Output :[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
explain : As shown in the figure above ,4 There are two different solutions to the queen problem .
analysis : Since you want to keep every line , Each column , Only one queen can exist in two slashes , You can create multiple identities bool Array , We can put queens in every row, so we Just create an identification array for each column and slash
, For the column identification array, it is still very simple , And how to identify the slash identification array ? Look at the picture below :
Code :
class Solution {
public:
vector<vector<string>>res;
vector<bool>col,dg,udg;
vector<string>path;
int nt;
vector<vector<string>> solveNQueens(int n) {
nt = n;
path = vector<string>(n,string(n,'.'));
col = dg = udg =vector<bool>( n * 2);// Yes x+y So the maximum will not exceed 2*n
dfs(0);// The first 0 Line start search
return res;
}
void dfs(int u)
{
if(u == nt)
{
res.push_back(path);
return;
}
// Enumerate each column
for(int i = 0; i < nt; i++)
{
if(!col[i] && !dg[u - i + nt] && !udg[u + i])
{
col[i] = dg[u - i + nt] = udg[u + i]=true;
path[u][i]='Q';
dfs(u + 1);
// Restore the scene
col[i] = dg[u - i + nt] = udg[u + i] = false;
path[u][i]='.';
}
}
return;
}
};
52.N Queen II
n queens problem It's about how to make n A queen is placed in n × n On the chessboard , And keep the Queens from attacking each other . Give you an integer n , return n queens problem Number of different solutions
.
Example 1:
Input :n = 4
Output :2
explain : As shown in the figure above ,4 There are two different solutions to the queen problem .
analysis : The idea of this question is the same, but the required thing is the number of schemes , You can use the code above to return size Can , You can also use the following code .
Code :
class Solution {
public:
int nt;
vector<string>path;
vector<bool>st,udg,dg;
int totalNQueens(int n) {
nt = n;
path = vector<string> (nt,string( n , '.' ));
st = vector<bool> (n);
udg = dg = vector<bool>(n*2);
return dfs(0);
}
int dfs(int u)
{
if(u == nt) return 1;
int res = 0;
for(int i = 0; i < nt; i++)
{
if(!st[i] && !udg[u - i + nt] && !dg[u + i])
{
st[i] = udg[u - i + nt] = dg[u + i] = true;
res += dfs(u + 1);
// Restore the scene
st[i] = udg[u - i + nt] = dg[u + i] = false;
}
}
return res;
}
};
53. Maximum subarray and
Give you an array of integers nums
, Please find a continuous subarray with the largest sum ( A subarray contains at least one element ), Return to its maximum and . Subarray Is a continuous part of the array .
Example 1:
Input :nums = [-2,1,-3,4,-1,2,1,-5,4]
Output :6
explain : Continuous subarray [4,-1,2,1] And the biggest , by 6 .
analysis : This problem can be solved by dynamic programming, and the time complexity can be O(n)
、 The space complexity is O(1)
, The analysis idea is shown in the figure below :
Code :
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res = INT_MIN;
for(int i = 0, last = 0; i<nums.size(); i++)
{
last = nums[i] + max(last , 0);
res = max(res , last);
}
return res;
}
};
54. Spiral matrix
To give you one m That's ok n Columns of the matrix matrix , Please follow Clockwise spiral sequence
, Returns all elements in the matrix .
Example 1:
Input :matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output :[1,2,3,6,9,8,7,4,5]
analysis : When moving clockwise, the current (x,y) For mobile , We can set two offset arrays according to this to move , When moving, judge whether it is out of bounds or whether the element has been traversed , Here's the picture :
Code :
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
vector<int>res;
if(!matrix.size())return res;
vector<vector<bool>>st(n , vector<bool>(m));// Whether the status array has been traversed
// Offset array dx,dy
int dx[] = {
0 , 1 , 0 , -1};
int dy[] = {
1 , 0 , -1 , 0};
int a , b;
for(int i = 0 , x = 0 , y = 0, d = 0; i < n * m; i++)
{
res.push_back(matrix[x][y]);
st[x][y] = true;
a = dx[d] + x ,b = dy[d] + y;
if(a>=n||a<0||b>=m||b<0||st[a][b])
{
d = (d+1)%4;
a = dx[d] + x ,b = dy[d] + y;
}
x = a , y = b;
}
return res;
}
};
55. Jumping game
Given an array of nonnegative integers nums
, You're in the beginning of the array The first subscript . Each element in the array represents the maximum length you can jump at that location . Judge whether you can reach the last subscript .
Example 1:
Input :nums = [2,3,1,1,4]
Output :true
explain : You can jump first 1 Step , From the subscript 0 Reach subscript 1, And then from the subscript 1 jump 3 Step to the last subscript .
analysis : Through analysis , If we can jump to the k Then you can jump to k-1 This point , And so on , You can find that if you can jump to i This point , Then you can jump to 0—k-1, Similarly, if even 0—k-1 If you can't get there, you must not get there k A little bit .
Code :
class Solution {
public:
bool canJump(vector<int>& nums) {
for(int i = 0, j = 0; i < nums.size(); i++)
{
if (j < i) return false;// Explain that you can't reach the i A little bit
j = max(j , i + nums[i]);// take j And i+nums[i] Compare
}
return true;// Reach the last point , Description successful arrival
}
};
边栏推荐
- Realization of epoll reactor model
- HDU 2008 digital statistics
- [线性代数] 1.3 n阶行列式
- 2500 common Chinese characters + 130 common Chinese and English characters
- 新入职一家公司需要去实践和注意的内容
- [leetcode daily clock in] 1020 Number of enclaves
- Data processing skills (7): MATLAB reads the data in the text file TXT with mixed digital strings
- 设置状态栏样式Demo
- GPS du début à l'abandon (XIII), surveillance autonome de l'intégrité du récepteur (raim)
- 硬件開發筆記(十): 硬件開發基本流程,制作一個USB轉RS232的模塊(九):創建CH340G/MAX232封裝庫sop-16並關聯原理圖元器件
猜你喜欢
C # réalise la liaison des données du rapport Crystal et l'impression du Code à barres 4
GPS from entry to abandonment (XVII), tropospheric delay
CCNA-思科网络 EIGRP协议
3DMax指定面贴图
Seata aggregates at, TCC, Saga and XA transaction modes to create a one-stop distributed transaction solution
墨西哥一架飞往美国的客机起飞后遭雷击 随后安全返航
Reset Mikrotik Routeros using netinstall
C#實現水晶報錶綁定數據並實現打印4-條形碼
GPS从入门到放弃(十五)、DCB差分码偏差
RESNET rs: Google takes the lead in tuning RESNET, and its performance comprehensively surpasses efficientnet series | 2021 arXiv
随机推荐
Record the process of cleaning up mining viruses
414. The third largest digital buckle
墨西哥一架飞往美国的客机起飞后遭雷击 随后安全返航
GPS从入门到放弃(十五)、DCB差分码偏差
Management background --1 Create classification
GPS from entry to abandonment (XVII), tropospheric delay
Force buckle 575 Divide candy
Set status bar style demo
Method return value considerations
Oracle-控制文件及日志文件的管理
新入职一家公司需要去实践和注意的内容
[sciter bug] multi line hiding
MariaDB database management system learning (I) installation diagram
GNN, please deepen your network layer~
Data processing skills (7): MATLAB reads the data in the text file TXT with mixed digital strings
Unity3D学习笔记6——GPU实例化(1)
2021 geometry deep learning master Michael Bronstein long article analysis
HDR image reconstruction from a single exposure using deep CNNs阅读札记
【数字IC手撕代码】Verilog无毛刺时钟切换电路|题目|原理|设计|仿真
硬件開發筆記(十): 硬件開發基本流程,制作一個USB轉RS232的模塊(九):創建CH340G/MAX232封裝庫sop-16並關聯原理圖元器件