自己网站的关键词怎么改,wordpress主题怎么使用教程,网络服务商简称,旅游主题网站策划书作为一个硬核作者#xff0c;绝不和你扯废话#xff0c;干货无套路送你 题目一#xff1a; 给定一个数组arr#xff0c;求出需要排序的最短子数组长度
要求#xff1a; 时间o(n),空间o(1)
思路#xff1a; 有序的数组中#xff0c;任意一个数字#xff0c;一定小于左… 作为一个硬核作者绝不和你扯废话干货无套路送你 题目一 给定一个数组arr求出需要排序的最短子数组长度
要求 时间o(n),空间o(1)
思路 有序的数组中任意一个数字一定小于左边的数大于右边的数。 我们找到的需要排序的子数组显然是比右边最小的值大或比左边最大的值小。 我们初始化变量noMinindex-1;从右往左遍历记录经过的最小值为min若当前数大于min说明如果要有序min一定要放 在当前数左边我们更新noMinindex。 也就是说我们的noMinindex是负责记录最左边出现这种情况的位置。我们反方向处理出noMaxindex 他们组成的区间就是最短需要排序的部分了
public class MinLengthForSort {public static int getMinLength(int[] arr) {if (arr null || arr.length 2) {return 0;}int min arr[arr.length - 1];int noMinIndex -1;for (int i arr.length - 2; i ! -1; i--) {if (arr[i] min) {noMinIndex i;} else {min Math.min(min, arr[i]);}}if (noMinIndex -1) {return 0;}int max arr[0];int noMaxIndex -1;for (int i 1; i ! arr.length; i) {if (arr[i] max) {noMaxIndex i;} else {max Math.max(max, arr[i]);}}return noMaxIndex - noMinIndex 1;}public static void main(String[] args) {int[] arr { 1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19 };System.out.println(getMinLength(arr));}}题目二 给定一个数组找出出现次数超过一半的数字
蠢思路排序找中间
思路 DP扫一遍一个变量count记录解出现的次数是当前解就否则--count为负就换掉当前解。解释想象解全都挨在 一起前面count先达到最大然后减为1或0而其他数字先出现可能会使正确解的count减为负数但都会使正确解 在后面更多从而保证了结束时肯定为正确解
int main()
{int n;//个数scanf(%d,n);int temp,k,count0;while(n--){scanf(%d,temp);if(tempk)count;else{count--;if(count0){count0;ktemp;}}}printf(%d\n,k);
} 题目三
给定一个有N×M的整型矩阵matrix和一个整数Kmatrix的每一行和每一列都是排好序的。实现一个函数判断K是否在matrix中。
例如
0 1 2 5
2 3 4 7
4 4 4 8
5 7 7 9
如果K为7返回true如果K为6返回false
要求
时间复杂度为O(NM)额外空间复杂度为O(1)。
思路
1.从矩阵最右上角的数开始寻找row0,colM-1。
2.比较当前数matrix[row][col]与K的关系
如果与K相等说明已找到直接返回true
如果比K大因为矩阵每一列都已排好序所以在当前数所在的列中处于当前数下方的数都会比K大则没有必要继续在第col列上寻找令colcol-1重复步骤2.
如果比K小因为矩阵每一行都已排好序所以在当前数所在的行中处于当前数左方的数都会比K小则没有必要继续在第row行上寻找令rowrow1,重复步骤2.
3.如果找到越界都没有发现与K相等的数则返回false。
或者可以从矩阵的最左下角的数开始寻找rowN-1,col0具体过程类似。
代码
/*** 在行列都排好序的矩阵中找数*/
public class IsContains {public boolean isContains(int[][] matrix, int K) {int row 0;int col matrix[0].length - 1;while (row matrix.length col -1) {if (matrix[row][col] K) {return true;} else if (matrix[row][col] K) {col--;} else {row;}}return false;}
}
题目四转圈打印矩阵 题目
给定一个整型矩阵matrix请按照转圈的方式打印它。例如1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,打印结果为1,2,3,4,5,12,16,15,14,13,9,5,6,7,11,10
要求
额外空间复杂度为O1 思路
矩阵分圈处理。在矩阵中用左上角的坐标tR,tC和右下角的坐标dR,dC就可以表示一个矩阵比如题目中的矩阵当tR,tC(0,0)dR,dC(3,3)时表示的子矩阵就是整个矩阵那么这个子矩阵的最外层的部分如下
1 2 3 4
5 8
9 12
13 14 15 16
如果能把这个子矩阵的外层转圈打印出来那么在(tR,tC)(0,0)、(dR,dC)(3,3)时打印结果为1,2,3,4,8,12,16,15,14,13,9,5。接下来令tR和tC加1即(tR,tC)(1,1)令dR和dC减1即(dR,dC)(2,2)此时表示的子矩阵如下
6 7
10 11
再把这个子矩阵转圈打印出来结果为6,7,11,10。把tR和tC加1即(tR,tC)(2,2)令dR和dC减1即(dR,dC)(1,1)。如果发现左上角坐标跑到右下角坐标的右方或下方整个过程就停止。已经打印的所有结果连接起来就是我们要求的打印结果。
代码
/*** 转圈打印矩阵*/
public class PrintMatrixSpiralOrder {public void spiralOrderPrint(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--);}}//转圈打印一个子矩阵的外层左上角点tR,tC右下角点dR,dCprivate void printEdge(int[][] matrix, int tR, int tC, int dR, int dC) {if (tR dR) {//子矩阵只有一行时for (int i tC; i dC; i) {System.out.print(matrix[tR][i] );}} else if (tC dC) {//子矩阵只有一列时for (int i tR; i dR; i) {System.out.print(matrix[i][tC] );}} else {//一般情况int curCol tC;int curRow tR;while (curCol ! dC) {//从左向右System.out.print(matrix[tR][curCol] );curCol;}while (curRow ! dR) {//从上到下System.out.print(matrix[curRow][dC] );curRow;}while (curCol ! tC) {//从右到左System.out.print(matrix[dR][curCol] );curCol--;}while (curRow ! tR) {//从下到上System.out.print(matrix[curRow][tC] );curRow--;}}}
} 题目五将正方形矩阵顺时针转动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).
思路
仍然使用分圈处理的方式
在矩阵中用左上角的坐标tR,tC和右下角的坐标dR,dC就可以表示一个矩阵比如题目中的矩阵当tR,tC(0,0)dR,dC(3,3)时表示的子矩阵就是整个矩阵那么这个子矩阵的最外层的部分如下
1 2 3 4
5 8
9 12
13 14 15 16
在这个外圈中1,4,16,13为一组然后让1占据4的位置4占据16的位置16占据13的位置13占据1的位置一组就调整完了。然后2,8,15,9为一组继续占据调整的过程最后3,12,14,5为一组继续占据调整的过程。然后(tR,tC)(0,0)、(dR,dC)(3,3)的子矩阵外层就调整完毕接下来令tR和tC加1即(tR,tC)(1,1)令dR和dC减1即dR,dC(2,2)此时表示的子矩阵如下
6 7
10 11
这个外层只有一组就是6,7,11,10占据调整之后即可。所以如果子矩阵的大小是M×M一共就有M-1组分别进行占据调整即可。
代码
/*** 将正方形矩阵顺时针旋转90°*/
public class RotateMatrix {public static void rotate(int[][] matrix) {int tR 0;int tC 0;int dR matrix.length - 1;int dC matrix[0].length - 1;while (tR dR) {rotateEdge(matrix, tR, tC, dR--, dC--);}}private static void rotateEdge(int[][] matrix, int tR, int tC, int dR, int dC) {int times dC - tC;//times就是总的组数int temp 0;for (int i 0; i ! times; i) {//一次循环就是一组占据调整temp matrix[tR][tC i];matrix[tR][tC i] matrix[dR - i][tC];matrix[dR - i][tC] matrix[dR][dC - i];matrix[dR][dC - i] matrix[tR - i][dC];matrix[tR - i][dC] temp;}}
} 题目六“之”字形打印矩阵 题目
给定一个矩阵matrix按照“之”字形的方式打印矩阵例如
1 2 3 4
5 6 7 8
9 10 11 12
“之”字形打印的结果为1,2,5,9,6,3,4,7,10,11,8,12
要求
额外空间复杂度为O1
思路;
上坐标tR,tC初始化为0,0,先沿着矩阵第一行移动tC当到达第一行最右边的元素后在沿着矩阵最后一列移动tR。 下坐标dR,dC初始为0,0,先沿着矩阵第一列移动dR当到达第一列最下边的元素时再沿着矩阵最后一行移动dC。 上坐标与下坐标同步移动每次移动后的上坐标与下坐标的连线就是矩阵中的一条斜线打印斜线上的元素即可。 如果上次斜线是从左下向右上打印的这次一定是从右上向左下打印反之亦然。总之可以把打印的方向用boolean值表示每次取反即可。 代码
/*** 之字形打印矩阵*/
public class PrintMatrixZigZag {public static void printMatrixZigZag(int[][] matrix) {int tR 0;int tC 0;int dR 0;int dC 0;int endRow matrix.length - 1;int endCol matrix[0].length - 1;boolean fromUp false;while (tR ! endRow 1) {printLevel(matrix, tR, tC, dR, dC, fromUp);tR tC endCol ? tR 1 : tR;tC tC endCol ? tC : tC 1;dR dR endRow ? dR : dR 1;dC dR endRow ? dC 1 : dC;fromUp !fromUp;}System.out.println();}private static void printLevel(int[][] matrix, int tR, int tC, int dR, int dC, boolean fromUp) {if (fromUp) {while (tR ! dR 1) {//从左下到右上System.out.print(matrix[tR][tC--] );}} else {while (dR ! tR - 1) {//从右上到左下System.out.print(matrix[dR--][dC] );}}}
}
题目七
给定一个长度为N的整型数组arr其中有N个互不相等的自然数1~N
请实现arr的排序
但是不要把下标0~N-1位置上的数值通过直接赋值的方式替换成1~N。
要求时间复杂度为O(N)额外空间复杂度为O(1)。 思路从左向右检查检查到需要换的以后就直接把它放到该去的位置然后被换掉的数位置肯定也不对继续重复相同的方法最后肯定会跳回来原因懒得说了自己想想然后继续往下检查即可。
public static void sort1(int[] arr) {int tmp 0;int next 0;for (int i 0; i ! arr.length; i) {tmp arr[i];while (arr[i] ! i 1) {next arr[tmp - 1];arr[tmp - 1] tmp;tmp next;}}}
题目八 本题一般思路依次查找找到比前后都小的数或者选出最小数他肯定是局部最小的等等
但这些都是O(n)的方法而用二分可以做到O(logn).
二分思路 考虑最左和最右的元素如果arr[0]arr[1] return 0; arr[N-1]arr[N-2] return N-1; 考虑最中间元素如果中间元素大于它左边的元素那么局部最小值就应该在数组的左半部分 如果中间元素小于大于它右边的元素那么局部最小值就应该在数组的右半部分 中间元素既小于它左边的值又小于它右边的值那么它就是局部最小
题目九 给定一个整数数组arr返回不包含本位置的累乘数组。
比如2 3 1 4返回12 8 24 6
方法一算出所有数的乘积每个位置除以自己即可。要注意坑如果数组中有一个0那么0这个位置就是其他数的乘积其他位置全为0如果有多个0那么所有位置都是0. public int[] product1(int[] arr) {if(arrnull || arr.length2) {return null;}int count0;//0的个数int all1;//除0以外的数的乘积for(int i0;i!arr.length;i) {if(arr[i]!0) {all*arr[i];}else {count;}}int[] resnew int[arr.length];if(count0) {for(int i0;i!arr.length;i) {res[i]all/res[i];}}else if(count1) {for(int i0;i!arr.length;i) {if(arr[i]0) {res[i]all;}}}return res;} 题目十子数组的最大累加和问题
输入一个整形数组求数组中连续的子数组使其和最大。比如数组x
应该返回 x[2..6]的和187. 这四个代码完成的功能都是求最大子数组注意用词准确子数组连续子序列可以不连续。
1
for(i 1; i n; i)scanf(%d, num[i]);
ans num[1];
for(i 1; i n; i)
{for(j i; j n; j) {s 0;for(k i; k j; k)s num[k];if(s ans)ans s;}
}
分别枚举每一个子数组的起点和终点也就是i和j对于每一个起点和终点对中间部分求和也就是k循环。显然有n个起点n个终点去重减半不影响复杂度所以子数组数量为O(N^2)对于每个子数组我们要遍历一下求和子数组长度1-n不等遍历一遍平均O(N)乘起来O(N^3).注意可能产生时间更大的错觉。找出所有子数组中最大的即可。
2
for(i 1; i n; i)scanf(%d, num[i]);
sum[0] 0;
for(i 1; i n; i) {sum[i] num[i] sum[i - 1];
}
ans num[1];
for(i 1; i n; i) {for(j i; j n; j) {s sum[j] - sum[i - 1];if(s ans) ans s;}
}
预处理出每一个以第一个元素开始第i个元素结尾的子数组和还是枚举每个起点终点但是我们求和时直接减就可以了不用遍历。对于每个子数组操作为O(1),子数组数量O(N^2),所以总时间O(N^2).
3
int solve(int left, int right)
{if(left right)return num[left];mid (left right) / 2;lans solve(left, mid);rans solve(mid 1, right);sum 0, lmax num[mid], rmax num[mid 1];for(i mid; i left; i--) {sum num[i];if(sum lmax) lmax sum;}sum 0;for(i mid 1; i right; i) {sum num[i];if(sum rmax) rmax sum;}ans lmax rmax;if(lans ans) ans lans;if(rans ans) ans rans;return ans;
}int main(void)
{scanf(%d, n);for(i 1; i n; i)scanf(%d, num[i]);printf(%d\n, solve(1, n));return 0;
}
二分求左右两边最大子数组取最大。但是还有一种情况包含断点的那些子数组也要考虑请思考那两个那两个循环为什么那么写最后逻辑为何正确
4动态规划入门思想
没有枚举num[i]的含义是以下标i结尾的所有子数组中最大的。
遍历数组对于第i个元素它的所有子数组下标范围有[1,i],[2,i].....[i-1,i],还有它自己我们看i-1个元素他的子数组为[1,i-1],[2,i-1].....[i-1]。请想num[i]的含义我们求i结尾的只要把i-1结尾的最大加上i就好了当然如果i-1结尾最大子数组是负的i结尾最大子数组就是它本身。
为什么O(N)时间省在哪里了我们省掉了许多没必要的计算计算i时之前的数组和已经都计算过朴素算法并没有记录下来而是重复计算造成时间浪费。算法优化的过程就是去掉重复计算的过程。
for(i 1; i n; i)scanf(%d, num[i]);num[0] 0;
ans num[1];
for(i 1; i n; i)
{if(num[i - 1] 0) num[i] num[i - 1];elsenum[i] 0;if(num[i] ans) ans num[i];
}
题目十一、子矩阵的最大累加和问题
给一个矩阵请找出一个矩阵中和最大的子矩阵。 如果大家看懂了上一题的讲解我给个提示利用第二个代码和第四个代码思想的结合 解释
1 2 3 4
-1 -2 1 2
1 3 -2 1
-1 -2 -1 -3
如图是前三行整体最大
怎么做呢
先用第二个代码的思想我们进行预处理
每个数代表这一列到这个数位置截止累加和。
1 2 3 4
0 0 4 6
1 3 2 7
0 1 1 4
然后我们枚举每一列的起点和终点分别为第0123行
然后压缩成一维来做
比如求1-3行的这个矩形我们拿0和3行减一下就行了
0-11-21-34-4-1-1-20就是1-3行压缩后的结果
然后按一维dp来做就好
public class SubMatrixMaxSum {public static int maxSum(int[][] m) {if (m null || m.length 0 || m[0].length 0) {return 0;}int max Integer.MIN_VALUE;int cur 0;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 ! s.length; k) {s[k] m[j][k];cur s[k];max Math.max(max, cur);cur cur 0 ? 0 : cur;}}}return max;}public static void main(String[] args) {int[][] matrix { { -90, 48, 78 }, { 64, -40, 64 }, { -81, -7, 66 } };System.out.println(maxSum(matrix));}}题目十二、子数组的最大累乘积
题目
给定一个double类型的数组arr其中的元素可正、可负、可为0。返回子数组累乘的最大乘积。
思路
假设以arr[i-1]结尾的数组最小累乘积为min最大累乘积为max那么以arr[i]结尾的数组的最大累乘积可能有三种情况。
max*arr[i]//本身乘之前的最大累乘min*arr[i]//可能是负负得正变成最大的arr[i]//可能就是它本身比如之前的max小于1public class SubArrayMaxProduct {public static double maxProduct(double[] arr) {if (arr null || arr.length 0) {return 0;}double max arr[0];double min arr[0];double res arr[0];double maxEnd 0;double minEnd 0;for (int i 1; i arr.length; i) {maxEnd max * arr[i];minEnd min * arr[i];max Math.max(Math.max(maxEnd, minEnd), arr[i]);min Math.min(Math.min(maxEnd, minEnd), arr[i]);res Math.max(res, max);}return res;}public static void main(String[] args) {double[] arr { -2.5, 4, 0, 3, 0.5, 8, -1 };System.out.println(maxProduct(arr));}}题目十三调整有序的arr数组使得左半部分有序且不重复不用保证右边是否有序。
思路 u : 左边的最后位置即0---u为答案 i : 从u到右遍历 当arr[i]和arr[u]不相等时说明是目前遇到的最大的数此时调换arr[u1]和arr[i] public static void leftUnique(int[] arr) {if (arr null || arr.length 2) {return;}int u 0;int i 1;while (i ! arr.length) {if (arr[i] ! arr[u]) {swap(arr, u, i - 1);}}} public static void swap(int[] arr, int index1, int index2) {int tmp arr[index1];arr[index1] arr[index2];arr[index2] tmp;}
题目十四数组arr中只有三种值012请排序
思路荷兰国旗问题https://blog.csdn.net/hebtu666/article/details/81772701
上面的网址介绍了思路和c实现本文给出java实现。 public static void sort(int[] arr) {if (arr null || arr.length 2) {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, index, --right);} else {index;}}} 题目十五数组arr给定k请实现比k小的放左边等于k的放中间大于k的放右边
同样的分三区只是条件改一下k,k,k即可。
