当前位置：网站首页>Leetcode dichotomy
Leetcode dichotomy
2022-06-22 13:21:00 【Linchong Fengxue mountain temple】
There are two kinds of dichotomy , One is that there is left,right, then mid Equal to the sum of the two and divide by 2, Binary search . The other one is to search in half during recursion .
Two points ,left = mid -1;right = mid + 1 , It is mainly to find the conditions for pointer movement (check function ）, Write according to the meaning of the title check function , For example, cocoa, which likes bananas , Want to find h Minimum speed to eat all bananas in hours k,check On the condition that , When nums[mid]>=target, Speed can be reduced .
4. seek 2 The median of a positive array
34. Find the first and last positions of the elements in the sort array
Two ways to write a separate interval
Left boundary ： shrinkage r, another r=mid, Use template 1
Right border : shrinkage l, another l=mid, Use template 2
Finally back to r And return l It's the same , Because the cyclic condition is while l<r, At the end of the exit, the two are equal .
class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums.length == 0) return new int[]{-1,-1};
int l = 0, r = nums.length - 1; // Dichotomous range
while( l < r) // Find the starting position of the element
{
int mid = (l + r )/2;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
if( nums[r] != target) return new int[]{-1,-1}; // To find the failure
int L = r;
l = 0; r = nums.length - 1; // Dichotomous range
while( l < r) // Find the end position of the element
{
int mid = (l + r + 1)/2;
if(nums[mid] <= target ) l = mid;
else r = mid - 1;
}
return new int[]{L,r};
}
}
author ：lin-shen-shi-jian-lu-k
link ：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/tu-jie-er-fen-zui-qing-xi-yi-dong-de-jia-ddvc/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .# Find the leftmost subscript , And the rightmost subscript ,2 The second dichotomy # The leftmost subscript , When check be equal to target When , Shrink the right border , Therefore, it can be judged that the condition is nums[mid]>=target # The rightmost subscript , When check be equal to target When , Shrink the left border , Therefore, it can be judged that the condition is nums[mid]<=target
class Solution:
def searchRange(self, nums, target):
left=0
right=len(nums)-1
# Find the left border
while left<right:
mid=(left+right)//2
if nums[mid]>=target:
right=mid
else:
left=mid+1
if nums[right] != target:
return [-1, -1]
a1=right
left = 0
right = len(nums) - 1
# Find the right border
while left < right:
mid = (left + right+1) // 2
if nums[mid] <= target:
left = mid
else:
right = mid-1
a2=left
return [a1,a2]
# nums = [5,7,7,8,8,10]
# target = 8
nums = [5,7,7,8,8,10]
target=6
res=Solution().searchRange(nums,target)
print(res)Use the way of adding and subtracting one to everything
When looking for the left boundary , The judgment condition is
nums[mid] >= target, If nums[mid] Greater than or equal to target, Just move the pointer to the left , Because on the left side, there are still those who meet the conditions , The left border hasn't arrived yet .
Decide which boundary to change according to the judgment conditions .
the last one nums[mid] >= target Of mid It's the left boundary .
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if not nums:
return [-1,-1]
# Find the left border
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] >= target:
right = mid - 1
else:
left = mid + 1
if right+1 < len(nums) and nums[right+1] == target:
b1 = right + 1
else:
b1 = -1
# Find the right border
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid - 1
if left - 1 >=0 and nums[left-1] == target:
b2 = left - 1
else:
b2 = -1
return [b1,b2]2064. The minimum value of the most items allocated to the store
Dichotomous sub problem
class Solution {
public:
bool check(vector<int> &quantities,int n,int x){
if(x == 0)return false;
int m = quantities.size(),counts = 0;
for(int i = 0; i < m;++i){
counts += ceil((double)quantities[i] / x);
}
return counts <= n;
}
int minimizedMaximum(int n, vector<int>& quantities) {
int left = 0,right = 100000;
while(left < right){
int mid = (right-left)/2 + left;
if(check(quantities,n,mid)){
right = mid;
}else
left = mid+1;
}
return left;
}
};
author ：liyinxin
link ：https://leetcode-cn.com/problems/minimized-maximum-of-products-distributed-to-any-store/solution/c-er-fen-cha-zhao-by-liyinxin-l4f3/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .
/**
* @param {number} n
* @param {number[]} quantities
* @return {number}
*/
var minimizedMaximum = function(n, quantities) {
let right = Math.max(...quantities);
let left = 1;
while(left <= right) {
let mid = (left + right) >> 1;
if(checked(mid)) {
right = mid - 1;
} else {
left = mid + 1;
}
}
function checked(num) {
let ans = 0;
for(let i=0; i<quantities.length; i++) {
ans += Math.ceil(quantities[i] / num);
}
return ans <= n;
}
return left;
};
author ：getify
link ：https://leetcode-cn.com/problems/minimized-maximum-of-products-distributed-to-any-store/solution/javascript-zui-da-zhi-zui-xiao-hua-wen-t-rr2v/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .class Solution(object):
def minimizedMaximum(self, n, quantities):
"""
:type n: int
:type quantities: List[int]
:rtype: int
"""
# Set the maximum number of items allocated to the store as x
# Greedy thoughts ：quantities[i]/x Must be less than or equal to n.
# Find this threshold . Just enough quantities[i]/x Must be less than or equal to n
def check(x):
total_cnt = 0
for q in quantities:
cnt = q // x
if q % x != 0:
cnt +=1
total_cnt += cnt
if total_cnt > n:
return False
else:
return True
left=0
right=100000
while left<right:
mid=(left+right)//2
if mid==0:
return 1
if check(mid):
right=mid
else:
left=mid+1
return left
875. Coco, who loves bananas
Dichotomous sub problem
class Solution(object):
def minEatingSpeed(self, piles, h):
"""
:type piles: List[int]
:type h: int
:rtype: int
"""
#k The conditions for meeting the requirements are :piles[i]/k Less than or equal to 8
def check(k):
total_cnt=0
for i in range(len(piles)):
cnt=piles[i]//k
if piles[i]%k>0:
cnt+=1
total_cnt+=cnt
if total_cnt<=h:
return True
return False
left=0
right=10**9
while left<right:
mid=(left+right)//2
if mid==0:
return 1
if check(mid):
right=mid
else:
left=mid+1
return left
Use the way of adding and subtracting one to everything
class Solution(object):
def minEatingSpeed(self, piles, h):
"""
:type piles: List[int]
:type h: int
:rtype: int
"""
def check(x):
count = 0
for i in range(len(piles)):
if piles[i] % x == 0:
count += piles[i] // x
else:
count += piles[i] // x + 1
if count <= h:
return True
else:
return False
left = 1
right = sum(piles)
while left <= right:
mid = (left + right) // 2
# You can eat all the bananas
if check(mid):
right = mid -1
else:
left = mid + 1
return right + 1
2080. The frequency of querying numbers in the interval
Two points , Find the upper and lower bounds
class RangeFreqQuery {
Map<Integer, List<Integer>> map = new HashMap<>();
public RangeFreqQuery(int[] arr) {
int n = arr.length;
for(int i = 0; i < n; i++){
List<Integer> tmp = map.getOrDefault(arr[i], new ArrayList<>());
tmp.add(i);
map.put(arr[i], tmp);
}
}
public int query(int left, int right, int value) {
if(!map.containsKey(value)) return 0;
int l = lower_bound(map.get(value), left);
int r = upper_bound(map.get(value), right);
return r - l;
}
public int lower_bound(List<Integer> a, int target){
int n = a.size();
int l = 0, r = n;
while(l < r){
int mid = (l + r) >> 1;
if(target <= a.get(mid)) r = mid;
else l = mid + 1;
}
return l;
}
public int upper_bound(List<Integer> a, int target){
int n = a.size();
int l = 0, r = n;
while(l < r){
int mid = (l + r) >> 1;
if(target >= a.get(mid)) l = mid + 1;
else r = mid;
}
return l;
}
}
author ：LCS_0215
link ：https://leetcode-cn.com/problems/range-frequency-queries/solution/ha-xi-biao-er-fen-si-chong-chang-yong-er-nwop/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .class RangeFreqQuery(object):
def __init__(self, arr):
"""
:type arr: List[int]
"""
# Record the subscript of each element
self.value_indexs=collections.defaultdict(list)
for i in range(len(arr)):
self.value_indexs[arr[i]].append(i)
def query(self, left, right, value):
"""
:type left: int
:type right: int
:type value: int
:rtype: int
"""
value_index =self.value_indexs[value]
#value index It is arranged from small to large ,
# for example value index= [2,4,6].left=3,right=5
cnt=0
for i in value_index:
if i>=left and i<=right:
cnt+=1
return cnt
# Your RangeFreqQuery object will be instantiated and called as such:
# obj = RangeFreqQuery(arr)
# param_1 = obj.query(left,right,value)1060. Missing elements in an ordered array
Be careful
if diff[mid] >= k:
right = midHave an equal sign , Otherwise, there are case will not pass . for example
nums = [4,7,9,10] # nums = [1,2,4] k = 3
diff=[0, 2, 3, 3]. We have to find the first one 3 .
class Solution:
def missingElement(self, nums: List[int], k: int) -> int:
# Find out diff
diff=[0 for _ in range(len(nums))]
for i in range(1,len(nums)):
diff[i]=(nums[i]-nums[i-1]-1)+diff[i-1]
# if diff[i]>=k:
# return nums[i-1]+(k-diff[i-1])
if k>diff[-1]:
return nums[-1]+(k-diff[-1])
# Search in two k The location of
left=0
right=len(nums)
while left<right:
mid=(left+right)//2
if diff[mid]>=k:
right=mid
else:
left=mid+1
return nums[left-1]+(k-diff[left-1])1182. The shortest distance from the target color
The board is divided into two parts
use
if left-1>=0:
a2=abs(indexs[left-1]-index)
res.append(min(a1,a2))
To determine whether it is in the front or behind
class Solution:
def shortestDistanceColor(self, colors: List[int], queries: List[List[int]]) -> List[int]:
# Save the index of the element as list
from collections import defaultdict
value_index=defaultdict(list)
for i in range(len(colors)):
value_index[colors[i]].append(i)
res=[]
for i in range(len(queries)):
index=queries[i][0]
target=queries[i][1]
if target not in value_index:
res.append(-1)
else:
indexs=value_index[target]
#target and indexs The shortest distance between
left=0
right=len(indexs)-1
while left<right:
mid=(left+right)//2
if indexs[mid]>=index:
right=mid
else:
left=mid+1
a1=abs(indexs[left]-index)
if left-1>=0:
a2=abs(indexs[left-1]-index)
res.append(min(a1,a2))
else:
res.append(a1)
return res1231. Share the chocolate
The difficulty of this question is how to judge whether it meets the conditions ,check function , I don't want to .
class Solution(object):
def maximizeSweetness(self, sweetness, k):
"""
:type sweetness: List[int]
:type k: int
:rtype: int
"""
def check(thres):
ans = 0
sub_sweetness = 0
for i in range(len(sweetness)):
sub_sweetness += sweetness[i]
if sub_sweetness >= thres:
ans += 1
sub_sweetness = 0
return ans > k
left, right = 1, sum(sweetness)
while left < right:
mid = left + ((right - left + 1) >> 1)
if check(mid):
left = mid
else:
right = mid - 1
return left
author ：mangoooosteen
link ：https://leetcode-cn.com/problems/divide-chocolate/solution/python-er-fen-cha-zhao-by-mangoooosteen-rvz8/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .class Solution:
def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
def check(index):
ans=0
count=0
for i in range(len(sweetness)):
count=count+sweetness[i]
if count>=index:
ans+=1
count=0
if ans>=k+1:
return True
return False
left=1
right=sum(sweetness)
while left<=right:
mid=(left+right)//2
if check(mid):
left=mid+1
else:
right=mid-1
return left-1
287 Look for repetitions
Dichotomize the range
const findDuplicate = (nums) => {
let lo = 1;
let hi = nums.length - 1; // The title indicates ：nums.length == n + 1
while (lo < hi) {
const mid = (lo + hi) >>> 1; // Find the middle index
let count = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] <= mid) {
count++;
}
}
if (count > mid) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
};
author ：xiao_ben_zhu
link ：https://leetcode-cn.com/problems/find-the-duplicate-number/solution/zhe-ge-shu-zu-you-dian-te-shu-suo-yi-ke-yi-yong-ku/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .【LeetCode- lookup 】 Look for repetitions - Flix - Blog Garden
How to write it 1
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int left = 1;
int right = nums.size()-1;
while(left<right){
int mid = left+(right-left)/2;
int cnt = 0;
for(int num:nums){
if(num<=mid) cnt++;
}
if(cnt>mid){
right = mid; // Because the cyclic condition is left<right, So this is right=mid;
}else{
left = mid+1;
}
}
return left;
}
};How to write it 2
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int left = 1;
int right = nums.size()-1;
while(left<=right){
int mid = left+(right-left)/2;
int cnt = 0;
for(int num:nums){
if(num<=mid) cnt++;
}
if(cnt>mid){
right = mid-1;
}else{
left = mid+1;
}
}
return left;
}
};The same as cocoa, which likes bananas
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
def check(x):
count = 0
for i in range(len(nums)):
if nums[i] < x:
count += 1
if count < x:
return True
return False
left = 1
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if check(mid):
left = mid + 1
else:
right = mid - 1
# The last satisfaction check Conditions of the mid, yes left - 1
return left - 1540. A single element in an ordered array
Parity dichotomy
class Solution {
public int singleNonDuplicate(int[] nums) {
int n = nums.length;
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (mid % 2 == 0) {
if (mid + 1 < n && nums[mid] == nums[mid + 1]) l = mid + 1;
else r = mid;
} else {
if (mid - 1 >= 0 && nums[mid - 1] == nums[mid]) l = mid + 1;
else r = mid;
}
}
return nums[r];
}
}
author ：AC_OIer
link ：https://leetcode-cn.com/problems/single-element-in-a-sorted-array/solution/gong-shui-san-xie-er-duan-xing-fen-xi-yu-17nv/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .410. The maximum value of the split array
6068. The maximum number of white bricks covered by the blanket
Two points to find the boundary
Similar questions are ：
436. Look for the right range
2055. Candles between plates
class Solution:
def maximumWhiteTiles(self, tiles: List[List[int]], carpetLen: int) -> int:
n = len(tiles)
tiles.sort() # Sort
nums = [t[1] for t in tiles] # The right end of the tile section
presum = [r - l +1 for (l,r) in tiles] # The prefix and
presum = list(itertools.accumulate(presum))
ans = 0
for i, (left, _) in enumerate(tiles): # left： The left end of the blanket ,right： Right end of blanket
right = left + carpetLen - 1
j = bisect.bisect_right(nums, right) # Two point search 【 Search right 】
cnt = presum[j-1] - (presum[i-1] if i >=1 else 0) # [i, j-1] The tiles in the section are covered with blankets
if j <= n-1 and right >= tiles[j][0]: # [j] The tiles in the section shall be judged separately ：
cnt += right - tiles[j][0] + 1 # The right end of the blanket is [j] Within the interval
ans = max(ans, cnt)
return ans
author ：flix
link ：https://leetcode.cn/problems/maximum-white-tiles-covered-by-a-carpet/solution/by-flix-zoqe/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .边栏推荐
- Sap-abap-se14 how to recover lost data
- Think PHP environment construction notes
- SSM based library management system, high-quality graduation thesis example (can be used directly), project import video, attached source code and database script, Thesis Writing Tutorial
- 卸载MySQL 8
- 934. Shortest Bridge
- leetcode-背包问题
- 338. Counting Bits
- 2017年度总结
- 461. Hamming Distance
- 476. Number Complement
猜你喜欢
Reconstruction practice of complex C-end project of acquisition technology
leetcode 11. Container with the most water
leetcode-背包问题
别再用 System.currentTimeMillis() 统计耗时了，太 Low，StopWatch 好用到爆！
310. Minimum Height Trees
基于JSP的图书馆管理系统，包含源码，数据库脚本，项目运行视频教程，毕设论文撰写视频教程
redis修改密码，及启动、查看等操作
卸载MySQL 8
Leetcode game 297
310. Minimum Height Trees
随机推荐
MAUI使用Masa blazor组件库
260. Single Number III
windows系统安装多个mysql版本（不用卸载原版本），新旧版本兼容。
vs code
SAP fi financial statement version setting
剑指 Offer II 114. 外星文字典
Secondary development of robotframework -- socket push real-time log
记录阿里云ECS实例重启之后无法登录解决方法（亲身实践）
Leetcode 297 match de la semaine
338. Counting Bits
从零开始写一个契约测试工具——数据库设计
Stop using system Currenttimemillis() takes too long to count. It's too low. Stopwatch is easy to use!
693. Binary Number with Alternating Bits
leetcode 85. 最大矩形
leetcode 1579. Ensure that the graph can be completely traversed
leetcode 11. 盛最多水的容器
47. Permutations II
RobotFramework二次开发——Socket推送实时日志
RobotFramework中setUp的小技巧
Set up your own website (5)