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 }
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 }
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 }
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 }
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); } };
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 } } directions := [][]int {{-1 ,0 }, {1 ,0 }, {0 ,-1 }, {0 ,1 }} captures := 0 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 }
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; } };
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 }
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 ; } };
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,"/" ) }
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 } }
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 }
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
题解 代码 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; } };