1.二维数组螺旋打印
给定一个二维数组 array，请返回「螺旋遍历」该数组的结果。
螺旋遍历：从左上角开始，按照 向右、向下、向左、向上 的顺序 依次 提取元素，然后再进入内部一层重复相同的步骤，直到提取完所有元素。
示例 1：
输入：array = [[1,2,3],[8,9,4],[7,6,5]]
输出：[1,2,3,4,5,6,7,8,9]class Solution {
public int[] spiralArray(int[][] array) {
if(array.length==0) {
return new int[0];
}
int[] res = new int[array.length*array[0].length];
int idx=0;
int up=0,down=array.length-1,left=0,right=array[0].length-1;
while(true) {
for(int i=left;i<=right;i++) {
res[idx++]=array[up][i];
}
if(++up>down) {
break;
}
for(int i=up;i<=down;i++) {
res[idx++]=array[i][right];
}
if(--right<left) {
break;
}
for(int i=right;i>=left;i--) {
res[idx++]=array[down][i];
}
if(--down<up) {
break;
}
for(int i=down;i>=up;i--) {
res[idx++]=array[i][left];
}
if(++left>right) {
break;
}
}
return res;
}
}https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/comments/
https://leetcode.cn/problems/spiral-matrix/comments/
2.求数组中最大乘积
public static int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int maxProduct = nums[0]; // 最终的最大乘积结果
int maxCurrent = nums[0]; // 当前的最大乘积
int minCurrent = nums[0]; // 当前的最小乘积
for (int i = 1; i < nums.length; i++) {
// 如果当前元素是负数，交换maxCurrent和minCurrent
if (nums[i] < 0) {
int temp = maxCurrent;
maxCurrent = minCurrent;
minCurrent = temp;
}
// 更新当前的最大乘积和最小乘积
maxCurrent = Math.max(nums[i], maxCurrent * nums[i]);
minCurrent = Math.min(nums[i], minCurrent * nums[i]);
// 更新最终的最大乘积结果
maxProduct = Math.max(maxProduct, maxCurrent);
}
return maxProduct;
}3.求数组中连续最大和
描述
一个数组有 N 个元素，求连续子数组的最大和。 例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int sums=0, maxsums=Integer.MIN_VALUE; //考虑全为负数的情况
sums+=sc.nextInt();
maxsums=Math.max(maxsums,sums);
sums= sums<0?0:sums; //代码核心了，如果当前求和为负，则抛弃之前的连续数组，重新开始求和
}
System.out.println(maxsums);
}4.和为 S 的连续正数序列
示例1
输入：9
输出：[[2,3,4],[4,5]]public ArrayList > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
int start=1,end=2;
int currSum = 3;
while(end < sum) {
if(currSum > sum) {
currSum-=start;
start++;
} else if (currSum < sum) {
end++;
currSum+=end;
} else{
temp = new ArrayList<>();
for(int i=start; i<=end; i++) {
temp.add(i);
}
ret.add(temp);
currSum-=start;
start++;
end++;
currSum+=end;
}
}
return ret;
}5.合并有序数组
两个有序数组合并成新的有序数组
示例 1：
输入：nums1 = [1,2,5], nums2 = [3,4,6]
输出：[1,2,3,4,5,6]public int[] mergeArray(int[] a,int[] b){
int[] result = new int[a.length+b.length];
int i = 0,j =0,k = 0;
if(a[i] < b[j]){
result[k++] = a[i++];
}
else{
result[k++] = b[j++];
}
}
/* 后面连个while循环是用来保证两个数组比较完之后剩下的一个数组里的元素能顺利传入 *
* 此时较短数组已经全部放入新数组，较长数组还有部分剩余，最后将剩下的部分元素放入新数组，大功告成*/
while(i < a.length)
result[k++] = a[i++];
while(j < b.length)
result[k++] = b[j++];
return result;
}6.数组排序
排序可以使用冒泡+插入+快速+希尔+归并+桶+基数等方式实现
最基础的四个算法：冒泡、选择、插入、快排中，快排的时间复杂度最小O(n*log2n)，其他都是O（n2）
排序法 | 平均时间 | 最差情形 | 稳定度 | 额外空间 | 备注 |
冒泡 | O(n2) | O(n2) | 稳定 | O(1) | n小时较好 |
选择 | O(n2) | O(n2) | 不稳定 | O(1) | n小时较好 |
插入 | O(n2) | O(n2) | 稳定 | O(1) | 大部分已排序时较好 |
基数 | O(logRB) | O(logRB) | 稳定 | O(n) | B是真数(0-9)， R是基数(个十百) |
Shell | O(nlogn) | O(ns) 1 | 不稳定 | O(1) | s是所选分组 |
快速 | O(nlogn) | O(n2) | 不稳定 | O(nlogn) | n大时较好 |
归并 | O(nlogn) | O(nlogn) | 稳定 | O(1) | n大时较好 |
堆 | O(nlogn) | O(nlogn) | 不稳定 | O(1) | n大时较好 |
public static void quickSort(int[] arr, int low, int high){
int i,j,temp,t;
if(low>high){
return;
}
i=low;
j=high;
//temp就是基准位
temp = arr[low];
while (i<j) {
//先看右边，依次往左递减
while (temp<=arr[j]&&i<j) {
j--;
}
//再看左边，依次往右递增
while (temp>=arr[i]&&i<j) {
i++;
}
//如果满足条件则交换
if (i<j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];
arr[i] = temp;
//递归调用左半数组
quickSort(arr, low, j-1);
//递归调用右半数组
quickSort(arr, j+1, high);
}