一、贪心
题目描述
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<len;i++){
if(sum<0){
sum=0;
}
sum+=A[i];
if(sum>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<t;i++){
if(Math.abs(t-i)==Math.abs(map[t]-map[i])||map[i]==map[t]){
return false;
}
}
return true;
}
}
三、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<String[]> resList=new ArrayList<>();
public ArrayList<String[]> solveNQueens(int n) {
backtrack(1,n);
return resList;
}
public StringBuilder drawOneLine(int n){
StringBuilder sb=new StringBuilder();
for(int i=0;i<n;i++){
sb.append('.');
}
return sb;
}
public boolean valid(int t){
for(int i=1;i<t;i++){
if(Math.abs(mark[i]-mark[t])==Math.abs(i-t)||mark[i]==mark[t]){
return false;
}
}
return true;
}
public void backtrack(int t,int n){
if(t>n){
String [] tem=new String[n];
for(int i=0;i<n;i++){
StringBuilder line=drawOneLine(n);
line.setCharAt(mark[i+1]-1,'Q');//因为String从0开始而我的mark是从1开始记的
//这里下标有点乱：mark数组是从1开始的，而tem是从0开始的。
tem[i]=line.toString();
}
resList.add(tem);
}
else{
for(int i=1;i<=n;i++){
mark[t]=i;
if(valid(t)){
backtrack(t+1,n);
}
}
}
}
}
