Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitb37d8dd

Browse files
committed
add new files
1 parent2f814b7 commitb37d8dd

File tree

3 files changed

+133
-0
lines changed

3 files changed

+133
-0
lines changed
Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
/*
2+
We are given a linked list with head as the first node. Let's number the nodes in the list: node_1, node_2, node_3, ... etc.
3+
4+
Each node may have a next larger value: for node_i, next_larger(node_i) is the node_j.val such that j > i, node_j.val > node_i.val, and j is the smallest possible choice. If such a j does not exist, the next larger value is 0.
5+
6+
Return an array of integers answer, where answer[i] = next_larger(node_{i+1}).
7+
8+
Note that in the example inputs (not outputs) below, arrays such as [2,1,5] represent the serialization of a linked list with a head node value of 2, second node value of 1, and third node value of 5.
9+
10+
11+
12+
Example 1:
13+
14+
Input: [2,1,5]
15+
Output: [5,5,0]
16+
Example 2:
17+
18+
Input: [2,7,4,3,5]
19+
Output: [7,0,5,5,0]
20+
Example 3:
21+
22+
Input: [1,7,5,1,9,2,5,1]
23+
Output: [7,9,9,9,0,5,0,0]
24+
25+
*/
26+
27+
package main
28+
29+
typeListNodestruct {
30+
Valint
31+
Next*ListNode
32+
}
33+
34+
funcnextLargerNodes(head*ListNode) []int {
35+
ifhead==nil {
36+
returnnil
37+
}
38+
varnums []int
39+
forhead!=nil {
40+
nums=append(nums,head.Val)
41+
head=head.Next
42+
}
43+
varstack []int
44+
top:=-1
45+
stack=append(stack,0)
46+
top++
47+
fori:=1;i<len(nums);i++ {
48+
fortop!=-1&&nums[stack[top]]<nums[i] {
49+
nums[stack[top]]=nums[i]
50+
stack=stack[:top]
51+
top--
52+
}
53+
stack=append(stack,i)
54+
top++
55+
}
56+
fortop!=-1 {
57+
nums[stack[top]]=0
58+
stack=stack[:top]
59+
top--
60+
}
61+
returnnums
62+
}
63+
64+
/**
65+
维护一个单调递减的栈，当前元素小于栈顶元素时，就是要找的元素，出栈
66+
*/
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
/**
2+
Given the root of a binary search tree with distinct values, modify it so that every node has a new value equal to the sum of the values of the original tree that are greater than or equal to node.val.
3+
4+
As a reminder, a binary search tree is a tree that satisfies these constraints:
5+
6+
The left subtree of a node contains only nodes with keys less than the node's key.
7+
The right subtree of a node contains only nodes with keys greater than the node's key.
8+
Both the left and right subtrees must also be binary search trees.
9+
10+
*/
11+
package main
12+
13+
typeTreeNodestruct {
14+
Valint
15+
Left*TreeNode
16+
Right*TreeNode
17+
}
18+
19+
funcbstToGst(root*TreeNode)*TreeNode {
20+
helper(root,nil)
21+
returnroot
22+
}
23+
funchelper(root,max*TreeNode) {
24+
ifroot==nil {
25+
return
26+
}
27+
root.Val+=findSum(root.Right)
28+
ifmax!=nil {
29+
root.Val+=max.Val
30+
}
31+
helper(root.Left,root)
32+
helper(root.Right,max)
33+
}
34+
35+
funcfindSum(root*TreeNode)int {
36+
ifroot==nil {
37+
return0
38+
}
39+
sum:=root.Val
40+
sum+=findSum(root.Left)
41+
sum+=findSum(root.Right)
42+
returnsum
43+
}

‎496. Next Greater Element I.go

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28,3 +28,27 @@ func find(A []int, a int) int {
2828
}
2929
return-1
3030
}
31+
32+
/*
33+
用栈来解决，如果栈顶的元素比当前的值大，那么栈顶元素就是要找的值，记录当前元素和栈顶元素的对应关系并出栈
34+
*/
35+
funcnextGreaterElement1(nums1 []int,nums2 []int) []int {
36+
data:=make(map[int]int,len(nums2))
37+
varstack []int
38+
for_,num:=rangenums2 {
39+
forlen(stack)!=0&&stack[len(stack)-1]<num {
40+
data[stack[len(stack)]-1]=num
41+
stack=stack[:len(stack)-1]
42+
}
43+
stack=append(stack,num)
44+
}
45+
res:=make([]int,len(nums1))
46+
fori,num:=rangenums1 {
47+
ifelem,ok:=data[num];ok {
48+
res[i]=elem
49+
}else {
50+
res[i]=-1
51+
}
52+
}
53+
returnres
54+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp