二分法
222. 完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)
/*
* 完全二叉樹(shù)編號(hào)從1開(kāi)始
* 如果第k個(gè)節(jié)點(diǎn)位于第h層,則k的二進(jìn)制表示包含h+1位,
* 其中最高位是1,其余各位從高到低表示從根節(jié)點(diǎn)到第k個(gè)節(jié)點(diǎn)的路徑,
* 0表示移動(dòng)到左子節(jié)點(diǎn),1表示移動(dòng)到右子節(jié)點(diǎn)。
* 通過(guò)位運(yùn)算得到第k個(gè)節(jié)點(diǎn)對(duì)應(yīng)的路徑,判斷該路徑對(duì)應(yīng)的節(jié)點(diǎn)是否存在,即可判斷第k個(gè)節(jié)點(diǎn)是否存在。
*/
bool exist(struct TreeNode *root, int height, int k) {
// 樹(shù)高h(yuǎn)eight(從1開(kāi)始),從根到葉節(jié)點(diǎn)需要往下走h(yuǎn)eight-1次
int count = height - 1;
while (count-- > 0) {
if (root == NULL) break;
// 從第二位開(kāi)始,根據(jù)每一位判斷往左往右
int bit = ((k >> count) & 1);
if (bit == 0) {
root = root->left;
} else {
root = root->right;
}
}
// 返回是否存在
return root != NULL;
}
int binarySearch(struct TreeNode *root, int height, int left, int right) {
int mid;
// 找最后一個(gè)節(jié)點(diǎn)的編號(hào)
while (left <= right) {
mid = (right - left) / 2 + left;
if (exist(root, height, mid)) {
// 若這個(gè)編號(hào)為mid的節(jié)點(diǎn)存在,往右找
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}
// 完全二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)
int countNodes(struct TreeNode *root) {
if (root == NULL) return 0;
struct TreeNode *node = root;
int height = 0;
while (node != NULL) {
height++;
node = node->left;
}
// 最下層,最左邊的節(jié)點(diǎn)編號(hào)
int left = (1 << (height - 1));
// 最下層,最右邊的節(jié)點(diǎn)編號(hào)
int right = (1 << height) - 1;
return binarySearch(root, height, left, right);
}
2089. 找出數(shù)組排序后的目標(biāo)下標(biāo)
int cmp(const void *a, const void *b) {
return (*(int *) a - *(int *) b);
}
// 找左邊界
int findLeft(int *nums, int left, int right, int target) {
int mid;
while (left <= right) {
mid = (right - left) / 2 + left;
if (nums[mid] >= target)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
// 找右邊界
int findRight(int *nums, int left, int right, int target) {
int mid;
while (left <= right) {
mid = (right - left) / 2 + left;
if (nums[mid] > target)
right = mid - 1;
else
left = mid + 1;
}
return right;
}
// 排完序后找左右邊界
int *targetIndices(int *nums, int numsSize, int target, int *returnSize) {
qsort(nums, numsSize, sizeof(int), cmp);
int left = findLeft(nums, 0, numsSize - 1, target);
int right = findRight(nums, 0, numsSize - 1, target);
int count = right - left + 1;
*returnSize = 0;
if (count <= 0)return NULL;
int *res = (int *) malloc(sizeof(int) * count);
for (int i = 0; i < count; ++i) {
res[(*returnSize)++] = left + i;
}
return res;
}
2529. 正整數(shù)和負(fù)整數(shù)的最大計(jì)數(shù)
int countPos(int *array, int start, int end) {
// 全是非正數(shù)
if (array[end] <= 0) return 0;
// 左右邊界
int i;
int j = end;
int left = start, right = end;
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
if (array[mid] > 0)
right = mid - 1;
else
left = mid + 1;
}
i = left;
return j - i + 1;
}
int countNeg(int *array, int start, int end) {
// 全是非負(fù)數(shù)
if (array[start] >= 0) return 0;
// 左右邊界
int i = start;
int j;
int left = start, right = end;
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
if (array[mid] >= 0)
right = mid - 1;
else
left = mid + 1;
}
j = right;
return j - i + 1;
}
int maximumCount(int *nums, int numsSize) {
int i = countPos(nums, 0, numsSize - 1);
int j = countNeg(nums, 0, numsSize - 1);
return i > j ? i : j;
}
1351. 統(tǒng)計(jì)有序矩陣中的負(fù)數(shù)
// 在非遞增序列中找-1插入的左邊界
int findPosition(int *array, int left, int right) {
int mid;
int target = -1;
while (left <= right) {
mid = (right - left) / 2 + left;
if (array[mid] <= target)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
// 一行行統(tǒng)計(jì),沒(méi)有利用到列也是非遞增的條件
int countNegatives(int **grid, int gridSize, int *gridColSize) {
int res = 0;
for (int i = 0; i < gridSize; ++i) {
res += gridColSize[i] - findPosition(grid[i], 0, gridColSize[i] - 1);
}
return res;
}
// 在非遞增序列中找-1插入的左邊界
int findPosition(int *array, int left, int right) {
int mid;
int target = -1;
while (left <= right) {
mid = (right - left) / 2 + left;
if (array[mid] <= target)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
// 每一行從前往后第一個(gè)負(fù)數(shù)的位置是不斷遞減的
// 右邊界也就是-1插入的位置,也就是負(fù)數(shù)應(yīng)該出現(xiàn)的位置,下標(biāo)不斷減小。沒(méi)必要每次都以gridSize作為二分法右邊界
int countNegatives(int **grid, int gridSize, int *gridColSize) {
int res = 0;
int tempPos = gridColSize[0];
int temp;
// 處理每行
for (int i = 0; i < gridSize; ++i) {
// 下標(biāo)從0到第一個(gè)負(fù)數(shù)出現(xiàn)的位置
temp = findPosition(grid[i], 0, tempPos - 1);
res += gridColSize[i] - temp;
// 更新第一個(gè)負(fù)數(shù)的下標(biāo)
tempPos = temp;
}
return res;
}
2389. 和有限的最長(zhǎng)子序列
int cmp(const void *a, const void *b) {
return (*(int *) a - *(int *) b);
}
// 找右邊界
int binarySearch(int *array, int left, int right, int target) {
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
if (array[mid] <= target)
left = mid + 1;
else
right = mid - 1;
}
return right;
}
int *answerQueries(int *nums, int numsSize, int *queries, int queriesSize, int *returnSize) {
int *res = (int *) malloc(sizeof(int) * queriesSize);
*returnSize = queriesSize;
qsort(nums, numsSize, sizeof(int), cmp);
// 保存前綴和
int sum[numsSize];
sum[0] = nums[0];
for (int i = 1; i < numsSize; ++i) {
sum[i] = sum[i - 1] + nums[i];
}
// 在前綴和數(shù)組里二分查找
for (int i = 0; i < queriesSize; ++i) {
res[i] = binarySearch(sum, 0, numsSize - 1, queries[i]) + 1;
}
return res;
}
LCR 069. 山脈數(shù)組的峰頂索引
// todo
int peakIndexInMountainArray(int *arr, int arrSize) {
int left = 0;
int right = arrSize - 1;
int mid;
while (left < right) {
mid = left + (right - left) / 2;
if (arr[mid] < arr[mid + 1]) {
// left左邊全都小于arr[left], arr[left]=arr[mid + 1]最大
left = mid + 1;
} else if (arr[mid] > arr[mid + 1]) {
// right右邊全都小于arr[right],arr[right]=arr[mid]最大
right = mid;
}
}
return left;
}
1337. 矩陣中戰(zhàn)斗力最弱的 K 行
// todo
LCR 179. 查找總價(jià)格為目標(biāo)值的兩個(gè)商品
// 雙指針
int *twoSum(int *numbers, int numbersSize, int target, int *returnSize) {
int *res = (int *) malloc(sizeof(int) * 2);
*returnSize = 0;
int left = 0, right = numbersSize - 1;
while (left < right) {
if (numbers[left] == target - numbers[right]) {
res[0] = numbers[left];
res[1] = numbers[right];
*returnSize = 2;
return res;
} else if (numbers[left] > target - numbers[right]) {
right--;
} else {
left++;
}
}
return res;
}
// 散列
int *twoSum(int *numbers, int numbersSize, int target, int *returnSize) {
int *res = (int *) malloc(sizeof(int) * 2);
*returnSize = 0;
int *hashMap = (int *) calloc(2000001, sizeof(int));
for (int i = 0; i < numbersSize; ++i) {
if ((target - numbers[i]) > 0 && hashMap[target - numbers[i]] == 1) {
res[0] = numbers[i];
res[1] = target - numbers[i];
*returnSize = 2;
return res;
}
hashMap[numbers[i]] = 1;
}
return res;
}
面試題 08.03. 魔術(shù)索引
// todo
// 二分+遞歸
int binarySearch(int *array, int left, int right) {
if (left > right) return -1;
int mid = ((right - left) >> 1) + left;
// 左區(qū)間能找到就返回左區(qū)間
int leftAns = binarySearch(array, left, mid - 1);
if (leftAns != -1) return leftAns;
// 左區(qū)間找不到就檢查當(dāng)前節(jié)點(diǎn)
if (array[mid] == mid) return mid;
// 當(dāng)前節(jié)點(diǎn)也不滿足就檢查右區(qū)間
return binarySearch(array, mid + 1, right);
}
int findMagicIndex(int *nums, int numsSize) {
return binarySearch(nums, 0, numsSize - 1);
}
LCR 006. 兩數(shù)之和 II - 輸入有序數(shù)組
// 雙指針
// 假設(shè)數(shù)組中存在且只存在一對(duì)符合條件的數(shù)字,同時(shí)一個(gè)數(shù)字不能使用兩次
int *twoSum(int *numbers, int numbersSize, int target, int *returnSize) {
int *res = (int *) malloc(sizeof(int) * 2);
*returnSize = 0;
int left = 0, right = numbersSize - 1;
while (left < right) {
if (numbers[left] == target - numbers[right]) {
res[0] = left;
res[1] = right;
*returnSize = 2;
return res;
} else if (numbers[left] > target - numbers[right]) {
right--;
} else {
left++;
}
}
return res;
}
int binarySearch(int *array, int left, int right, int target) {
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
if (array[mid] == target) {
return mid;
} else if (array[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
// 假設(shè)數(shù)組中存在且只存在一對(duì)符合條件的數(shù)字,同時(shí)一個(gè)數(shù)字不能使用兩次
// 在當(dāng)前節(jié)點(diǎn)的右邊二分查找
int *twoSum(int *numbers, int numbersSize, int target, int *returnSize) {
int *res = (int *) malloc(sizeof(int) * 2);
*returnSize = 0;
for (int i = 0; i < numbersSize; ++i) {
int k = binarySearch(numbers, i + 1, numbersSize - 1, target - numbers[i]);
if (k != -1) {
res[0] = i;
res[1] = k;
*returnSize = 2;
return res;
}
}
return res;
}
1385. 兩個(gè)數(shù)組間的距離值
int cmp(const void *a, const void *b) {
return (*(int *) a - *(int *) b);
}
// 大于等于(找應(yīng)該插入的位置,左邊界)
int binarySearch1(int *array, int size, int target) {
int left = 0;
int right = size - 1;
int mid;
while (left <= right) {
mid = left + (right - left) / 2;
if (target > array[mid])
left = mid + 1; // left更新之后,left左邊必然都小于target
else if (target <= array[mid])
right = mid - 1; // right更新之后,right右邊必然都大于等于target
}
// 循環(huán)結(jié)束時(shí)left = right + 1
return left;
}
// 小于等于(右邊界)
int binarySearch2(int *array, int size, int target) {
int left = 0;
int right = size - 1;
int mid;
while (left <= right) {
mid = left + (right - left) / 2;
if (target >= array[mid]) // 即使等于left也右移,這樣小于等于的就都在left左邊了,循環(huán)結(jié)束時(shí),right就在left-1的位置
left = mid + 1; // left更新之后,left左邊必然都小于等于target
else if (target < array[mid])
right = mid - 1; // right更新之后,right右邊必然都大于target
}
return right;
}
// 求arr1中與arr2所有元素之差絕對(duì)值大于d的元素個(gè)數(shù)
int findTheDistanceValue(int *arr1, int arr1Size, int *arr2, int arr2Size, int d) {
qsort(arr2, arr2Size, sizeof(int), cmp);
int sum = 0;
for (int i = 0; i < arr1Size; ++i) {
int right = binarySearch1(arr2, arr2Size, arr1[i]);
int left = binarySearch2(arr2, arr2Size, arr1[i]);
printf("%d %d\n", left, right);
if ((left < 0 || abs(arr2[left] - arr1[i]) > d)
&& (right >= arr2Size || abs(arr2[right] - arr1[i]) > d)) {
sum++;
}
}
return sum;
}
888. 公平的糖果交換
int cmp(const void *a, const void *b) {
return *(int *) a - *(int *) b;
}
int binarySearch(int *array, int size, int target) {
int left = 0;
int right = size - 1;
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
if (target == array[mid])
return mid;
else if (target < array[mid])
right = mid - 1;
else
left = mid + 1;
}
return -1;
}
int *fairCandySwap(int *aliceSizes, int aliceSizesSize, int *bobSizes, int bobSizesSize, int *returnSize) {
int *res = (int *) malloc(sizeof(int) * 2);
*returnSize = 2;
// 先把bobSizes排序,再根據(jù)aliceSizes[i]在bobSizes中二分查找
qsort(bobSizes, bobSizesSize, sizeof(int), cmp);
int sum1 = 0, sum2 = 0;
for (int i = 0; i < aliceSizesSize; ++i) sum1 += aliceSizes[i];
for (int i = 0; i < bobSizesSize; ++i) sum2 += bobSizes[i];
// sum1給出x,sum2給出y
// sum1-x+y = sum2-y+x
// gap = sum1-sum2 = 2*(x-y)
// y = x - gap/2
int gap = sum1 - sum2;
for (int i = 0; i < aliceSizesSize; ++i) {
int t = binarySearch(bobSizes, bobSizesSize, aliceSizes[i] - gap / 2);
if (t != -1) {
res[0] = aliceSizes[i];
res[1] = bobSizes[t];
return res;
}
}
return res;
}
1608. 特殊數(shù)組的特征值
int cmp(const void *a, const void *b) {
return (*(int *) a) - (*(int *) b);
}
// 左邊界
int binarySearch(int *array, int size, int target) {
int left = 0;
int right = size - 1;
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
if (array[mid] >= target)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
int specialArray(int *nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), cmp);
for (int i = 0; i <= nums[numsSize - 1]; ++i) {
int index = binarySearch(nums, numsSize, i);
if (numsSize - index == i)
return i;
}
return -1;
}
350. 兩個(gè)數(shù)組的交集 II
// 散列
int *intersect(int *nums1, int nums1Size, int *nums2, int nums2Size, int *returnSize) {
int min = nums1Size > nums2Size ? nums2Size : nums1Size;
int *res = (int *) malloc(sizeof(int) * min);
*returnSize = 0;
int *hashMap = (int *) calloc(1001, sizeof(int));
// 統(tǒng)計(jì)出現(xiàn)次數(shù)
for (int i = 0; i < nums1Size; ++i) hashMap[nums1[i]]++;
for (int i = 0; i < nums2Size; ++i) {
if (hashMap[nums2[i]] > 0) {
// 表中減一
hashMap[nums2[i]]--;
res[(*returnSize)++] = nums2[i];
}
}
return res;
}
// 左邊界
int binarySearch(int *array, int left, int right, int target) {
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
if (array[mid] >= target)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
int cmp(const void *a, const void *b) {
return *(int *) a - *(int *) b;
}
// 排序后雙指針,第二個(gè)指針用二分法定位
int *intersect(int *nums1, int nums1Size, int *nums2, int nums2Size, int *returnSize) {
int min = nums1Size > nums2Size ? nums2Size : nums1Size;
int *res = (int *) malloc(sizeof(int) * min);
*returnSize = 0;
// 排序
qsort(nums1, nums1Size, sizeof(int), cmp);
qsort(nums2, nums2Size, sizeof(int), cmp);
int j = 0;
for (int i = 0; i < nums1Size && j < nums2Size; ++i) {
int k = binarySearch(nums2, j, nums2Size - 1, nums1[i]);
if (k >= 0 && k < nums2Size && nums1[i] == nums2[k]) {
res[(*returnSize)++] = nums1[i];
// 數(shù)組2的j指針同時(shí)后移
j = k + 1;
}
}
return res;
}
面試題 10.05. 稀疏數(shù)組搜索
int binarySearch(char **words, int left, int right, char *s) {
int mid;
while (left <= right) {
// 跳過(guò)左右的空字符串
while (left <= right && strcmp(words[left], "") == 0) left++;
while (left <= right && strcmp(words[right], "") == 0) right--;
mid = ((right - left) >> 1) + left;
// 中間的是空字符串,就在兩側(cè)找
if (strcmp(words[mid], "") == 0) {
// 找左邊
int leftAns = binarySearch(words, left, mid - 1, s);
if (leftAns != -1) return leftAns;
// 找右邊
return binarySearch(words, mid + 1, right, s);
}
// 中間不是空字符串
int k = strcmp(words[mid], s);
if (k == 0) {
return mid;
} else if (k > 0) {
right = mid - 1;
} else if (k < 0) {
left = mid + 1;
}
}
return -1;
}
// 二分+遞歸
int findString(char **words, int wordsSize, char *s) {
return binarySearch(words, 0, wordsSize - 1, s);
}
int findString(char **words, int wordsSize, char *s) {
int left = 0, right = wordsSize - 1;
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
int beforeMid = mid;
// 無(wú)法二分時(shí),線性探測(cè)
while (mid <= right && strcmp(words[mid], "") == 0) {
mid++;
}
if (mid <= right) {
// 沒(méi)有越界,words[mid]一定不是空字符串
if (strcmp(words[mid], s) == 0) {
return mid;
} else if (strcmp(words[mid], s) > 0) {
right = beforeMid - 1;
} else {
left = mid + 1;
}
} else {
right = beforeMid - 1;
}
}
return -1;
}
1539. 第 k 個(gè)缺失的正整數(shù)
int findKthPositive(int *arr, int arrSize, int k) {
int left = 0, right = arrSize - 1;
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
// 到arr[mid]為止,包括arr[mid],缺失的正整數(shù)個(gè)數(shù)
int lossCount = arr[mid] - mid - 1;
// 找左邊界
if (lossCount >= k) {
// 代碼a,執(zhí)行這條代碼,right右面的必然都滿足lossCount >= k
right = mid - 1;
} else {
left = mid + 1;
}
}
// 循環(huán)結(jié)束一定是left=right+1
// right是剛好lossCount嚴(yán)格小于k的位置,下個(gè)位置right+1是lossCount大于等于k的位置(代碼a決定的)
if (right >= 0) {
// index = [0,1,2,3,4]
// array = [2,3,4,7,11]
// lossCount = [1,1,1,3,6]
// right = 3, arr[right] = 7, lossCount[right] = 3, lossCount[right+1] = 6
// lossCount[right] < k < lossCount[right+1],丟失的數(shù)一定就在arr[right]到arr[right+1]之間
// 到arr[right]為止,包括arr[right],缺失的正整數(shù)個(gè)數(shù)為lossCount,從arr[right]往后數(shù)(k-lossCount)個(gè)數(shù)就是答案
return k - (arr[right] - (right) - 1) + arr[right];
}
return k;
}
LCR 172. 統(tǒng)計(jì)目標(biāo)成績(jī)的出現(xiàn)次數(shù)
// 左邊界
int binarySearch1(int *array, int size, int target) {
int left = 0, right = size - 1;
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
if (array[mid] >= target)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
// 右邊界
int binarySearch2(int *array, int size, int target) {
int left = 0, right = size - 1;
int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
if (array[mid] <= target)
left = mid + 1;
else
right = mid - 1;
}
return right;
}
int countTarget(int *scores, int scoresSize, int target) {
int left = binarySearch1(scores, scoresSize, target);
int right = binarySearch2(scores, scoresSize, target);
if(left >= scoresSize || scores[left] != target) return 0;
return right - left + 1;
}
154. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值 II
// todo
// 含重復(fù)元素的增序數(shù)組,循環(huán)右移后找最小元素
int findMin(int *nums, int numsSize) {
int left = 0;
int right = numsSize - 1;
int mid;
// 規(guī)律:最小值下標(biāo)x,[0,x)值都大于等于末尾元素,[x,array.length-1]都小于等于末尾元素
while (left < right) {
mid = left + (right - left) / 2;
// 和末尾元素比較
if (nums[mid] > nums[right]) {
// [left, mid]都大于numbers[right],都排除
left = mid + 1;
} else if (nums[mid] < nums[right]) {
// numbers[mid]是[mid,right]上最小的,忽略(mid,right]上的
right = mid;
} else {
// 忽略末尾,新的末尾numbers[right-1]也符合規(guī)律
right--;
}
}
return nums[left];
}
441. 排列硬幣
// 右邊界
int arrangeCoins(int n) {
int left = 1, right = n;
long int mid;
// k行全滿,共(1+k)*k/2個(gè)元素
while (left <= right) {
mid = ((right - left) >> 1) + left;
long int sum = (1 + mid) * mid >> 1;
if (sum <= n)
left = mid + 1;
else
right = mid - 1;
}
return right;
}
367. 有效的完全平方數(shù)
// 小于等于(右邊界
bool isPerfectSquare(int num) {
int left = 0;
int right = num;
long int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
long int temp = mid * mid;
if (temp <= num)
left = mid + 1;
else
right = mid - 1;
}
return right * right == num;
}
LCR 072. x 的平方根
// 小于等于(右邊界
int mySqrt(int x) {
int left = 0;
int right = x;
long int mid;
while (left <= right) {
mid = ((right - left) >> 1) + left;
long int temp = mid * mid;
if (temp <= x)
left = mid + 1;
else
right = mid - 1;
}
return right;
}
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-819655.html
文章來(lái)源:http://www.zghlxwxcb.cn/news/detail-819655.html
到了這里,關(guān)于二分法簡(jiǎn)單題的文章就介紹完了。如果您還想了解更多內(nèi)容,請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!