一、贪心

题目描述

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array[−2,1,−3,4,−1,2,1,−5,4],

the contiguous subarray[4,−1,2,1]has the largest sum =6.

click to show more practice.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

思路

贪心的基本思想就是局部找最优解，然后通过局部的最优解得出来的结果，就是全局的最优解，往往很难证明，但不妨先试一试。

就像这道题，因为要求的是最大的子串和，那显然负数是起到反作用的，所以如果当前和是负的，那就果断舍去，这也是贪心的思路。

这样的解法时间复杂度是O(n）题目中说明了，可以使用分治进一步优化，请看代码二。

代码一

public class Solution {    public int maxSubArray(int[] A) {        int len=A.length;        if(len==0){            return 0;        }        int sum=A[0];        int max=A[0];        for(int i=1;i
    
     max){                max=sum;            }        }        return max;    }}

代码二

public class Solution {        public int div(int [] A,int left,int right){            int mid=(left+right)/2;            if(left==right){                return A[left];            }            int max1=div(A,left,mid);            int max2=div(A,mid+1,right);            int max3=-999999;//这里不严谨，但不能用Integer.MIN_VALUE。            //否则max3+max4如果是负数和Integer.MIN_VALUE相加会溢出            int max4=-999999;            int tem=0;            for(int i=mid;i>=left;i--){                tem+=A[i];                max3=Math.max(max3,tem);            }            tem=0;            for(int i=mid+1;i<=right;i++){                tem+=A[i];                max4=Math.max(max4,tem);            }            return Math.max(Math.max(max1,max2),max3+max4);                }    public int maxSubArray(int[] A) {        int len=A.length;        if(len==0){            return 0;        }        return div(A,0,len-1);    }    }

二、N皇后问题

题目描述

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

思路

经典的老题目了，存储当然是用一个数组map解决：下标表示行号，每个map[i]中存放的数字表示列号。

然后就是写一个判断函数：1.判断行是否重复：这个不需要判定，因为数组下标即使行。2.判断列是否重复，即map[t]!=map[i]。3.判断对角线是否重复：即map[t]-map[i]!=t-i。

代码

public class Solution {    public int [] map=new int[30];    public int count=0;//注意！！不能写成public static int count=0;    //否则全局静态变量的话，内存地址是一个，    //也就是当前测试用例会受到上一个测试用例中count的影响    public int totalNQueens(int n) {        backtrack(1,n);        return count;    }    public void backtrack(int t,int n){        if(t>n){            count++;        }        else{            for(int i=1;i<=n;i++){                map[t]=i;                if(valid(t)){                    backtrack(t+1,n);                }            }        }    }    public boolean valid(int t){        for(int i=1;i

三、N皇后问题再度升级

题目描述

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where'Q'and'.'both indicate a queen and an empty space respectively.

For example,

There exist two distinct solutions to the 4-queens puzzle:

[ [".Q..",  // Solution 1  "...Q",  "Q...",  "..Q."], ["..Q.",  // Solution 2  "Q...",  "...Q",  ".Q.."]]

思路

和上一道只需要输出个数，这道题也需要把所有的图输出来。只需要改动一个地方就OK。具体的看代码，写的很清楚。

代码

import java.util.ArrayList;public class Solution {    public int [] mark=new int [30];    public int count=0;    public ArrayList
    
      resList=new ArrayList<>();    public ArrayList
     
       solveNQueens(int n) {        backtrack(1,n);        return resList;    }    public StringBuilder drawOneLine(int n){        StringBuilder sb=new StringBuilder();        for(int i=0;i
      
       n){            String [] tem=new String[n];            for(int i=0;i