51. N 皇后

date:2024-12-1 tag:回溯

题解

这道题一行一行地放置皇后,尝试在每一列放置皇后,放置前用isValid判断这个位置是否可以放置。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>>res;
vector<string>board(n,string(n,'.'));
backtrack(res,board,0,n);
return res;
}
private:
void backtrack(vector<vector<string>>&res,vector<string>&board,int row,int n){
if(row==n){//表示放置足够数目的皇后
res.push_back(board);
return;
}
for(int col=0;col<n;col++){
if(isValid(board,row,col,n)){
board[row][col]='Q';
backtrack(res,board,row+1,n);
board[row][col]='.';//撤回操作
}
}
}
bool isValid(vector<string>&board,int row,int col,int n){
for(int i=0;i<row;i++){//同列是否合法
if(board[i][col]=='Q'){
return false;
}
}
for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
if(board[i][j]=='Q'){//左上角是否合法
return false;
}
}
for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){
if(board[i][j]=='Q'){//右上角是否合法
return false;
}
}
return true;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
func solveNQueens(n int) [][]string {
res:=[][]string{}
board:=make([][]byte,n)
for i,_:=range board{
board[i]=make([]byte,n)
for j,_:=range board[i]{
board[i][j]='.'
}
}
backtrack(&res,board,0,n)
return res
}
func backtrack(res *[][]string,board [][]byte,row int,n int){
if row==n{
solution := make([]string, n)
for i := range board {
solution[i] = string(board[i])
}
*res = append(*res, solution)
return
}
for col:=0;col<n;col++{
if isValid(board,row,col,n){
board[row][col]='Q'
backtrack(res,board,row+1,n)
board[row][col]='.'
}
}
}
func isValid(board [][]byte,row int,col int,n int)bool{
for i:=0;i<n;i++{
if board[i][col]=='Q'{
return false
}
}
for i,j:=row-1,col+1;i>=0&&j<n;i,j=i-1,j+1{
if board[i][j]=='Q'{
return false
}
}
for i,j:=row-1,col-1;i>=0&&j>=0;i,j=i-1,j-1{
if board[i][j]=='Q'{
return false
}
}
return true
}

52. N 皇后 II

date:2024-12-2 tag:回溯

题解

位运算

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func totalNQueens(n int) int {
return solve(n,0,0,0,0)
}
func solve(n int,row int,col int,diag1 int,diag2 int)int{
if row==n{
return 1
}
count:=0
for c:=0;c<n;c++{
currCol:=1<<c
currDiag1:=1<<(row+c)
currDiag2:=1<<(row-c+n-1)
if (col & currCol == 0) && // 列无冲突
(diag1 & currDiag1 == 0) && // 正对角线无冲突
(diag2 & currDiag2 == 0) { // 反对角线无冲突

count += solve(n, row+1,
col | currCol, // 标记列已占用
diag1 | currDiag1, // 标记正对角线
diag2 | currDiag2) // 标记反对角线
}
}
return count
}

3274. 检查棋盘方格颜色是否相同

date:2024-12-3

题解

都转化成数字,通过差值的奇偶性判断颜色。

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
bool checkTwoChessboards(string coordinate1, string coordinate2) {
int s1=(coordinate1[0]-'a')-(coordinate2[0]-'a');
int s2=(coordinate1[1]-'0')-(coordinate2[1]-'0');
if((s1%2+s2%2)%2==0){
return true;
}
return false;
}
};
1
2
3
4
5
6
7
8
func checkTwoChessboards(coordinate1 string, coordinate2 string) bool {
s1:=(coordinate1[0]-'a')-(coordinate2[0]-'a')
s2:=(coordinate1[1]-'0')-(coordinate2[1]-'0')
if (s1%2+s2%2)%2==0{
return true
}
return false
}

560. 和为 K 的子数组

date:2024-12-4

题解

使用前缀和加哈希表的方式解题,用哈希表存储前缀和出现的次数,初始化0为1次,
遍历数组,记录当前的前缀和prefixsum,在哈希表中寻找是否有prefisxum-k的前缀和,找到则说明找到了和为K的子数组。
每次遍历将当前前缀和加入到哈希表中,
最后返回结果count

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int,int>prefixsumcount;
prefixsumcount[0]=1;
int count=0,prefixsum=0;
for(auto num:nums){
prefixsum+=num;
if(prefixsumcount.count(prefixsum-k)){
count+=prefixsumcount[prefixsum-k];
}
prefixsumcount[prefixsum]++;
}
return count;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func subarraySum(nums []int, k int) int {
prefixsumcount:=make(map[int]int)
prefixsumcount[0]=1
prefixsum:=0
count:=0
for _,num:=range nums{
prefixsum+=num
if val,exists:=prefixsumcount[prefixsum-k];exists{
count+=val
}
prefixsumcount[prefixsum]++
}
return count
}

3001. 捕获黑皇后需要的最少移动次数

date:2024-12-5

题解

结果只有两种车走两步,或者象和车走一步。重点是找到走一步的情况。
一步的情况:车和皇后在同一行或同一列,且中间没有象。
象直接攻击到皇后,中间没有车。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
func inBetween(l, m, r int) bool {
return min(l, r) < m && m < max(l, r)
}

func minMovesToCaptureTheQueen(a, b, c, d, e, f int) int {
if a == e && (c != e || !inBetween(b, d, f)) || // 车直接攻击到皇后(同一行)
b == f && (d != f || !inBetween(a, c, e)) || // 车直接攻击到皇后(同一列)
c+d == e+f && (a+b != e+f || !inBetween(c, a, e)) || // 象直接攻击到皇后
c-d == e-f && (a-b != e-f || !inBetween(c, a, e)) {
return 1
}
return 2
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int minMovesToCaptureTheQueen(int a, int b, int c, int d, int e, int f) {
if(
a==e&&(c!=e||!isBetween(b,d,f))||
b==f&&(d!=f||!isBetween(a,c,e))||
c+d==e+f&&(a+b!=e+f||!isBetween(c,a,e))||
c-d==e-f&&(a-b!=e-f||!isBetween(c,a,e))
){
return 1;
}
return 2;
}
bool isBetween(int l,int m,int r){
return min(l,r)<m&&m<max(l,r);
}
};

999. 可以被一步捕获的棋子数

date:2024-12-6

题解

见代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
func numRookCaptures(board [][]byte) int {
// 找到白车的位置
var rr, rc int
found := false
for r := 0; r < 8; r++ {
for c := 0; c < 8; c++ {
if board[r][c] == 'R' {
rr, rc = r, c
found = true
break
}
}
if found {
break
}
}

// 4个方向: 上、下、左、右
directions := [][]int{{-1,0}, {1,0}, {0,-1}, {0,1}}
captures := 0

// 遍历4个方向
for _, dir := range directions {
r, c := rr, rc
for {
r += dir[0]
c += dir[1]

// 超出棋盘边界
if r < 0 || r >= 8 || c < 0 || c >= 8 {
break
}

// 遇到白象,阻挡
if board[r][c] == 'B' {
break
}

// 遇到黑卒,计数并结束该方向
if board[r][c] == 'p' {
captures++
break
}
}
}

return captures
}

688. 骑士在棋盘上的概率

date:2024-12-7 tag:动态规划

题解

创建三维动态规划数组,dp[k][n][n],k表示移动步数,n和n表示当前的位置,初始化当前位置dp[0][row][column]概率为1
动态规划计算moves表示移动步数,r和c表示在棋盘的概率

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func knightProbability(n int, k int, row int, column int) float64 {
directions := [][]int{
{-2, -1}, {-1, -2}, {1, -2}, {2, -1},
{-2, 1}, {-1, 2}, {1, 2}, {2, 1},
}
dp := make([][][]float64, k+1)
for i := range dp {
dp[i] = make([][]float64, n)
for j := range dp[i] {
dp[i][j] = make([]float64, n)
}
}
dp[0][row][column] = 1.0
for moves := 1; moves <= k; moves++ {
for r := 0; r < n; r++ {
for c := 0; c < n; c++ {
for _, dir := range directions {
prevC := c - dir[1]
prevR := r - dir[0]
//检查是否在棋盘内
if prevR >= 0 && prevR < n && prevC >= 0 && prevC < n {
dp[moves][r][c] += dp[moves-1][prevR][prevC] / 8.0
}
}

}
}
}
var res float64
for r := 0; r < n; r++ {
for c := 0; c < n; c++ {
res += dp[k][r][c]
}
}
return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
double knightProbability(int n, int k, int row, int column) {
vector<pair<int,int>>directions{
{-2, -1}, {-1, -2}, {1, -2}, {2, -1},
{-2, 1}, {-1, 2}, {1, 2}, {2, 1},
};
vector<vector<vector<double>>>dp(k+1,vector<vector<double>>(n,vector<double>(n,0.0)));
dp[0][row][column]=1.0;
for(int moves=1;moves<=k;moves++){
for(int r=0;r<n;r++){
for(int c=0;c<n;c++){
for(auto dir:directions){
int prevR=r-dir.first;
int prevC=c-dir.second;
if(prevR>=0&&prevR<n&&prevC>=0&&prevC<n){
dp[moves][r][c]+=dp[moves-1][prevR][prevC]/8.0;
}
}
}
}
}
double res=0.0;
for(int r=0;r<n;r++){
for(int c=0;c<n;c++){
res+=dp[k][r][c];
}
}
return res;
}
};

931. 下降路径最小和

date:2024-12-8 tag:动态规划

题解

创建与矩阵相同的动态规划数组
从第二行开始,找到移动前左上角,右上角,正上方的最小值,加入到移动后的动态规划数组中
最后返回最后一行的最小值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
int n=matrix.size();
vector<vector<int>>dp=matrix;
for(int r=1;r<n;r++){
for(int c=0;c<n;c++){
int minVal=INT_MAX;
if(c>0){
minVal=min(minVal,dp[r-1][c-1]);
}
minVal=min(minVal,dp[r-1][c]);
if(c<n-1){
minVal=min(minVal,dp[r-1][c+1]);
}
dp[r][c]+=minVal;
}
}
return *min_element(dp[n-1].begin(),dp[n-1].end());
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
func minFallingPathSum(matrix [][]int) int {
n:=len(matrix)
dp:=make([][]int,n)
for i:=range dp{
dp[i]=make([]int,n)
copy(dp[i],matrix[i])
}
for r:=1;r<n;r++{
for c:=0;c<n;c++{
minVal:=math.MaxInt32
if c>0{
minVal=min(minVal,dp[r-1][c-1])
}
minVal=min(minVal,dp[r-1][c])
if c<n-1{
minVal=min(minVal,dp[r-1][c+1])
}
dp[r][c]+=minVal
}
}
return findminslice(dp[n-1])
}
func min(a,b int)int{
if a>b{
return b
}
return a
}
func findminslice(slice []int)int{
if len(slice)==0{
return 0
}
min:=slice[0]
for _,val:=range slice{
if val<min{
min=val
}
}
return min
}

1812. 判断国际象棋棋盘中一个格子的颜色

date:2024-12-9

题解

怎么又是棋盘

代码

1
2
3
4
5
6
class Solution {
public:
bool squareIsWhite(string coordinates) {
return ((coordinates[0] - 'a' + 1) + (coordinates[1] - '0')) % 2 == 1;
}
};

71. 简化路径

date:2024-12-10

题解

使用strings.Split()分割路径,将字符串按照分隔符转换成字符串切片,
使用切片模拟栈
使用strings.Join()构建路径字符串,将字符串切片按照分隔符连成一个字符串。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func simplifyPath(path string) string {
stack:=[]string{}
dirs:=strings.Split(path,"/")
for _,dir:=range dirs{
if dir==""||dir=="."{
continue
}
if dir==".."{
if len(stack)>0{
stack=stack[:len(stack)-1]
}
continue
}
stack=append(stack,dir)
}
return "/"+strings.Join(stack,"/")
}

2717. 半有序排列

date:2024-12-11

题解

先找到1和n的位置,如果1在n的前面,正常计算,如果1在n的后面,减少一次计算。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int semiOrderedPermutation(vector<int>& nums) {
int n = nums.size();
int pos1 = -1, posn = -1;
for (int i = 0; i < n; i++) {
if (nums[i] == 1) pos1 = i;
if (nums[i] == n) posn = i;
}

if (pos1 < posn) {
return pos1 + (n - 1 - posn);
}
else {
return pos1 + (n - 1 - posn) - 1;
}
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func semiOrderedPermutation(nums []int) int {
n := len(nums)
pos1, posn := -1, -1
for i := 0; i < n; i++ {
if nums[i] == 1 {
pos1 = i
}
if nums[i]==n{
posn=i
}
}
if pos1 < posn {
return pos1 + (n - 1 - posn)
} else {
return pos1 + (n - 1 - posn) - 1
}
}

2931. 购买物品的最大开销

date:2024-12-12

题解

将价值低的先使用,价值高的最后使用可以得到最大总开销。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
long long maxSpending(vector<vector<int>>& values) {
int m=values.size(),n=values[0].size();
vector<int>nums;
nums.reserve(m*n);
for(auto value:values){
nums.insert(nums.begin(),value.begin(),value.end());
}
sort(nums.begin(),nums.end());
long long res=0;
for(int i=0;i<m*n;i++){
res+=(long long)nums[i]*(i+1);
}
return res;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

func maxSpending(values [][]int) int64 {
m,n:=len(values),len(values[0])
nums:=make([]int,0,m*n)
for _,value:=range values{
nums=append(nums,value...)
}
slices.Sort(nums)
var res int64=0
for i:=0;i<m*n;i++{
res += int64(nums[i]) * int64(i+1)
}
return res
}

3264. K 次乘运算后的最终数组 I

date:2024-12-13

题解

遍历找到最下元素,原地修改。

代码

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
for(int i=0;i<k;i++){
int minIndex=min_element(nums.begin(),nums.end())-nums.begin();
nums[minIndex]*=multiplier;
}
return nums;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
func getFinalState(nums []int, k int, multiplier int) []int {
for i:=0;i<k;i++{
minIndex:=0;
for j:=range nums{
if nums[j]<nums[minIndex]{
minIndex=j
}
}
nums[minIndex]*=multiplier
}
return nums
}

date:2024-12-14

题解

代码

1338. 数组大小减半

date:2024-12-15

题解

使用哈希表统计 数字出现的次数,
将频率存入优先队列,removed代表当前删除的数字个数,setSize表示要删除的具体数字个数,

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int minSetSize(vector<int>& arr) {
unordered_map<int,int>map;
for(auto value:arr){
map[value]++;
}
priority_queue<int> pq;
for(auto &[num,count]:map){
pq.push(count);
}
int removed=0,setSize=0,halfLength=arr.size()/2;
while(removed<halfLength){
removed+=pq.top();
setSize++;
pq.pop();
}
return setSize;
}
};