package com.model.number;

/**
 * @Description:测试类
 * @Author: 张紫韩
 * @Crete 2021/8/28 20:04
 * 跳跃问题
 */
public class NumberDemo03 {
    public static int res=Integer.MAX_VALUE;
    public static void main(String[] args) {

        int[] arr={4,1,5,1,1,1,7,1,1,1};
        System.out.println(jump2(arr));

    }
    

    public static int jump2(int[] arr){
//        无法跳跃的情况
        if (arr.length<1||arr[0] == 0){
            return -1;
        }
//
        int jump=0;
        int next=0;
        int cur=0;
        for (int i = 0; i < arr.length; i++) {
            if (i>cur){
                jump++;
                cur=next;
            }
            next=Math.max(next, i+arr[i]);
        }

        return jump;
    }
}

package com.model.number;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @Description:测试类
 * @Author: 张紫韩
 * @Crete 2021/8/28 23:16
 * 找出一个区间内最大的连续空间的长度
 */
public class NumberDemo04 {
    public static void main(String[] args) {
        int[] arr={1,3,5,4,9,81,132,5456,65,2123,2};
        System.out.println(len(arr));
        System.out.println(arrLen(arr));

    }
    public static int len(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-1-i; j++) {
                if (arr[j]>arr[j+1]){
                    arr[j]=arr[j]^arr[j+1];
                    arr[j+1]=arr[j]^arr[j+1];
                    arr[j]=arr[j]^arr[j+1];
                }
            }
        }
        System.out.println(Arrays.toString(arr));
        int max=0;
        for (int i = 0; i < arr.length; i++) {
            int temp=1;
            for (int j = i+1; j < arr.length; j++) {
                if (j-i==arr[j]-arr[i]){
                    temp++;
                }else {
                    i=j;

                    break;
                }
            }
            max=Math.max(max    , temp);
        }
        return max;
    }

    public static int arrLen(int[] arr){

        HashMap<Integer, Integer> map = new HashMap<>();
//        map 中存放以某个数据为开头或者结尾的数据,key代表某个数,value代表的一共有几个连续的数
//        首先将某个数据放进map中,查看是否存在以 num-1和num+1 为开头或结尾的数据存在
//        如果存在就是将他们进行合并
        int res=0;
        for (int num:arr){
            if (!map.containsKey(num)){
                map.put(num, 1);
                Integer leftLen = map.getOrDefault(num - 1, 0);
                Integer rightLen =  map.getOrDefault(num + 1, 0);
                int all=leftLen+1+rightLen;
               map.put(num-leftLen, all);
               map.put(num+ rightLen, all);
               res=Math.max(all, res);
            }


        }
        return res;



    }
}

package com.model.array;

/**
 * @Description:测试类
 * @Author: 张紫韩
 * @Crete 2021/8/28 23:58
 * 在二维数组中找出某个数target是否存在
 * 二维数组每一行都是有序的
 */
public class ArrayDemo02 {
    public static void main(String[] args) {

        int[][] matrix={{1,2,3,4},{10,20,30,40},{11,12,13,45}};
        System.out.println(find(matrix, 13));
    }
    public static boolean find(int[][] matrix,int target){

        int row=0;
        int col=matrix[0].length-1;
        while (row<matrix.length&&col>=0){
            if (matrix[row][col]<target){
                row++;
                col=matrix[0].length-1;
            }else {
                if (target==matrix[row][col]){
                    return true;
                }
                col--;
            }
        }
        return false;

    }
}

package com.model.array;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Description:测试类
 * @Author: 张紫韩
 * @Crete 2021/8/29 0:14
 * 找到一个有0和1组成的二位数组
 * 找出那个行有最多1,返回那个行号
 * */
public class ArrayDemo03 {
    public static void main(String[] args) {

        int[][] matrix={{1,1,1,1,1,1,1,1},{0,0,1,1,1,1,1,1},{0,0,0,0,1,1,1,1},{0,0,1,1,1,1,1,1}};
        ArrayList<Integer> list = matrix(matrix);
        for(Integer num:list){
            System.out.println(num);
        }
    }
    public static ArrayList<Integer> matrix(int[][] matrix){
        ArrayList<Integer> resList = new ArrayList<>();

        int row=0;
        int col=matrix[0].length-1;
        int max=0;
        int temp=0;
        while (row< matrix.length&&col>=0){
            if (matrix[row][col]==1){
                col--;
                temp++;
                if (col==0) break;
            }else{
                if (matrix[row][col+1]==1){
                    if (max < temp) {
                        resList.clear();
                        max = temp;
                    }
                    resList.add(row);
                }
                row++;
            }

        }
        
        if (col==0){
            for (int i = 0; i <matrix.length ; i++) {
                if (matrix[i][0]==1){
                    resList.add(i);
                }
            }

        }
        return resList;
    }
}