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 stub if(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; }
