牛客bm101-二分查找/排序
bm17
核心点
一道简单的二分查找的题，指定left/right，然后比较mid和target，按照比较结果移动left或者right
代码
public int search (int[] nums, int target) {
// write code here
if (nums == null || nums.length<=0) {
return -1;
}
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if ((nums[mid] > target)) {
right = mid-1;
}
}
return -1;
}
bm18
核心点
这道题变成了二维数组，不在是和第一题一样的简单的平铺结构了，
这个需要找准一个中间位置，从中间位置向上或向右移动
因为数组是从左到右，从上到下，都是递增的，我们可以选一个中间点，跟target进行比较，如果比target大，指针就向右移，如果比target小，指针就向上移
image.png
代码
public static boolean find(int target, int[][] array) {
//array的长度，就是竖着的行数，main函数中1，2，4，6，长度就是4
int m = array.length;
if (m <= 0) {
return false;
}
//这个就是二维数组的每一个子数组的长度，main函数中，1，2，8，9，每一个子函数长度就是4
int n = array[0].length;
if (n <= 0) {
return false;
}
//采用二分法的思想，找一个中间点，开始遍历，
// 在二维数组的中间点的位置，比如array[m-1][0]就是一个中间点
//在main函数中，就是6，以6为起点，然后target比6大，就横向移动，往左，如果target比6小，就竖向移动，往上
for (int i = m - 1, j = 0; i >= 0 && j <= n - 1; ) {
if (array[i][j] == target) {
return true;
} else if (array[i][j] > target) {
i--;
} else if (array[i][j] < target) {
j++;
}
}
return false;
}
bm19
核心点
这道题是寻找峰值，峰值是比左右严格意义上都要大的值，比如一个数组有3个数，array[1]>array[0]&& array[1]>array[2],1就是峰值
由于需要进行左右比较，需要选取一个方向做比较，拿nums[mid]和nums[mid+1]循环进行比较
判断mid和mid+1比，是升序还是降序，如果nums[mid]>nums[mid+1]，则mid可能是一个峰值，right指针需要向左移，如果nums[mid] <= nums[mid+1]，则是向右侧递增的，峰值可能还在更右边，需要left指针右移，注意while循环退出条件
代码
public int findPeakElement(int[] nums) {
// write code here
if (nums == null || nums.length <= 0) {
return -1;
}
if (nums.length <= 1) {
return 0;
}
int n = nums.length;
int left = 0;
int right = n - 1;
//退出条件，<=会有死循环
while (left < right) {
int mid = left + (right - left) / 2;
//选取一个比较基准，mid和mid+1进行比较
if (nums[mid] > nums[mid + 1]) {
//mid比mid+1大的话，右侧是一个下坡的状态，把right往左移
right = mid;
} else if (nums[mid] <= nums[mid + 1]) {
//mid比mid+1小的话，右侧是一个上坡的状态，把left向右移
left = mid + 1;
}
}
return left;
}
bm21
核心点
这道题是把一个升序数组旋转2个升序的部分，示例的012345，旋转成450123，0就是旋转后的最小数字。
3，4，5是左半区间，1，2是右半区间，因为是升序数组，所以array[0]>array[length-1]
如果array[mid]>array[right]，则mid是落在左半区间，left需要往右移，如果array[mid]<array[right]，则mid是落在右半区间(这里存疑，mid会不会存在下图那个4的情况，落在左半区间?)，right需要往左移，如果相等的情况，right向左--即可。
image.png
代码
public int minNumberInRotateArray(int[] array) {
if (array == null || array.length <= 0) {
return -1;
}
if (array.length == 1) {
return array[0];
}
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] > array[right]) {
//如果mid比right都大，mid落在左半部分的升序区间里，需要left向右移动
left = mid + 1;
} else if (array[mid] < array[right]) {
//如果mid比right小，mid落在右半部分的升序区间里，需要right向左移
//right需要为mid，如果为mid-1可能会丢失最小值
right = mid;
} else if (array[mid] == array[right]) {
//考虑11101这种，相等的情况下，把right向左移动一位
right--;
}
}
return array[left];
}
bm22
核心点
这道题是2个字符传，根据点做分割，比较版本号，题目提示用快慢指针做，需要定义2个指针，去遍历2个字符串。
循环结束的条件是left < v1.length或 right<v2.length，这里不能用 &&，因为v1和v2长度不是相等的，有可能一个结束了，另一个还没结束，需要||
下面就是定义2个指针，去遍历v1和v2了，子循环条件是v1.charAt(left)!='.' 和v2.charAt(right)!='.'
然后分别遍历这2个字符串，进行比较
代码
public static int compare(String version1, String version2) {
// write code here
int v1 = version1.length();
int v2 = version2.length();
int i = 0;
int j = 0;
while (i < v1 || j < v2) {
int temp1 = 0;
//1.1234
while (i < v1 && version1.charAt(i) != '.') {
//数学计算小技巧，以1.1234为例，循环结束之后temp1=1234
temp1 = temp1 * 10 + (version1.charAt(i) - '0');
i++;
}
//这里需要i++，避免上方循环没执行到
i++;
int temp2 = 0;
//1.01
while (j < v2 && version2.charAt(j) != '.') {
temp2 = temp2 * 10 + (version2.charAt(j) - '0');
j++;
}
//这里需要j++，避免上方循环没执行到
j++;
if (temp1 > temp2) {
return 1;
}
if (temp1 < temp2) {
return -1;
}
}
return 0;
}
