Open azl397985856 opened 1 year ago
(参考题解)
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
(供暖期那题 class Solution: def findRadius(self, houses: List[int], heaters: List[int]) -> int:
houses.sort()
heaters.sort()
def possible(diameter):
# 上一次能够加热的最右端坐标
last_right = 0
# 遍历每个取暖器
for heater in heaters:
# 二分查询取暖器加热半径能够覆盖最左边的房子编号
left = bisect.bisect_left(houses, heater - diameter)
# 如果最左边不能跟上一次最右边重叠,表示不能覆盖加热
if left > last_right:
return False
# 更新当前取暖器加热半径能够覆盖最右边的房子编号
last_right = bisect.bisect_right(houses, heater + diameter)
# 如果已经到达最后一个房子,表示已经全部覆盖完了
if last_right >= len(houses):
return True
return False
l, r = 0, max(houses[-1], heaters[-1])
while l <= r:
mid = (l + r) // 2
if possible(mid):
r = mid - 1
else:
l = mid + 1
return l
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
参考题解
(链接打不开 写了lc796)
s+s中check原来的str
class Solution:
def rotateString(self, s: str, goal: str) -> bool:
check=s+s
if len(goal)!=len(s):
return False
if goal in check:
return True
return False
。。。
// leetcode 475
class Solution {
public int findRadius(int[] houses, int[] heaters) {
// 二分 + 滑动窗口
Arrays.sort(houses);
Arrays.sort(heaters);
int left = 0, right = (int)(1e9);
while (left < right) {
int mid = (left + right) / 2;
if (isCheck(houses, heaters, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public boolean isCheck(int[] houses, int[] heaters, int cover) {
int n = houses.length, cnt = 0, m = heaters.length;
for (int l = 0, r = 0, i = 0; i < m; i++) {
int lo = heaters[i] - cover, hi = heaters[i] + cover;
while (l < n && houses[l] < lo) l++;
while (r < n && houses[r] <= hi) r++;
cnt += r - l;
l = r;
}
return cnt == n;
}
}
class Solution {
public:
int findRadius(vector
for(int i = 0, j = 0; i < houses.size() && j < heaters.size(); )
{
if(houses[i] <= heaters[j]){
res[i] = heaters[j] - houses[i];
i++;
}
else{
j++;
}
}
for(int i = houses.size() - 1, j = heaters.size() - 1; i >= 0 && j >= 0;){
if(houses[i] >= heaters[j]){
res[i] = min(res[i], houses[i] - heaters[j]);
i--;
}
else{
j--;
}
}
return *max_element(res.begin(), res.end());
}
};
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
class Solution:
def rotateString(self, A: str, B: str) -> bool:
n = len(A)
if A =="" and B =="":
return True
for i in range(n):
if B == A[i:] +A[0:i]:
return True
return False
copy的别人的题解
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)
找到每个房子最近的左边的heater,右边的heater为左边的下一个。算出房子和两个heater的距离,选出最小加热半径。遍历所有房子。最近最左的heater可用二分查找
var findRadius = function(houses, heaters) {
let ans = 0;
heaters.sort((a, b) => a - b);
for (const house of houses) {
// 最近的小于house的heater
const i = search(heaters, house);
const j = i + 1;
const leftDistance = i < 0 ? Infinity : house - heaters[i];
const rightDistance = j >= heaters.length ? Infinity : heaters[j] - house;
// 左边和右边找到最近的,覆盖到就可以了
const curDistance = Math.min(leftDistance, rightDistance);
// 最大的,说明是最少需要的距离
ans = Math.max(ans, curDistance);
}
return ans;
};
var search = function(nums, target) {
let low = 0;
let high = nums.length - 1;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (nums[mid] <= target) {
if (mid == nums.length - 1) {
return mid;
}
if (nums[mid+1] > target) {
return mid;
}
low = mid + 1
} else {
high = mid - 1
}
}
return -1;
};
时间O(nlogn)
code
public double findRadius(int[] lights) {
Arrays.sort(lights);
int left = 0;
int right = (lights[lights.length - 1] - lights[0] + 2) / 3;
while (left < right) {
int mid = left + (right - left) / 2;
if (feasible(lights, mid))
right = mid;
else
left = mid + 1;
}
return left / 2.0;
}
private boolean feasible(int[] lights, int diameter) {
int lightDist = lights[0] + diameter;
for (int i = 0; i < 3; i++) {
int idx = Arrays.binarySearch(lights, lightDist);
if (idx < 0) idx = -idx - 1;
if (idx >= lights.length) return true;
lightDist = lights[idx] + diameter;
}
return false;
}
public int findRadius(int[] houses, int[] heaters) {
int res = 0;
Arrays.sort(heaters);
for (int house : houses) {
int rightHeater = binarySearch(heaters, house);
int leftHeater = rightHeater - 1;
int leftDist = leftHeater < 0 ? Integer.MAX_VALUE : house - heaters[leftHeater];
int rightDist = rightHeater >= heaters.length ? Integer.MAX_VALUE : heaters[rightHeater] - house;
int curDist = Math.min(leftDist, rightDist);
res = Math.max(res, curDist);
}
return res;
}
private int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target)
right = mid;
else
left = mid + 1;
}
return left;
}
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int left = 0;
int right = Math.max(houses[houses.length - 1] - houses[0], heaters[heaters.length - 1]);
while (left < right) {
int mid = left + (right - left) / 2;
if (feasible(houses, heaters, mid))
right = mid;
else
left = mid + 1;
}
return left;
}
private boolean feasible(int[] houses, int[] heaters, int radius) {
for (int i = 0, j = 0; i < houses.length; i++) {
while (j < heaters.length && houses[i] > heaters[j] + radius) j++;
if (j < heaters.length && houses[i] >= heaters[j] - radius && houses[i] <= heaters[j] + radius)
continue;
return false;
}
return true;
}
class Solution:
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
ans = 0
heaters.sort()
for house in houses:
j = bisect_right(heaters,house)
i = j-1
if j < len(heaters):
rd = heaters[j] - house
else:
rd = float("inf")
if i >= 0:
ld = house - heaters[i]
else:
ld = float("inf")
cd = min(ld, rd)
ans = max(ans, cd)
return ans
O((n+m)logn)
O(logn)
class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int left = 0, right = (int)(1e9);
while (left < right) {
int mid = (left + right) / 2;
if (isCheck(houses, heaters, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public boolean isCheck(int[] houses, int[] heaters, int cover) {
int n = houses.length, cnt = 0, m = heaters.length;
for (int l = 0, r = 0, i = 0; i < m; i++) {
int lo = heaters[i] - cover, hi = heaters[i] + cover;
while (l < n && houses[l] < lo) l++;
while (r < n && houses[r] <= hi) r++;
cnt += r - l;
l = r;
}
return cnt == n;
}
}
class Solution:
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
ans = 0
heaters.sort()
for house in houses:
j = bisect_right(heaters,house)
i = j-1
if j < len(heaters):
rd = heaters[j] - house
else:
rd = float("inf")
if i >= 0:
ld = house - heaters[i]
else:
ld = float("inf")
cd = min(ld, rd)
ans = max(ans, cd)
return ans
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;
int curDistance = Math.min(leftDistance, rightDistance);
ans = Math.max(ans, curDistance);
}
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 = (right - left + 1) / 2 + left;
if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid;
}
}
return left;
}
}
链接打不开看评论做的475题 使用二分法来找到房子最近的暖炉,找到左边和右边的暖炉,在比较左边和右边暖炉距离的最小值,即为当前房子距暖炉的最小半径。最后,再取每个房子距暖炉的最小半径的最大值
const findRadius = (houses, heaters) => {
heaters.sort((a, b) => a - b)
let result = 0
const len = heaters.length
for (let house of houses) {
// 当前房子左侧暖炉的位置
let i = headtersPosSearch(heaters, house)
// 当前房子右侧暖炉的位置
let j = i + 1
const left = i < 0 ? Infinity : house - heaters[i]
const right = j >= len ? Infinity : heaters[j] - house
result = Math.max(result, Math.min(left, right))
}
return result
}
const headtersPosSearch = (nums, target) => {
let left = 0, right = nums.length - 1
if (nums[left] > target) return -1 // 说明房屋左侧没有暖炉
while (left < right) {
const mid = left + Math.floor((right - left + 1) / 2)
if (nums[mid] > target) {
right = mid - 1
} else {
left = mid
}
}
return left
}
复杂度分析: 时间复杂度:O(N*logN)
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
二分法:寻找最左边的满足条件的值
from sortedcontainers import SortedList
class Solution:
def solve(self, A):
d = SortedList()
ans = 0
for a in A:
i = d.bisect_right(a * 3)
ans += len(d) - i
d.add(a)
return ans
class Solution: def solve(self, nums): nums.sort() N = len(nums) if N <= 3: return 0 LIGHTS = 3 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
class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int l = 0, r = (int) 1e9;
while (l < r) {
int mid = l + r >> 1;
if (check(houses, heaters, mid)) {
r = mid;
}else{
l = mid + 1;
}
}
return r;
}
boolean check(int[] houses, int[] heaters, int x) {
int n = houses.length, m = heaters.length;
for (int i = 0, j = 0; i < n; i++) {
while (j < m && houses[i] > heaters[j] + x){
j++;
}
if (j < m && heaters[j] - x <= houses[i] && houses[i] <= heaters[j] + x) {
continue;
}
return false;
}
return true;
}
}
func solve(nums []int) float32 {
possible := func(mid int) bool {
start := nums[0]
end := start + mid
for i := 0; i < 3; i++ {
index := 0
for nums[index] <= end {
index++
}
if index >= len(nums) {
return true
}
start = nums[index]
end = start + mid
}
return false
}
l := 0
r := nums[len(nums)-1] - nums[0]
for l <= r {
mid := l + (r-l)/2
if possible(mid) {
r = mid - 1
} else {
l = mid + 1
}
}
return float32(l) / 2
}
class Solution {
public:
int findRadius(vector<int> &houses, vector<int> &heaters) {
int ans = 0;
sort(heaters.begin(), heaters.end());
for (int house: houses) {
int j = upper_bound(heaters.begin(), heaters.end(), house) - heaters.begin();
int i = j - 1;
int rightDistance = j >= heaters.size() ? INT_MAX : heaters[j] - house;
int leftDistance = i < 0 ? INT_MAX : house - heaters[i];
int curDistance = min(leftDistance, rightDistance);
ans = max(ans, curDistance);
}
return ans;
}
};
var rotateString = function(s, goal) { const m = s.length, n = goal.length; if (m !== n) { return false; } for (let i = 0; i < n; i++) { let flag = true; for (let j = 0; j < n; j++) { if (s[(i + j) % n] !== goal[j]) { flag = false; break; } } if (flag) { return true; } } return false; };
475 二分查找到最近的加热器,看一前一后哪个近,取最远的最近距离。
class Solution {
public:
int find(vector<int>&heaters,int house){
int l=0,r=heaters.size()-1;
while(l<=r){
int mid=(l+r)/2;
if(heaters[mid]==house)return mid;
else if(heaters[mid]<house){
l=mid+1;
}else{
r=mid-1;
}
}
return l;
}
int findRadius(vector<int>& houses, vector<int>& heaters) {
int ans=0;
sort(heaters.begin(),heaters.end());
for(auto& h:houses){
// int j=upper_bound(heaters.begin(),heaters.end(),h)-heaters.begin();
int j=find(heaters,h);
cout<<j<<endl;
int r=j>=heaters.size()?INT_MAX:heaters[j]-h;
cout<<r<<endl;
int l=j<1?INT_MAX:h-heaters[j-1];
cout<<l<<endl;
int cur=l<r?l:r;
cout<<"cur:"<<cur<<endl;
ans=ans<cur?cur:ans;
}
return ans;
}
};
O((n+m)logn) O(logn)
class Solution {
public:
int findRadius(vector<int>& houses, vector<int>& heaters) {
sort(houses.begin(),houses.end());
sort(heaters.begin(),heaters.end());
int ans = 0;
int h = 0;
for(int i=0;i<houses.size();i++){
while(h+1<heaters.size() && abs(houses[i]-heaters[h])>=abs(houses[i]-heaters[h+1]))
h++;
ans = max(ans,abs(houses[i]-heaters[h]));
}
return ans;
}
};
复杂度分析
class Solution {
public double solve(int[] nums) {
Arrays.sort(nums);
int streetLength = nums[nums.length - 1] - nums[0];
int low = 0, high = streetLength / 3 + 1;
while (low + 1 < high) {
int mid = low + (high - low) / 2;
if (isPossible(nums, mid, 3)) {
high = mid;
} else {
low = mid;
}
}
if (isPossible(nums, low, 3)) {
return low / 2D;
}
return high / 2D;
}
private boolean isPossible(int[] nums, int diameter, int lightNumber) {
int lightDiameter = -1;
int currentLightNum = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > lightDiameter) {
currentLightNum++;
lightDiameter = nums[i] + diameter;
}
if (currentLightNum > lightNumber) {
return false;
}
}
return true;
}
}
能力二分。
class Solution {
public double solve(int[] nums) {
Arrays.sort(nums);
int streetLength = nums[nums.length - 1] - nums[0];
int low = 0, high = streetLength / 3 + 1;
while (low + 1 < high) {
int mid = low + (high - low) / 2;
if (isPossible(nums, mid, 3)) {
high = mid;
} else {
low = mid;
}
}
if (isPossible(nums, low, 3)) {
return low / 2D;
}
return high / 2D;
}
private boolean isPossible(int[] nums, int diameter, int lightNumber) {
int lightDiameter = -1;
int currentLightNum = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > lightDiameter) {
currentLightNum++;
lightDiameter = nums[i] + diameter;
}
if (currentLightNum > lightNumber) {
return false;
}
}
return true;
}
}
复杂度分析
/**
二分确定半径是否合规 TC: O(max(n,m)∗logL) SC: O(logn+logm)
*/
class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int l = 0, r = (int) 1e9;
while (l < r) {
int mid = l + r >> 1;
if (check(houses, heaters, mid))
r = mid;
else
l = mid + 1;
}
return r;
}
private boolean check(int[] houses, int[] heaters, int radius) {
int N = houses.length, M = heaters.length;
for (int i = 0, j = 0; i < n; i++) {
while (j < m && houses[i] > heaters[j] + radius)
j++;
if (j < m &&
heaters[j] - radius <= houses[i] &&
houses[i] <= heaters[j] + radius) {
continue;
}
return false;
}
return true;
}
}
public double solve(int[] nums) {
Arrays.sort(nums);
int streetLength = nums[nums.length - 1] - nums[0];
int low = 0, high = streetLength / 3 + 1;
while (low + 1 < high) {
int mid = low + (high - low) / 2;
if (isPossible(nums, mid, 3)) {
high = mid;
} else {
low = mid;
}
}
if (isPossible(nums, low, 3)) {
return low / 2D;
}
return high / 2D;
}
private boolean isPossible(int[] nums, int diameter, int lightNumber) {
int lightDiameter = -1;
int currentLightNum = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > lightDiameter) {
currentLightNum++;
lightDiameter = nums[i] + diameter;
}
if (currentLightNum > lightNumber) {
return false;
}
}
return true;
}
}
Java Code:
class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(houses);
Arrays.sort(heaters);
int l = 0, r = (int) 1e9;
while (l < r) {
int mid = l + r >> 1;
if (check(houses, heaters, mid)) r = mid;
else l = mid + 1;
}
return r;
}
boolean check(int[] houses, int[] heaters, int x) {
int n = houses.length, m = heaters.length;
for (int i = 0, j = 0; i < n; i++) {
while (j < m && houses[i] > heaters[j] + x) j++;
if (j < m && heaters[j] - x <= houses[i] && houses[i] <= heaters[j] + x) continue;
return false;
}
return true;
}
}
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.