原創公眾號：bigsai 希望和優秀的你做朋友，感覺不錯還請一鍵三連。
回復進群即可加入和200+人一起打卡。上周打卡：
LeetCode 47全排列Ⅱ&48旋轉圖像
LeetCode 49字母異位詞分組&50pow(x,n)&51八皇后

n皇后Ⅱ

n 皇后問題研究的是如何將 n 個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。

上圖為 8 皇后問題的一種解法。

給定一個整數 n，返回 n 皇后不同的解決方案的數量。

示例:

輸入: 4
輸出: 2
解釋: 4 皇后問題存在如下兩個不同的解法。

[[".Q..", // 解法 1"...Q","Q...","..Q."],["..Q.", // 解法 2"Q...","...Q",".Q.."] ]

提示：

皇后，是國際象棋中的棋子，意味著國王的妻子。皇后只做一件事，那就是“吃子”。當她遇見可以吃的棋子時，就迅速沖上去吃掉棋子。當然，她橫、豎、斜都可走一或 N-1 步，可進可退。（引用自 百度百科 - 皇后 ）

n皇后問題我想跟著我們打卡的鐵鐵們都應該刷爛了，核心思路就是模擬試探，典型的回溯算法，如果八皇后還不會的請看這篇：回溯算法 | 追憶那些年曾難倒我們的八皇后問題 。

對于本題和上一題相比略有區別之處，就是讓你輸出滿足條件的迷宮，這個也很容易啊，在執行回溯的時候維護一個字符型數組，滿足條件時候將字符數組。

實現代碼為：

boolean shu[];boolean zuoxie[];boolean youxie[];int count=0; public int totalNQueens(int n) {shu=new boolean[n];zuoxie=new boolean[n*2-1];youxie=new boolean[n*2-1];dfs(0,n);return count;}//行 map地圖private void dfs(int index,int n) {// TODO Auto-generated method stubif(index==n)//存入{count++;}else {for(int j=0;j<n;j++){if(!shu[j]&&!zuoxie[index+j]&&!youxie[index+(n-1-j)]){shu[j]=true;zuoxie[index+j]=true;youxie[index+(n-1-j)]=true;dfs(index+1, n);shu[j]=false;zuoxie[index+j]=false;youxie[index+(n-1-j)]=false; }}} }

至于還有用位運算0ms的方法待維護補充。

最大子序列和

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。

進階:

如果你已經實現復雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

使用dp的方法就是O(n)的方法。如果dp[i]表示以第i個結尾的最大序列和，而這個dp的狀態方程為：

dp[0]=a[0] dp[i]=max(dp[i-1]+a[i],a[i])

也不難解釋，如果以前一個為截至的最大子序列和大于0，那么就連接本個元素，否則本個元素就自立門戶。

實現代碼為：

public int maxSubArray(int[] nums) {int dp[]=new int[nums.length];int max=nums[0];dp[0]=nums[0];for(int i=1;i<nums.length;i++){dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);if(dp[i]>max)max=dp[i];}return max;}

至于分治算法，這題復雜度dp為O(n),分治為O(nlogn).并不算快，而分治主要運用遞歸的過程先分再和，如果當然函數為maxsub(int nums[],int left,int right)最大的可能在以下三種情況產生：

其中中間部分就是分別向左向右進行拓展取最大了。ac代碼為(2ms)：

public int maxSubArray(int[] nums) {int max=maxsub(nums,0,nums.length-1);return max; } int maxsub(int nums[],int left,int right) {if(left==right)return nums[left];int mid=(left+right)/2;int leftmax=maxsub(nums,left,mid);int rightmax=maxsub(nums,mid+1,right);int midleft=nums[mid];int midright=nums[mid+1];int team=0;for(int i=mid;i>=left;i--){team+=nums[i];if(team>midleft)midleft=team;}team=0;for(int i=mid+1;i<=right;i++){team+=nums[i];if(team>midright)midright=team;}int max=midleft+midright;//中間的最大值if(max<leftmax)max=leftmax;if(max<rightmax)max=rightmax;return max; }

螺旋矩陣

給定一個包含 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]

分析
本題是順時針返回矩陣中的所有數字，而大致有兩個方法。
法一用一個坐標點進行移動維護，右下左上四個方向循環，并且用boolean數組標記。最后返回輸出結果，當然這種方法我沒有實現因為比較麻煩。

法二數學方法
可以把矩形最外圈分成四份，每次可以根據數學規律找到數字。
如果最短的那邊是偶數沒啥問題：

但是如果是奇數的話需要特殊考慮最后的剩余情況：

具體怎么處理看個人，我這里是在循環之外特殊處理的。

具體代碼為：

public List<Integer> spiralOrder(int[][] matrix) {List<Integer>list=new ArrayList<Integer>();if(matrix==null||matrix.length==0)return list;int m=matrix.length;int n=matrix[0].length;int min=Math.min(m, n);int index;for( index=0;index<min/2;index++){for(int i=index;i<n-index-1;i++)//最上面{list.add(matrix[index][i]);}for(int i=index;i<m-index-1;i++){list.add(matrix[i][n-index-1]);}for(int i=n-index-1;i>index;i--){list.add(matrix[m-index-1][i]);}for(int i=m-index-1;i>index;i--){list.add(matrix[i][index]);}}if(min%2==1){for(int i=index;i<=n-index-1;i++)//最上面{list.add(matrix[index][i]);}for(int i=index+1;i<=m-index-1;i++){list.add(matrix[i][n-index-1]);}}return list;}

最后，給大家推薦一門挺好的數據結構與算法的視頻課程，老師語速較慢，適合1.5倍速。

總結

以上是生活随笔為你收集整理的LeetCode打卡 52八皇后Ⅱ53最大子序和54螺旋矩阵的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。