当前位置：网站首页>Daily leetcode force deduction (21~25)
Daily leetcode force deduction (21~25)
2022-06-27 11:51:00 【What do you want to say】
21. Merge two ordered lists
Merge two ascending linked lists into a new Ascending Link list and return . The new linked list is made up of all the nodes of the given two linked lists .
Example ：
Input ：1->2->4, 1->3->4
Output ：1->1->2->3->4->4
- 1.
- 2.
- 3.
- 4.
- Problem solving
fun _0021_mergeTwoLists() {
println("--------_0021_mergeTwoLists-------")
mergeTwoLists(
ListNode(1, ListNode(2, ListNode(4))),
ListNode(1, ListNode(3, ListNode(4)))
)?.print()
}
/**
* Recursive writing , When a linked list is empty , Just go back to the other one . Then the core compares the current two node values , If l1 Small ,
* So for l1 The next node of and l2 Call recursive functions , Assign return value to l1.next, Then return l1;
* Otherwise, for l2 The next node of and l1 Call recursive functions , Assign return value to l2.next, Then return l2
*/
fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
if (l1 == null) return l2
if (l2 == null) return l1
return if (l1.data < l2.data) {
l1.next = mergeTwoLists(l1.next, l2);l1
} else {
l2.next = mergeTwoLists(l1, l2.next);l2
}
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
22. Bracket generation
Numbers n Represents the logarithm of the generated bracket , Please design a function , Used to be able to generate all possible and Effective Bracket combination .
Example ：
Input ：n = 3
Output ：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- Problem solving
fun _0022_generateParenthesis() {
println("--------_0022_generateParenthesis-------")
println(generateParenthesis(1))
println(generateParenthesis(2))
println(generateParenthesis(3))
println(generateParenthesis(4))
}
/**
* Thought is to find the left parenthesis , Every left parenthesis found , Just put a complete parenthesis after it , Finally, add a word at the beginning (), All the conditions are formed ,
* It should be noted that , Sometimes there will be repetition , So use set data structure , The advantage is that if you encounter duplicates , Will not be added to the results ,
* Finally, we will set To vector that will do
*/
fun generateParenthesis(n: Int): List<String> {
val res = HashSet<String>()
if (n == 0) {
res.add("")
} else {
val pre = generateParenthesis(n - 1)
for (str in pre) {
var str = str
for (i in str.indices) {
if (str[i] == '(') {
str = str.substring(0, i + 1) + "()" + str.substring(i + 1, str.length)
res.add(str)
str = str.substring(0, i + 1) + str.substring(i + 3, str.length)
}
}
res.add("()$str")
}
}
return res.toList()
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
23. Merge K An ascending list
Here's an array of linked lists , Each list has been listed in ascending order .
Please merge all the linked lists into one ascending list , Return the merged linked list .
Example 1：
Input ：lists = [[1,4,5],[1,3,4],[2,6]]
Output ：[1,1,2,3,4,4,5,6]
explain ： The linked list array is as follows ：
[
1->4->5,
1->3->4,
2->6
]
Combine them into an ordered list to get .
1->1->2->3->4->4->5->6
Example 2：
Input ：lists = []
Output ：[]
Example 3：
Input ：lists = [[]]
Output ：[]
Tips ：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] Press Ascending array
lists[i].length The sum of is not more than 10^4
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- Problem solving
fun _0023_mergeKLists() {
println("--------_0023_mergeKLists-------")
mergeKLists(
arrayOf(
ListNode(1, ListNode(4, ListNode(5))),
ListNode(1, ListNode(3, ListNode(4))),
ListNode(2, ListNode(6)),
)
)?.print()
mergeKLists(arrayOf())?.print()
}
fun mergeKLists(lists: Array<ListNode?>): ListNode? {
val len = lists.size
if (len == 0) return null
else if (len == 1) return lists[0]
var min: ListNode? = null
val prev = ListNode(0)
var head: ListNode? = prev
while (true) {
var id = -1
for (i in 0 until len) {
if (min == null && lists[i] != null) {
min = lists[i]
}
val curr = lists[i]
if (curr != null && curr.data <= min?.data!!) {
min = curr
id = i
}
}
if (id != -1) {
head?.next = min
head = head?.next
min = null
lists[id] = lists[id]?.next
} else break
}
return prev.next
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
- 39.
- 40.
24. Two or two exchange nodes in a linked list
Given a linked list , Two or two exchange the adjacent nodes , And return the list after exchange .
You can't just change the values inside the node , It needs to actually exchange nodes .
Example 1：
Input ：head = [1,2,3,4]
Output ：[2,1,4,3]
Example 2：
Input ：head = []
Output ：[]
Example 3：
Input ：head = [1]
Output ：[1]
Tips ：
The number of nodes in the linked list is in the range [0, 100] Inside
0 <= Node.val <= 100
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- Problem solving
fun _0024_swapPairs() {
println("--------_0024_swapPairs-------")
swapPairs(ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, ListNode(6)))))))?.print()
swapPairs(ListNode(1, ListNode(2, ListNode(3, ListNode(4)))))?.print()
swapPairs(ListNode(1, ListNode(2, ListNode(3))))?.print()
swapPairs(ListNode(1))?.print()
}
/**
* Using the idea of backtracking , Recursively traverse to the end of the linked list , Then swap the last two , Then switch forward in turn ：
*/
fun swapPairs(head: ListNode?): ListNode? {
if (head?.next == null) {
return head
}
var temp = head.next
head.next = swapPairs(head.next?.next)
temp?.next = head
return temp
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
25. K A set of flip list
I'll give you a list , Every time k Group of nodes to flip , Please return to the flipped list .
k Is a positive integer , Its value is less than or equal to the length of the linked list .
If the total number of nodes is not k Integer multiple , Please keep the last remaining nodes in the original order .
Example ：
Here is the list ：1->2->3->4->5
When k = 2 when , Should return : 2->1->4->3->5
When k = 3 when , Should return : 3->2->1->4->5
explain ：
Your algorithm can only use constant extra space .
You can't just change the values inside the node , It's about actually switching nodes .
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- Problem solving
fun _0025_reverseKGroup() {
println("--------_0025_reverseKGroup-------")
reverseKGroup(ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))), 2)?.print()
reverseKGroup(ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))), 3)?.print()
reverseKGroup(
ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, ListNode(6)))))),
2
)?.print()
reverseKGroup(
ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, ListNode(6)))))),
3
)?.print()
reverseKGroup(
ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, ListNode(6)))))),
4
)?.print()
}
/**
* First, traverse the whole linked list , Count the length of the linked list , Then if the length is greater than or equal to k, Switching nodes , When k=2 when , Each segment only needs to be exchanged once ,
* When k=3 when , Each section needs to be exchanged 2 this , therefore i from 1 Start the cycle , Pay attention to updating after exchanging a paragraph pre The pointer , then num Self reduction k,
* until num<k When the cycle ends
*/
fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
var dummy = ListNode(-1)
var pre: ListNode? = dummy
var cur: ListNode? = pre
dummy.next = head
var num = 0
while (cur?.next != null) {
cur = cur.next
++num
}
while (num >= k) {
cur = pre?.next
for (i in 1 until k) {
var temp = cur?.next
cur?.next = temp?.next
temp?.next = pre?.next
pre?.next = temp
}
pre = cur
num -= k
}
return dummy.next
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
- 39.
- 40.
- 41.
- 42.
- 43.
- 44.
- 45.
- 46.
I'm Jinyang , If you want to upgrade and learn more about dry goods , Welcome to the official account ” Jinyang said “ Receive my latest articles
边栏推荐
- 器审科普：创新医疗器械系列科普——胸骨板产品
- Qstype implementation of self drawing interface project practice (I)
- Unity shader learning (II) the first shader
- Summary of qstype class usage (II)
- Jerry added an input capture channel [chapter]
- Oracle group statistics query
- 千万不要错过，新媒体运营15个宝藏公众号分享
- Wechat applet realizes five-star evaluation
- 【TcaplusDB知识库】TcaplusDB单据受理-建表审批介绍
- MQTT协议栈原理及交互流程图
猜你喜欢
Naacl 2022 | TAMT: search the transportable Bert subnet through downstream task independent mask training
Safe landing practice of software supply chain under salesforce containerized ISV scenario
【TcaplusDB知识库】TcaplusDB单据受理-事务执行介绍
等等， 怎么使用 SetMemoryLimit?
Redis distributed lock 15 ask, what have you mastered?
"24 of the 29 students in the class successfully went to graduate school" rushed to the hot search! Where are the remaining five?
C/s architecture
机器学习系统在生产中的挑战
alibaba jarslink
政策关注 | 加快构建数据基础制度，维护国家数据安全
随机推荐
QStyle实现自绘界面项目实战（一）
2022CISCN华中 Web
【TcaplusDB知识库】TcaplusDB单据受理-创建业务介绍
内存四区（栈，堆，全局，代码区）
L'utilisation de C language 0 length Array
ECMAScript 6（es6）
[tcapulusdb knowledge base] Introduction to tcapulusdb table data caching
R语言使用epiDisplay包的followup.plot函数可视化多个ID（病例）监测指标的纵向随访图、使用stress.labels参数在可视化图像中为强调线添加标签信息
【TcaplusDB知识库】TcaplusDB常规单据介绍
最大路径和问题（摘樱桃问题）
Build the Internet of things system from scratch
Wait, how do I use setmemorylimit?
R语言使用glm函数构建泊松对数线性回归模型处理三维列联表数据构建饱和模型、使用step函数基于AIC指标实现逐步回归筛选最佳模型、解读分析模型
Microsoft cloud technology overview
Four memory areas (stack, heap, global, code area)
Oracle group statistics query
Naacl 2022 | TAMT: search the transportable Bert subnet through downstream task independent mask training
Heap heap sort TOPK
杰理之无缝循环播放【篇】
R语言使用epiDisplay包的dotplot函数通过点图的形式可视化不同区间数据点的频率、使用by参数指定分组参数可视化不同分组的点图分布、使用dot.col参数指定分组数据点的颜色