bm17
核心點(diǎn)
一道簡單的二分查找的題，指定left/right，然后比較mid和target，按照比較結(jié)果移動(dòng)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
二維數(shù)組中的查找，中等
https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj
核心點(diǎn)
這道題變成了二維數(shù)組，不在是和第一題一樣的簡單的平鋪結(jié)構(gòu)了，
這個(gè)需要找準(zhǔn)一個(gè)中間位置，從中間位置向上或向右移動(dòng)
因?yàn)閿?shù)組是從左到右，從上到下，都是遞增的，我們可以選一個(gè)中間點(diǎn)，跟target進(jìn)行比較，如果比target大，指針就向右移，如果比target小，指針就向上移
代碼
public static boolean find(int target, int[][] array) {
//array的長度，就是豎著的行數(shù)，main函數(shù)中1，2，4，6，長度就是4
int m = array.length;
if (m <= 0) {
return false;
}
//這個(gè)就是二維數(shù)組的每一個(gè)子數(shù)組的長度，main函數(shù)中，1，2，8，9，每一個(gè)子函數(shù)長度就是4
int n = array[0].length;
if (n <= 0) {
return false;
}
//采用二分法的思想，找一個(gè)中間點(diǎn)，開始遍歷，
// 在二維數(shù)組的中間點(diǎn)的位置，比如array[m-1][0]就是一個(gè)中間點(diǎn)
//在main函數(shù)中，就是6，以6為起點(diǎn)，然后target比6大，就橫向移動(dòng)，往左，如果target比6小，就豎向移動(dòng)，往上
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
核心點(diǎn)
這道題是尋找峰值，峰值是比左右嚴(yán)格意義上都要大的值，比如一個(gè)數(shù)組有3個(gè)數(shù)，array[1]>array[0]&& array[1]>array[2],1就是峰值
由于需要進(jìn)行左右比較，需要選取一個(gè)方向做比較，拿nums[mid]和nums[mid+1]循環(huán)進(jìn)行比較
判斷mid和mid+1比，是升序還是降序，如果nums[mid]>nums[mid+1]，則mid可能是一個(gè)峰值，right指針需要向左移，如果nums[mid] <= nums[mid+1]，則是向右側(cè)遞增的，峰值可能還在更右邊，需要left指針右移，注意while循環(huán)退出條件
代碼
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;
//退出條件，<=會有死循環(huán)
while (left < right) {
int mid = left + (right - left) / 2;
//選取一個(gè)比較基準(zhǔn)，mid和mid+1進(jìn)行比較
if (nums[mid] > nums[mid + 1]) {
//mid比mid+1大的話，右側(cè)是一個(gè)下坡的狀態(tài)，把right往左移
right = mid;
} else if (nums[mid] <= nums[mid + 1]) {
//mid比mid+1小的話，右側(cè)是一個(gè)上坡的狀態(tài)，把left向右移
left = mid + 1;
}
}
return left;
}
bm21
旋轉(zhuǎn)數(shù)組的最小數(shù)字，簡單
https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj
核心點(diǎn)
這道題是把一個(gè)升序數(shù)組旋轉(zhuǎn)2個(gè)升序的部分，示例的012345，旋轉(zhuǎn)成450123，0就是旋轉(zhuǎn)后的最小數(shù)字。
3，4，5是左半?yún)^(qū)間，1，2是右半?yún)^(qū)間，因?yàn)槭巧驍?shù)組，所以array[0]>array[length-1]
如果array[mid]>array[right]，則mid是落在左半?yún)^(qū)間，left需要往右移，如果array[mid]<array[right]，則mid是落在右半?yún)^(qū)間(這里存疑，mid會不會存在下圖那個(gè)4的情況，落在左半?yún)^(qū)間?)，right需要往左移，如果相等的情況，right向左--即可。
代碼
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落在左半部分的升序區(qū)間里，需要left向右移動(dòng)
left = mid + 1;
} else if (array[mid] < array[right]) {
//如果mid比right小，mid落在右半部分的升序區(qū)間里，需要right向左移
//right需要為mid，如果為mid-1可能會丟失最小值
right = mid;
} else if (array[mid] == array[right]) {
//考慮11101這種，相等的情況下，把right向左移動(dòng)一位
right--;
}
}
return array[left];
}
bm22
核心點(diǎn)
這道題是2個(gè)字符傳，根據(jù)點(diǎn)做分割，比較版本號，題目提示用快慢指針做，需要定義2個(gè)指針，去遍歷2個(gè)字符串。
循環(huán)結(jié)束的條件是left < v1.length或 right<v2.length，這里不能用 &&，因?yàn)関1和v2長度不是相等的，有可能一個(gè)結(jié)束了，另一個(gè)還沒結(jié)束，需要||
下面就是定義2個(gè)指針，去遍歷v1和v2了，子循環(huán)條件是v1.charAt(left)!='.' 和v2.charAt(right)!='.'
然后分別遍歷這2個(gè)字符串，進(jìn)行比較
代碼
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) != '.') {
//數(shù)學(xué)計(jì)算小技巧，以1.1234為例，循環(huán)結(jié)束之后temp1=1234
temp1 = temp1 * 10 + (version1.charAt(i) - '0');
i++;
}
//這里需要i++，避免上方循環(huán)沒執(zhí)行到
i++;
int temp2 = 0;
//1.01
while (j < v2 && version2.charAt(j) != '.') {
temp2 = temp2 * 10 + (version2.charAt(j) - '0');
j++;
}
//這里需要j++，避免上方循環(huán)沒執(zhí)行到
j++;
if (temp1 > temp2) {
return 1;
}
if (temp1 < temp2) {
return -1;
}
}
return 0;
}
