第五章习题总结

Demo 01

解答：

数据：用户输入的数组

步骤：

1. 提示用户输入数据 
2. 构建动态的扩容数组填充数据
3. 判断数据中是否存在0  存在则跳出遍历
4. 验证用户输入数据的合法性
5. 按照输出的结果 将数据中的数据进行排序
6. 输出连续相等的数字
7. 将问题转化成如何判断连续相等的数出现的次数

import java.util.*;
class Demo05_01{
    public static void main(String[] args){
        /*
        思路1：数组长度不固定 需要读取一个数据 数组扩容 填入数据
        数据填入之后进行排序 然后遍历数组依次判断数据的个数
        连续相等
        2 2 2 2 3 3 4 4 4 4 5 5 6 6 6 6 7 7
        思路2：借助计数排序的思想 将数组固定起来
        */
        //1.获取用户输入的数据 动态的扩容数组填充数据
        Scanner scanner = new Scanner(System.in);
        int[] arr=new int[0];
        System.out.print("Enter numbers:");

        while(true){
            int num=scanner.nextInt();
            if(num==0){
                break;
            }
            //验证用户输入数据的正确性
            if(num<1||num>100){
                System.out.println("有非法数据！");
                return;
            }
            arr=copyOf(arr,arr.length+1);
            arr[arr.length-1]=num;
        }
        //2.按照输出结果 将数据中的数据进行排序
        insertSort(arr);
        //3.输出连续相等的数字
        show(arr);
    }
    public static int[] copyOf(int[] arr,int newLen){
        int[] newArr=new int[newLen];
        for(int i=0;i<arr.length;i++){
            newArr[i]=arr[i];
        }
        return newArr;
    }
    public static void insertSort(int[] arr){
        for(int i=1;i<arr.length;i++){
            int e=arr[i];
            int j;
            for(j=i;j>0&&arr[j-1]>e;j--){
                arr[j]=arr[j-1];
            }
            arr[j]=e;
        }
    }
    /*
    Arrays Math都是属于工具类
    Arrays 特殊的是数组的工具类
        toString(arr) 就是将数据的每个元素进行拼接 并返回拼接后的字符串数据
        "[1,2,3,4]"
    */
    public static void show(int[] arr){
        System.out.println(Arrays.toString(arr));
        //此时就将问题转成了如何判断连续相等的数据分别出现多少次
        //[1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 5, 5, 6]
        for(int i=0;i<arr.length;){
            int count=1;
            for(int j=i+1;j<arr.length;j++){
                if(arr[j]==arr[i]){
                    count++;
                }else{
                    break;
                }
            }
            System.out.println(arr[i]+" occurs "+count+(count>1?" times":" time"));
            i+=count;
        }
    }
}

Demo 02

 

 

解答：

数据：用户输入数据 

步骤：

1. 提示用户输入数据 创建动态数组进行赋值
2. 不创建额外空间 不改变原先的顺序
3. 利用插入排序对数据进行排序
4. 找出连续相等的数进行覆盖
5. 整理输出结果

import java.util.*;
class Demo05_02{
    public static void main(String[] args){
        /*
        思路1
            在全部输入之后去重复 func1
        思路2
            边输入边去重复 func2
        */
        // func1();
        func2();
    }
    public static void func2(){
        int[] arr=new int[0];
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter numbers:");
        for(int i=0;i<10;i++){
            int num=scanner.nextInt();
            if(!contains(arr,num)){
                arr=copyOf(arr,arr.length+1);
                arr[arr.length-1]=num;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
    public static void func1(){
        //1.循环遍历数组进行赋值
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter numbers:");
        int[] arr = new int[10];
        for(int i = 0;i < arr.length;i++){
            arr[i] = scanner.nextInt();
        }
        //2.开始对已有的数据进行去重复操作
        // 1 2 3 3 2 4 3 2 4 1
        // 1 2 3 4
        // method1(arr);        //空间S(n) 时间O(nm)
        // method2(arr);        //空间S(1) 时间O(n^2)
        // method3(arr);
    }
    public static void method3(int[] arr){
        //不创建额外空间 不许改变原先的顺序
        int i=0;
        int size=arr.length;
        while(i<size){
            for(int j=i+1;j<size;){
                if(arr[j]==arr[i]){
                    for(int k=j+1;k<size;k++){
                        arr[k-1]=arr[k];
                    }
                    size--;
                }else{
                    j++;
                }
            }
            i++;
        }
        for(i=0;i<size;i++){
            System.out.print(arr[i]+" ");
        }
    }
    public static void method2(int[] arr){
        //插入排序
        for(int i=1;i<arr.length;i++){
            int e=arr[i];
            int j;
            for(j=i;j>0&&arr[j-1]>e;j--){
                arr[j]=arr[j-1];
            }
            arr[j]=e;
        }
        //连续相等
        for(int i=0;i<arr.length;){ //O(n)
            System.out.print(arr[i]+" ");
            int count=1;
            for(int j=i+1;j<arr.length;j++){
                if(arr[j]==arr[i]){
                    count++;
                }else{
                    break;
                }
            }
            i+=count;
        }
    }
    public static void method1(int[] arr){
        int[] newArr=new int[0];
        for(int i=0;i<arr.length;i++){ //O(n)
            if(!contains(newArr,arr[i])){ //O(m)
                newArr=copyOf(newArr,newArr.length+1);
                newArr[newArr.length-1]=arr[i];
            }
        }
        System.out.println(Arrays.toString(newArr));
    }
    public static boolean contains(int[] arr,int key){
        for(int i=0;i<arr.length;i++){
            if(arr[i]==key){
                return true;
            }
        }
        return false;
    }
    public static int[] copyOf(int[] arr,int newLen){
        int[] newArr=new int[newLen];
        for(int i=0;i<arr.length;i++){
            newArr[i]=arr[i];
        }
        return newArr;
    }

}

Demo 03

 

 

 

解答：

数据：用户输入 list1  

步骤：

1. 提示用户输入数据
2. 构造动态数据遍历数据对数组进行赋值
3. 对数组进行有序的判断 true （“The list is already sorted”） false（“The list is not sorted”）
4. 构造函数 寻找数列中左大右小的情况 判断
5. 输出判断结果

import java.util.*;
class Demo05_03{
    public static void main(String[] args){
        //1.获取用户的输入 只不过第一个输入的数据时数据的个数(数组的长度)
        Scanner scanner=new Scanner(System.in);
        System.out.print("Enter a list:");
        int len=scanner.nextInt();//获取的第一个数值就是数组的长度
        int[] arr=new int[len];
        for(int i=0;i<arr.length;i++){
            arr[i]=scanner.nextInt();
        }
        //2.对数组进行有序的判断
        if(isSorted(arr)){
            System.out.println("The list is already sorted.");
        }else{
            System.out.println("The list is not sorted.");
        }
    }
    public static boolean isSorted(int[] list){
        //如果不是升序排列 那么势必会出现有一组数据 左大右小的情况
        for(int i=1;i<list.length;i++){
            if(list[i-1]>list[i]){
                return false;
            }
        }
        return true;
    }

}

Demo 04

 

 

 

解答：

数据：用户输入小球数 balls 槽子数 slots  路径 path 左 L  右 R  \

步骤：

1. 提示用户输入小球数balls 和槽子数 slots
2. 根据已有的槽子的个数去创建槽子容器  
3. 根据已有的球和槽子的个数去创建一个小球的下落路径  运用随机数产生
4. 路径中经过几个钉子？路径的步骤有几 步和槽子的个数有关
5. 如何通过路径的经过得知最终所落入的槽子
6. 按照题目要求用LR输出路径和小球分布状况

import java.util.*;
class Demo05_04{
    /*
    输入的数据：槽子的个数 球的个数=路径的个数
               创建槽子的具体的容器int[]
               每一个小球下落的路径L R 字符串
               对于每一个小球而言其路径中的步骤是随机产生L R
    1.提示用户输入槽子的个数和小球的个数
    2.根据已有的槽子的个数去创建槽子容器
    3.根据已有的球和槽子的个数去随机创建一个小球下落的路径
    4.路径中经过几个钉子？路径的步骤有几步 和槽子的个数有关
    5.如何通过路径的经过得知最终所落入的槽子？
    */
    public static void main(String[] args){
        //1.
        Scanner scanner=new Scanner(System.in);
        System.out.print("Enter the number of balls to drop:");
        int balls=scanner.nextInt();
        System.out.print("Enter the number of slots in the bean machine:");
        int slots=scanner.nextInt();
        //2.
        int[] arr=new int[slots];
        //3.几个球几个路径path
        for(int i=0;i<balls;i++){
            String path=getPath(slots);
            System.out.println(path);
            //5.只要看当前路径中R的个数即可
            arr[getR(path)]++;
        }
        //6.输出
        System.out.println(Arrays.toString(arr));
        show(arr);
    }
    public static void show(int[] arr){
        int w=arr.length;
        int h=0;
        for(int i=0;i<arr.length;i++){
            if(arr[i]>h){
                h=arr[i];
            }
        }
        for(int i=h-1;i>=0;i--){
            for(int j=0;j<w;j++){
                if(i<arr[j]){
                    System.out.print("O");
                }else{
                    System.out.print(" ");
                }
            }
            System.out.println();
        }

    }
    public static int getR(String path){
        int count=0;
        for(int i=0;i<path.length();i++){
            if(path.charAt(i)=='R'){
                count++;
            }
        }
        return count;
    }
    public static String getPath(int slots){
        //4.根据槽子的个数计算每一个球下落的路径
        Random random=new Random();
        String path="";
        for(int j=0;j<slots-1;j++){
            if(random.nextInt(2)==0){   //向左
                path+="L";
            }else{  //向右
                path+="R";
            }
        }
        return path;
    }
}

Demo 05

 

解答：

数据： 用户输入 list1   list2

步骤：

1. 提示用户输入数据
2. 先判断两个数组的长度是否相同
3. 再判断两个数组中的元素是否完全相同
4. 最终输出判断结果

import java.util.*;
class Demo05_05{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter list1:");
        int length1 = scanner.nextInt();
        int[] list1 = new int[length1];
        for(int i =0;i<list1.length;i++){
              list1[i]=scanner.nextInt();
        }
      
        System.out.print("Enter list2:");
        int length2 = scanner.nextInt();
        int[] list2 = new int[length2];
        for(int j =0;j<list2.length;j++){
              list2[j]=scanner.nextInt();
        }

        System.out.println(equals(list1,list2));
    }
    public static boolean equals(int[] list1,int[] list2){
        //判断两个数组是否完全相同
        //1.先判断长度
        if(list1.length!=list2.length){
            return false;
        }
        //2.再依次判断元素大小
        for(int i=0;i<list1.length;i++){
            if(list1[i]!=list2[i]){
                return false;
            }
        }
        return true;
    }
}

 

Demo 06

 

 

 

解答：

数据：  用户输入 list 1  list 2  合并 list3

步骤：

1. 提示用户输入数据 list1 list2
2. 判断list1 与list是否存在空串
3. 判断list 1 list 2长度差异 
4. 合并成list3

import java.util.*;
class Demo05_07{
    public static void main(String[] args){
        int[] list1={1,3,5,7,9};
        int[] list2={2,4,6,8,10};
        System.out.println(Arrays.toString(merge(list1,list2)));
    }
    /*
    有序数组的合并
    最主要的问题在于 数组之间有长有短
    */
    public static int[] merge(int[] list1,int[] list2){
        if(list1==null&&list2==null){
            return null;
        }
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        //只有两个都不是null的情况再考虑具体操作
        int[] list3=new int[list1.length+list2.length];
        int p1=0;
        int p2=0;
        int p3=0;
        while(true){
            if(p1==list1.length&&p2==list2.length){
                break;
            }
            if(p1<list1.length&&p2==list2.length){
                list3[p3++]=list1[p1++];
            }else if(p1==list1.length&&p2<list2.length){
                list3[p3++]=list2[p2++];
            }else{
                if(list1[p1]<=list2[p2]){
                    list3[p3++]=list1[p1++];
                }else{
                    list3[p3++]=list2[p2++];
                }
            }
        }
        return list3;
    }
}