Java-15

数组

产生伪随机数的方法

Math.random()：该方法返回一个double型的范围在[0.0, 1.0)的正数。
(int)(Math.random() * (b - a) + a)：利用该方法产生范围在[a, b)的整数。

字符串比较的方法

String.equals(Object anObject)：该方法返回一个boolean值，当且仅当参数对象非null且字符序列与String的字符序列一致时，返回true，否则返回false。简单地说，就是比较两个字符串中每个字符是否相等。

快捷键note

alt + /：方法提示。

涉及数组的常见算法

数组元素的赋值

这类算法要解决的关键问题是：如何给数组赋值。

给数组赋值涉及两种情况：
1）针对一维数组，只需考虑如何给每个位置的元正确赋值。
2）针对二维数组（或者说多维数组），给数组元素赋值就涉及设置每个元素的长度和值，因为每个元素又是一个数组。

这类算法题一般就是针对二维数组的情况，代表性算法题有：杨辉三角、回形数。

杨辉三角就是典型的既要设计好二维数组中每个元素的形状，也要考虑好每个元素的元素如何正确赋值。
回形数重点是如何给每个位置正确赋值。

回形数
1）算法1：

确定是否需要设计数组形状：回形数问题中所要赋的值是固定规律的就是顺序的自然数，数和形状之间不像杨辉三角那样存在明显规律，因此无需考虑设计数组形状。
因此，对该题按照标准的二维数组形状（该题输出要求就是这样的形状），来考虑如何在每个位置上正确赋值。
此时可以分为两种情况：1）回形数形状为1时，此时无需创建二维数组，直接输出1即可。2）回形数形状大于1时假设为n，此时二维数组形状就为n * n，此时就需要考虑在每个位置上正确赋值。
考虑到每个值的固定规律是顺序自然数，因此按照顺序自然数来观察赋值规律，发现是按照四个方向顺时针循环赋值，四个方向赋值完一次结束一次循环。
因此，需要考虑每个方向每次赋值到哪个位置。发现每次循环每个方向有一个赋值终点位置，而每个方向的前一个方向的赋值终点位置是每个方向的起始赋值位置。并且每次循环结束后，需要更新每个方向的赋值终点位置，实际上就是从外层到内层的更新，以保证下次按方向赋值的正确。

最后考虑终止循环方向赋值的条件。
存在两种情况：1）最后四个方向归于一个位置；2）最后四个方向位置相邻。
根据每个方向的终点位置是下一个方向的起点位置可知，当起点位置超过或终点位置时即结束赋值，这实际上对应于第二种情况。另外，起点位置等于终点位置时表示最后四个方向都归于一个位置，此时不需要循环，但需要给最后一个位置赋值，对应于第一种情况。
2023-08-26T10:00:15.png
2）代码1：

package arrayexercise;

import java.util.Scanner;

public class ReturnNumber {

 public static void main(String[] args) {
     Scanner s = new Scanner(System.in);
     System.out.print("Please input a number: ");
     int num = s.nextInt();
     if(num == 1) {
         System.out.println("Return number is: " + num);
     }
     else {
         int[][] returnNum = new int[num][num];
         // 4个方向的终点
         //每次按照顺时针，分别对四个方向进行赋值，每个方向赋值到终点位置的前一个位置，
         //且每个方向的终点位置为下一个方向的起点位置
         int[] left2Right = new int[] {0, num - 1};  //(0, 2)
         int[] up2Down = new int[] {num - 1, num - 1};  //(2, 2)
         int[] right2Left = new int[] {num - 1, 0};  //(2, 0)
         int[] down2Up = new int[] {0, 0};  //(0, 0)
         
         //赋值变量，每赋值一次加1
         int value = 1;
         
         //终止条件标志
         boolean isContinue = true;
         boolean condition = false;
         
         do {
             //每个方向对应的数组的0位置，代表了该方向当前在第几行，1位置代表了应该在当前行赋值的终点
             for(int i = down2Up[1]; i < left2Right[1]; i++) {
                 returnNum[left2Right[0]][i] = value++;
             }
             for(int i = left2Right[0]; i < up2Down[0]; i++) {
                 returnNum[i][up2Down[1]] = value++;
             }
             for(int i = up2Down[1]; i > right2Left[1]; i--) {
                 returnNum[right2Left[0]][i] = value++;
             }
             for(int i = right2Left[0]; i > down2Up[0]; i--) {
                 returnNum[i][down2Up[1]] = value++;
             }
             
             //更新各个方向的赋值终点
             left2Right[0]++;
             left2Right[1]--;
             up2Down[0]--;
             up2Down[1]--;
             right2Left[0]--;
             right2Left[1]++;
             down2Up[0]++;
             down2Up[1]++;
             
             //判断是否终止赋值
             condition = left2Right[0] >= up2Down[0] && up2Down[1] <= right2Left[1] && right2Left[0] <= down2Up[0] && down2Up[1] >= left2Right[1];
             if(condition) {
                 if(left2Right[0] == up2Down[0] && up2Down[1] == right2Left[1] && right2Left[0] == down2Up[0] && down2Up[1] == left2Right[1]) {
                     returnNum[left2Right[0]][left2Right[1]] = value;
                 }
                 isContinue = false;
             }
         }while(isContinue);
         for(int i = 0; i < returnNum.length; i++) {
             for (int j = 0; j < returnNum[i].length; j++) {
                 System.out.print(returnNum[i][j] + "\t");
             }
             System.out.println();
         }
     }

 }

}

2023-08-26T10:01:22.png

求数值型数组中的最大值、最小值、平均数、总和等

2023-08-26T12:41:44.png
2023-08-26T12:41:58.png

数组的复制、反转、查找

1 数组的复制

无法通过赋值运算符，即=，实现数组的复制。
使用=，实现的只是将数组指针指向另一个数组，也就是说并没有创建新的数组出来，两个数组是共享内存空间中的一个数组。
实现数组的复制，需要通过先定义一个新的数组，然后赋值元素，以实现。

2 数组元素的反转
通过观察反转顺序和原始顺序，能够发现元素与元素之间实现反转过程的规律，也就是两头对称的元素交换。
2023-08-26T13:08:56.png
2023-08-26T13:14:26.png

3 数组元素的查找
数组元素的查找，也称为搜索，该问题是：有一个目标，通过某种方式查看数组中是否存在该目标，存在则返回该目标的在数组中的索引，不存在则提示不存在。

这里介绍两种数组元素的查找算法：
1) 线性查找
线性查找是指，通过将数组中每个元素与目标元素进行匹配，以实现查找。
线性查找适用于所有场景，但效率也是最低的。
2023-08-27T08:11:11.png

2) 二分查找
有些场景下，可以采用更高效的方法实现查找。
有些场景下，目标元素与数组中的元素满足同一个原则，比如数字元素之间存在比较原则，使得数组中每个元素与目标元素的匹配结果，即使不是匹配成功，也能够排除掉一些元素，从而大大提高查找效率。

二分查找就是利用了排除这一点，在数组元素有序的场景下，初始时将目标元素与数组中的中间元素进行匹配，匹配成功则直接返回索引，匹配失败则根据匹配的比较结果，能够排除一半的元素，使得目标元素只需在另一半元素中进行匹配，每次匹配都按照上述同样的方法，即每次匹配要么匹配成功要么排除当前匹配元素中的一半元素，因此大大提高查找效率。

二分查找并不适用于所有场景，通常使用在有序场景下。
2023-08-27T08:10:41.png

数组元素的排序

1) 排序
排序是指通过对数组中的元素进行比较和移动，使得数组中所有元素都在要求的顺序下的合适位置上。

排序存在两种策略：

每次完成对一个元素的正确排序，一共进行元素数-1次即可完成对所有元素的排序。
通过每次进行一种比较和移动，使得所有元素逐次变得有序。

对应于排序的两种策略，排序本质上就是对一种操作的循环：

对于第一种策略：需要一种能够完成对一个元素正确排序的方法，将该方法转换为一种操作，然后循环进行。
对于第二种策略：需要一种能够实现某种效果的方法，该方法重复多次即可实现排序，将该方法转换为一种操作，然后循环进行。
比如每次完成一部分有序，多次进行，可以扩展到所有元素有序。

因此排序主要考虑两个问题：

一种能够实现一个元素正确排序或某种局部排序效果的循环方法
如何循环实现所有元素的正确的排序
- 每次循环的条件设计
- 循环的次数

2023-08-27T08:35:10.png
2023-08-27T08:36:28.png

稳定性往往用作一种前提条件，比如当前数组中元素是按照销量从大到小排序的，需要在该基础上将元素按照价格从大到小排序，也就是说结果需要的是价格从大到小，同时相同价格的元素销量高的在前面，这时就要求在销量排序基础上进行的价格排序要具备稳定性。

2023-08-27T08:41:20.png
2023-08-27T08:41:59.png

算法，可以理解为解决问题的解决方案。

输入：有的解决方案需要一些前提条件。
输出：既然目的是解决问题，必然有一个解决结果，不然没有意义。
有穷性：无穷就没有意义。
确定性：步骤不确定，如何确定它能解决问题是确定的。
可行性：不可行，就没有意义。

这里介绍两种数组元素排序的算法：冒泡排序和快速排序。

2) 冒泡排序
冒泡排序的策略就是每次完成对一个元素的正确排序，对元素数-1个元素完成正确排序即可实现所有元素的正确排序。

冒泡排序仅利用交换操作，完成元素的比较和移动。换句话说，冒泡排序中所有元素的比较和移动都是交换操作中的。
因此，冒泡排序完成一个元素的正确排序的方法就是仅利用交换操作完成一个元素的正确排序。

而交换操作只涉及两个元素，实现的是判断出两个元素哪个大哪个小。而一个元素的排序涉及的是与其他所有元素的关系。
将多个交换操作联系在一起，能实现判断出多个元素中最大值或最小值，原理类似于利用两个数的比较实现多个数的比较。比如得到3个数中的最大值，先比较两个数得到两个数的最大值，再将两个数中的最大值和第三个数比较，就可以得到三个数中的最大值。
因此，通过这种交换方法能够实现待排序元素中最值元素的正确排序。

实际上，上述利用交换操作实现对一个元素的正确排序本身也是一种循环操作：

通过每次确定一部分元素中的最值，不断循环，实现确定所有待排序元素中的最值。
第一次交换实现的是两个元素中的最值，将两个元素中的最值与第三个元素进行第二次交换实现三个元素中的最值，以此类推，实现所有待排序元素中最值的确定。
交换操作包括两个步骤：比较和交换，根据比较结果来进行交换的。也就是说可能不交换，不交换意味着两个位置的元素顺序正确，顺序正确的基础上将较大的和第三个位置交换，如果仍然不交换，说明三个位置的顺序都正确，以此类推，如果最后一个待排序元素比较完，也没有交换，说明所有待排序元素顺序正确。

由于冒泡排序每次实现对一个待排序元素的正确排序，因此每次循环仅需完成对待排序元素的更新，进行所有元素数-1次循环即可实现对所有元素的正确排序。
2023-08-27T13:15:34.png

3) 快速排序
快速排序的策略也是每次完成对一个元素的正确排序。
但冒泡排序每次只能确定待排元素中的最值，因此完成所有元素的排序需要对n-1个元素进行排序，其中n表示所有待排元素数。
与冒泡排序不同的是，快速排序每次能够确定任意一个待排元素的正确位置，其思想就是，任意一个元素其正确位置的左边全是小于它的数，右边全是大于它的数，这里假设要求从小到大的顺序。

这里具体说明一下快速排序中通过让一个元素的左边全是小于它的数，右边全是大于它的数实现的确定一个元素的正确位置：

首先确定要排序的元素是哪个，通常设置为当前待排元素中的第一个，称为pivot。以及待排元素有哪些，初始时是整个数组。
当一个位置左边全是小于pivot的数，右边全是大于pivot的数，该位置就为pivot的正确位置。快速排序实现这种思想的方式是：
- 设置两个指针分别指向所有待排元素的最左边和最右边，称为low和high。
  low表示low左边的位置都是小于等于pivot的元素，high表示high右边的位置都是大于pivot的位置。
  因此，由于初始时不确定任何元素与pivot的大小关系，并且需要遍历所有待排元素，因此初始时low在所有待排元素最左边，high在所有待排元素最右边，分别就表示确定的小于等于或大于pivot的元素。
- 从low当前指的数开始，判断low位置元素与pivot的大小关系，如果满足小于等于，则确定一个小于等于pivot的数，low则向右移到一个新元素上，low位置的元素不满足小于等于时，则low就指向这个位置不动。
  这里需要考虑，low一直移动的情况，这表明low经过的位置全满足小于等于，因此当low遍历完所有待排元素时，就可以停止判断，也就是当low在high的位置都完成判断时，表明所有元素已经被判断完，此时若low继续移动到了high右边，表明low左边包括high的位置上全是小于等于pivot的数，此时已经能够确定pivot的位置，因为已经判断完所有待排序元素，也就是说low左边是所有待排序元素中小于等于pivot的数，那么pivot的位置就是在low的前一个位置。
  换句话说，low停下的位置要么指向不满足小于等于pivot的数，要么超出范围（此时表示所有元素都是小于等于pivot），总之能够确定，low左边全是小于等于pivot的元素。
- 当low停下，且没有完成对所有待排序元素的判断时，即low < high（low = high时表示high位置元素是不满足的元素），开始对high进行类似于low的操作。即从high当前指的数开始，判断high位置元素与pivot的大小关系，如果满足大于，则确定一个大于pivot的数，high则向左移到一个新元素上，high位置的元素不满足大于时，则high就指向这个位置不动。
  类似于low，high表示的是，其右边的所有数都是大于pivot的，因此，high停下的位置表明只会是小于等于pivot的元素位置，high之所以不会超出范围，因为这里设定了low先开始操作，因此high总是在low操作后再移动，要么指向low已经确定的小于等于的元素位置，要么指向一个待判断的大于等于的元素位置。
- 当low和high停止时满足low < high即表示并没有判断完所有待排序元素即确定不了一个元素的正确位置，则交换两个位置的元素，这样做就可以满足low，high的原则，然后继续上述low再high和交换操作，直到low > high，表明判断完所有待排序元素，此时low左边是待排元素中所有小于等于pivot的元素，而由于此时high右边是待排元素中所有大于pivot的元素或者没有元素（所有元素都是小于等于pivot的low一直移动的情况），且high本身停止的位置是不满足大于的元素位置，换句话说，high的位置是最后一个小于等于pivot的元素，即high + 1 = low，同时由于pivot元素本身属于待排元素也参与到low和high操作中，实际上由于low初始的位置就是pivot，因此实际上pivot始终没变，因此high的位置就是pivot的最终正确位置，因此pivot只需与high位置元素进行交换即可。

这样由于每次确定的正确位置，以这个位置为基准，只需再分别对左右两部分的元素进行排序即可，而对每一部分再进行同样地任取一个元素排序，再分两部分排序，直到每部分只剩1个元素，无需再排，这种方式需要排序的元素数比n-1还要少。

因此，快速排序需要循环的操作是每次完成对一个元素的正确排序。
但并不像常规循环那样有一个确定的循环次数，其循环方式是根据每次确定位置后的划分部分，每个部分进行这种排序，直到划分的部分的待排元素数为1时，该部分不再需要划分，待所有划分部分排序结束，即实现所有元素的正确排序。
2023-08-28T10:44:02.png