LeetCode数组

1160.拼写单词(统计出现次数)

题目

分析

1. 主要思想就是：通过计算参考表和单词表每个单词出现次数对比(参照表出现次数一定要比找的多 才可能拼出来)
2. 具体步骤：
    2.1 分别设计一个jishu数组统计参考表每个单词出现次数 || 一个temp数组统计要查的每个单词的出现次数(用完就要清0)
    2.2 然后每个单词位都需要对比，然后对比成功+1之后达到26就说明能凑出来这个单词，输出长度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
public class PingXieDanCi {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        String[] words=new String[n];   //输入要判断的words表
        for(int i=0;i<words.length;i++){
                words[i]=input.next();
        }
        String chars=input.next();  //输入chars字符串
		//可以试试每一次统计是否正确
        /*int[] b=countCharacters(words,chars);
        for(int i=0;i<26;i++){
            if(b[i]!=0) {
                System.out.println((char) (i + 97) + "有" + b[i] + "个");
            }
        }*/
        System.out.println(countCharacters(words,chars));
    }

    public static int countCharacters(String[] words, String chars) {
        int sum=0;  //记录总长度
        char[] a=chars.toCharArray();  //chars字符串转字符数组
        int[] jishu=new int[26];
        int[] temp=new int[26];

        for(int i=0;i<chars.length();i++){
            jishu[chars.charAt(i)-97]++;  //计算chars字符串中各单词个数
        }

        for(int i=0;i<words.length;i++){
            int chang=words[i].length();  //计算每一个要判断的词汇的长度

            for(int j=0;j<words[i].length();j++){
                temp[words[i].charAt(j)-97]++;  //计算chars字符串中各单词个数
            }

            //对比两个数组
            int flag=0; //每位判断是否满足条件
            for(int z=0;z<26;z++){
                if(jishu[z]>=temp[z]){
                    flag+=1;  //满足要凑的比我有的少 就+1
                }
                if(jishu[z]<temp[z]){
                    break;  //有参考表没有的单词 一定凑不出来!
                }
            }

            if(flag==26){
                sum+=chang;  //每一位都满足 就可以拼凑出来
            }

            //用完之后将temp数组清0
            for(int w=0;w<26;w++){
                temp[w]=0;  //计算chars字符串中各单词个数
            }

        }
        return sum;
    }

}

结果

88.合并两个有序整数数组(ArrayList集合)

题目

分析

1. 主要通过有序的ArrayList集合存放两个数组元素
2. 通过Collections.sort()方法进行排序然后返回

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class HeBinShuZu {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int m=input.nextInt();  //数组1的长度
        int n=input.nextInt();  //数组2的长度
        int[] a=new int[m];  //定义数组1
        int[] b=new int[n];  //定义数组2
        for(int i=0;i<m;i++){
            a[i]=input.nextInt();  //按序输入数组1的值
        }
        for(int j=0;j<n;j++){
            b[j]=input.nextInt();  //按序输入数组2的值
        }

        System.out.println("调函数之后的list"+merge(a,m,b,n).toString());  //list集合转字符串
    }

    public static ArrayList<Integer> merge(int[] nums1, int m, int[] nums2, int n) {
        ArrayList<Integer> list=new ArrayList<Integer>();
        for(int i=0;i<m;i++){
            list.add(nums1[i]);
        }
        System.out.println("第一次添加之后的list:"+list.toString());
        System.out.println("第一次的长度"+list.size());
        System.out.println("----------------------");
        for(int j=0;j<n;j++){
            list.add(nums2[j]);
        }
        System.out.println("第二次添加之后的list:"+list.toString());
        System.out.println("第二次的长度"+list.size());
        System.out.println("----------------------");
        Collections.sort(list);
        System.out.println("排序后的list:"+list.toString());
        System.out.println("排序后的长度"+list.size());
        System.out.println("----------------------");
        return list;
    }

}

结果

53. 0-n-1中缺失的数字(双指针二分查找)

题目

分析

1. 数组下标计数：新建数组然后利用数组下标记录每个数组出现次数，如果出现次数为0就是缺失的数字。
2. 双指针：使用二分法进行分左右两部分对比，只要是顺序不缺少的话肯定是下标和当前值一定一样。
    2.1 左边没缺   左指针挪到中间指针的右边
    2.2 左边缺失   右指针挪到中间指针的左边

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class QueShiShuZi {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int m=input.nextInt();  //数组1的长度
        int[] a=new int[m];  //定义数组1
        for(int i=0;i<m;i++){
            a[i]=input.nextInt();  //按序输入数组1的值
        }
        System.out.println("挨个遍历"+missingNumber(a));
        System.out.println("双指针"+missingNumber2(a));
    }

	//挨个遍历存到计数数组中
    public static int missingNumber(int[] a) {
        int que=0;
        int[] b=new int[a.length+1];
        for(int i=0;i<a.length;i++){
            b[a[i]]++;
        }
        for(int i=0;i<b.length;i++){
            if(b[i]==0){
                que=i;   //下标计数的数组里面没出现肯定就是缺失了
            }
        }
        return que;
    }

	//双指针二分法查询
    public static int missingNumber2(int[] a) {
        int que=0;  //缺失的结果
        int left=0;  //左指针
        int right=a.length-1;  //右指针
        while(left<=right){
            int zhong=(left+right)/2;  //中间指针
            if(a[zhong]==zhong){
                left=zhong+1; //左边的下标和数值没有断就肯定是相等 所以缺失的在右边 左指针放在中间指针右边
            }
            else{
                right=zhong-1; //左边肯定缺失了 右指针放到中间指针的左边
            }
        }
        return left;  //最后一定是三个指向同一个位置
    }

}

实现

118.杨辉三角形(动态递归)

题目

分析

1. 动态递归：遍历迭代之后进行增加
2. list集合：使用Arraylist集合

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class YangHuiSanJiao {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();   //输入杨辉三角形的行数
        long[][] b=yanghui(n);  //接住调用方法的结果
        System.out.println("动态递归解法:");
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                System.out.printf(b[i][j]+" ");
            }
            System.out.println();
        }
    }

    //动态递归
    public static long[][] yanghui(int n){
        if(n==0){
            return null;  //0行就返回null
        }
        long[][] a=new long[n][n];
        a[0][0]=1; //第一行第一列赋值1 方便后面的加
        for(int i=1;i<n;i++){  //从第二行开始
            for(int j=0;j<n;j++) {
                if(j==0){
                    a[i][j]+=a[i-1][j];  //第一列的只能加上面的
                }else{
                    a[i][j]=a[i-1][j]+a[i-1][j-1];  //上面的和上面的左边之和
                }
            }
        }
        return a;
    }

}

实现

26.删除排序数组中的重复项(HashSet集合)

题目

分析

1. 不重复就需要使用set集合：我们使用HashSet集合
2. 循环将每个数组元素往set插入(刚好不能插入重复的)
3. 输出set.size()就是最后要的长度

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class ShanChuChongFu {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(removeDuplicates(a));
    }

    public static int removeDuplicates(int[] nums) {
        HashSet<Integer> set=new HashSet<Integer>();  //建立hashset集合
        for(int i=0;i<nums.length;i++){
            set.add(nums[i]);  //遍历添加元素
        }
        System.out.println(set.toString());  //输出set集合元素
        return set.size(); //输出set集合的长度
    }
}

结果

1051.高度检查器(桶排序)

题目

分析

1. 非递减就是说必须是递增/相等
2. 利用桶排序数组下标记录每个桶的数量，然后进行对比，一旦桶里面的数量和下标不相等那么就是要移动的点，所有计数器加一

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class GaoDuJianChaQi {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(heightChecker(a));  //调用结果返回
    }

    //桶排序
    public static  int heightChecker(int[] heights) {
        int count=0; //用于记录最少需要几次
    //建立1,2,3,4,5...100一共101个桶
        int[] arr=new int[101];
    //遍历数组 -- 计算每个桶中有多少元素
        for(int i:heights){
            arr[i]++;
        }
    	
		for(int i=1,j=0;i<arr.length;i++){
        	while(arr[i]-->0){  //一直到结束(桶用完)
            	if(heights[j++]!=i){
                	count++;  //非递减就是说必须下标和当前桶数量相等
            	}
        	}
    	}
        return count;  //返回次数
    }

}

实现

674.最长连续递增序列(动态递归)

题目

分析

1. 主要是一个ans和count两个计数(ans一直是当前位置最长的序列长度)
2. 每一次判断如果是递增就+1 如果不符合就直接为1 这样保证每次最长的给了ans
3. 最后输出的时候看ans大还是count大就输出(有可能count一直++最后一次的时候count比ans还大一个)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class ZuiChangXuLie {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(findLengthOfLCIS(a));
    }

    public static int findLengthOfLCIS(int[] nums) {
        if(nums.length<=1){
            return nums.length;  //长度0/1就是1
        }
        int ans=1;  //存当前的最大的长度
        int count=1;
        for(int i=0;i<nums.length-1;i++){  //因为i+1 所以i只能到最长-1
            if(nums[i]<nums[i+1]){
                count++;  //递增+1
            }else{
                count=1;  //断了就从1开始
            }
            ans=count>ans?count:ans; //返回最大的值
        }
        return ans;
    }

}

实现

35.搜索插入位置(双指针二分法)

题目

分析

1. 找到：就是二分法直到某一次中间指针和要找的一样
2. 没找到：就和之前的找缺少的数字一样不断地二分法

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class SouSuoChaRuWeiZhi {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        int m=input.nextInt();
        System.out.println(searchInsert(a,m));  //调用方法返回结果
    }

    public static int searchInsert(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            int zhong=(left+right)/2;
            if(nums[zhong]==target){ //如果找到了就返回
                return zhong;
            }else   //如果找不到就找缺的位置(和之前的找缺少点一样)
                if(nums[zhong]<target){  //在右边
                   left=zhong+1; 
            }else{   //在左边
                right=zhong-1;
            }
        }
        return left;
    }

}

结果

1299.将每个元素替换成右侧最大元素(反序遍历)

题目

分析

1. 这个题反序遍历会很好做！！！
2. 思路：
    2.1 设置max存放右边最大的值(对比一次就更新一次)
    2.2 设置temp存当前的值(用于更新对比)
    2.3 存放最大值max给当前值 然后进行max更新

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class TiHuanYouCeZuiDa {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        int[] b=replaceElements(a);  //新数组接结果
        for(int i=0;i<n;i++){
            System.out.print(b[i]+" ");
        }
    }
    //反序遍历
    public static int[] replaceElements(int[] arr) {
        int max=-1;  //一开始从最后一个开始赋-1
        for(int i=arr.length-1;i>=0;i--){
            int temp=arr[i];
            arr[i]=max;  //当前值赋给右边最大值
            max=temp>max?temp:max; //max更新为右边最大值
        }
        return arr;
    }

}

结果

167.两数之和II -输入有序数组(双指针)

题目

分析

1. 使用双指针思路： 左右指针相加计算
2. 计算思路(return new int[]{left+1,right+1})：
    2.1 左右指针之和 == target  就直接新建数组返回两个下标
    2.2 左右指针之和 < target 左边太小 左指针右移
    2.3 左右指针之和 > target 右边太大 右指针左移

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class LiangShuHe {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        int m=input.nextInt();
        int[] c=twoSum(a,m);  //接结果数组
        for(int i=0;i<2;i++){
            System.out.print(c[i]+" ");
        }

    }

    public static int[] twoSum(int[] numbers, int target) {
        if(numbers==null){
            return null;
        }
        int left=0;  //左指针
        int right=numbers.length-1;  //右指针
        while(left<right){
            int sum=numbers[left]+numbers[right];  //两个指针所在数组的值
            if(sum==target){
               return new int[]{left+1,right+1};  //直接返回一个新建数组 值就是两个下标
            }else
            if(sum<target){  //左边的太小  左指针右移
                left++;
            }
            else{   //右边的太大 右指针左移
                right--;
            }
        }
        return null;
    }

}

结果

1266.访问所有点的最小时间(切比雪夫距离)

题目

分析

其实就是dx和dy的最大值之和

代码

1
2
3
4
5
6
7
8
9
public int minTimeToVisitAllPoints(int[][] points) {
    int res=0; //最后的距离
    for(int i=1;i<points.length;++i){
        int xMinus=Math.abs(points[i][0]-points[i-1][0]);
        int yMinus=Math.abs(points[i][1]-points[i-1][1]);
        res+=(xMinus>yMinus?xMinus:yMinus); //加两坐标差最大值
    }
    return res;
}

结果

1010.总持续时间可被60整除的歌曲(排列组合)

题目

分析

1. 思路：主要是卡在了如何配对 因为假如20和40配对了但是20还可以和后面的100配对所以没办法取消
        因此借鉴了大佬的将所有数组%60取余数进行分类讨论
2. 具体实现：
        2.1 余数是0的两两配对选择   n*(n-1)/2
        2.2 余数是30的两两配对也是  n*(n-1)/2
        2.3 其他余数就是 n*m

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class LiuShiZhengChuGeQu {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(numPairsDivisibleBy60(a));  //调用方法返回结果
    }

    public static int numPairsDivisibleBy60(int[] time) {
        int[] yu=new int[60];
        for(int i=0;i<time.length;i++) {
            yu[time[i]%60]++;  //每个数字的余数放在yu数组对应下标
        }
        //记录总数的count
        int count=0;
        //1. 余数是0的情况两两选择 ls*(ls-1)/2
        	int ls=yu[0];
        	count=ls*(ls-1)/2;
        //2. 余数是30的情况两两选择 ss*(ss-1)/2
        	int ss=yu[30];
        	count+=ss*(ss-1)/2;
		//3.其余的1对59 2对58就用双指针进行移动添加  n*m
        	int i=1;  //左指针
        	int j=59;//右指针
        	while(i<j){
            	count+=yu[i++]*yu[j--];  //1对59 2对58 3对57等等
        	}
        return count;  //返回成功的对数
    }

}

结果

1351.统计有序矩阵中的负数

题目

分析

1. 类似于剑指offer内的统计正数的个数
2. 我们考虑用两个指针识别
    2.1 如果当前值>0 说明左边的这行都不符合 直接行指针下移一行
    2.2 如果当前值<0 说明下边的这列都符合   直接列指针左移一列 然后将这列的其他元素计数++

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class TongJiFuShu {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int m=input.nextInt();
        int n=input.nextInt();
        int[][] a=new int[m][n];
        for(int i=0;i<m;i++) {
            for (int j=0;j<n;j++) {
                a[i][j]=input.nextInt();  //输入二维数组
            }
        }
        System.out.println("最终负数的个数是:"+countNegatives(a));
    }

    public static int countNegatives(int[][] grid) {
        int count=0;
        int hang=0;  //初始从第一行
        int lie=grid[0].length-1;  //初始从最后一列开始
        for(;hang<grid.length&&lie>=0;){
          //1. 当前位置是正数 因为是递减所以它前面的不符合 直接换下一行
            if(grid[hang][lie]>=0){
                hang++;  //换下一行
            }
          //2. 当前位置是负数  因为是递减所以它下面的都符合 直接换前面一列
            else{
                int temp=hang;  //找个中间值替换行 不然while会改变hang影响count计数
                while(temp<grid.length) {
                    System.out.print(grid[temp++][lie]+" "); //输出这列所有负数
                }
                count+=grid.length-hang; //这一列有几个数字符合 (行长度-当前行)
                lie--;  //换前一列
            }
        }
        return count;
    }

}

结果

1089.复写零(ArrayList集合)

题目

分析

这种题目主要是在0后面加0如果用数组比较麻烦，因此选择list集合

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class FuXieLin {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++) {
            a[i]=input.nextInt();
        }
        ArrayList<Integer> lister=duplicateZeros(a);
        for(int i=0;i<a.length;i++){
            System.out.print(lister.get(i));
        }

    }

    public static ArrayList<Integer> duplicateZeros(int[] arr) {
        ArrayList<Integer> list=new ArrayList<Integer>();
        for(int i=0;i<arr.length;i++){
            if(arr[i]!=0){
                list.add(arr[i]);
            }
            if (arr[i]==0) {
                list.add(arr[i]);
                list.add(arr[i]);
            }
        }
        return list;
    }

}

结果

605.种花问题(贪心)

题目

分析

1. 最左侧： 00...  考虑一侧是不是为0
2. 最右侧： ...00  考虑一侧是不是为0
3. 中间位置：...000...  考虑两侧是不是为0

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class ZhongHua {public static void main(String[] args) {
    Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++) {
            a[i]=input.nextInt();
        }
        int m=input.nextInt();
        System.out.println(canPlaceFlowers(a,m));
    }

    public static boolean canPlaceFlowers(int[] flowerbed, int n) {
        if(n==0) {
            return true; //不种花 返回成功
        }
        int count=0; //记录可以种的个数
        int i=0; //记录下标
        while (i < flowerbed.length) {
            if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {
                flowerbed[i] = 1;  //种花 +1 
                count++;  //记录种了多少次
            }
            i++;
        }
            return count>=n;  //返回是否可以
    }

}

结果

1346.检查整数及其两倍数是否存在(哈希表HashMap)

题目

分析

1. 思路：使用hashMap进行存放数组的所有元素
2. 步骤：
    2.1 先新建hashmap将数组依次放入
    2.2 然后判断0的情况 如果有两个0以上就符合条件
    2.3 然后判断非0的情况 如果2倍的在map里面有的话就说明符合条件

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean checkIfExist(int[] arr) {
    Map map=new HashMap();
    int zeroCount=0;// 对0进行特殊处理
    for (int i = 0; i < arr.length; i++) {
        if(arr[i]==0){// 计算0的个数
            zeroCount++;
        }
        map.put(arr[i],0);  
    }
    if(zeroCount>=2){// 如果存在两个以上的0，就符合
        return true;
    }else {
        for (int i : arr) {
            if (i!=0&&map.containsKey(i * 2)) {  //如果map里面有2倍的i存在
                return true;
            }
        }
    }
    return false;
}

结果

53.最大子序和(动态递归)

题目

分析

1. 首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
2. sum>0，则说明sum有增益效果，则sum保留并加上当前遍历数字
3. sum<=0则说明sum需要舍弃，则sum直接为当前遍历数字
4. 每次比较sum和ans的大小，将最大值置为ans，遍历结束返回结果

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class ZuiDaZiXuHe {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++) {
            a[i]=input.nextInt();
        }
        System.out.println(maxSubArray(a));
    }

    public static int maxSubArray(int[] nums) {
        int ans=nums[0]; //当前最大就是第一个数
        int sum=0;
        for(int i=0;i<nums.length;i++){
          if(sum>0){
             sum+=nums[i];  //sum>0就说明对结果有好处
          }else{
              sum=nums[i];  //sum<0就说明需要扔掉 sum直接成为当前数字
          }
          ans=Math.max(ans,sum);  //每次将当前最大值和 一轮之后的sum比较
        }
        return ans;
    }

}

结果

643.子数组最大平均数(滑动窗口)

题目

分析

1. 思路：我们需要初始化前k个的值,设置ans存最好的结果，he是目前的结果。
2. 滑动窗口：he+=nums[i]-nums[i-k];  //加后面的一个就必须要减去前面一个

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class ZuiDaPingJunShu {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++) {
            a[i]=input.nextInt();
        }
        int k=input.nextInt();
        System.out.println(findMaxAverage(a,k));  //调用方法
    }

    public static double findMaxAverage(int[] nums, int k) {
        double he=0;
        for(int i=0;i<k;i++) {
            he += nums[i];   //加上前面的k个当做初始和
        }
        double ans=he;  //目前结果为初始和
        for(int i=k;i<nums.length;i++){  //从前k个和之后遍历
             he+=nums[i]-nums[i-k];  //加后面的一个就必须要减去前面一个
             ans=Math.max(he,ans);  //每次选最大的更新
        }
        return ans/k;  //he/k就是最终平均值
    }

}

结果

1122.循环遍历矩阵(四个指针)

题目

分析

1. 如果数组为空 --返回为null
2. 如果数组不为空
     2.1 建立ArrayList集合
     2.2 建立四个坐标用于标识数组变化
     2.3 从左往右(行：top            列：left到right)
     2.4 从上到下(行：top+1到bottom  列：right) 
     2.5 从右到左(行：bottom         列：right-1到left)  --注意可能最后是一行就不进行这一步
     2.6 从下到上(行：bottom-1到top  列：left)    --注意可能最后是一列就不进行这一步

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class XiangDuiPaiXu {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int m=input.nextInt();
        int[][] a=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                a[i][j]=input.nextInt();
            }
        }
        System.out.println(spiralOrder(a).toString()); //接结果按字符串返回
    }

    public static ArrayList<Integer> spiralOrder(int[][] a) {
        if(a==null){
            return null;  //如果数组为空 就输出null
        }
        ArrayList<Integer> list=new ArrayList<Integer>();  //新建list集合存结果
        int row=a.length;     //行
        int col=a[0].length;  //列
        int left=0;   //二维数组上面行的最左边
        int right=col-1; //二维数组上面行的最右边
        int top=0;   //二维数组左边的最上边
        int bottom=row-1;  //二维数组左边的最下边
		/*
			假设以4*4举例：
				1  2   3  4
				5  6   7  8
				9  10 11 12
				13 14 15 16
		*/
        while(left<=right&&top<=bottom){
            //1.左到右
                for(int i=left;i<=right;i++){  //输出1 2 3 4(一直到right)
                    list.add(a[top][i]);
                }
            //2.上到下
                for(int i=top+1;i<=bottom;i++){  //输出 8 12 16(从top+1到bottom)
                    list.add(a[i][right]);
                }
            //3.右到左
                if(top!=bottom) {
                    for (int i = right-1; i >=left; i--) {  //输出15 14 13(从right-1到left)
                        list.add(a[bottom][i]);
                    }
                }
            //4.下到上
                if(left!=right) {
                    for (int i = bottom-1; i > top; i--) {  //输出 9 5 1(从bottom到top-1)
                       list.add(a[i][left]);
                    }
                }
            //5.一轮结束之后更改四个坐标
                left++;
                right--;
                top++;
                bottom--;
        }
        return list;  //返回集合
    }

}

结果

53.在排列数组中查找出现次数(二分法)

题目

分析

1. 使用两次二分法确定左边和右边界限
2. 最终次数就是出现的长度 (right-right-1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

public class ChaZhaoShuZi {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
           a[i]=input.nextInt();
        }
        int m=input.nextInt();
        System.out.println(search(a,m));
    }

    public static int search(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
    //1. 找右边界
        while(left<=right){
            int middle=(left+right)/2;
            if (nums[middle]<=target){   //一直找最右边的数字！！！！！！
                left=middle+1;   //在右边
            }else{
                right=middle-1;  //在左边
            }
        }
        int righter=left;

    //初始化左右指针
       left=0;
       right=nums.length-1;

    //2. 找左边界
        while(left<=right){
            int middle=(left+right)/2; 
            if (nums[middle]>=target){   //一直找最左边的数字！！！！！！！
                right=middle-1;   //在右边
            }else{
                left=middle+1;    //在左边
            }
        }
        int lefter=right;
        
        return righter-lefter-1;  //返回出现区间的大小
    }

}

结果

面试4.二维数组中查找(两个指针移动)

题目

分析

1. 制定hang和lie两个指针
2. 二维数组遍历
    /*
        1 4 7 11 15
        2 5 8 12 19
        3 6 9 16 22      假设目标是13
        10 13 14 17 24
        18 21 23 26 30
    */
    2.1 只要当前的比target大(16>13) 说明这一列下面都不符合    换前一列lie--；
    2.2 只要当前的比target小(7<13)  说明这一行左边的都不符合  换下一行hang++；
    2.3 直到遇到的话输出true，没有的话就是false

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class ErWeiShuZuChaZhao {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int m=input.nextInt();
        int[][] a=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                a[i][j]=input.nextInt();
            }
        }
        int target=input.nextInt();
        System.out.println(findNumberIn2DArray(a,target));
    }

    public static boolean findNumberIn2DArray(int[][] a, int target) {
        int hang=0;
        int lie=a.length-1;
        for(int i=0;i<a.length;i++){   //二维数组循环
            for(int j=0;j<a[i].length;j++){
                if(a[i][j]>target){  //这列下面的都比当前的大 只能换前一列找
                    lie--;
                }
                if(a[i][j]<=target){  //这行没看的了 换下一行
                    hang++;
                }
                if(a[i][j]==target){  //找到了就返回true
                    return true;
                }
            }
        }
        return false;
    }

}

结果

面试3.数组中重复的数字(数组下标存储)

题目

分析

1. 遍历数组使用Arrays.sort()方法排序之后通过数组下标存到另外一个数组B。
2. 遍历数组如果里面的值>1就直接break就行，题目只需要输出一个。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class ShuZuChongFuShu {
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(findRepeatNumber(a));
    }

    public static int findRepeatNumber(int[] nums){
        int flag=0;
        Arrays.sort(nums);
        int[] b=new int[nums.length];
        for(int i=0;i<nums.length;i++){
            b[nums[i]]++;
        }
        for(int i=0;i<nums.length;i++){
            if(b[i]>1){
                flag=i;
                break;
            }
        }
        return flag;
    }

}

结果

面试17.主要元素(投票)

题目

分析

1. 思路：我们可以sort排序之后查看中间位置的数字就是主要元素。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class ZhuYaoYuanSu {
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(majorityElement(a));
    }

    public static int majorityElement(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;    //如果没有数组/数组为空  --> 返回-1
        }
        Arrays.sort(nums);  //排序
        int result = nums[nums.length/2];  //下标在中间的数一定是要找的数
        return result;
    }
}

结果

面试17.22.单词转换(DFS/BFS)

题目

分析

代码

1
2


结果

面试17.4消失的数字(双指针二分法)

题目

分析

找缺失数字系列题目
1. 排序(保证按照顺序啦)
2. while循环双指针二分法
    2.1 中间数==下标(前面的没缺少) 左指针到中间的右边一个数字
    2.2 中间数!=下标(前面有缺少)     右指针到中间的左边一个数字

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class DanCiZhuanHuan {
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(missingNumber(a));
    }

    public static int missingNumber(int[] nums) {
        Arrays.sort(nums);  //排序
        int left=0; //左指针
        int right=nums.length-1;  //右指针
            while (left <= right) {
                int zhong = (left + right) / 2;
                if(nums[zhong]==zhong){
                    left=zhong+1; //左边的下标和数值没有断就肯定是相等 所以缺失的在右边 左指针放在中间指针右边
                }
                else{
                    right=zhong-1; //左边肯定缺失了 右指针放到中间指针的左边
                }
            }
        return left;
    }

}

结果

面试16.17.连续数列(动态递归)

题目

分析

1. 首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
2. sum>0，则说明sum有增益效果，则sum保留并加上当前遍历数字
3. sum<=0则说明sum需要舍弃，则sum直接为当前遍历数字
4. 每次比较sum和ans的大小，将最大值置为ans，遍历结束返回结果

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class LianXuShuLie {
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(maxSubArray(a));
    }

    public static int maxSubArray(int[] nums) {
        int ans=nums[0]; //当前最大就是第一个数
        int sum=0;
        for(int i=0;i<nums.length;i++){
            if(sum>0){
                sum+=nums[i];  //sum>0就说明对结果有好处
            }else{
                sum=nums[i];  //sum<0就说明需要扔掉 sum直接成为当前数字
            }
            ans=Math.max(ans,sum);  //每次将当前最大值和 一轮之后的sum比较
        }
        return ans;
    }

}

结果

面试16.15珠玑妙算(HashMap集合)

题目

分析

1. 伪猜中=real-fake
2. 使用HashMap集合：一个存储字母一个是次数
3. 遍历solution字符串，保存每个字母对应的次数
4. 遍历guess字符串，两个字符串 抵消掉猜对的数字其他的就是伪猜中的次数(计算最大匹配成功数)
5. 遍历两个字符串得到真正匹配成功数
6. 最后新建数组弹出real和real-fake即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class ZhuJi {
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        String a=input.next();
        String b=input.next(); 
        int[] ans=masterMind(a,b);
        for(int i=0;i<ans.length;i++){
            System.out.print(ans[i]+" ");
        }
    }

    public static int[] masterMind(String solution, String guess) {
        HashMap<Character,Integer> map = new HashMap<Character,Integer>();

        for(char c:solution.toCharArray()){
            map.put(c,map.getOrDefault(c,0)+1);  //往map里面存solution里面每个字母的个数
        }

        int fake=0,real=0;  //fake伪没猜中  //real为猜中

        for(char c:guess.toCharArray()){
            if(map.containsKey(c)&&map.get(c)>0){  //抵消掉猜对的数字其他的就是伪猜中的次数
                fake++;
                map.put(c,map.get(c)-1);  //减少出现的次数(最后计算最大的匹配成功数)
            }
        }

        for(int i=0;i<4;i++){
            if(solution.charAt(i)==guess.charAt(i)){real++;}  //如果每一位相等说明猜中了+1
        }

        int[] ans={real,fake-real};  //伪猜中包含猜中次数
        return ans;
    }

}

结果

面试08.03魔术索引(双指针二分法)

题目

分析

1. 和找缺失的数组的下标题一样
2. 双指针二分法判断

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class MoShuSuoYin {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(findMagicIndex(a));
    }

    public static int findMagicIndex(int[] nums) {
        int left = 0, right = nums.length;  //左右指针
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] != mid)  //左边有缺少的数字
			{
                if (nums[mid] >= 0) 
				{  
                    right = mid;
                } 
				else 
				{
                    left = mid + 1;  //在右边
                }
            } 
			else
			 {
                left = mid + 1;  //右边有缺少的数字
            }
        }
        return left -1;
    }

}

结果

面试01.02判断是否互为字符重排

题目

分析

1. 统计每个出现次数如果出现次数一样就肯定可以重排
2. 步骤
    2.1 如果长度不同肯定false
    2.2 将s1的每个单词的ascii码存进去一个int数组
    2.3 将s2的每个单词的ascii码从int数组删除掉
    2.4 如果数组还是一直全是0就成功true

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class ZiFuChongPai {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String s1=input.next();
        String s2=input.next();
        System.out.println(CheckPermutation(s1,s2));
    }

    public static boolean CheckPermutation(String s1, String s2) {
        int l1=s1.length();
        int l2=s2.length();
        if(l1!=l2){     //如果两个长度不一样直接返回false
            return false;
        }
        int[] index=new int[128];  //char存的是里面的ascii码
        for(int i=0;i<l1;i++){
            index[s1.charAt(i)]++;  //将s1里面的字符的ascii码添加到数组
            index[s2.charAt(i)]--;  //将s2里面的字符的ascii码从数组删除
        }
        for(int i=0;i<index.length;i++){
            if(index[i]!=0){  //如果存的那个数组里面全空 那就是能重排
                return false;
            }
        }
        return true;
    }

}

结果

面试01.01判断字符是否唯一(首次和最后一次出现位置不同)

题目

分析

1. 使用indexof和lastindexof方法
2. 只要首次和末次出现位置不同就说明至少出现两次以上！！！！

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class PanDuanWeiYi {  public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        String s1=input.next();
        System.out.println(isUnique(s1));
    }
    public static boolean isUnique(String s1) {
        for(char ch:s1.toCharArray()){  ///增强for循环 s1的每个字符
        //第一次和最后一次出现位置不同(一定至少两个)
            if(s1.indexOf(ch)!=s1.lastIndexOf(ch)){
                return false;
            }
        }
        return true;
    }

}

结果

面试01.07旋转矩阵(二次旋转)

题目

分析

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static void rotate(int[][] matrix) {
        int n=matrix.length;  //获取数组长度
        //1. 以对角线(左上-右下)为轴反转
            for(int i=0;i<n-1;i++){  //假如n=3 只取0 1这两行(我们只看右上角)
                for(int j=i+1;j<n;j++){  //假如n=3  依次取01 02 12(右上角三个数字) 
                    int tmp=matrix[i][j];  
                    matrix[i][j] = matrix[j][i];  //对角线的两边的两个数互换
                    matrix[j][i] = tmp;
                }
            }

        //2. 每一行以中点进行翻转
            int mid=n>>1;  //就是取一半(>>二进制向右挪一位)
			/*
				3(0011) -> 1(0001)  所以三列中间的是第二列(下标是1)
				5(0101) -> 2(0010)  所以五列中间的是第三列(下标为2)		
			*/
        for (int i = 0; i < n; i++) {    //所有行都循环
            for (int j = 0; j < mid; j++) {  //列只找到左边一半
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];   //中点行两边的互换 
                matrix[i][n - 1 - j] = tmp;
            }
        }

    }

结果

面试01.08零矩阵(一维数组定行列)

题目

分析

1. 思路：
    1.1 新建两个一维数组存放需要清0的行和列 
2. 步骤：
    2.1 先遍历获取出来要清0的行和列的下标
    2.2 然后遍历查找需要清0的行然后清0
    2.3 然后遍历查找需要清0的列然后清0

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class LingJuZheng {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int m = input.nextInt();
        int n = input.nextInt();
        int[][] a = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++){
                a[i][j] = input.nextInt();
            }
        }
        setZeroes(a); //调用方法进行清0
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++){
                System.out.print(a[i][j]+" ");  //输出数组
            }
            System.out.println();
        }

    }

    public static void setZeroes(int[][] matrix) {
        boolean[] line = new boolean[matrix.length];   //设置两个存放行和列的布尔数组
        boolean[] column = new boolean[matrix[0].length];
        //1.找出要清零的行列
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    line[i] = true;   //存放要清0的行
                    column[j] = true; //存放要清0的列
                }
            }
        }

        //2.开始对行清零
        for (int i = 0; i < matrix.length; i++) {
            if (line[i]) {  //行存在
                for (int j = 0; j < matrix[0].length; j++) {
                    matrix[i][j] = 0;   //所在列清0
                }
            }
        }

        //3.开始对列清零
        for (int i = 0; i < matrix[0].length; i++) {
            if (column[i]) { //列存在
                for (int j = 0; j < matrix.length; j++) {
                    matrix[j][i] = 0;  //所在行清0
                }
            }
        }

    }

}

结果

面试05.08绘制直线(位运算)

题目

分析

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] drawLine(int length, int w, int x1, int x2, int y) {  
        int[] ans=new int[length];
        int low=(y*w+x1)/32;
        int high=(y*w+x2)/32;
        for(int i=low;i<=high;i++){
            ans[i]=-1;
        }
        ans[low]=ans[low]>>>x1%32;
        ans[high]=ans[high]&Integer.MIN_VALUE>> x2 % 32;
        return ans;

    }
}

结果

面试08.04幂集(回溯法)

题目

分析

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class MiDeng {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=input.nextInt();
        }
        System.out.println(subsets(a));
    }

    public static List<List<Integer>> subsets(int[] nums) {
        //结果集合
            List<List<Integer>> list = new ArrayList();
        //回溯方法
            backtrack(list,new ArrayList<>(),nums,0);
        //返回list集合
            return list;
    }

    public static void backtrack(List<List<Integer>>list,List<Integer>tempList,int []nums,int start){
        List<Integer> templist=new ArrayList<>();  //里面临时集合templist
        list.add(tempList); //新建名为tempList集合
        for(int i=start;i<nums.length;i++){
            tempList.add(nums[i]);  //把start之后的元素添加进去
            backtrack(list,tempList,nums,i+1);  //进行下次回溯
            tempList.remove(tempList.size()-1); //移除最后一个
        }
    }

}

结果

所有奇数长度子数组的和

题目

分析

1. 难点就在于怎么确定截取的位置，怎么找到所有奇数位置
2. 考虑从第一位开始找每一位符合的奇数，所以i从0到len
3. 然后就是考虑j的变化，因为每次i变化之后j只能从i后面取，所以j从等于i开始遍历
4. 符合条件: 如果j-i是0 2 4这种的话就是符合条件(i和j都是第二位的话，就算是奇数位，所以是0 2 4)
5. 就可以单独写一个方法计算i到j的和，每次if符合调用返回结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int[] arr=new int[]{1,4,2,5,3};
        System.out.println(sumOddLengthSubarrays(arr));
    }
 
    public static int sumOddLengthSubarrays(int[] arr) {
        int res=0;
        int len=arr.length; //获取数组长度
        for(int i=0;i<len;i++){
           for(int j=i;j<len;j++){
               if((j-i)%2==0){  //奇数距离
                   res+=find(i,j,arr);
                   System.out.println("这次是从第"+(i+1)+"到第"+(j+1)+"个位置求和，和为:"+res);
               }
           }
        }
        return res;
    }

    public static int find(int i,int j,int[] arr){
        int sum=0;
        for(int z=i;z<=j;z++){
            sum+=arr[z];
        }
        return sum;
    }

}

结果

根据数字二进制下1的数目排序(Integer.bitCount()方法)

题目

分析

1. 遍历所有数组求1的个数
2. 将每个数中1的个数*10000+原数
3. Arrays.sort()排序之后在%10000就可以得到排序

代码

1
2
3
4
5
6
7
8
9
10
11
12

public int[] sortByBits(int[] arr) {
    int[] map = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        map[i] = Integer.bitCount(arr[i]) * 10000000 + arr[i];  //1的个数*100000000+原数
    }
    Arrays.sort(map);  //排序
    for (int i = 0; i < map.length; i++) {
        map[i] = map[i] % 10000000;  //取余
    }
    return map;  //返回数组
}

结果

分糖果(一半和不同糖果数对比)

题目

分析

1. 妹妹和弟弟手里都是a.length/2个糖果
2. 具体妹妹拿多少就要看set去重和平均值得大小对比

代码

1
2
3
4
5
6
7
8

public int distributeCandies(int[] candies) {
       HashSet < Integer > set = new HashSet < > ();
       for (int candy: candies) {
           set.add(candy);  //记录不同糖果的个数
       }
       return Math.min(set.size(), candies.length / 2);  //对比两者
   }

结果

数组序号转换(map集合存<数字,序号>)

题目

分析

1. 因为有重复的数字 所以直接输出不太好弄
2. 使用map集合存储每个数字和数字出现的位置(排序sort之后就好弄)
3. for循环a数组，这样可以顺序填进去

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public static int[] arrayRankTransform(int[] a) {
       int n=a.length;  //数组长度
       int[] temp=a.clone();  //赋值a数组生成新的temp数组
       Arrays.sort(temp);  //sort排序
       int count=1;
       Map<Integer,Integer> map=new HashMap<>();  //生成map集合
       for(int i=0;i<n;i++){
           if(!map.containsKey(temp[i])){
               map.put(temp[i],count++);  //只将不重复的数字  存入数字和序号
           }
       }
       for(int i=0;i<n;i++){
           a[i]=map.get(a[i]);  //遍历a数组 将序号放入
       }
       return a;  //输出原数组
   }

结果

最长和谐子序列(枚举)

题目

分析

1. 从第一位开始遍历 找到跟他一样大而且比他大1的数字就count计数器+1
2. 注意就是一定要有比他大1的数，用一个布尔值确定有没有。!!!!!

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public int findLHS(int[] nums) {
       int res = 0;   //接住最后结果
       for (int i = 0; i < nums.length; i++) {   //遍历所有元素
           int count = 0;  //记录每个元素的个数
           boolean flag = false;
           for (int j = 0; j < nums.length; j++) {
               if (nums[j] == nums[i])  //找到和当前值一样的值可以当做序列值
                   count++;
               else if (nums[j] + 1 == nums[i]) {  //找到比当前值大1的值也可以当序列值
                   count++;
                   flag = true; //标志改为true  说明满足有最大最小值
               }
           }
           if (flag)
               res = Math.max(count, res);  //如果有的话 就找最大值
       }
       return res;  //返回res结果
   }

结果

赏

×

纯属好玩

扫码支持
扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦

本文标题:LeetCode数组

文章作者:Larkkkkkkk

发布时间:2020年05月27日 - 21时24分

最后更新:2020年11月02日 - 15时31分

原始链接:https://larkkkkkkk.github.io/2020/05/27/LeetCode%E6%95%B0%E7%BB%84/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 1160.拼写单词(统计出现次数)
    1. 1.1. 题目
    2. 1.2. 分析
    3. 1.3. 代码
    4. 1.4. 结果
  2. 2. 88.合并两个有序整数数组(ArrayList集合)
    1. 2.1. 题目
    2. 2.2. 分析
    3. 2.3. 代码
    4. 2.4. 结果
  3. 3. 53. 0-n-1中缺失的数字(双指针二分查找)
    1. 3.1. 题目
    2. 3.2. 分析
    3. 3.3. 代码
    4. 3.4. 实现
  4. 4. 118.杨辉三角形(动态递归)
    1. 4.1. 题目
    2. 4.2. 分析
    3. 4.3. 代码
    4. 4.4. 实现
  5. 5. 26.删除排序数组中的重复项(HashSet集合)
    1. 5.1. 题目
    2. 5.2. 分析
    3. 5.3. 代码
    4. 5.4. 结果
  6. 6. 1051.高度检查器(桶排序)
    1. 6.1. 题目
    2. 6.2. 分析
    3. 6.3. 代码
    4. 6.4. 实现
  7. 7. 674.最长连续递增序列(动态递归)
    1. 7.1. 题目
    2. 7.2. 分析
    3. 7.3. 代码
    4. 7.4. 实现
  8. 8. 35.搜索插入位置(双指针二分法)
    1. 8.1. 题目
    2. 8.2. 分析
    3. 8.3. 代码
    4. 8.4. 结果
  9. 9. 1299.将每个元素替换成右侧最大元素(反序遍历)
    1. 9.1. 题目
    2. 9.2. 分析
    3. 9.3. 代码
    4. 9.4. 结果
  10. 10. 167.两数之和II -输入有序数组(双指针)
    1. 10.1. 题目
    2. 10.2. 分析
    3. 10.3. 代码
    4. 10.4. 结果
  11. 11. 1266.访问所有点的最小时间(切比雪夫距离)
    1. 11.1. 题目
    2. 11.2. 分析
    3. 11.3. 代码
    4. 11.4. 结果
  12. 12. 1010.总持续时间可被60整除的歌曲(排列组合)
    1. 12.1. 题目
    2. 12.2. 分析
    3. 12.3. 代码
    4. 12.4. 结果
  13. 13. 1351.统计有序矩阵中的负数
    1. 13.1. 题目
    2. 13.2. 分析
    3. 13.3. 代码
    4. 13.4. 结果
  14. 14. 1089.复写零(ArrayList集合)
    1. 14.1. 题目
    2. 14.2. 分析
    3. 14.3. 代码
    4. 14.4. 结果
  15. 15. 605.种花问题(贪心)
    1. 15.1. 题目
    2. 15.2. 分析
    3. 15.3. 代码
    4. 15.4. 结果
  16. 16. 1346.检查整数及其两倍数是否存在(哈希表HashMap)
    1. 16.1. 题目
    2. 16.2. 分析
    3. 16.3. 代码
    4. 16.4. 结果
  17. 17. 53.最大子序和(动态递归)
    1. 17.1. 题目
    2. 17.2. 分析
    3. 17.3. 代码
    4. 17.4. 结果
  18. 18. 643.子数组最大平均数(滑动窗口)
    1. 18.1. 题目
    2. 18.2. 分析
    3. 18.3. 代码
    4. 18.4. 结果
  19. 19. 1122.循环遍历矩阵(四个指针)
    1. 19.1. 题目
    2. 19.2. 分析
    3. 19.3. 代码
    4. 19.4. 结果
  20. 20. 53.在排列数组中查找出现次数(二分法)
    1. 20.1. 题目
    2. 20.2. 分析
    3. 20.3. 代码
    4. 20.4. 结果
  21. 21. 面试4.二维数组中查找(两个指针移动)
    1. 21.1. 题目
    2. 21.2. 分析
    3. 21.3. 代码
    4. 21.4. 结果
  22. 22. 面试3.数组中重复的数字(数组下标存储)
    1. 22.1. 题目
    2. 22.2. 分析
    3. 22.3. 代码
    4. 22.4. 结果
  23. 23. 面试17.主要元素(投票)
    1. 23.1. 题目
    2. 23.2. 分析
    3. 23.3. 代码
    4. 23.4. 结果
  24. 24. 面试17.22.单词转换(DFS/BFS)
    1. 24.1. 题目
    2. 24.2. 分析
    3. 24.3. 代码
    4. 24.4. 结果
  25. 25. 面试17.4消失的数字(双指针二分法)
    1. 25.1. 题目
    2. 25.2. 分析
    3. 25.3. 代码
    4. 25.4. 结果
  26. 26. 面试16.17.连续数列(动态递归)
    1. 26.1. 题目
    2. 26.2. 分析
    3. 26.3. 代码
    4. 26.4. 结果
  27. 27. 面试16.15珠玑妙算(HashMap集合)
    1. 27.1. 题目
    2. 27.2. 分析
    3. 27.3. 代码
    4. 27.4. 结果
  28. 28. 面试08.03魔术索引(双指针二分法)
    1. 28.1. 题目
    2. 28.2. 分析
    3. 28.3. 代码
    4. 28.4. 结果
  29. 29. 面试01.02判断是否互为字符重排
    1. 29.1. 题目
    2. 29.2. 分析
    3. 29.3. 代码
    4. 29.4. 结果
  30. 30. 面试01.01判断字符是否唯一(首次和最后一次出现位置不同)
    1. 30.1. 题目
    2. 30.2. 分析
    3. 30.3. 代码
    4. 30.4. 结果
  31. 31. 面试01.07旋转矩阵(二次旋转)
    1. 31.1. 题目
    2. 31.2. 分析
    3. 31.3. 代码
    4. 31.4. 结果
  32. 32. 面试01.08零矩阵(一维数组定行列)
    1. 32.1. 题目
    2. 32.2. 分析
    3. 32.3. 代码
    4. 32.4. 结果
  33. 33. 面试05.08绘制直线(位运算)
    1. 33.1. 题目
    2. 33.2. 分析
    3. 33.3. 代码
    4. 33.4. 结果
  34. 34. 面试08.04幂集(回溯法)
    1. 34.1. 题目
    2. 34.2. 分析
    3. 34.3. 代码
    4. 34.4. 结果
  35. 35. 所有奇数长度子数组的和
    1. 35.1. 题目
    2. 35.2. 分析
    3. 35.3. 代码
    4. 35.4. 结果
  36. 36. 根据数字二进制下1的数目排序(Integer.bitCount()方法)
    1. 36.1. 题目
    2. 36.2. 分析
    3. 36.3. 代码
    4. 36.4. 结果
  37. 37. 分糖果(一半和不同糖果数对比)
    1. 37.1. 题目
    2. 37.2. 分析
    3. 37.3. 代码
    4. 37.4. 结果
  38. 38. 数组序号转换(map集合存<数字,序号>)
    1. 38.1. 题目
    2. 38.2. 分析
    3. 38.3. 代码
    4. 38.4. 结果
  39. 39. 最长和谐子序列(枚举)
    1. 39.1. 题目
    2. 39.2. 分析
    3. 39.3. 代码
    4. 39.4. 结果
,