Open azl397985856 opened 1 year ago
从左开始模拟放置灯。先在 nums[0] + r 处放置一个灯,其可以覆盖 [0, 2 r]。由于 nums 已经排好序了,那么这个灯可以覆盖到的房间其实就是 nums 中坐标小于等于 2 r 所有房间,使用二分查找即可。对于 nums 右侧的所有的房间我们需要继续放置灯,采用同样的方式即可。
key: binary search; greedy - find minimum
# 从左开始模拟放置灯。先在 nums[0] + r 处放置一个灯,其可以覆盖 [nums[0], 2 * r]。
# 由于 nums 已经排好序了,那么这个灯可以覆盖到的房间其实就是 nums 中坐标小于等于 2 * r 所有房间,使用能力检测二分查找即可。
# 对于 nums 右侧的所有的房间我们需要继续放置灯,采用同样的方式即可。
def solve(arr):
arr.sort()
n = len(arr)
if n <= 3:
return 0
n_lights = 3
def check(radius):
lo, hi = arr[0], arr[0]+2*radius
for i in range(n_lights):
idx = bisect_right(arr, hi) # find idx that hi can be inserted into sorted arr # O(logn)
if idx >= n_lights:
return True
lo = nums[idx]
hi = lo + 2*radius
return False
# l, r = arr[0], arr[-1]
# binarySearchFindMinimum(arr)
return radius
Time : O(nlogn) - sort()
Space: O(1)
二分找左边界
class Solution:
def solve(self, nums):
nums.sort()
N = len(nums)
if N <= 3:
return 0
LIGHTS = 3
# 这里使用的是直径,因此最终返回需要除以 2
def possible(diameter):
start = nums[0]
end = start + diameter
for i in range(LIGHTS):
idx = bisect_right(nums, end)
if idx >= N:
return True
start = nums[idx]
end = start + diameter
return False
l, r = 0, nums[-1] - nums[0]
while l <= r:
mid = (l + r) // 2
if possible(mid):
r = mid - 1
else:
l = mid + 1
return l / 2
复杂度分析
import math
class StreetLights:
def __init__(self, nums):
self.nums = sorted(nums)
self.n = len(nums)
def smallest_r(self):
min_r = float('inf')
for i in range(self.n - 2):
for j in range(i + 1, self.n - 1):
mid = (self.nums[i] + self.nums[j]) / 2
max_dist = max(mid - self.nums[i], self.nums[j] - mid)
for k in range(j + 1, self.n):
dist = max(self.nums[k] - mid, max_dist)
min_r = min(min_r, dist)
return min_r / 2
nums = [3, 4, 5, 6]
lights = StreetLights(nums)
print(lights.smallest_r())
/*
思路:
能力检测
最左二分
复杂度: 时间复杂度: O(nlogn+logn∗log(MAX−MIN)) 空间复杂度: O(1) */
func solve(nums []int) float64 {
if len(nums) <= 3 {
return 0
}
sort.Ints(nums)
l := 0
r := nums[len(nums)-1] - nums[0]
for l <= r {
mid := l + (r-l)>>1
if isPossible(nums, mid) {
r = mid - 1
} else {
l = mid + 1
}
}
return float64(l) / 2
}
func isPossible(nums []int, mid int) bool {
start := nums[0]
end := start + mid
for i := 0; i < 3; i++ {
index := 0
for index < len(nums) && nums[index] <= end {
index++
}
if index >= len(nums) {
return true
}
start = nums[index]
end = start + mid
}
return false
}
class Solution:
def findRadius(self, houses, heaters):
houses.sort()
heaters.sort()
radius = 0
for house in houses:
left, right = 0, len(heaters)
while left < right:
mid = (left + right) // 2
if heaters[mid] < house:
left = mid + 1
else:
right = mid
left_dist = abs(heaters[left] - house) if left < len(heaters) else float('inf')
prev_dist = abs(heaters[left - 1] - house) if left > 0 else float('inf')
radius = max(radius, min(left_dist, prev_dist))
return radius
public class HardMinimumLight796 {
public double minimumLightRadius(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
//直径的最大值是最右侧房子和最左侧房子坐标之差的1/3
int left = 0, right = (nums[n - 1] - nums[0]) / 3;
while(left <= right){
int mid = (left + right) / 2;
if(allCovered(mid, nums)){
//当前直径可以覆盖,有边界-1
right = mid - 1;
}else{
//当前直径不能覆盖,增大一下
left = mid + 1;
}
}
return left / 2.0;
}
private boolean allCovered(int d, int[] nums){
int target = nums[0] + d, n = nums.length;
int left = 0, right = n - 1;
while(left <= right){
int mid = (left + right) / 2;
if(nums[mid] > target){
right = mid - 1;
}else{
left = mid + 1;
}
}
int leftBorder = left;
target = nums[n - 1] - d;
left = 0;
right = n - 1;
while(left <= right){
int mid = (left + right) / 2;
if(nums[mid] < target){
left = mid + 1;
}else{
right = mid - 1;
}
}
int rightBorder = right;
if(rightBorder < 0 || nums[rightBorder] - nums[leftBorder] <= d){
return true;
}else{
return false;
}
}
}
二分查找: 遍历houses中的每一个元素,找到离每一个元素最近的heater(使用二分的方式进行查找) 最终的答案是上面找到的 离每一个元素最近的heater 中的最小值
var findRadius = function(houses, heaters) {
let ans = 0;
heaters.sort((a, b) => a - b);
for (const house of houses) {
const i = binarySearch(heaters, house);
const j = i + 1;
const leftDistance = i < 0 ? Number.MAX_VALUE : house - heaters[i];
const rightDistance = j >= heaters.length ? Number.MAX_VALUE : heaters[j] - house;
const curDistance = Math.min(leftDistance, rightDistance);
ans = Math.max(ans, curDistance);
}
return ans;
};
const binarySearch = (nums, target) => {
let left = 0, right = nums.length - 1;
if (nums[left] > target) {
return -1;
}
while (left < right) {
const mid = Math.floor((right - left + 1) / 2) + left;
if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid;
}
}
return left;
}
复杂度分析
class Solution {
public int findRadius(int[] houses, int[] heaters) {
int ans = 0;
Arrays.sort(heaters);
for(int house:houses){
int i = binarySearch(heaters, house);
int j = i +1;
int leftDistance = i < 0? Integer.MAX_VALUE : house - heaters[i];
int rightDistance = j >= heaters.length ? Integer.MAX_VALUE : heaters[j] - house;
ans = Math.max(ans, leftDistance < rightDistance ? leftDistance : rightDistance);
}
return ans;
}
public int binarySearch(int[] nums, int target){
int left = 0, right = nums.length - 1;
if(nums[left] > target){
return -1;
}
while(left < right){
int mid = left + (right - left + 1) / 2;
if (nums[mid] > target){
right = mid - 1;
} else {
left = mid;
}
}
return left;
}
}
二分法
class Solution:
def findRadius(self, houses, heaters):
houses.sort()
heaters.sort()
radius = 0
for house in houses:
left, right = 0, len(heaters)
while left < right:
mid = (left + right) // 2
if heaters[mid] < house:
left = mid + 1
else:
right = mid
left_dist = abs(heaters[left] - house) if left < len(heaters) else float('inf')
prev_dist = abs(heaters[left - 1] - house) if left > 0 else float('inf')
radius = max(radius, min(left_dist, prev_dist))
return radius
复杂度分析
class Solution: def findRadius(self, houses, heaters): houses.sort() heaters.sort() radius = 0
for house in houses:
left, right = 0, len(heaters)
while left < right:
mid = (left + right) // 2
if heaters[mid] < house:
left = mid + 1
else:
right = mid
left_dist = abs(heaters[left] - house) if left < len(heaters) else float('inf')
prev_dist = abs(heaters[left - 1] - house) if left > 0 else float('inf')
radius = max(radius, min(left_dist, prev_dist))
return radius
class Solution:
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
"""存放每个房屋与加热器的最短距离"""
res = []
heaters.sort()
for c in houses:
"""二分查找"""
left = 0
right = len(heaters) - 1
while left < right:
mid = (left + right) >> 1
if heaters[mid] < c:
left = mid + 1
else:
right = mid
"""得出的 left 所指的加热器并不一定是离房屋 c 最近的一个,需要判断以下情况"""
if heaters[left] == c:
"""若找到的值等于 c ,则说明 c 房屋处放有一个加热器,c 房屋到加热器的最短距离为 0"""
res.append(0)
elif heaters[left] < c:
"""若该加热器的坐标值小于 c ,说明该加热器的坐标与 c 之间没有别的加热器"""
res.append(c - heaters[left])
elif left == 0:
"""
若left == 0 即二分查找的结果指向第一个加热器的坐标,说明 heaters[left] 坐标的房屋之前的位置
未放置加热器,直接相减就是到房屋 c 最近加热器的距离
"""
res.append(heaters[left] - c)
else:
"""
若left不等于 0 ,说明 c 介于left和left-1之间,房屋到加热器的最短距离就是left和left - 1处
加热器与 c 差值的最小值.
"""
res.append(min(heaters[left] - c, c - heaters[left - 1]))
return max(res)
class Solution {
public boolean rotateString(String s, String goal) {
int n = s.length();
List<Integer> var = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (s.charAt(i) == goal.charAt(0)) var.add(i);
}
for (int i = 0; i < var.size(); i++) {
if (goal.equals(s.substring(var.get(i), s.length()) + s.substring(0, var.get(i)))) return true;
}
return false;
}
}
796. Minimum Light Radius
入选理由
暂无
题目地址
https://binarysearch.com/problems/Minimum-Light-Radius
前置知识
题目描述
Constraints
n ≤ 100,000 where n is the length of nums Example 1 Input nums = [3, 4, 5, 6] Output 0.5 Explanation If we place the lamps on 3.5, 4.5 and 5.5 then with r = 0.5 we can light up all 4 houses.