读书笔记之《程序员代码面试指南（数组和矩阵问题）》 未排序正整数数组中累加和为给定值的最长子数组长度 数组partition调整使数组的左部分单调有序 将正方形矩阵顺时针转动90度 找到无序数组中最小的K个数 三数排序 转圈打印矩阵 "之"字形打印矩阵 自然数数组的排序 奇数下标都是奇数或偶数下标都是偶数 子数组的最大累加和问题 子矩阵的最大累计和问题 在数组中找到一个局部最小的位置 不包含本位置值的累乘数组 求最短通路值 最长的可整合数组的长度 边界都是1的最大正方形大小 需要排序的最短子数组长度
数组和矩阵问题，这些做得比较多。
package Array;
/**
* Created by zdmein on 2017/8/30.
*未排序正整数数组中累加和为给定值的最长子数组长度
* 给定一个无需数组arr,其中元素为正，给定一个整数k。求arr的所有子数组中累加和为k的最长子数组的长度。
* arr=[1,2,1,1,1],k=3
* 结果返回3
*/
public class getMaxLength1 {
public static void main(String [] args){
int [] arr={1,2,1,1,1};
int k=3;
System.out.println(getMaxLength(arr,k));
}
public static int getMaxLength(int [] arr ,int k){
if(arr==null||arr.length<0||k<0){
return 0;
}
int right =0;
int left=0;
int len=0;
int sum=arr[0];
while (right<arr.length){
if(sum==k){
len=Math.max(len,right-left+1);
sum-=arr[left++];
}else if(sum<k){
right++;
if(right==arr.length){
break;
}
sum+=arr[right];
}else {
sum-=arr[left++];
}
}
return len;
}
}
数组partition调整使数组的左部分单调有序
给定一个有序数组arr，调整使得数组的左部分无重复元素且有序，右边部分不要求。如数组arr[]={1,2,2,2,3,3,4,5,6,9,9} ;调整过后可以为：[1, 2, 3, 4, 5, 6, 9, 2, 3, 2, 9] 。
思路：使用标记 u 其中arr[0…u] 表示已经处理过的没有重复元素且有序的区间，从arr[u+1…i-1]表示有重复元素的部分。则算法主要分为下面两部分。
1. 比较 arr[i] 与 arr[u] 是否相同如果不同，则将 arr[i] 的值赋给arr[u+1],u++;
2. i++遍历数组。
import java.util.HashSet;
public class Main {
public static void main(String[] args) {
int[] arr = {1, 2, 2, 2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 8, 8, 9};
leftUnique(arr);
}
public static void leftUnique(int[] arr) {
if (arr.length == 0 || arr == null) {
return;
}
int u=0;
int i=1;
while (i!=arr.length){
if(arr[i++]!=arr[u]){
swap(arr,i-1,++u);
}
}
for( i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
}
public static int [] swap(int[] arr,int m, int n){
int temp= arr[m];
arr[m]=arr[n];
arr[n]=temp;
return arr ;
}
}
将正方形矩阵顺时针转动90度
题目：给定一个N*N的矩阵matrix,求把这个矩阵调整成顺时针转动90度后的形式。
例如：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
顺时针转动90度后为:
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4
要求：额外空间复杂度为O(1)
public class Main {
public static void main(String[] args) {
int[][] m = { {1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,16} };
rotate(m);
}
public static void rotate(int[][] arr) {
int tR=0;
int tC=0;
int dR=arr.length-1;
int dC=arr[0].length-1;
while (tR<dR){
rotateEdge(arr,tR++,tC++,dR--,dC--);
}
for (int i=0;i<arr.length;i++) {
for (int j = 0; j < arr[0].length; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println(" ");
}
}
public static void rotateEdge(int [][] arr ,int tR,int tC ,int dR ,int dC){
int times=dR-tR;
int temp=0;
for(int i=0;i!=times;i++){
temp = arr[tR][tC+i];
arr[tR][tC+i]=arr[dR-i][tC];
arr[dR-i][tC]=arr[dR][dC-i];
arr[dR][dC-i]=arr[tR+i][dC];
arr[tR+i][dC]=temp;
}
}
}
找到无序数组中最小的K个数
给定一个无序的整型数组arr，找到其中最小的k个数。
时间复杂度：O(nlogk)
维护一个有k个数的大根堆，这个堆代表目前选出的k个最小的数。在堆的k个元素中堆顶元素是最小的k个数中最大的那个。
接下来要遍历整个数组，遍历的过程中看当前数是否比堆顶元素小。如果是，就把堆顶元素替换成当前数，然后调整堆。如果不是，则不做任何操作，继续遍历下一个数。在遍历完成后，堆中的k个数就是所有数组中最小的k个数。
public class Main {
public static void main(String[] args) {
int[] arr = {5 ,9,3,4,7,2,8,1,6};
int k=3;
int [] res= getMinKNumsByHeap(arr,k);
for(int i=0;i<res.length;i++){
System.out.println(res[i]);
}
}
public static int [] getMinKNumsByHeap(int[] arr,int k) {
if(k<1&&k>arr.length){
return arr;
}
int kHeap[]=new int [k];
for(int i=0;i!=k;i++){
heapInsert(kHeap,arr[i],i);
}
for(int i = k;i !=arr.length;i++){
if(arr[i]<kHeap[0]){
kHeap[0]=arr[i];
heapify(kHeap,0,k);
}
}
return kHeap;
}
public static void heapify(int [] arr, int index ,int heapsize){
int left= index*2+1;
int right=index*2+2;
int largest=index;
while(left<heapsize){
if(arr[left]>arr[index]){
largest=left;
}
if(right<heapsize && arr[right]>arr[largest]){
largest=right;
}
if(largest!=index){
swap(arr,largest,index);
}else {
break;
}
index=largest;
left= index*2+1;
right=index*2+2;
}
}
public static void heapInsert(int [] kHeap ,int arri ,int i){
kHeap[i]=arri;
while (i!=0){
int parent=(i-1)/2;
if(kHeap[parent]<kHeap[i]){
swap(kHeap,parent,i);
i=parent;
}else {
break;
}
}
}
public static void swap(int [] arr ,int m ,int n){
int temp=arr[m];
arr[m]=arr[n];
arr[n]=temp;
}
}
三数排序
给定一个数组，其中只有三个数0,1,2三个值，请实现arr排序。
三个颜色的球排序
用left和right标记数组头和尾，用index遍历，遇到该交换的交换，直到index==right为止。
import java.util.HashSet;
public class Main {
public static void main(String[] args) {
int[] arr = {1,0,2,0,1,2,1,0 ,2, 2,0};
leftUnique(arr);
}
public static void leftUnique(int[] arr) {
if (arr.length <2 || arr == null) {
return;
}
int left=-1;
int index=0;
int right=arr.length;
while (index<right){
if(arr[index]==0){
swap(arr,++left,index++);
}else if(arr[index]==2){
swap(arr,--right,index);
}else {
index++;
}
}
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
}
public static int [] swap(int[] arr,int m, int n){
int temp= arr[m];
arr[m]=arr[n];
arr[n]=temp;
return arr ;
}
}
转圈打印矩阵
给一个整型矩阵matrix，按照转圈的方式打印它。
1 2 3
4 5 6
7 8 9
打印就是：1 2 3 6 9 8 7 4 5
public class CircleDynamic {
public static void main(String [] args){
int [][] m= {{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,16}};
spirOrderPrint(m);
}
public static void spirOrderPrint(int [][]matrix){
int tR = 0;
int tC = 0;
int dR=matrix.length-1;
int dC=matrix[0].length-1;
while (tR<=dR && tC<=dC){
printEdge(matrix,tR++,tC++,dR--,dC--);
}
}
public static void printEdge(int [][] matrix ,int tR ,int tC,int dR , int dC){
if(tR==dR){
for(int i=0;i<=dC;i++){
System.out.print(matrix[tR][i]+" ");
}
}else if(tC==dC){
for(int i=0;i<dR ;i++){
System.out.print(matrix[i][tC]+ " ");
}
}else {
int curC=tC;
int curR=tR;
while (curC != dC){
System.out.print(matrix[tR][curC]+" ");
curC++;
}
while (curR!=dR){
System.out.print(matrix[curR][dC]+" ");
curR++;
}
while (curC != tC){
System.out.print(matrix[dR][curC]+" ");
curC--;
}
while (curR!=tR){
System.out.print(matrix[curR][tC]+" ");
curR--;
}
}
}
}
- 上坐标（tR,tC）初始为（0,0），先向右走（tC++）,再向下走tR++
- 下坐标类似
- 打印斜线方向用boolean判断
public class CircleDynamic {
public static void main(String [] args){
int [][] m= {{1,2,3, 4},
{5,6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};
printMatrixZigZag(m);
}
public static void printMatrixZigZag(int [][] matrix){
int tR = 0;
int tC = 0;
int dR = 0;
int dC = 0;
int endR = matrix.length-1;
int endC = matrix[0].length-1;
boolean flag=false;
while (tR!=matrix.length){
printZigZag(matrix,tR,tC,dR,dC,flag);
tC=tC==endC?tC:tC+1;
tR= tC==endC ?tR+1:tR;
dR=dR==endR?dR:dR+1;
dC=dR==endR?dC+1:dC;
flag=!flag;
}
}
public static void printZigZag(int [][] matrix,int tR,int tC,int dR,int dC,boolean flag ){
if(flag){
while (tR!=dR+1){
System.out.print(matrix[tR++][tC--]+" ");
}
}else {
while (dR!=tC-1) {
System.out.print(matrix[dR--][dC++]+" ");
}
}
}
}
自然数数组的排序
public class CircleDynamic {
public static void main(String [] args){
int [][] m= {{1,2,3, 4},
{5,6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};
printMatrixZigZag(m);
}
public static void printMatrixZigZag(int [][] matrix){
int tR = 0;
int tC = 0;
int dR = 0;
int dC = 0;
int endR = matrix.length-1;
int endC = matrix[0].length-1;
boolean flag=false;
while (tR!=matrix.length){
printZigZag(matrix,tR,tC,dR,dC,flag);
tC=tC==endC?tC:tC+1;
tR= tC==endC ?tR+1:tR;
dR=dR==endR?dR:dR+1;
dC=dR==endR?dC+1:dC;
flag=!flag;
}
}
public static void printZigZag(int [][] matrix,int tR,int tC,int dR,int dC,boolean flag ){
if(flag){
while (tR!=dR+1){
System.out.print(matrix[tR++][tC--]+" ");
}
}else {
while (dR!=tC-1) {
System.out.print(matrix[dR--][dC++]+" ");
}
}
}
}
给定一个长度为N的整型数组arr，其中有N个互不相等的自然数1N，请实现arr的排序，但是不要把下标0N-1位置上的数值通过直接赋值的方式替换成1~N。
要求：时间复杂度为O(N)，额外空间复杂度为O(1)。
思路：
1.从左向右遍历arr，假设当前遍历到i位置。
2.if arr[i]==i+1,不需要调整，继续遍历。
3.if arr[i]!=i+1,进行调整。
根据调整功能的方法不同，可以有不同的实现过程。
public class CircleDynamic {
public static void main(String [] args){
int [] m= {1,2,5,3, 4};
m=sort(m);
for(int i=0;i<m.length;i++){
System.out.println(m[i]);
}
}
public static int [] sort(int [] matrix){
for(int i=0;i<matrix.length;i++){
while(matrix[i]!=i+1){
int temp=matrix[matrix[i]-1];
matrix[matrix[i]-1]=matrix[i];
matrix[i]=temp;
}
}
return matrix;
}
}
奇数下标都是奇数或偶数下标都是偶数
给定一个长度不小于2的数组arr，实现一个函数调整arr，要么使所有的偶数下标都是偶数，要么使所有的奇数下标都是奇数。
要求：时间复杂度为O(N),额外空间复杂度为O(1)。
算法解释：
最后位置的数是偶数，就替换前面的偶数下标，最后位置的是奇数，就替换前面的奇数下标，每替换一次，最后位置的数都是变化的，这样就都替换了。
public class CircleDynamic {
public static void main(String [] args){
int [] m= {1,8,3,2,4,6};
modify(m);
}
public static void modify(int [] matrix){
if(matrix==null || matrix.length<2){
return;
}
int even=0;
int odd=1;
int end=matrix.length-1;
while (even<=end && odd<=end){
if((matrix[end]&1)==0){
swap(matrix,even,end);
even+=2;
}else {
swap(matrix,odd,end);
odd+=2;
}
}
for(int i=0;i<matrix.length;i++){
System.out.println(matrix[i]);
}
}
public static void swap(int [] m,int index1,int index2){
int temp=m[index1];
m[index1]=m[index2];
m[index2]=temp;
}
}
子数组的最大累加和问题
给定一个数组，返回子数组的最大累加和。
例如：arr=[1,-2,3,5,-2,6,-1]，所有子数组中，[3,5,-2,6]可以累加出最大的和12，return 12.
时间复杂度为O(N)，额外空间复杂度为O(1)。
如果arr中没有正数，产生的最大累加和一定是数组中的最大值。
如果arr中有正数，从左向右遍历arr，用变量cur记录每一步的累加和，遍历到正数cur增加，遍历到负数cur减少。当cur<0时，舍弃当前部分，令cur=0，表示重新从下一个数开始累加。当cur>=0时，每一次的累加都可能是最大的累加和，所以，用另外一个变量max全程跟踪cur出现的最大值。
cur累加到负数就重新累加，max记录当前cur的最大值。
public class CircleDynamic {
public static void main(String [] args){
int [] m= {1,-2,3,5,-2,6,-1};
maxSum(m);
}
public static void maxSum(int[] m){
if(m==null||m.length==0){
return;
}
int cur=0;
int max=0;
for(int i=0;i<m.length;i++){
cur+=m[i];
if(max<cur){
max=cur;
}
if(cur<0){
cur=0;
}
}
System.out.println(max);
}
}
子矩阵的最大累计和问题
给定一个矩阵，其中的值有正、有负、有0。返回子矩阵的最大累计和。
如果一个矩阵一共有K行且限定必须含有K行元素的情况下，只要把矩阵中每一行的K个元素累加生成一个累加数组，然后求出这个数组的最大累加和，这个最大累加和就是必须含有K行元素的子矩阵中的最大累加和。
用i动态测试每一层往下累计的最大值，i+1实际上是把i层之上的全部不算。实现动态遍历
j和k是普通遍历
用s[k]存每次往下加的数字
cur加s[k]如果大就保存，如果不是最大就不存，如果小于0就清零。
public class Main {
public static void main(String[] args) {
int[][] m = {{-90, 48, 78},
{64, -40, 64},
{-81, -7, 66}};
maxSum(m);
}
public static void maxSum(int[][] m) {
if (m == null || m.length == 0 || m[0].length == 0) {
return;
}
int cur = 0;
int max = Integer.MIN_VALUE;
int []s=null;
for (int i = 0; i < m.length; i++) {
s = new int[m[0].length];
for (int j = i; j < m.length; j++) {
cur = 0;
for (int k = 0; k < m[0].length; k++) {
s[k] += m[j][k];
cur += s[k];
max = Math.max(max, cur);
if (cur < 0) {
cur = 0;
}
}
}
}
System.out.println(max);
}
}
在数组中找到一个局部最小的位置
定义局部最小的概念。arr长度为1时，arr[0]是局部最小。arr的长度为N(N>1)时，如果arr[0]<arr[1]，那么arr[0]为局部最小。如果arr[N-1]<arr[N-2]，那么arr[N-1]是局部最小。如果0<i<N-1，arr[i]<arr[i+1]&&arr[i]<arr[i-1]，那么arr[i]是局部最小。
给定无序数组arr，已知arr中任何两个相邻的数不相等。写一个函数，只需返回arr中任何一个局部最小出现的位置即可。
利用二分查找可以做到时间复杂度O(logN)、额外空间复杂度为O(1)
public class Main {
public static void main(String[] args) {
int[] m = {90,78, 48, 78};
System.out.println(getLessIndex(m));
}
public static int getLessIndex(int[] arr) {
if(arr==null || arr.length==0){
return -1;
}
if(arr[0]<arr[1]){
return 0;
}
if(arr[arr.length-1]<arr[arr.length-2]){
return arr[arr.length-1];
}
int left = 1;
int right= arr.length-2;
int mid=0;
while (left<right){
mid=(right+left)/2;
if(arr[mid]>arr[mid-1]){
right=mid-1;
}else if(arr[mid]>arr[mid+1]){
left=mid+1;
}else {
return mid;
}
}
return left;
}
}
不包含本位置值的累乘数组
给定一个整型数组，返回不包含本位置的累乘数组。
例如：arr=[2,3,1,4],返回[12,8,24,6],即除自己外，其他位置的类乘。
1.时间复杂度为O(N).
2.除需要返回的结果数组之外，额外空间复杂度为O(1).
使用除法：
结果数组记为res，所有数的乘积记为all。如果数组中不含0，则设置res[i]=all/arr[i]。如果数组中有一个0，对唯一的arr[i]==0的位置令res[i]=all,其他位置都是0。如果数组中0的数量大于1，那么res所有位置上的值都是0。
不使用除法：
1.生成两个长度和arr一样的新数组lr[]和rl[]，lr[i]=arr[0…i],rl[i]=arr[i…N-1]。
2.res[i]=lr[i-1]*rl[i+1]
3.res[0]=rl[1],res[N-1]=lr[N-2]
这里又额外使用了两个数组，可以通过res数组复用的方式省略掉这两个数组，先把res数组作为辅助计算的数组，然后把res调整成结果数组返回。
public class Main {
public static void main(String[] args) {
int[] m = {2,3, 1, 4};
m= product(m);
for(int i=0;i<m.length;i++){
System.out.println(m[i]);
}
}
public static int [] product(int[] arr) {
if(arr==null || arr.length==0){
return null;
}
int[] res=new int [arr.length];
res[arr.length-1]=1;
for(int i=arr.length-2;i>=0;i--){
res[i]=res[i+1]*arr[i+1];
}
int temp=1;
for(int i=0;i<arr.length;i++){
res[i]*=temp;
temp*=arr[i];
}
return res;
}
}
求最短通路值
用一个整形矩阵matrix表示一个网络，1代表有路，0代表没路，每一个位置只要不越界，都有上下左右4个方向，求从最左上角到最右下角的最短通路值。
例如：
1 0 1 1 1
1 0 1 0 1
1 1 1 0 1
0 0 0 0 1
通路只有1条，由12个1组成，所以返回12。
使用宽度优先遍历即可，如果矩阵大小为NM，时间复杂度为O(NM)，
1.开始时生成map矩阵，map[i][j]的含义是从（0,0）位置走到（i，j）位置最短的路径值。然后将左上角位置（0,0）的行坐标和列坐标放入行队列rQ、列队列 cQ。
2.不断从队列弹出一个位置（r,c）,然后看这个位置的上下左右四个位置哪些在matrix上的值是1，这些都是能走的位置。
3.将那些能走的位置设置好各自在map中的值，即map[r][c]+1。同时将这些位置加入到rQ和cQ的中，用队列完成宽度优先遍历。
4.在步骤3中，如果一个位置走过，就不要重复走，这个逻辑可以根据一个位置在map中的值来确定，比如map[i][j]!=0，就可以知道这个位置之前走过。
5.一直重复步骤2~步骤4。直到遇到右下角位置，说明已经找到终点，返回终点在map中的值即可，如果rQ和cQ已经为空都没有遇到终点位置，return 0。
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
int[][] m = { {1,0,1,1,1},
{1,0,1,0,1},
{1,1,1,0,1},
{0,0,0,0,1} };
System.out.println(minPathValue(m));
}
public static int minPathValue(int [][] m){
if(m==null || m.length==0|| m[0].length==0||m[0][0]!=1||m[m.length-1][m[0].length-1]!=1){
return 0;
}
int res=0;
int [][] map=new int [m.length][m[0].length];
map[0][0]=1;
Queue<Integer> rQ=new LinkedList<Integer>();
Queue<Integer> cQ=new LinkedList<Integer>();
rQ.add(0);
cQ.add(0);
int r=0;
int c=0;
while (!rQ.isEmpty()){
r=rQ.poll();
c=cQ.poll();
if( ( r==m.length-1 ) && ( c==m[0].length-1)){
//查map路径
for(int i=0;i<map.length;i++){
for (int j=0;j<map[0].length;j++){
System.out.print(map[i][j]+" ");
}
System.out.println(" ");
}
//输出结果
return map[r][c];
}
walkTo(map[r][c],r-1,c,m,map,rQ,cQ);
walkTo(map[r][c],r+1,c,m,map,rQ,cQ);
walkTo(map[r][c],r,c-1,m,map,rQ,cQ);
walkTo(map[r][c],r,c+1,m,map,rQ,cQ);
}
return res;
}
public static void walkTo(int pre,int toR,int toC ,int [][]m , int [][] map,Queue<Integer> rQ , Queue<Integer> cQ ){
if (toR < 0 || toR == m.length || toC < 0 || toC == m[0].length || m[toR][toC] != 1 || map[toR][toC] != 0) {
return;
}
map[toR][toC]=pre+1;
rQ.add(toR);
cQ.add(toC);
}
}
---res:
1 0 7 8 9
2 0 6 0 10
3 4 5 0 11
0 0 0 0 12
12
最长的可整合数组的长度
如果一个数组再排序之后，每相邻两个数差的绝对值都为1，则该数组为可整合数组。例如，[5,3,4,6,2]排序之后为[2,3,4,5,6],符合每相邻两个数差的绝对值为1，所以这个数组为可整合数组。
给定一个整型数组，请返回其中最大可整合子数组的长度。例如，[5,5,3,2,6,4,3]的最大可整合子数组为[5,3,2,6,4]，所以返回5.
一个数组中如果没有重复元素，并且如果最大值减去最小值，再加上1的结果等于元素的个数（max-min+1=元素个数）,那么这个数组就是可整合数组。
这样，验证一个数组是否是可整合数组的时间复杂度可以从第一种方法的O(NlogN)减少至O(1),整个过程的时间复杂度为O(N^2)
无需排序，仅仅只需要遍历比较大小
public class Main {
public static void main(String[] args) {
int[] m = { 5,5,3,2,6,4,3};
System.out.println(getLIL(m));
}
public static int getLIL(int [] arr){
if(arr.length==0||arr==null){
return 0;
}
int max=0;
int min=0;
int len=0;
HashSet<Integer> set=new HashSet<Integer>();
for(int i=0;i<arr.length;i++){
max=Integer.MIN_VALUE;
min=Integer.MAX_VALUE;
for(int j=i;j<arr.length;j++){
if(set.contains(arr[j])){
break;
}
set.add(arr[j]);
max=Math.max(max,arr[j]);
min=Math.min(min,arr[j]);
if(max-min==j-i){
len=Math.max(len,j-i+1);
}
}
set.clear();
}
return len;
}
}
边界都是1的最大正方形大小
给定一个M*N的矩阵，在这个矩阵中，只有0和1两种值，返回边框全是1的最大正方形的边长长度。
例如：
[0, 1, 1, 1, 1],
[0, 0, 1, 0, 1],
[0, 1, 1, 0, 1],
[0, 1, 1, 1, 1],
[0, 1, 0, 1, 1]
其中，边框全是1的最大正方形的大小为4。
解析：
1.正方形边长为0<=size<=Math.min(rows,cols);
2.边长为size时，左上角的坐标范围为 0<=i<=rows-size，0<=j<=cols-size;
3.使用预处理矩阵right和down，空间换时间，right[i][j]保存matrix[i][j]包括自己往右边有多少个1，同理down[i][j]。
3.对每一个左上角的边长为size的矩形判断边上是否全为1，发现有满足的直接返回当前size。
public class Main {
public static void main(String[] args) {
int[][] arr = { {0,1,1,1,1},
{0,1,0,0,1},
{0,1,0,0,1},
{0,1,1,1,1},
{0,1,0,1,1}};
System.out.println(getMaxSize(arr));
}
public static int getMaxSize(int [][]m){
int [][] right=new int [m.length][m[0].length];
int [][] down= new int [m.length][m[0].length];
setBorderMap(m,right,down);
for(int size=Math.min(m.length,m[0].length);size!=0;size--){
if(hasSizeOfBorder(size,right,down)){
return size;
}
}
return 0;
}
public static void setBorderMap(int [][] m,int [][]right ,int [][]down){
int r=m.length;
int c=m[0].length;
if(m[r-1][c-1]==1){
right[r-1][c-1]=1;
down[r-1][c-1]=1;
}
for(int i=r-2;i>=0;i--){
if(m[i][c-1]==1){
right[i][c-1]=1;
down[i][c-1]=down[i+1][c-1]+1;
}
}
for(int j=c-2;j>=0;j--){
if(m[r-1][j]==1){
right[r-1][j]=right[r-1][j+1]+1;
down[r-1][j]=1;
}
}
for(int i=r-2;i>=0;i--){
for (int j=c-2;j>=0;j--){
right[i][j]=right[i][j+1]+1;
down[i][j]=down[i+1][j]+1;
}
}
}
public static boolean hasSizeOfBorder(int size ,int [][]right ,int [][] down){
for(int i=0;i<right.length-size+1;i++){
for(int j=0;j<right[0].length-size+1;j++){
if(right[i][j]>=size&&down[i][j]>=size
&&right[i+size-1][j]>=size
&&down[i][j+size-1]>=size)
return true;
}
}
return false;
}
}
需要排序的最短子数组长度
package Array;
/**
* Created by zdmein on 2017/9/15.
* 需要排序的最短子数组长度
* 思路：
用noMin 记录从右到左，可以遍历的，最左边开始需要重新排的
用noMax 记录从左到右，可以遍历的，最右边需要重新排的
1, 5,3,4,2, 6,7
返回 4
*/
public class getMinLength1 {
public static void main(String args[]){
int []arr={1,5,3,4,2,6,7};
System.out.println(getMinLength(arr));
}
public static int getMinLength(int [] arr){
if(arr==null||arr.length<2){
return 0;
}
int min=arr[arr.length-1];
int noMin=-1;
for(int i=arr.length-2;i>=0;i--){
if(arr[i]>min){
noMin=i;
}else {
min=Math.min(arr[i],min);
}
}
if(noMin==-1)
return 0;
int max=arr[0];
int noMax=-1;
for(int i=1;i<arr.length;i++){
if(arr[i]<max){
noMax=i;
}else {
max=Math.max(max,arr[i]);
}
}
return noMax-noMin+1;
}
}