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

Commit5d34e78

Browse files
committed
add new files
1 parentfa147a0 commit5d34e78

File tree

7 files changed

+311
-0
lines changed

7 files changed

+311
-0
lines changed

‎321-1.go

Lines changed: 158 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,158 @@
1+
package main
2+
3+
/*
4+
* @lc app=leetcode id=321 lang=golang
5+
*
6+
* [321] Create Maximum Number
7+
*
8+
* https://leetcode.com/problems/create-maximum-number/description/
9+
*
10+
* algorithms
11+
* Hard (25.16%)
12+
* Total Accepted: 28.7K
13+
* Total Submissions: 114K
14+
* Testcase Example: '[3,4,6,5]\n[9,1,2,5,8,3]\n5'
15+
*
16+
* Given two arrays of length m and n with digits 0-9 representing two numbers.
17+
* Create the maximum number of length k <= m + n from digits of the two. The
18+
* relative order of the digits from the same array must be preserved. Return
19+
* an array of the k digits.
20+
*
21+
* Note: You should try to optimize your time and space complexity.
22+
*
23+
* Example 1:
24+
*
25+
*
26+
* Input:
27+
* nums1 = [3, 4, 6, 5]
28+
* nums2 = [9, 1, 2, 5, 8, 3]
29+
* k = 5
30+
* Output:
31+
* [9, 8, 6, 5, 3]
32+
*
33+
* Example 2:
34+
*
35+
*
36+
* Input:
37+
* nums1 = [6, 7]
38+
* nums2 = [6, 0, 4]
39+
* k = 5
40+
* Output:
41+
* [6, 7, 6, 0, 4]
42+
*
43+
* Example 3:
44+
*
45+
*
46+
* Input:
47+
* nums1 = [3, 9]
48+
* nums2 = [8, 9]
49+
* k = 3
50+
* Output:
51+
* [9, 8, 9]
52+
*
53+
*/
54+
55+
funcmin(a,bint)int {
56+
ifa<b {
57+
returna
58+
}
59+
returnb
60+
}
61+
62+
// 如果nums1>nums2，返回true；否则返回false
63+
funccompare(nums1,nums2 []int)bool {
64+
i:=0
65+
for ;i<len(nums1)&&i<len(nums2);i++ {
66+
ifnums1[i]>nums2[i] {
67+
returntrue
68+
}elseifnums2[i]>nums1[i] {
69+
returnfalse
70+
}
71+
}
72+
ifi==len(nums1) {
73+
returnfalse
74+
}
75+
returntrue
76+
}
77+
78+
/*
79+
思路： 2*greedy + 1*DP
80+
81+
子问题1：找到数组中由k个数组成的最大数的组合（不改变先后顺序）
82+
getMax(nums []int, k int) []int {}
83+
84+
子问题2：将长度为i和k-i的两个最大值组合进行合并(不改变先后顺序)
85+
mergeMax(max1, max2 []int) []int {}
86+
87+
子问题3：获取子问题2中所有合并所得结果的最大组合
88+
dpMax(max1, max2 []int) []int {}
89+
*/
90+
funcgetMax(nums []int,kint) []int {
91+
size:=len(nums)
92+
res:=make([]int,k)
93+
// j代表res的长度，不是index
94+
j:=0
95+
fori:=0;i<size;i++ {
96+
forj>0&&nums[i]>res[j-1]&&size-i>k-j {
97+
j--
98+
}
99+
ifj<k {
100+
res[j]=nums[i]
101+
j++
102+
}
103+
}
104+
returnres
105+
}
106+
107+
funcmergeMax(max1,max2 []int,kint) []int {
108+
res:=make([]int,k)
109+
i1,i2:=0,0
110+
n1,n2:=len(max1),len(max2)
111+
fori:=0;i<k;i++ {
112+
ifi1==n1 {
113+
res[i]=max2[i2]
114+
i2++
115+
continue
116+
}
117+
ifi2==n2 {
118+
res[i]=max1[i1]
119+
i1++
120+
continue
121+
}
122+
//if max1[i1] > max2[i2] {
123+
ifcompare(max1[i1:],max2[i2:]) {
124+
res[i]=max1[i1]
125+
i1++
126+
}else {
127+
res[i]=max2[i2]
128+
i2++
129+
}
130+
}
131+
returnres
132+
}
133+
134+
funcdpMax(max1,max2 []int,kint) []int {
135+
fori:=0;i<k;i++ {
136+
ifmax1[i]>max2[i] {
137+
returnmax1
138+
}elseifmax2[i]>max1[i] {
139+
returnmax2
140+
}
141+
}
142+
returnmax1
143+
}
144+
145+
funcmaxNumber(nums1 []int,nums2 []int,kint) []int {
146+
n1,n2:=len(nums1),len(nums2)
147+
ifn2<n1 {
148+
returnmaxNumber(nums2,nums1,k)
149+
}
150+
iMax:=min(n1,k)
151+
res:=make([]int,k)
152+
fori:=0;i<=iMax;i++ {
153+
ifk-i<=n2 {
154+
res=dpMax(res,mergeMax(getMax(nums1,i),getMax(nums2,k-i),k),k)
155+
}
156+
}
157+
returnres
158+
}

‎454. 4Sum II.go

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
package main
2+
3+
/**
4+
思路类似两个数相加
5+
*/
6+
funcfourSumCount(A []int,B []int,C []int,D []int)int {
7+
maps:=make(map[int]int)
8+
fori:=0;i<len(A);i++ {
9+
forj:=0;j<len(B);j++ {
10+
maps[A[i]+B[j]]++
11+
}
12+
}
13+
ret:=0
14+
fori:=0;i<len(C);i++ {
15+
forj:=0;j<len(D);j++ {
16+
ret+=maps[-1*(C[i]+D[j])]
17+
}
18+
}
19+
returnret
20+
}

‎461. Hamming Distance.go

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
package main
2+
3+
funchammingDistance(xint,yint)int {
4+
res:=x^y
5+
ret:=0
6+
forres>0 {
7+
res&=res-1
8+
ret++
9+
}
10+
returnret
11+
}

‎464. Can I Win.go

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package main
2+
3+
/**
4+
dp
5+
用bitmap保存中间状态
6+
*/
7+
funchelper(maxInt,left,bitint,dpmap[int]bool,bitmap []int)bool {
8+
ifval,ok:=dp[bit];ok {
9+
returnval
10+
}
11+
ifleft<=maxInt {
12+
fori:=maxInt;i>=left;i-- {
13+
if (bit&bitmap[i])==0 {
14+
dp[bit]=true
15+
returntrue
16+
}
17+
}
18+
}
19+
fori:=maxInt;i>0;i-- {
20+
if (bit&bitmap[i])>0 {
21+
continue
22+
}
23+
bit|=bitmap[i]
24+
ret:=helper(maxInt,left-i,bit,dp,bitmap)
25+
bit&=^bitmap[i]
26+
ifret==false {
27+
dp[bit]=true
28+
returntrue
29+
}
30+
}
31+
dp[bit]=false
32+
returnfalse
33+
}
34+
funccanIWin(maxChoosableIntegerint,desiredTotalint)bool {
35+
dp:=make(map[int]bool)
36+
sum:=0
37+
bitmap:=make([]int,maxChoosableInteger+1)
38+
fori:=maxChoosableInteger;i>0;i-- {
39+
sum+=i
40+
bitmap[i]=1<<uint8(i)
41+
}
42+
ifsum<desiredTotal {
43+
returnfalse
44+
}
45+
returnhelper(maxChoosableInteger,desiredTotal,0,dp,bitmap)
46+
47+
}

‎475. Heaters.go

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package main
2+
3+
import (
4+
"math"
5+
"sort"
6+
)
7+
8+
funcfindRadius(houses []int,heaters []int)int {
9+
sort.Ints(heaters)
10+
ret:=-1
11+
for_,house:=rangehouses {
12+
idx:=sort.SearchInts(heaters,house)
13+
l,r:=math.MaxInt32,math.MaxInt32
14+
ifidx-1>=0 {
15+
l=house-heaters[idx-1]
16+
}
17+
ifidx<len(heaters) {
18+
r=heaters[idx]-house
19+
}
20+
ret=mymax(ret,mymin(l,r))
21+
}
22+
returnret
23+
}
24+
funcmymax(x,yint)int {
25+
ifx>y {
26+
returnx
27+
}
28+
returny
29+
}
30+
funcmymin(x,yint)int {
31+
ifx>y {
32+
returny
33+
}
34+
returnx
35+
}

‎476. Number Complement.go

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
package main
2+
3+
/**
4+
如果我们能知道该数最高位的1所在的位置，就可以构造一个长度和该数据所占位置一样长的一个掩码mask，然后概述和mask进行异或即可。
5+
*/
6+
7+
funcfindComplement(numint)int {
8+
mask:=1
9+
tmp:=num
10+
fortmp>0 {
11+
mask<<=1
12+
tmp>>=1
13+
}
14+
returnnum^ (mask-1)
15+
}

‎704. Binary Search.go

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package main
2+
3+
/**
4+
简单的二分查找
5+
*/
6+
funcsearch(nums []int,targetint)int {
7+
iflen(nums)==0 {
8+
return-1
9+
}
10+
start,end:=0,len(nums)-1
11+
forstart<=end {
12+
mid:= (start+end)/2
13+
ifnums[mid]==target {
14+
returnmid
15+
}
16+
ifnums[mid]>target {
17+
end=mid-1
18+
continue
19+
}
20+
ifnums[mid]<target {
21+
start=mid+1
22+
}
23+
}
24+
return-1
25+
}

0 commit comments

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