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

Commit9c7025d

Browse files
committed
add 204 find primes problem
1 parent170995d commit9c7025d

File tree

4 files changed

+221
-2
lines changed

4 files changed

+221
-2
lines changed

‎src/0097.Interleaving-String/Solution.go

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -21,8 +21,7 @@ func isInterleave(s1 string, s2 string, s3 string) bool {
2121
}elseifj==0 {
2222
dp[i][j]=dp[i-1][j]&&s1[i-1]==s3[i+j-1]
2323
}else {
24-
dp[i][j]= (dp[i-1][j]&&s1[i-1]==s3[i+j-1])||
25-
(dp[i][j-1]&&s2[j-1]==s3[i+j-1])
24+
dp[i][j]= (dp[i-1][j]&&s1[i-1]==s3[i+j-1])|| (dp[i][j-1]&&s2[j-1]==s3[i+j-1])
2625
}
2726
}
2827
}

‎src/0204.Count-Primes/README.md

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
#[204. Count Primes][title]
2+
3+
##Description
4+
5+
Count the number of prime numbers less than a non-negative number, n.
6+
7+
**Example 1:**
8+
9+
```
10+
Input: 10
11+
Output: 4
12+
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
13+
```
14+
15+
**Tags:** Math, String
16+
17+
##题意
18+
>求一个数以内的质数的个数
19+
20+
##题解
21+
22+
###思路1
23+
>求质数可以用`Sieve of Eratosthenes` 算法将时间复杂度降到
24+
25+
```json
26+
（1）先把1删除（现今数学界1既不是质数也不是合数）
27+
（2）读取队列中当前最小的数2，然后把2的倍数删去
28+
（3）读取队列中当前最小的数3，然后把3的倍数删去
29+
（4）读取队列中当前最小的数5，然后把5的倍数删去
30+
（5）读取队列中当前最小的数7，然后把7的倍数删去
31+
（6）如上所述直到需求的范围内所有的数均删除或读取
32+
```
33+
34+
```go
35+
funccountPrimes(numint)int {
36+
isPrime:=make([]bool, num)
37+
//初始化数组 true表示都是质数
38+
fori:=0; i < num; i++ {
39+
isPrime[i] =true
40+
}
41+
//循环检查质数 i<sqrt(n)可以转换为i*i < n
42+
//因为提劲的进行标记所以时间复杂可以到O(log N)
43+
fori:=2; i*i < num; i++ {
44+
if isPrime[i] ==false {
45+
continue
46+
}
47+
forj:= i * i; j < num; j = j + i {
48+
isPrime[j] =false
49+
}
50+
}
51+
ans:=0
52+
fori:=2; i < num; i++ {
53+
if isPrime[i] {
54+
ans++
55+
}
56+
}
57+
return ans
58+
}
59+
60+
```
61+
62+
###思路2
63+
>思路2
64+
```go
65+
66+
```
67+
68+
##结语
69+
70+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
71+
72+
[title]:https://leetcode.com/problems/count-primes/
73+
[me]:https://github.com/kylesliu/awesome-golang-leetcode

‎src/0204.Count-Primes/Solution.go

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
package Solution
2+
3+
//整合简化版
4+
funccountPrimes(nint)int {
5+
varansint
6+
prime:=make([]bool,n)
7+
fori:=2;i<n;i++ {
8+
ifprime[i]==false {
9+
ans++
10+
forj:=2;j*i<n;j++ {
11+
prime[j*i]=true
12+
}
13+
}
14+
15+
}
16+
returnans
17+
}
18+
19+
funccountPrimes2(nint)int {
20+
varansint
21+
fori:=2;i<n;i++ {
22+
ifisPrime(i) {
23+
ans++
24+
}
25+
26+
}
27+
returnans
28+
}
29+
30+
funcisPrime(numint)bool {
31+
ifnum<=1 {
32+
returnfalse
33+
}
34+
fori:=2;i*i<=num;i++ {
35+
ifnum%i==0 {
36+
returnfalse
37+
}
38+
}
39+
returntrue
40+
}
41+
42+
funccountPrimes3(numint)int {
43+
isPrime:=make([]bool,num)
44+
//初始化数组 true表示都是质数
45+
fori:=0;i<num;i++ {
46+
isPrime[i]=true
47+
}
48+
//循环检查质数 i<sqrt(n)可以转换为i*i < n
49+
//因为提劲的进行标记所以时间复杂可以到O(log N)
50+
fori:=2;i*i<num;i++ {
51+
ifisPrime[i]==false {
52+
continue
53+
}
54+
forj:=i*i;j<num;j=j+i {
55+
isPrime[j]=false
56+
}
57+
}
58+
ans:=0
59+
fori:=2;i<num;i++ {
60+
ifisPrime[i] {
61+
ans++
62+
}
63+
}
64+
returnans
65+
}
Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
package Solution
2+
3+
import (
4+
"reflect"
5+
"testing"
6+
)
7+
8+
funcTestSolution(t*testing.T) {
9+
//测试用例
10+
cases:= []struct {
11+
namestring
12+
inputsint
13+
expectint
14+
}{
15+
{"TestCase 1",10,4},
16+
}
17+
18+
//开始测试
19+
for_,c:=rangecases {
20+
t.Run(c.name,func(t*testing.T) {
21+
got:=countPrimes(c.inputs)
22+
if!reflect.DeepEqual(got,c.expect) {
23+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
24+
c.expect,got,c.inputs)
25+
}
26+
})
27+
}
28+
}
29+
30+
funcTestSolution2(t*testing.T) {
31+
//测试用例
32+
cases:= []struct {
33+
namestring
34+
inputsint
35+
expectint
36+
}{
37+
{"TestCase 1",10,4},
38+
}
39+
40+
//开始测试
41+
for_,c:=rangecases {
42+
t.Run(c.name,func(t*testing.T) {
43+
got:=countPrimes2(c.inputs)
44+
if!reflect.DeepEqual(got,c.expect) {
45+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
46+
c.expect,got,c.inputs)
47+
}
48+
})
49+
}
50+
}
51+
52+
53+
funcTestSolution3(t*testing.T) {
54+
//测试用例
55+
cases:= []struct {
56+
namestring
57+
inputsint
58+
expectint
59+
}{
60+
{"TestCase 1",10,4},
61+
}
62+
63+
//开始测试
64+
for_,c:=rangecases {
65+
t.Run(c.name,func(t*testing.T) {
66+
got:=countPrimes3(c.inputs)
67+
if!reflect.DeepEqual(got,c.expect) {
68+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
69+
c.expect,got,c.inputs)
70+
}
71+
})
72+
}
73+
}
74+
//压力测试
75+
funcBenchmarkSolution(b*testing.B) {
76+
77+
}
78+
79+
//使用案列
80+
funcExampleSolution() {
81+
82+
}

0 commit comments

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