專欄——LeetCode
文章目錄
- 專欄——LeetCode
- 51. N 皇后
- 52. N皇后 II
- 53. 最大子序和
- 54. 螺旋矩陣
- 55. 跳躍游戲
51. N 皇后
n 皇后問題研究的是如何將 n 個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊，
上圖為 8 皇后問題的一種解法，
給定一個整數 n，回傳所有不同的 n 皇后問題的解決方案，
每一種解法包含一個明確的 n 皇后問題的棋子放置方案，該方案中 ‘Q’ 和 ‘.’ 分別代表了皇后和空位，
示例：
輸入：4
輸出：[
[".Q…", // 解法 1
“…Q”,
“Q…”,
“…Q.”],
["…Q.", // 解法 2
“Q…”,
“…Q”,
“.Q…”]
]
解釋: 4 皇后問題存在兩個不同的解法，
提示：
皇后彼此不能相互攻擊，也就是說：任何兩個皇后都不能處于同一條橫行、縱行或斜線上，
題解：
(暴力搜索) O(n!)
暴力搜索所有方案，
為了優化時間效率，定義 vectorrow, col, diag, anti_diag;，用來記錄每一行、每一列、每條對角線上是否有皇后存在，
搜索時需要記錄4個狀態：x,y,s,nx,y,s,n，分別表示橫縱坐標、已擺放的皇后個數、棋盤大小，
對于每步搜索，有兩種選擇：
當前格子不放皇后，則轉移到 dfs(x, y + 1, s, n);
如果 (x,y)(x,y) 所在的行、列、對角線不存在皇后，則當前格子可以擺放皇后，更新row, col, diag,anti_diag后
轉移到 dfs(x, y + 1, s + 1, n);，回溯時不要忘記恢復row, col, diag, anti_diag等狀態，
c++版
class Solution {
public:
vector<string> path;
vector<vector<string>> ans;
vector<bool> row, col, d, fd;
vector<vector<string>> solveNQueens(int n) {
path = vector<string> (n, string(n, '.'));
row = col = vector<bool> (n, false);
d = fd = vector<bool> (2*n, false);
dfs(0, 0, 0, n);
return ans;
}
void dfs(int x, int y, int s, int n){
if(y == n)x++, y = 0;
if(x == n){
if(s == n)
ans.push_back(path);
return ;
}
dfs(x, y + 1, s, n);
if(!row[x] && !col[y] && !d[x + y] && !fd[n - 1 - x + y]){
row[x] = col[y] = d[x + y] = fd[n - 1 - x + y] = true;
path[x][y] = 'Q';
dfs(x, y + 1, s + 1, n);
path[x][y] = '.';
row[x] = col[y] = d[x + y] = fd[n - 1 - x + y] = false;
}
}
};
python版
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
row = [False] * n
col = [False] * n
d = [False] * 2 * n
fd = [False] * 2 * n
ans = []
path = []
path = [['.' for _ in range(n)] for _ in range(n)]
def dfs(x, y, s, n):
if y == n:
x += 1
y = 0
if x == n:
if(s == n):
l = []
for i in path:
l.append(''.join(i))
ans.append(l)
return
dfs(x, y + 1, s, n)
if not row[x] and not col[y] and not d[x + y] and not fd[n - 1 - x + y]:
row[x] = True
col[y] = True
d[x + y] = True
fd[n - 1 - x + y] = True
path[x][y] = 'Q'
dfs(x, y + 1, s + 1, n)
row[x] = False
col[y] = False
d[x + y] = False
fd[n - 1 - x + y] = False
path[x][y] = '.'
dfs(0, 0, 0, n)
return ans
52. N皇后 II
n 皇后問題研究的是如何將 n 個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊，
上圖為 8 皇后問題的一種解法，
給定一個整數 n，回傳 n 皇后不同的解決方案的數量，
示例:
輸入: 4
輸出: 2
解釋: 4 皇后問題存在如下兩個不同的解法，
[
[".Q…", // 解法 1
“…Q”,
“Q…”,
“…Q.”],
["…Q.", // 解法 2
“Q…”,
“…Q”,
“.Q…”]
]
提示：
皇后，是國際象棋中的棋子，意味著國王的妻子，皇后只做一件事，那就是“吃子”，當她遇見可以吃的棋子時，就迅速沖上去吃掉棋子，當然，她橫、豎、斜都可走一或 N-1 步，可進可退，（參考自 百度百科 - 皇后 ）
題解：
此題解法和上一題 完全相同，只是將記錄方案，改成記錄方案數，
c++版
class Solution {
public:
int ans = 0;
vector<bool> row, col, d, fd;
int totalNQueens(int n) {
row = col = vector<bool> (n, false);
d = fd = vector<bool> (2*n, false);
dfs(0, 0, 0, n);
return ans;
}
void dfs(int x, int y, int s, int n){
if(y == n)x++, y = 0;
if(x == n){
if(s == n)
ans ++;
return ;
}
dfs(x, y + 1, s, n);
if(!row[x] && !col[y] && !d[x + y] && !fd[n - 1 - x + y]){
row[x] = col[y] = d[x + y] = fd[n - 1 - x + y] = true;
dfs(x, y + 1, s + 1, n);
row[x] = col[y] = d[x + y] = fd[n - 1 - x + y] = false;
}
}
};
python版
class Solution:
def totalNQueens(self, n: int) -> int:
self.ans = 0
row = [False] * n
col = [False] * n
d = [False] * 2 * n
fd = [False] * 2 * n
def dfs(x, y, s, n):
if y == n:
x += 1
y = 0
if x == n:
if(s == n):
self.ans += 1
return
dfs(x, y + 1, s, n)
if not row[x] and not col[y] and not d[x + y] and not fd[n - 1 - x + y]:
row[x] = True
col[y] = True
d[x + y] = True
fd[n - 1 - x + y] = True
dfs(x, y + 1, s + 1, n)
row[x] = False
col[y] = False
d[x + y] = False
fd[n - 1 - x + y] = False
dfs(0, 0, 0, n)
return self.ans
53. 最大子序和
給定一個整數陣列 nums ，找到一個具有最大和的連續子陣列（子陣列最少包含一個元素），回傳其最大和，
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續子陣列 [4,-1,2,1] 的和最大，為 6，
題解：
動態規劃 O(n)
1.設 f(i) 表示以第 i 個數字為結尾的最大連續子序列的 總和 是多少，
2.初始化 f(0)=nums[0]，
3.轉移方程 f(i)=max(f(i?1)+nums[i],nums[i])，可以理解為當前有兩種決策，一種是將第 i 個數字和前邊的數字拼接起來；
另一種是第 i 個數字單獨作為一個新的子序列的開始，
4.最終答案為 ans=max(f(k)),0≤k<n，
c++版
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ans = nums[0];
int n = nums.size();
vector<int> f(n);
f[0] = nums[0];
for(int i = 1; i < n; i++){
f[i] = max(f[i - 1] + nums[i], nums[i]);
ans = max(ans, f[i]);
}
return ans;
}
};
python版
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
f = [0 for _ in range(n)]
ans = nums[0]
f[0] = nums[0]
for i in range(1, n):
f[i] = max(f[i - 1] + nums[i], nums[i])
ans = max(ans, f[i])
return ans
54. 螺旋矩陣
給定一個包含 m x n 個元素的矩陣（m 行, n 列），請按照順時針螺旋順序，回傳矩陣中的所有元素，
示例 1:
輸入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
輸出: [1,2,3,6,9,8,7,4,5]
示例 2:
輸入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
輸出: [1,2,3,4,8,12,11,10,9,5,6,7]
題解：
(模擬) O(nm)
定義四個方向的常數方向陣列 dir，不妨假設 0 表示方向為向右，1 為向下，2 為向左，3 為向上，
定義二維陣列 vis，代表該位置是否被訪問過，
從坐標 (0, 0) 開始，初始方向為 0，
每次遍歷后列舉下一個可行的方向是哪個，可行是指下一個位置沒有被訪問過，如果四個方向都不可行，則遍歷結束，
c++版
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> ans;
int n = matrix.size();
if (!n) return ans;
int m = matrix[0].size();
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
vector<vector<bool>> vis(n, vector<bool>(m));
for(int i = 0, x = 0, y = 0, d = 0; i < m * n; i++){
ans.push_back(matrix[x][y]);
vis[x][y] = true;
int a = x + dx[d];
int b = y + dy[d];
if(a < 0 || a >= n || b < 0 || b >= m || vis[a][b]){
d++;
d %= 4;
a = x + dx[d];
b = y + dy[d];
}
x = a;
y = b;
}
return ans;
}
};
python版
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
ans = []
n = len(matrix)
if not n:
return ans
m = len(matrix[0])
vis = [[False for _ in range(m)] for _ in range(n)]
x = 0
y = 0
d = 0
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
for i in range(n*m):
ans.append(matrix[x][y])
vis[x][y] = True
a = x + dx[d]
b = y + dy[d]
if a < 0 or a >= n or b < 0 or b >= m or vis[a][b]:
d += 1
d %= 4
a = x + dx[d]
b = y + dy[d]
x = a
y = b
return ans
55. 跳躍游戲
給定一個非負整數陣列，你最初位于陣列的第一個位置，
陣列中的每個元素代表你在該位置可以跳躍的最大長度，
判斷你是否能夠到達最后一個位置，
示例 1:
輸入: [2,3,1,1,4]
輸出: true
解釋: 我們可以先跳 1 步，從位置 0 到達 位置 1, 然后再從位置 1 跳 3 步到達最后一個位置，
示例 2:
輸入: [3,2,1,0,4]
輸出: false
解釋: 無論怎樣，你總會到達索引為 3 的位置，但該位置的最大跳躍長度是 0 ， 所以你永遠不可能到達最后一個位置，
c++版
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
int last = 0;
for(int i = 1; i < n; i++){
while(last < i && i > last + nums[last])
last++;
if(last == i) return false;
}
return true;
}
};
python版
class Solution:
def canJump(self, nums: List[int]) -> bool:
n = len(nums)
last = 0
for i in range(1, n):
while last < i and i > last + nums[last]:
last += 1
if last == i:
return False
return True
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/68015.html
標籤：其他
上一篇：【詳細】Python基礎（一）