当前位置:网站首页>Leetcode divide and conquer / dichotomy
Leetcode divide and conquer / dichotomy
2022-07-05 06:13:00 【Dawnlighttt】
List of articles
q23 Merge k A sort list
Answer key
Use the idea of partition to solve , Merge sort . Because there is k A linked list , So traverse the linked list array , Then sort them one by one .
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
if len(lists) == 1 {
return lists[0]
}
var L *ListNode
L = mergeList(lists[0], lists[1])
for i := 2; i < len(lists); i++ {
L = mergeList(L, lists[i])
}
return L
}
func mergeList(L1, L2 *ListNode) *ListNode {
L := &ListNode{
}
curr := L
var next *ListNode
for L1 != nil && L2 != nil {
if L1.Val < L2.Val {
next = L1.Next
curr.Next = L1
L1.Next = nil
L1 = next
} else {
next = L2.Next
curr.Next = L2
L2.Next = nil
L2 = next
}
curr = curr.Next
}
if L1 != nil {
curr.Next = L1
}
if L2 != nil {
curr.Next = L2
}
return L.Next
}
q33 Search rotation sort array
Answer key
In this question , Arrays are not globally ordered , But partial order , But it can still be solved by dichotomy .
You can find that when we rotate the array , There must be a part of the array that is ordered , For example, in the example : The array becomes [4, 5, 6] and [7, 0, 1, 2] Two parts , And the left side of it [4, 5, 6] The array of this part is ordered .
So in the loop, we can check the mid Separate sides , Which side is orderly , And decide target Is it on the orderly side , If not on the orderly side , It must be on the other side . Through this idea, we finally get the answer .
func search(nums []int, target int) int {
n := len(nums)
if n == 0 {
return -1
}
if n == 1 {
if target == nums[0] {
return 0
} else {
return -1
}
}
l, r := 0, n - 1
for l <= r {
mid := (l + r) / 2
if nums[mid] == target {
return mid
}
// If the left side is in order
if nums[0] <= nums[mid] {
// If target Just in the left section
if nums[0] <= target && target < nums[mid] {
r = mid - 1
} else {
l = mid + 1
}
// If the right side is in order
} else {
// If target Just in the right section
if nums[mid] < target && target <= nums[n - 1] {
l = mid + 1
} else {
r = mid - 1
}
}
}
return -1
}
q34 Find the first and last positions of the elements in the sort array
Answer key
First use two points to find the value target The subscript midIndex, And then to midIndex Is the midpoint , Look left and right for target The left and right borders of .
func searchRange(nums []int, target int) []int {
l, r, midIndex, n := 0, len(nums) - 1, -1, len(nums)
for l <= r {
mid := (l + r) / 2
if nums[mid] == target {
midIndex = mid
break
}
if nums[mid] < target && target <= nums[n - 1] {
l = mid + 1
} else {
r = mid - 1
}
}
if midIndex == -1 {
return []int{
-1, -1}
}
start, end := 0, 0
for i := midIndex; i >= 0; i--{
if nums[i] == target {
start = i
} else {
break
}
}
for i := midIndex; i <= n - 1; i++{
if nums[i] == target {
end = i
} else {
break
}
}
return []int{
start, end}
}
边栏推荐
- Error ora-28547 or ora-03135 when Navicat connects to Oracle Database
- 打印机脱机时一种容易被忽略的原因
- Records of some tools 2022
- [rust notes] 13 iterator (Part 2)
- Network security skills competition in Secondary Vocational Schools -- a tutorial article on middleware penetration testing in Guangxi regional competition
- 1041 Be Unique
- Implement an iterative stack
- 927. Trisection simulation
- 1.14 - assembly line
- Liunx starts redis
猜你喜欢
随机推荐
Appium自动化测试基础 — Appium测试环境搭建总结
Wazuh开源主机安全解决方案的简介与使用体验
SQLMAP使用教程(一)
QQ computer version cancels escape character input expression
[rust notes] 14 set (Part 1)
Solution to game 10 of the personal field
CPU内核和逻辑处理器的区别
Leetcode-6109: number of people who know secrets
leetcode-556:下一个更大元素 III
Daily question 2006 Number of pairs whose absolute value of difference is k
leetcode-22:括号生成
Daily question 1342 Number of operations to change the number to 0
LeetCode 1200. Minimum absolute difference
JS quickly converts JSON data into URL parameters
Shutter web hardware keyboard monitoring
1041 Be Unique
“磐云杯”中职网络安全技能大赛A模块新题
1039 Course List for Student
[practical skills] how to do a good job in technical training?
Daily question 1189 Maximum number of "balloons"