File tree Expand file tree Collapse file tree 18 files changed +705
-15
lines changed
0001.Iterations/Binary-Gap
NumberOfDiscIntersections Expand file tree Collapse file tree 18 files changed +705
-15
lines changed Original file line number Diff line number Diff line change @@ -27,4 +27,49 @@ Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized cop
2727先找出bit 1的位子, 再開始算中間最長的長度
2828
2929## 來源
30- * https://app.codility.com/programmers/lessons/1-iterations/binary_gap/
30+ * https://app.codility.com/programmers/lessons/1-iterations/binary_gap/
31+
32+ ## 解答
33+ https://github.com/kimi0230/LeetcodeGolang/blob/master/Codility/Lesson/0001.Iterations/Binary-Gap/Binary-Gap.go
34+
35+
36+ ``` go
37+ package binarygap
38+
39+ // O(log n)
40+ func Solution (N int ) int {
41+ maxLen , curLen := 0 , 0
42+ findOne := false
43+ for N > 0 {
44+ curBit := N & 1
45+ if curBit == 1 {
46+ curLen = 0
47+ findOne = true
48+ } else if curBit == 0 && findOne {
49+ curLen++
50+ }
51+
52+ if curLen > maxLen {
53+ maxLen = curLen
54+ }
55+ N = N >> 1
56+ }
57+ return maxLen
58+ }
59+
60+ // https://wandbox.org/permlink/totZwDAbL1wCgsqt
61+ func evil (x int ) int {
62+ if x&(x+1 ) > 0 {
63+ return evil (x|(x>>1 )) + 1
64+ } else {
65+ return 0
66+ }
67+ }
68+
69+ func SolutionRecur (N int ) int {
70+ for (N & 1 ) == 0 {
71+ N = N >> 1
72+ }
73+ return evil (N)
74+ }
75+ ```
Original file line number Diff line number Diff line change @@ -44,4 +44,31 @@ Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized cop
4444## 解題思路
4545
4646## 來源
47- * https://app.codility.com/programmers/lessons/2-arrays/cyclic_rotation/
47+ * https://app.codility.com/programmers/lessons/2-arrays/cyclic_rotation/
48+
49+ ## 解答
50+ https://github.com/kimi0230/LeetcodeGolang/blob/master/Codility/Lesson/0002.Array/CyclicRotation/CyclicRotation.go
51+
52+
53+ ``` go
54+ package cyclicrotation
55+
56+ func Solution (A []int , K int ) []int {
57+ if K == 0 || len (A) <= 1 {
58+ return A
59+ }
60+
61+ K = K % len (A)
62+ return append (A[len (A)-K:], A[:len (A)-K]...)
63+ }
64+
65+ func Solution2 (A []int , K int ) []int {
66+ if K == 0 || len (A) <= 1 {
67+ return A
68+ }
69+ if K > len (A) {
70+ K = K % len (A)
71+ }
72+ return append (A[len (A)-K:], A[:len (A)-K]...)
73+ }
74+ ```
Original file line number Diff line number Diff line change @@ -39,4 +39,37 @@ Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized cop
39392 . 方法二: 所有的整數XOR起來, 若是兩個整數相同XOR得到0, 最後剩下基數次的數字
4040
4141## 來源
42- * https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/
42+ * https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/
43+
44+
45+ ## 解答
46+ https://github.com/kimi0230/LeetcodeGolang/blob/master/Codility/Lesson/0002.Array/OddOccurrencesInArray/OddOccurrencesInArray.go
47+
48+
49+ ``` go
50+ package oddoccurrencesinarray
51+
52+ func Solution (A []int ) int {
53+ intMap := make (map [int ]int )
54+ for i := 0 ; i < len (A); i++ {
55+ intMap[A[i]] += 1
56+ }
57+
58+ for k , v := range intMap {
59+ if v%2 != 0 {
60+ return k
61+ }
62+ }
63+ return -1
64+ }
65+
66+ // 所有的整數XOR起來, 若是兩個整數相同XOR得到0, 最後剩下基數次的數字
67+ // 前提只能有一個基數數字
68+ func Solution2 (A []int ) int {
69+ result := 0
70+ for i := 0 ; i < len (A); i++ {
71+ result ^= A[i]
72+ }
73+ return result
74+ }
75+ ```
Original file line number Diff line number Diff line change @@ -31,4 +31,24 @@ Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized cop
3131## 解題思路
3232
3333## 來源
34- * https://app.codility.com/programmers/lessons/3-time_complexity/frog_jmp/
34+ * https://app.codility.com/programmers/lessons/3-time_complexity/frog_jmp/
35+
36+ ## 解答
37+ https://github.com/kimi0230/LeetcodeGolang/blob/master/Codility/Lesson/0003.Time-Complexity/FrogJmp/FrogJmp.go
38+
39+
40+ ``` go
41+ package frogjump
42+
43+ import (
44+ " math"
45+ )
46+
47+ func Solution (X int , Y int , D int ) int {
48+ if Y < X {
49+ return 0
50+ }
51+ remainDist := Y - X
52+ return int (math.Ceil (float64 (remainDist) / float64 (D)))
53+ }
54+ ```
Original file line number Diff line number Diff line change @@ -31,3 +31,26 @@ Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized cop
3131
3232## 來源
3333* https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/
34+
35+ ## 解答
36+ https://github.com/kimi0230/LeetcodeGolang/blob/master/Codility/Lesson/0003.Time-Complexity/PermMissingElem/PermMissingElem.go
37+
38+
39+ ``` go
40+ package permmissingelem
41+
42+ func Solution (A []int ) int {
43+ if len (A) < 1 {
44+ return 1
45+ }
46+
47+ n := len (A) + 1
48+ predictSume := (n + 1 ) * n / 2
49+
50+ var sum int
51+ for _ , v := range A {
52+ sum += v
53+ }
54+ return predictSume - sum
55+ }
56+ ```
Original file line number Diff line number Diff line change @@ -52,3 +52,39 @@ Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized cop
5252
5353## 來源
5454* https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/
55+
56+ ## 解答
57+ https://github.com/kimi0230/LeetcodeGolang/blob/master/Codility/Lesson/0003.Time-Complexity/TapeEquilibrium/TapeEquilibrium.go
58+
59+
60+ ``` go
61+ package TapeEquilibrium
62+
63+ import " math"
64+
65+ func Solution (A []int ) int {
66+
67+ totalSum := 0
68+ for _ , v := range A {
69+ totalSum += v
70+ }
71+
72+ leftSum := A[0 ]
73+ rightSum := totalSum - leftSum
74+ result := math.MaxInt32
75+ for i := 1 ; i < len (A); i++ {
76+ tmpDiff := int (math.Abs (float64 (rightSum) - float64 (leftSum)))
77+ if tmpDiff < result {
78+ result = tmpDiff
79+ }
80+ rightSum -= A[i]
81+ leftSum += A[i]
82+ }
83+
84+ if result == math.MaxInt32 {
85+ result = 0
86+ }
87+
88+ return result
89+ }
90+ ```
Original file line number Diff line number Diff line change @@ -53,3 +53,22 @@ Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized cop
5353
5454## 來源
5555* https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/
56+
57+ ## 解答
58+ https://github.com/kimi0230/LeetcodeGolang/blob/master/Codility/Lesson/0004.Counting-Elements/FrogRiverOne/FrogRiverOne.go
59+
60+
61+ ``` go
62+ package FrogRiverOne
63+
64+ func Solution (X int , A []int ) int {
65+ intMap := make (map [int ]bool )
66+ for i := 0 ; i < len (A); i++ {
67+ intMap[A[i]] = true
68+ if len (intMap) == X {
69+ return i
70+ }
71+ }
72+ return -1
73+ }
74+ ```
Original file line number Diff line number Diff line change @@ -59,4 +59,48 @@ Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized cop
5959## 解題思路
6060
6161## 來源
62- https://app.codility.com/programmers/lessons/4-counting_elements/
62+ https://app.codility.com/programmers/lessons/4-counting_elements/
63+
64+ ## 解答
65+ https://github.com/kimi0230/LeetcodeGolang/blob/master/Codility/Lesson/0004.Counting-Elements/MaxCounters/MaxCounters.go
66+
67+
68+ ``` go
69+ package MaxCounters
70+
71+ func Max (x , y int ) int {
72+ if x > y {
73+ return x
74+ }
75+ return y
76+ }
77+
78+ // 時間 O(N+M) , 空間 O(N)
79+ func Solution (N int , A []int ) []int {
80+ result := make ([]int , N)
81+ maxNum := 0
82+ nowMaxNum := 0
83+ for i := 0 ; i < len (A); i++ {
84+ if A[i] > N {
85+ // 如果A[i] 大於 N 則將計數器中所有的數更新為計數器當前的最大數值
86+ maxNum = nowMaxNum
87+ } else {
88+ // 如果A[i] 小於 N 則將計數器中對應位置的數+1,
89+ if result[A[i]-1 ] < maxNum {
90+ result[A[i]-1 ] = maxNum
91+ }
92+ result[A[i]-1 ]++
93+
94+ if nowMaxNum < result[A[i]-1 ] {
95+ nowMaxNum = result[A[i]-1 ]
96+ }
97+ }
98+ }
99+ for i := 0 ; i < N; i++ {
100+ if result[i] < maxNum {
101+ result[i] = maxNum
102+ }
103+ }
104+ return result
105+ }
106+ ```
Original file line number Diff line number Diff line change @@ -29,4 +29,34 @@ Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized cop
2929先講出現的數字記錄起來, 再依序從1開始往後找出最小的整數且沒出現過
3030
3131## 來源
32- https://app.codility.com/programmers/lessons/4-counting_elements/missing_integer/
32+ https://app.codility.com/programmers/lessons/4-counting_elements/missing_integer/
33+
34+ ## 解答
35+ https://github.com/kimi0230/LeetcodeGolang/blob/master/Codility/Lesson/0004.Counting-Elements/MissingInteger/MissingInteger.go
36+
37+
38+ ``` go
39+ package MissingInteger
40+
41+ func Solution (A []int ) int {
42+ smallNum := 1
43+ intMap := make (map [int ]bool )
44+
45+ // 將出現的數字塞入map
46+ for _ , v := range A {
47+ if v > 0 && !intMap[v] {
48+ intMap[v] = true
49+ }
50+ }
51+
52+ for i := 1 ; i <= len (intMap); i++ {
53+ if !intMap[i] {
54+ // 此正整數沒在map找到
55+ return i
56+ }
57+ smallNum = i + 1
58+ }
59+
60+ return smallNum
61+ }
62+ ```
Original file line number Diff line number Diff line change @@ -55,4 +55,51 @@ Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized cop
5555最後檢查總時對不對
5656
5757## 來源
58- https://app.codility.com/programmers/lessons/4-counting_elements/perm_check/
58+ https://app.codility.com/programmers/lessons/4-counting_elements/perm_check/
59+
60+ ## 解答
61+ https://github.com/kimi0230/LeetcodeGolang/blob/master/Codility/Lesson/0004.Counting-Elements/PermCheck/PermCheck.go
62+
63+
64+ ``` go
65+ package PermCheck
66+
67+ func Solution (A []int ) int {
68+ intMap := make (map [int ]bool )
69+
70+ for _ , v := range A {
71+ if !intMap[v] {
72+ intMap[v] = true
73+ } else {
74+ // 重複出現
75+ return 0
76+ }
77+ }
78+
79+ for i := 1 ; i <= len (A); i++ {
80+ if !intMap[i] {
81+ return 0
82+ }
83+ }
84+ return 1
85+ }
86+
87+ func Solution2 (A []int ) int {
88+ intMap := make (map [int ]bool )
89+ sum := 0
90+ for _ , v := range A {
91+ if !intMap[v] {
92+ intMap[v] = true
93+ sum += v
94+ } else {
95+ // 重複出現
96+ return 0
97+ }
98+ }
99+
100+ if sum == (len (A)+1 )*len (A)/2 {
101+ return 1
102+ }
103+ return 0
104+ }
105+ ```
You can’t perform that action at this time.
0 commit comments