ARTS打卡第五周
Algorithm:
class Solution {
public int search(int[] nums, int target) {
int left=0, right=nums.length-1, mid;
while(left<=right){
mid=left+(right-left)/2;
if(nums[mid]==target){
return mid;
}
if(nums[mid]>=nums[left]){
if(target>=nums[left] && target<nums[mid]){
right=mid-1;
} else {
left=mid+1;
}
} else {
if(target>nums[mid] && target<=nums[right]){
left=mid+1;
} else {
right=mid-1;
}
}
}
return -1;
}
}
当nums[mid]>=nums[left]，说明mid在左边的有序区间，这时可以在左边的区间使用二分查找，否则就在右边的有序区间使用二分查找，注意nums[mid]==nums[left]时，仍然要在左边的区间寻找target。
当在左边查找target时，target>=nums[left] && target<nums[mid]时，right=mid-1，否则就让right=mid+1，为什么要有等号呢，因为 [left, mid) 范围是有序的，我们仍然要在左边查找，不能跑到mid的右边。
当在右边查找target时，target>nums[mid] && target<=nums[right]时，left=mid+1，否则就让right=mid-1，这里为什么有等号呢，因为 (mid, right] 范围是有序的，不能跑到左边。
Review:
Tip:
1、今天学习《深入理解Java虚拟机》，自己动手编译一个JDK，书中的例子是JDK12，所以需要gcc-7和g++-7，并且把gcc和g++的优先级设为gcc-7和g++-7，所有命令使用sudo运行，这样就不会报错。
2、Java 中的内部类有两类，根据oracle的文档，有两种内部类，非静态的和静态的，非静态的嵌套类叫做内部类，静态的嵌套类叫做静态嵌套类。
3、使用MySQL的load指令批量插入数据，需要注意文件的路径不能有中文，而且Windows环境下要对文件夹的’/’分隔符做’//’转义，或者直接用’/’，插入的目标表也要写上具体的数据库，比如tb_sku数据库下面的tb_sku表，写成tb_sku.tb_sku的形式。
以下两种示例
load data local infile 'D:q/tb_sku5.sql' into table tb_sku.tb_sku fields terminated by ',' lines terminated by '\n'; load data local infile 'D:q\\tb_sku5.sql' into table tb_sku.tb_sku fields terminated by ',' lines terminated by '\n';
4、Java 的线程可以使用join()方法等待这个线程终止。
5、使用快指针每次走两个位置，慢指针每次走一个位置，可以判断一个链表的个数是否为奇数，如果链表元素个数为奇数，fast指针指向最后一元素，slow指针指向中间的元素。如果链表元素个数为偶数，fast指针指向倒数第二个元素，slow指针指向前一半元素的最后一个元素。
Share:
学习完堆排序，做个分享。我写的是大顶堆，堆排序的三个步骤是：
（1）从堆的最后一个建立一个非叶子节点建立堆
（2）把堆顶元素放到最后面的位置
（3）从堆顶继续建立堆
注意（2）和（3）步要循环做下去，直到遇到移动完所有的元素。
步骤（1）是初始整个数组元素成一个堆结构，然后在循环体里面执行（2）和（3），步骤（1）从索引位置arr.length/2-1位置开始建立堆，直到索引是0。经过步骤（1），堆的顶部元素是最大值，所以循环体里面要先把0索引处元素和最后一个元素交换，然后对索引[0, cnt]范围的元素从0位置建立堆，因为0索引的元素被更换过，并且这时候堆的大小减少1，这个减少的操作用cnt控制。
我写了一个测试程序，经过测试，我的代码没有问题。
import java.util.Arrays;
import java.util.Random;
public class HeapSort {
public static void main(String[] args) {
int len = 200;
int[] arr = new int[len];
Random random = new Random();
boolean flag = true;
int num = 100;
while (num-- >= 0) {
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(len);
}
int[] copyArr = Arrays.copyOf(arr, arr.length);
Arrays.sort(copyArr);
for (int i = arr.length / 2 - 1; i >= 0; i--) {
heapify(arr, i, arr.length);
}
for (int cnt = arr.length - 1; cnt >= 0; cnt--) {
swap(arr, 0, cnt);
heapify(arr, 0, cnt);
}
if (!Arrays.equals(arr, copyArr)) {
flag = false;
}
}
if (flag) {
System.out.println("相等");
} else {
System.out.println("不相等");
}
}
public static void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
public static void heapify(int[] arr, int i, int len) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest, len);
}
}
}