leetcode刷题打卡（数组1）

题目：

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

1.暴力法

2.模拟

参考K神思路：将矩阵向左旋转45度，即可发现由中间向左递减，向右递增

作者：Krahets

以下边3为起点

取row=len-1(>=0),col=0(

若matrix[row][col]>target:row—

若matrix[row][col]

注意：（以上边的7为起点有个坑，空数组的话取列长度会报错,需要排除空数组，空数组取行长度则不会

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int col=0,row=matrix.length-1;
        while(row>=0&&coltarget)row--;
            else col++;
        }
        return false;

    }
}

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

示例：

输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一。

双指针（位运算）

初始化存储数组与奇数指针、偶数指针（位运算优）

由于题目对大小并无排序要求

奇数则移动奇数指针

偶数则移动偶数指针

class Solution {
    public int[] exchange(int[] nums) {
        int[] res=new int[nums.length];
        int i=0,j=nums.length-1;
        for(int num:nums){
            if((num&1)==1)res[i++]=num;
            else res[j--]=num;
        } 
        return res;
    }
}

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

模拟

空值处理： 当 matrix 为空时，直接返回空列表 [] 即可。
初始化： 矩阵 左、右、上、下 四个边界 l , r , t , b ，用于打印的结果列表 res 。
循环打印： “从左向右、从上向下、从右向左、从下向上” 四个方向循环，每个方向打印中做以下三件事 （各方向的具体信息见下表） ；
根据边界打印，即将元素按顺序添加至列表 res 尾部；
边界向内收缩 11 （代表已被打印）；
判断是否打印完毕（边界是否相遇），若打印完毕则跳出。
返回值： 返回 res 即可

打印方向    1. 根据边界打印    2. 边界向内收缩    3. 是否打印完毕
从左向右    左边界l ，右边界 r    上边界 t 加 11    是否 t > b
从上向下    上边界 t ，下边界b    右边界 r 减 11    是否 l > r
从右向左    右边界 r ，左边界l    下边界 b 减 11    是否 t > b
从下向上    下边界 b ，上边界t    左边界 l 加 11    是否 l > r

作者：jyd
链接：https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/solution/mian-shi-ti-29-shun-shi-zhen-da-yin-ju-zhen-she-di/

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix.length==0)return new int[0];
        int m=matrix.length,n=matrix[0].length;
        int l=0,t=0,r=n-1,b=m-1,k=0;
        int[] res=new int[n*m];
        while(true){
            for(int i=l;i<=r;i++)res[k++]=matrix[t][i];if(++t>b)break;
            for(int i=t;i<=b;i++)res[k++]=matrix[i][r];if(--r=l;i--)res[k++]=matrix[b][i];if(--b=t;i--)res[k++]=matrix[i][l];if(++l>r)break;
        }
        return res;
    }
}

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

1. 哈希表:map键值对存储并判定即可
2. 排序，中数：对数组排序，长度大于数组一半的数必定是排序后的
3. 摩尔投票法：初始化第一个为默认值，次数N=1，开始遍历：遇到相同就加，不同就减，如果计数为0就换人（谁行谁上，只适应于此类题）

class Solution {
    public int majorityElement(int[] nums) {
        int res=nums[0],n=1;
        for(int num:nums){
            if(num==res)n++;
            else{
                n--;
                if(n==0){
                    res=num;
                    n=1;
                }
            }
        }
        return res;
    }
}

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

1.前缀和

初始化前缀和为0，最大值为nums[0]，min为0,

(1)先取前缀和与min的最小值（sum如果加负数，会比min还小），取得最小前缀和

(2)更新当前位置前缀和

(3)判断max与当前最大和的大小。连续子数组最大和 = 某个位置的前缀和 - 之前遇到的最小的前缀和

class Solution {
    public int maxSubArray(int[] nums) {
        int sum=0,min=0,max=nums[0];
        for(int num:nums){
            min=Math.min(min,sum);
            sum+=num;
            max=Math.max(max,sum-min);
        }
        return max;
    }
}

2.动态规划

当前sum:判断当前数对上一个sum是否有贡献，没有则不加入。

res取之前的res和当前的sum最大值。

class Solution {
    public int maxSubArray(int[] nums) {
    int dp[]=new int[nums.length];
    dp[0]=nums[0];
    int res=dp[0];
    for(int i=1;i 
3.动态规划空间复杂度优化：
 
利用原始累加和：判断之前累加和是否大于0，
 
class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        for(int i = 1; i < nums.length; i++) {
            nums[i] += Math.max(nums[i - 1], 0);
            res = Math.max(res, nums[i]);
        }
        return res;
    }
}

作者：jyd
链接：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/solution/mian-shi-ti-42-lian-xu-zi-shu-zu-de-zui-da-he-do-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 
剑指 Offer 45. 把数组排成最小的数（中等） 
 
 
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
 
 
示例 1:
 
 
输入: [10,2]
 输出: "102"
 示例 2:
 
 
输入: [3,30,34,5,9]
 输出: "3033459"
 
 
调用函数库（不用库是）
 
Int数组转String数组（不能用foreach循环），调用字符串排序方法(a+b).compareTo(b+a),拼接返回即可。
 
class Solution {
    public String minNumber(int[] nums) {
        String[] strs=new String[nums.length];
        for(int i=0;i (o1+o2).compareTo(o2+o1));
        StringBuilder sb=new StringBuilder();
        for(String s:strs){
            sb.append(s);
        }
        return  sb.toString();
    }
}
 

 剑指 Offer 61. 扑克牌中的顺子（简单） 
 
 
从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
 
 
 
 
示例 1:
 
 
输入: [1,2,3,4,5]
 输出: True
  
 
 
示例 2:
 
 
输入: [0,0,1,2,5]
 输出: True
 
 
问题转换：最大值和最小值差<5
 
满足两个条件：
 
（1）无重复（重复return false）
 
（2）差值<5（遍历过程种存储最大最小值比排序效率高，因为只进行了一次）
 
class Solution {
    public boolean isStraight(int[] nums) {
        List alist=new ArrayList<>();
        int max=0,min=100;
        for(int num:nums){
            if(num==0)continue;
            max=Math.max(max,num);
            min=Math.min(min,num);
            if(alist.contains(num))return false;
            alist.add(num);
        }
        return max-min<5;
    }
}
 

 题目来源：力扣（LeetCode）