Leetcode-array

1
2
3
4
type Interval struct {
Start int
End int
}

1 best time to buy and sell stock

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func maxProfit(prices []int) int {
if len(prices) < 1 {
return 0
}

var mp int
min_p := prices[0]
for _, price := range prices {
if price-min_p > mp {
mp = price - min_p
}
if price < min_p {
min_p = price
}
}

return mp
}

2 best time to buy and sell stock II

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
func maxProfit(prices []int) int {
if len(prices) < 1 {
return 0
}

var mp, pre_p, buy_p int
var status string // buy sell
for index, price := range prices {
if index == 0 {
pre_p = price
buy_p = price
status = "buy"
continue
}

if price > pre_p && status == "sell" {
buy_p = pre_p
status = "buy"
}

if pre_p > price && status == "buy" {
mp += pre_p - buy_p
status = "sell"
}

pre_p = price
}

if pre_p > buy_p && status == "buy" {
mp += pre_p - buy_p
}

return mp
}

3 plus one

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func plusOne(digits []int) []int {
var carry int
carry = 1
for index := len(digits) - 1; index >= 0; index -= 1 {
if carry+digits[index] == 10 {
carry = 1
digits[index] = 0
} else {
digits[index] += carry
carry = 0
}

if carry == 0 {
break
}
}

if carry == 1 {
return append([]int{1}, digits...)
}

return digits
}

4 pascal's triangle

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
func generate(numRows int) [][]int {
pt_arr := make([][]int, 0)
if numRows < 1 {
return pt_arr
}
pt_arr = append(pt_arr, []int{1})
if numRows == 1 {
return pt_arr
}
pt_arr = append(pt_arr, []int{1, 1})
if numRows < 3 {
return pt_arr
}
for i := 3; i <= numRows; i += 1 {
pt := make([]int, i)
pre_pt := pt_arr[i-2]
var pre int
for index, _ := range pre_pt {
if index == 0 {
pt[index] = pre_pt[index]
pre = pre_pt[index]
continue
}

if index == len(pre_pt)-1 {
pt[index] = pre + pre_pt[index]
pt[index+1] = pre_pt[index]
continue
}

pt[index] = pre + pre_pt[index]
pre = pre_pt[index]
}
pt_arr = append(pt_arr, pt)
}

return pt_arr
}
1
2
3
func main() {
fmt.Println(generate(3))
}

5 pascal's triangle II

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
func getRow(rowIndex int) []int {
rowIndex += 1
pt_row := make([]int, rowIndex)
if rowIndex < 1 {
return pt_row
}
pt_row[0] = 1
if rowIndex == 1 {
return pt_row
}
pt_row[1] = 1

for i := 3; i <= rowIndex; i += 1 {
ptr := pt_row[0:i]
pre_ptr := pt_row[0 : i-1]
var pre int
for index, _ := range pre_ptr {
if index == 0 {
pre = pre_ptr[index]
continue
}

if index == len(pre_ptr)-1 {
ptr[index+1] = pre_ptr[index]
ptr[index] = pre + pre_ptr[index]
continue
}

pre_num := pre_ptr[index]
ptr[index], pre = pre+pre_num, pre_num
}
}

return pt_row
}
1
2
3
func main() {
fmt.Println(getRow(4))
}

6 array partition I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func min(a, b int) int {
if a > b {
return b
} else {
return a
}
}

func arrayPairSum(nums []int) int {
sort.Ints(nums)
var p_sum int
for index := 0; index < len(nums); index += 2 {
p_sum += min(nums[index], nums[index+1])
}

return p_sum
}

7 find all numbers disappeared in an array

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
47
48
func findDisappearedNumbers(nums []int) []int {
if len(nums) < 1 {
return nums
}
dis_nums := make([]int, 0)

var pre, pre_index int
for index, num := range nums {
if index+1 != num && num != 0 {
pre = num
pre_index = index
break
}
}
if pre == 0 {
return dis_nums
}

for i := 0; i < len(nums); i += 1 {
if nums[pre-1] != pre && nums[pre-1] != 0 {
nums[pre-1], pre = pre, nums[pre-1]
continue
}

if nums[pre-1] == 0 {
nums[pre-1] = pre
}

nums[pre_index] = 0
for index, num := range nums {
if index+1 != num && num != 0 {
pre = num
pre_index = index
break
}
}
}

nums[pre-1] = pre

for index, num := range nums {
if index+1 != num {
dis_nums = append(dis_nums, index+1)
}
}

return dis_nums
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func findDisappearedNumbers(nums []int) []int {
marks := make([]int, 0)
for _, num := range nums {
marks[num-1] = 1
}

dis_nums := make([]int, 0)
for index, mark := range marks {
if mark == 0 {
dis_nums = append(dis_nums, index+1)
}
}
return dis_nums
}
1
2
3
func main() {
fmt.Println(findDisappearedNumbers([]int{4,3,2,7,8,2,3,1}))
}

8 two sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func twoSum(nums []int, target int) []int {
indices := make([]int, 0)
for i := 0; i < len(nums); i += 1 {
fir := nums[i]
for j := i+1; j < len(nums); j +=1 {
secd := nums[j]
if fir + secd == target {
indices = append(indices, i)
indices = append(indices, j)
break
}
}
}
return indices
}
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
var carry int
var sum_head, sum_curr *ListNode
for {
if l1 == nil && l2 == nil {
if carry > 0 {
sum_node := &ListNode{
Val: carry,
Next: nil,
}
if sum_head != nil {
sum_curr.Next = sum_node
sum_curr = sum_node
} else {
sum_head = sum_node
sum_curr = sum_node
}
}
break
}

var sum int
if l1 != nil && l2 != nil {
sum = l1.Val + l2.Val + carry
l1, l2 = l1.Next, l2.Next
} else if l2 == nil {
sum = l1.Val + carry
l1 = l1.Next
} else if l1 == nil {
sum = l2.Val + carry
l2 = l2.Next
}

if sum > 9 {
carry = 1
sum -= 10
} else {
carry = 0
}

sum_node := &ListNode{
Val: sum,
Next: nil,
}
if sum_head != nil {
sum_curr.Next = sum_node
sum_curr = sum_node
} else {
sum_head = sum_node
sum_curr = sum_node
}
}
return sum_head
}
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
type ListNode struct {
Val int
Next *ListNode
}



func make_list(vals []int) *ListNode{
var lst, lst_c *ListNode
for _, val := range vals {
node := &ListNode{
Val: val,
Next: nil,
}
if lst != nil {
lst_c.Next = node
lst_c = node
} else {
lst = node
lst_c = node
}
}
return lst
}

func print_list(lst *ListNode) {
var str string
for {
if lst == nil {
break
}
str += fmt.Sprintf("%d,", lst.Val)
lst = lst.Next
}
str = strings.Trim(str, ",")
fmt.Printf("[%s]", str)
}

func main() {
l1 := make_list([]int{2,4,3})
l2 := make_list([]int{5,6,4})
sum_lst := addTwoNumbers(l1,l2)
print_list(sum_lst)
}

9 two sum II - input array is sorted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func twoSum(nums []int, target int) []int {
indices := make([]int, 0)
for i := 0; i < len(nums); i += 1 {
fir := nums[i]
for j := i + 1; j < len(nums); j += 1 {
secd := nums[j]
if fir+secd == target {
indices = append(indices, i+1)
indices = append(indices, j+1)
break
}
}
}
return indices
}

10 remove duplicates from sorted array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func removeDuplicates(nums []int) int {
if (len(nums)) <2 {
return len(nums)
}

pre := nums[0]
size := 1
for _, num := range nums {
if pre != num {
pre = num
nums[size] = num
size++
}
}

return size
}

11 remove duplicates from sorted array II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func removeDuplicates(nums []int) int {
if (len(nums)) < 3 {
return len(nums)
}

size := 2
pp_num := nums[0]
p_num := nums[1]
nums_size := len(nums)
for i := 2; i < nums_size; i++ {
if nums[i] == p_num && p_num == pp_num {
continue
}

pp_num = p_num
p_num = nums[i]
nums[size] = nums[i]
size++
}

return size
}

12 remove element

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func removeElement(nums []int, val int) int {
var size int
for index, num := range nums {
if index == 0 {
if num == val {
size = 0
} else {
size = 1
}
continue
}

if num != val {
nums[size] = num
size += 1
}
}

return size
}

13 majority element

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func majorityElement(nums []int) int {
num_M := make(map[int]int)
for _, num := range nums {
time := num_M[num]
num_M[num] = time + 1
}

var mt_num, max_times int
for num, time := range num_M {
if time > max_times {
mt_num = num
max_times = time
}
}
return mt_num
}

14 DONE shortest unsorted continuous subarray

  • State "DONE" from "STARTED" [2017-07-17 Mon 23:32]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func findUnsortedSubarray(nums []int) int {
n_nums := make([]int, len(nums))
copy(n_nums, nums)
sort.Ints(n_nums)
var start, end int
for index, _ := range nums {
if nums[index] != n_nums[index] {
start = index
break
}
}

for index := len(nums) - 1; index >= 0; index -= 1 {
if nums[index] != n_nums[index] {
end = index + 1
break
}
}

return end - start
}

15 reshape the matrix

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
func matrixReshape(nums [][]int, r int, c int) [][]int {
if len(nums) < 1 || len(nums[0]) < 1 {
return [][]int{}
}

or := len(nums)
oc := len(nums[0])
if or*oc != r*c {
return nums
}

f_nums := make([]int, 0)
for index, _ := range nums {
row := nums[index]
f_nums = append(f_nums, row...)
}

n_nums := make([][]int, r)
for i := 0; i < r; i += 1 {
row := make([]int, c)
for j := 0; j < c; j += 1 {
row[j] = f_nums[i*c+j]
}
n_nums[i] = row
}

return n_nums
}

16 search insert position

1
2
3
4
5
6
7
8
9
10
11
12
13
func searchInsert(nums []int, target int) int {
for index, num := range nums {
if num == target {
return index
}

if num > target {
return index
}
}

return len(nums)
}

17 merge sorted array

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
func merge(nums1 []int, m int, nums2 []int, n int) {
if m == 0 {
for i := 0; i < n; i += 1 {
nums1[i] = nums2[i]
}
return
}

if n == 0 {
return
}

n1_index := m - 1
n2_index := n - 1
index := m + n - 1
for {
if n1_index < 0 || n2_index < 0 {
break
}

if nums1[n1_index] > nums2[n2_index] {
nums1[index] = nums1[n1_index]
n1_index -= 1
index -= 1
} else {
nums1[index] = nums2[n2_index]
n2_index -= 1
index -= 1
}
}

if n2_index >= 0 {
for i := 0; i <= n2_index; i += 1 {
nums1[i] = nums2[i]
}
}

return
}

18 maximum product of three numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}

func maximumProduct(nums []int) int {
sort.Ints(nums)
size := len(nums)
return max(nums[size-1]*nums[size-2]*nums[size-3], nums[0]*nums[1]*nums[size-1])
}

19 maximum average subarray I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func findMaxAverage(nums []int, k int) float64 {
var max_average float64
for index := 0; index <= len(nums)-k; index += 1 {
var sub_sum int
for j := 0; j < k; j += 1 {
sub_sum += nums[index+j]
}

average := float64(sub_sum) / float64(k)
if index == 0 {
max_average = average
continue
}

if max_average < average {
max_average = average
}
}

return max_average
}

20 move zeroes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func moveZeroes(nums []int) {
for index, num := range nums {
if num == 0 {
continue
}

for j := index; 0 < j; j -= 1 {
if nums[j-1] == 0 {
nums[j-1], nums[j] = nums[j], nums[j-1]
} else {
break
}
}
}

return
}
1
2
3
4
5
func main() {
nums := []int{0, 1, 0, 3, 12}
moveZeroes(nums)
fmt.Println(nums)
}

21 can place flowers

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
47
48
49
50
51
func canPlaceFlowers(flowerbed []int, n int) bool {
if len(flowerbed) < 1 && n > 0 {
return false
}

if n == 0 {
return true
}

if len(flowerbed) < n {
return false
}

if len(flowerbed) == 1 {
if flowerbed[0] == 0 && n == 1 {
return true
} else {
return false
}
}

for index, _ := range flowerbed {
if flowerbed[index] == 1 {
continue
}

switch index {
case 0:
if flowerbed[index+1] == 0 {
flowerbed[index] = 1
n -= 1
}
case len(flowerbed) - 1:
if flowerbed[index-1] == 0 {
flowerbed[index] = 1
n -= 1
}
default:
if flowerbed[index-1] == 0 && flowerbed[index+1] == 0 {
flowerbed[index] = 1
n -= 1
}
}

if n < 1 {
return true
}
}

return false
}

22 contains duplicate

1
2
3
4
5
6
7
8
func containsDuplicate(nums []int) bool {
num_M := make(map[int]bool)
for _, num := range nums {
num_M[num] = true
}

return len(nums) > len(num_M)
}

23 contains duplicate II

1
2
3
4
5
6
7
8
9
10
11
12
13
func containsNearbyDuplicate(nums []int, k int) bool {
num_M := make(map[int]bool)
for index, num := range nums {
if index > k {
delete(num_M, nums[index-k-1])
}
if num_M[num] {
return true
}
num_M[num] = true
}
return false
}

24 contains duplicate III

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
func abs(x int) int {
if x < 0 {
return -x
} else {
return x
}
}

func getQuot(i, w int) int {
if i < 0 {
return (i+1)/w - 1
} else {
return i / w
}
}

func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
if t < 0 {
return false
}
num_M := make(map[int]int)
w := t + 1
for index, num := range nums {

quot := getQuot(num, w)
if _, ok := num_M[quot]; ok {
return true
}

if pre_num, ok := num_M[quot-1]; ok && abs(num-pre_num) < w {
return true
}

if pre_num, ok := num_M[quot+1]; ok && abs(num-pre_num) < w {
return true
}

num_M[quot] = num

if index >= k {
delete(num_M, getQuot(nums[index-k], w))
}

}
return false
}

25 k-diff pairs in an array

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
func findPairs(nums []int, k int) int {
sort.Ints(nums)
var base_index, pair_size int
for {
for i := base_index + 1; i < len(nums); i += 1 {
if nums[i]-nums[base_index] > k {
break
}
if nums[i]-nums[base_index] == k {
pair_size += 1
break
}
}

old_bi := base_index
for i := base_index + 1; i < len(nums); i += 1 {
if nums[i]-nums[base_index] > 0 {
base_index = i
break
}
}

if old_bi == base_index {
break
}

if base_index == len(nums)-1 {
break
}
}

return pair_size
}

26 best time to buy and sell stock II

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
func maxProfit(prices []int) int {
if len(prices) < 1 {
return 0
}

var mp, pre_p, buy_p int
var status string // buy sell
for index, price := range prices {
if index == 0 {
pre_p = price
buy_p = price
status = "buy"
continue
}

if price > pre_p && status == "sell" {
buy_p = pre_p
status = "buy"
}

if pre_p > price && status == "buy" {
mp += pre_p - buy_p
status = "sell"
}

pre_p = price
}

if pre_p > buy_p && status == "buy" {
mp += pre_p - buy_p
}

return mp
}

27 DONE maximum subarray

  • State "DONE" from "WAITING" [2017-07-18 Tue 23:30]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func maxSubArray(nums []int) int {
if len(nums) < 1 {
return 0
}

size := len(nums)
max_sum := nums[0]
pre_sum := nums[0]
for i := 1; i < size; i += 1 {
if pre_sum > 0 {
pre_sum = nums[i] + pre_sum
} else {
pre_sum = nums[i]
}
if pre_sum > max_sum {
max_sum = pre_sum
}
}

return max_sum
}

28 missing number

1
2
3
4
5
6
7
8
9
func missingNumber(nums []int) int {
var sum int
for _, num := range nums {
sum += num
}

size := len(nums)
return size*(size+1)/2 - sum
}

29 max consecutive ones

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func findMaxCntecutiveOnes(nums []int) int {
var cnt, max_cnt int
for _, num := range nums {
if num == 0 {
if cnt > max_cnt {
max_cnt = cnt
}
cnt = 0
}

if num == 1 {
cnt += 1
}
}
if cnt > max_cnt {
max_cnt = cnt
}

return max_cnt
}

30 rotate array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func reverse(nums []int) {
size := len(nums)
mid := size / 2
for i := 0; i < mid; i += 1 {
nums[i], nums[size-i-1] = nums[size-i-1], nums[i]
}
}

func rotate(nums []int, k int) {
size := len(nums)
if size == 1 {
return
}
k = k % size
reverse(nums[0 : size-k])
reverse(nums[size-k : size])
reverse(nums)
}
1
2
3
4
5
func main() {
arr := []int{1,2,3,4,5,6,7}
rotate(arr, 3)
fmt.Println(arr)
}

31 find peak element

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
func findPeakElement(nums []int) int {
if len(nums) < 1 {
return -1
}
if len(nums) == 1 {
return 0
}

var pe int
size := len(nums)
for i := 0; i < size; i += 1 {
switch i {
case 0:
if nums[0] > nums[1] {
return 0
}
case size - 1:
if nums[size-1] > nums[size-2] {
return size - 1
}
default:
if nums[i-1] < nums[i] && nums[i] > nums[i+1] {
return i
}
}
}

return -1
}

32 maximum product subarray

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}

func min(a, b int) int {
if a > b {
return b
} else {
return a
}
}

func maxProduct(nums []int) int {
if len(nums) < 1 {
return 0
}

size := len(nums)
maxp_sub_arr := make([]int, size)
ng_maxp_sub_arr := make([]int, size)
maxp_sub_arr[0] = nums[0]
if maxp_sub_arr[0] < 0 {
ng_maxp_sub_arr[0] = maxp_sub_arr[0]
} else {
ng_maxp_sub_arr[0] = 1
}
for i := 1; i < size; i += 1 {
if nums[i] == 0 {
continue
}

if maxp_sub_arr[i-1] == 0 {
maxp_sub_arr[i] = nums[i]
if nums[i] < 0 {
ng_maxp_sub_arr[i] = maxp_sub_arr[i]
} else {
ng_maxp_sub_arr[i] = 1
}
}

if nums[i] > 0 {
maxp_sub_arr[i] = max(nums[i]*maxp_sub_arr[i-1], nums[i])
ng_maxp_sub_arr[i] = nums[i] * ng_maxp_sub_arr[i-1]
}

if nums[i] < 0 {
maxp_sub_arr[i] = nums[i] * ng_maxp_sub_arr[i-1]
ng_maxp_sub_arr[i] = min(nums[i]*maxp_sub_arr[i-1], nums[i])
}
}

maxp := maxp_sub_arr[0]
for _, subp := range maxp_sub_arr {
if subp > maxp {
maxp = subp
}
}

return maxp
}
1
2
3
func main() {
fmt.Println(maxProduct([]int{2,3,-2,4,0,-3,-4}))
}

33 minimum size subarray sum

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
func minSubArrayLen(s int, nums []int) int {
if len(nums) < 0 {
return 0
}

var sub_sum, msub_arl, sub_arl int
size := len(nums)
msub_arl = size + 1
for index, num := range nums {
if sub_sum+num < s {
sub_sum += num
sub_arl += 1
continue
}

if sub_sum+num >= s {
for {
if sub_arl < 1 {
break
}

del_num := nums[index-sub_arl]
sub_sum -= del_num
sub_arl -= 1
if sub_sum+num < s {
sub_sum += num
sub_arl += 1
break
}
}

if sub_arl+1 < msub_arl {
msub_arl = sub_arl + 1
}
}
}

if msub_arl == size+1 {
msub_arl = 0
}

return msub_arl
}
1
2
3
func main() {
fmt.Println(minSubArrayLen(15, []int{5,1,3,5,10,7,4,9,2,8}))
}

34 array nesting

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
func arrayNesting(nums []int) int {
anl_arr := make([]int, len(nums))

var max_anl int
for _, num := range nums {
if anl_arr[num] > 0 {
continue
}

var anl int
next_num := num
for {
anl_arr[next_num] = 1
anl += 1

next_num = nums[next_num]
if next_num == num {
break
}
}

if anl > max_anl {
max_anl = anl
}
}

return max_anl
}
1
2
3
func main() {
fmt.Println(arrayNesting([]int{5,4,0,3,1,6,2}))
}

35 triangle

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
func min(a, b int) int {
if a < b {
return a
} else {
return b
}
}

func minimumTotal(triangle [][]int) int {
pre_nums := triangle[0]
trg_size := len(triangle)
for i := 1; i < trg_size; i += 1 {
nums := triangle[i]
n_size := len(nums)
for j, _ := range nums {
switch j {
case 0:
nums[0] += pre[0]
case n_size - 1:
nums[n_size-1] += pre_nums[n_size-2]
default:
nums[j] += min(pre_nums[j-1], pre_nums[j])
}
}
pre_nums = nums
}

min_total := pre_nums[0]
for _, num := range pre_nums {
if num < min_total {
min_total = num
}
}

return min_total
}

36 subsets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func subsets(nums []int) [][]int {
if len(nums) < 1 {
return [][]int{[]int{}}
}

sub_sets := subsets(nums[1:])
sets := sub_sets
num := nums[0]
for _, set := range sub_sets {
nset := append([]int{num}, set...)
sets = append(sets, nset)
}

return sets
}

37 subsets II

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
type Item struct {
Num int
Count int
}

func subsetsWithDup(nums []int) [][]int {
num_M := make(map[int]int)
for _, num := range nums {
num_M[num] += 1
}

items := make([]*Item, 0)
for num, count := range num_M {
item := &Item{
Num: num,
Count: count,
}
items = append(items, item)
}

return subsets(items)
}

func subsetsHelper(item *Item, sub_sets [][]int) [][]int {
sets := sub_sets
for _, set := range sub_sets {
var _count int
for {
if _count == item.Count {
break
}
set = append([]int{item.Num}, set...)
sets = append(sets, set)
_count += 1
}
}
return sets
}

func subsets(items []*Item) [][]int {
if len(items) < 1 {
return [][]int{[]int{}}
}

return subsetsHelper(items[0], subsets(items[1:]))
}

38 search in rotated sorted array

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
func search(nums []int, target int) int {
start, end := 0, len(nums)-1
for start <= end {
mid := start + (end-start)/2
if nums[mid] == target {
return mid
}

if start == end {
break
}

if (nums[start] <= nums[mid] && (target < nums[start] || nums[mid] < target)) ||
(nums[mid] <= nums[end] && (target >= nums[mid] && nums[end] >= target)) {
start = mid + 1
continue
}

if (nums[start] <= nums[mid] && (target >= nums[start] && nums[mid] >= target)) ||
(nums[mid] <= nums[end] && (target < nums[mid] || nums[end] < target)) {
end = mid - 1
continue
}
}

return -1
}

39 search in rotated sorted array II

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
47
48
func search(nums []int, target int) bool {
start, end := 0, len(nums)-1
for start <= end {
if nums[start] == nums[end] {
if nums[start] == target {
return true
}

dup_num := nums[start]
for {
if start == end || nums[start] != dup_num {
break
}
start++
}

for {
if start == end || nums[end] != dup_num {
break
}
end--
}
}

mid := start + (end-start)/2
if nums[mid] == target {
return true
}

if start == end {
break
}

if (nums[start] <= nums[mid] && (target < nums[start] || nums[mid] < target)) ||
(nums[mid] <= nums[end] && (target >= nums[mid] && nums[end] >= target)) {
start = mid + 1
continue
}

if (nums[start] <= nums[mid] && (target >= nums[start] && nums[mid] >= target)) ||
(nums[mid] <= nums[end] && (target < nums[mid] || nums[end] < target)) {
end = mid - 1
continue
}
}

return false
}

40 search a 2d matrix

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
func searchMatrix(matrix [][]int, target int) bool {
length := len(matrix)
if length < 1 {
return false
}
start, end := 0, length-1
width := len(matrix[0])
for start <= end {
if start == end {
break
}
mid := start + (end-start)/2
if matrix[mid][0] > target {
end = mid - 1
} else if matrix[mid][0] < target {
if target > matrix[mid][width-1] {
start = mid + 1
} else {
start = mid
break
}
} else {
return true
}
}

return binary_search(matrix[start], target) != -1
}

func binary_search(nums []int, target int) int {
start, end := 0, len(nums)-1
for start <= end {
mid := start + (end-start)/2
if nums[mid] > target {
end = mid - 1
} else if nums[mid] < target {
start = mid + 1
} else {
return mid
}
}

return -1
}

41 sort colors

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func sortColors(nums []int) {
colors := make([]int, 3)
for _, num := range nums {
colors[num] += 1
}

var base int
for color, count := range colors {
for count > 0 {
nums[base] = color
count--
base++
}
}

return
}

42 set matrix zeroes

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
func setZeroes(matrix [][]int) {
length := len(matrix)
if length < 1 {
return
}
width := len(matrix[0])
row_M := make(map[int]bool, length)
col_M := make(map[int]bool, width)
for i := 0; i < length; i++ {
for j := 0; j < width; j++ {
if matrix[i][j] == 0 {
row_M[i] = true
col_M[j] = true
}
}
}

if len(row_M) > 0 {
for row, _ := range row_M {
for i := 0; i < width; i++ {
matrix[row][i] = 0
}
}
}

if len(col_M) > 0 {
for col, _ := range col_M {
for i := 0; i < length; i++ {
matrix[i][col] = 0
}
}
}

return
}

43 unique paths

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func uniquePaths(m int, n int) int {
if m < 2 {
return m
}

matrix := make([][]int, 2)
matrix[0] = make([]int, n)
matrix[1] = make([]int, n)
for i := 0; i < n; i++ {
matrix[0][i] = 1
}
matrix[1][0] = 1

pre_row := matrix[0]
curr_row := matrix[1]
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
curr_row[j] = curr_row[j-1] + pre_row[j]
}
pre_row, curr_row = curr_row, pre_row
}

return pre_row[n-1]
}

44 unique paths II

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
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
m := len(obstacleGrid)
if m < 1 {
return 0
}
n := len(obstacleGrid[0])
if n < 1 {
return 0
}
if obstacleGrid[0][0] == 1 {
return 0
}

matrix := make([][]int, 2)
matrix[0] = make([]int, n)
matrix[1] = make([]int, n)
for i := 0; i < n; i++ {
if obstacleGrid[0][i] == 1 {
break
}
matrix[0][i] = 1
}
if m > 1 && obstacleGrid[1][0] == 0 {
matrix[1][0] = 1
}

pre_row := matrix[0]
curr_row := matrix[1]
for i := 1; i < m; i++ {
for j := 0; j < n; j++ {
if obstacleGrid[i][j] == 0 {
if j > 0 {
curr_row[j] = curr_row[j-1] + pre_row[j]
} else {
curr_row[j] = pre_row[j]
}
} else {
curr_row[j] = 0
}
}
pre_row, curr_row = curr_row, pre_row
}

return pre_row[n-1]
}

45 spiral matrix

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
47
func spiralOrder(matrix [][]int) []int {
m := len(matrix)
if m < 1 {
return []int{}
}
n := len(matrix[0])
row_start := 0
row_end := m
col_start := 0
col_end := n
so_arr := make([]int, 0, m*n)
for {
for i := col_start; i < col_end; i++ {
so_arr = append(so_arr, matrix[row_start][i])
}
row_start += 1
if row_start == row_end {
break
}

for i := row_start; i < row_end; i++ {
so_arr = append(so_arr, matrix[i][col_end-1])
}
col_end -= 1
if col_start == col_end {
break
}

for i := col_end - 1; i >= col_start; i-- {
so_arr = append(so_arr, matrix[row_end-1][i])
}
row_end -= 1
if row_start == row_end {
break
}

for i := row_end - 1; i >= row_start; i-- {
so_arr = append(so_arr, matrix[i][col_start])
}
col_start += 1
if col_start == col_end {
break
}
}

return so_arr
}

46 spiral matrix II

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
47
48
49
50
51
52
53
func generateMatrix(n int) [][]int {
if n == 0 {
return [][]int{}
}

matrix := make([][]int, n)
for i := 0; i < n; i++ {
matrix[i] = make([]int, n)
}
row_start := 0
row_end := n
col_start := 0
col_end := n
num := 1
for {
for i := col_start; i < col_end; i++ {
matrix[row_start][i] = num
num += 1
}
row_start += 1
if row_start == row_end {
break
}

for i := row_start; i < row_end; i++ {
matrix[i][col_end-1] = num
num += 1
}
col_end -= 1
if col_start == col_end {
break
}

for i := col_end - 1; i >= col_start; i-- {
matrix[row_end-1][i] = num
num += 1
}
row_end -= 1
if row_start == row_end {
break
}

for i := row_end - 1; i >= row_start; i-- {
matrix[i][col_start] = num
num += 1
}
col_start += 1
if col_start == col_end {
break
}
}
return matrix
}

47 merge intervals

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
func merge(intervals []Interval) []Interval {
size := len(intervals)
if size < 2 {
return intervals
}

sort.Slice(intervals,
func(i, j int) bool {
return intervals[i].Start < intervals[j].Start
})

merge_intervals := make([]Interval, 0)
interval := intervals[0]
for i := 1; i < size; i++ {
if interval.End >= intervals[i].Start {
if interval.End < intervals[i].End {
interval.End = intervals[i].End
}
} else {
merge_intervals = append(merge_intervals, interval)
interval = intervals[i]
}
}
if interval.Start != intervals[0].Start {
merge_intervals = append(merge_intervals, interval)
}
if len(merge_intervals) < 1 {
merge_intervals = append(merge_intervals, interval)
}

return merge_intervals
}

48 jump game

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
class Solution {
public:
bool canJump(vector<int>& nums) {
if (nums.size() < 2) {
return true;
}

if (nums[0]==0) {
return false;
}

deque<int> position_deq;
set<int> position_set;
position_deq.push_back(0);
position_set.insert(0);
while (position_deq.size()>0) {
int position = position_deq.front();
position_deq.pop_front();
if (nums[position] > 0) {
for (int i = 1; i <= nums[position]; i++) {
int new_position = position +i;
if (new_position == nums.size()-1) {
return true;
}

if (nums[new_position]>0 &&
position_set.find(new_position) != position_set.end()) {
position_deq.push_back(new_position);
}
}
}
}

return false;
}
};
1
2
3
4
5
6
7
8
9
10
func canJump(nums []int) bool {
size := len(nums)
var i, reach int
for ; i < size && i <= reach; i++ {
if i+nums[i] > reach {
reach = i + nums[i]
}
}
return i == size
}

49 search for a range

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
func searchRange(nums []int, target int) []int {
target_index := binary_search(nums, target)
if target_index == -1 {
return []int{-1, -1}
}

start_index := target_index
for {
s_index := binary_search(nums[:start_index], target)
if s_index == -1 {
break
}
start_index = s_index
}

end_index := target_index
for {
e_index := binary_search(nums[end_index+1:], target)
if e_index == -1 {
break
}
end_index += 1 + e_index
}

return []int{start_index, end_index}
}

func binary_search(nums []int, target int) int {
start, end := 0, len(nums)-1
for start <= end {
mid := start + (end-start)/2
if nums[mid] > target {
end = mid - 1
} else if nums[mid] < target {
start = mid + 1
} else {
return mid
}
}

return -1
}

50 rotate image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func rotate(matrix [][]int) {
if len(matrix) < 2 {
return
}

size := len(matrix)
for i := 0; i < size-1; i++ {
var tmp int
matrix[i][size-1], tmp = matrix[0][i], matrix[i][size-1]
matrix[size-1][size-i-1], tmp = tmp, matrix[size-1][size-i-1]
matrix[size-i-1][0], tmp = tmp, matrix[size-i-1][0]
matrix[0][i] = tmp
}

if size-2 > 0 {
sub_matrix := make([][]int, 0, size-2)
for i := 1; i < size-1; i++ {
sub_matrix = append(sub_matrix, matrix[i][1:size-1])
}
rotate(sub_matrix)
}
return
}

51 valid triangle number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func triangleNumber(nums []int) int {
if len(nums) < 3 {
return 0
}
sort.Ints(nums)
size := len(nums)

var count int
for i := 0; i < size-2; i++ {
for j := i + 1; j < size-1; j++ {
for k := j + 1; k < size; k++ {
if nums[i]+nums[j] <= nums[k] {
break
}
count++
}
}
}

return count
}

52 DONE task scheduler

  • State "DONE" from "TODO" [2018-03-07 Wed 21:55]
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
func leastInterval(tasks []byte, n int) int {
if n == 0 {
return len(tasks)
}
n += 1

task_M := make(map[byte]int)
for _, tc := range tasks {
task_M[tc] += 1
}

task_num_arr := make([]int, 0)
for _, task_num := range task_M {
task_num_arr = append(task_num_arr, task_num)
}
sort.Ints(task_num_arr)

remain_tc_num := len(task_num_arr)
var interval_num int
for {
if remain_tc_num < 1 {
break
}
fmt.Println(remain_tc_num, interval_num, task_num_arr)

if remain_tc_num < n {
remain_max_tn := task_num_arr[remain_tc_num-1]
tn_index := remain_tc_num - 2
same_max_tn_num := 1
for {
if tn_index < 0 || task_num_arr[tn_index] < remain_max_tn {
break
}
same_max_tn_num += 1
tn_index -= 1
}
interval_num += (task_num_arr[remain_tc_num-1]-1)*n + same_max_tn_num
break
}

min_tn := task_num_arr[remain_tc_num-n]
tn_index := remain_tc_num - n + 1
same_min_tn_num := 1
for {
if tn_index == remain_tc_num || task_num_arr[tn_index] > min_tn {
break
}
same_min_tn_num += 1
tn_index += 1
}
interval_num += (min_tn) * n

rs_index := remain_tc_num - n
ls_index := rs_index + same_min_tn_num
fmt.Println(rs_index, ls_index, same_min_tn_num)
for {
if ls_index == remain_tc_num {
for {
if rs_index == remain_tc_num {
break
}
task_num_arr[rs_index] = task_num_arr[remain_tc_num-1]
rs_index += 1
}
break
}
task_num_arr[rs_index] = task_num_arr[ls_index] - min_tn
rs_index += 1
ls_index += 1
}
remain_tc_num -= same_min_tn_num
sort.Ints(task_num_arr)
}

return interval_num
}
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
func leastInterval(tasks []byte, n int) int {
if n == 0 {
return len(tasks)
}

task_M := make(map[byte]int)
for _, tc := range tasks {
task_M[tc] += 1
}

task_num_arr := make([]int, 26)
tn_index := 0
for _, task_num := range task_M {
task_num_arr[tn_index] = task_num
tn_index += 1
}
sort.Ints(task_num_arr)

var interval_num int
for {
if task_num_arr[25] <= 0 {
break
}

var tn_index int
for {
if tn_index > n {
break
}
if task_num_arr[25] == 0 {
break
}

if tn_index < 26 && task_num_arr[25-tn_index] > 0 {
task_num_arr[25-tn_index] -= 1
}
interval_num += 1
tn_index += 1
}
sort.Ints(task_num_arr)
}

return interval_num
}
1
2
3
4
5
6
7
package main



func main() {
fmt.Println(leastInterval([]byte("FJJAJFCHJBEGGFACIFJCJCHCADGHBFGCCAEBHJEIFDEACDBDJJCFDDJHAECDJDGGBCEGHIDHFEIBDEIECJGIDEDJCACCDIJBDHHJGBGAHEHEDEJEJCFCJGBCIIHFADGFCCFGCJBBICJJEGHCIGJIGGJGGEGBIJBHDHGFCHCDAGBHHBJCAFJGFEBFEBBAEFEHIICGJDHEFGGDEBFJJJDHEBDJIFCIEHFEGDECFEDEAIEADHGCIEGAHIGGAGFHJDFAGHBJAHBHCGFACCBIGGBCJJIEGDIJICGAJGFJFCFGJIEBGFADAIAEHFDDCBJIJHICDAGFIBEDCJGIHECEIIBBHJCFIDBFHFACAABDCAGBGFEGAAACJHHGCCBCEBEFIEEDIHGFAHBJBGHCCBGCBAEGAJGDCIGFGGAJEIDEAFAHCEDDDHIFFAFAACJDJHIFACBCACCHAJIBAIFJCIBCEEEJGFEIAAEBJHHHAHJEFEFGJDIDIFBJDAADFGBJHFADHCBAJHIFHEGBAFFACDGIIJHHCJGBADBFJDIAFFFFAEBCGHEBBAGDCCEACFGAIFBHJGCBHDAHBHHCAFICFACJIHHFBBDECJFCEAJECAEBAJFJJJHHCIEGGHJJHHHJHAGICECDGGFHDGHAEIDAHGEABFICAFBAIFGIFDABJBDFGJJAACHGFBIIJAHDFEFJBFCGEAGHEHHFIGCCGJBHFHDIBDIFHIDFGGEACAGHGHJFDFGDDCJCJGGGGHHGDEHGCBFIFCHJIAFDCFCEEDDCGBFEJCIEDBBIIIHCECJFGAIJDICGFIEIEFAGEJAIADAGJFEDIAEJICJBFBECEFGEJJIEDFCHHBGDIIFBGCFJBGJHDGCCIIEIBHBIGFHGCJDCEGFCHDACDHBCHIBAJCBDJDHFBAGGJIEFADHDBCAHFGBFHBHIJDHIBCDGAEAAIFIFBBIFAEIABGCFIAFIDHBIIBJFEBBBDCJEJJGDFFFGIHJJGDGF") 8))
}

53 DONE word search

  • State "DONE" from "TODO" [2017-07-24 Mon 00:27]
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
struct Coord {
int x;
int y;
char letter;
int seq_num;
int dir;
};

struct CoordComp {
bool operator() (const Coord& lhs, const Coord& rhs) const {
if (lhs.x<rhs.x) {
return true;
} else if (lhs.x>rhs.x) {
return false;
} else {
return lhs.y<rhs.y;
}
}
};

class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
for (int i=0; i < board.size(); i++) {
for (int j=0; j < board[i].size(); j++) {
if (board[i][j]==word[0]) {
Coord coord={i,j,word[0],0,0};
stack<Coord> coord_stk;
set<Coord,CoordComp> coord_set;
coord_stk.push(coord);
coord_set.insert(coord);
while (coord_stk.size()>0) {
Coord coord = coord_stk.top();
if (coord.seq_num == word.size()-1) {
return true;
}
coord_stk.pop();
coord_set.erase(coord);
int x, y;
x = coord.x;
y = coord.y;
for (int dir=coord.dir; dir<4; dir++) {
if (dir == 0 && y > 0 && board[x][y-1]==word[coord.seq_num+1]) {
coord.dir = 1;
coord_stk.push(coord);
coord_set.insert(coord);
Coord next_coord={x,y-1,word[coord.seq_num+1],coord.seq_num+1,0};
if (coord_set.find(next_coord) == coord_set.end()) {
coord_stk.push(next_coord);
coord_set.insert(next_coord);
}
break;
}

if (dir == 1 && x > 0 && board[x-1][y]==word[coord.seq_num+1]) {
coord.dir = 2;
coord_stk.push(coord);
coord_set.insert(coord);
Coord next_coord={x-1,y,word[coord.seq_num+1],coord.seq_num+1,0};
if (coord_set.find(next_coord) == coord_set.end()) {
coord_stk.push(next_coord);
coord_set.insert(next_coord);
}
break;
}

if (dir == 2
&& y < board[x].size()-1
&& board[x][y+1]==word[coord.seq_num+1]) {
coord.dir = 3;
coord_stk.push(coord);
coord_set.insert(coord);
Coord next_coord={x,y+1,word[coord.seq_num+1],coord.seq_num+1,0};
if (coord_set.find(next_coord) == coord_set.end()) {
coord_stk.push(next_coord);
coord_set.insert(next_coord);
}
break;
}

if (dir == 3
&& x < board.size()-1
&& board[x+1][y]==word[coord.seq_num+1]) {
coord.dir = 4;
coord_stk.push(coord);
coord_set.insert(coord);
Coord next_coord={x+1,y,word[coord.seq_num+1],coord.seq_num+1,0};
if (coord_set.find(next_coord) == coord_set.end()) {
coord_stk.push(next_coord);
coord_set.insert(next_coord);
}
break;
}
}
}
}
}
}

return false;
}
};

54 TODO next permutation

1
2
3
func nextPermutation(nums []int)  {

}

55 TODO 4sum

1
2
func fourSum(nums []int, target int) [][]int {
}

56 TODO 3sum closest

1
2
3
func threeSumClosest(nums []int, target int) int {

}

57 TODO 3sum

1
2
func threeSum(nums []int) [][]int {
}

58 DONE Image Smoother

  • State "DONE" from "STARTED" [2017-09-20 Wed 10:27]
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
func imageSmoother(M [][]int) [][]int {
m := len(M)
n := len(M[0])
if m == 0 || n == 0 {
return [][]int{}
}
dirs := [][]int{
[]int{0, 1}, []int{0, -1}, []int{1, 0}, []int{-1, 0},
[]int{-1, -1}, []int{1, 1}, []int{-1, 1}, []int{1, -1}}

sM := make([][]int, m)
for i := 0; i < m; i += 1 {
ar := make([]int, n)
for j := 0; j < n; j += 1 {
sum := M[i][j]
cnt := 1
for k := 0; k < len(dirs); k += 1 {
x := i + dirs[k][0]
y := j + dirs[k][1]
if x < 0 || x > m-1 || y < 0 || y > n-1 {
continue
}
sum += M[x][y]
cnt++
}
ar[j] = sum / cnt
}
sM[i] = ar
}
return sM
}

59 DONE Longest Continuous Increasing Subsequence

  • State "DONE" from [2017-09-20 Wed 22:35]
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
func findLengthOfLCIS(nums []int) int {
if len(nums) < 1 {
return 0
}

var length, sub_length int
pre_num := nums[0]
for _, num := range nums {
if num > pre_num {
sub_length += 1
} else {
if sub_length > length {
length = sub_length
}
sub_length = 1
}
pre_num = num
}

if sub_length > length {
length = sub_length
}

return length
}

60 DONE Non-decreasing Array

  • State "DONE" from "STARTED" [2017-09-21 Thu 09:50]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func checkPossibility(nums []int) bool {
var cnt int
for i := 0; i < len(nums)-1; i += 1 {
if nums[i] > nums[i+1] {
if i == 0 || nums[i-1] <= nums[i+1] {
nums[i] = nums[i+1]
} else {
nums[i+1] = nums[i]
}
cnt += 1
}

if cnt > 1 {
return false
}
}

return true
}

61 Find All Duplicates in an Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func findDuplicates(nums []int) []int {
marks := make([]int, len(nums))
for _, num := range nums {
marks[num-1] += 1
}

dups_nums := make([]int, 0)
for index, mark := range marks {
if mark > 1 {
dups_nums = append(dups_nums, index+1)
}
}
return dups_nums
}

62 TODO Beautiful Arrangement

1
2
3
func countArrangement(N int) int {

}

63 DONE Beautiful Arrangement II

  • State "DONE" from "TODO" [2018-03-09 Fri 23:05]
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
func constructArray(n int, k int) []int {
arr := make([]int, 0)
l, h := 1, 1+k
for {
arr = append(arr, l)
arr = append(arr, h)
l += 1
h -= 1

if l == h {
arr = append(arr, l)
break
}

if l > h {
break
}
}

for i := k + 2; i <= n; i += 1 {
arr = append(arr, i)
}

return arr
}
1
2
3
4
5
6
7
8
9
10
11
package main



func main() {
fmt.Println(constructArray(10, 1))
fmt.Println(constructArray(10, 3))
fmt.Println(constructArray(10, 5))
fmt.Println(constructArray(10, 7))
fmt.Println(constructArray(10, 9))
}

64 TODO Degree of an Array

1
2
func findShortestSubArray(nums []int) int {
}

65 DONE Toeplitz Matrix

  • State "DONE" from "TODO" [2018-03-07 Wed 22:36]
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
func isToeplitzMatrix(matrix [][]int) bool {
if len(matrix) < 2 {
return true
}

r_num := len(matrix)
c_num := len(matrix[0])

r_index := r_num - 1
c_index := 0

for {
if r_index == 0 && c_index == c_num {
break
}

rd_index := r_index + 1
cd_index := c_index + 1
num := matrix[r_index][c_index]
for {
if rd_index == r_num || cd_index == c_num {
break
}

if matrix[rd_index][cd_index] != num {
return false
}

rd_index += 1
cd_index += 1
}

if r_index > 0 {
r_index -= 1
} else {
c_index += 1
}
}

return true
}

66 DONE Insert Delete GetRandom O(1) - Duplicates allowed

  • State "DONE" from "TODO" [2018-03-26 Mon 18:07]
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package main

import (
"fmt"
"math/rand"
)

type RcPair struct {
Val int
MIndex int
}

type RandomizedCollection struct {
Nums []RcPair
NumM map[int][]int
}

/** Initialize your data structure here. */
func Constructor() RandomizedCollection {
return RandomizedCollection{
Nums: make([]RcPair, 0),
NumM: make(map[int][]int),
}
}

/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
func (this *RandomizedCollection) Insert(val int) bool {
iArr, bExist := this.NumM[val]
if !bExist {
iArr = make([]int, 0)
}
rcPair := RcPair{
Val: val,
MIndex: len(iArr),
}
this.Nums = append(this.Nums, rcPair)
iArr = append(iArr, len(this.Nums)-1)
this.NumM[val] = iArr

return !bExist
}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */
func (this *RandomizedCollection) Remove(val int) bool {
if iArr, bExist := this.NumM[val]; bExist {
last_p := this.Nums[len(this.Nums)-1]
this.Nums[iArr[len(iArr)-1]] = last_p
this.NumM[last_p.Val][last_p.MIndex] = iArr[len(iArr)-1]
iArr = iArr[:len(iArr)-1]
this.Nums = this.Nums[:len(this.Nums)-1]
if len(iArr) == 0 {
delete(this.NumM, val)
} else {
this.NumM[val] = iArr
}
return true
} else {
return false
}
}

/** Get a random element from the collection. */
func (this *RandomizedCollection) GetRandom() int {
return this.Nums[rand.Intn(len(this.Nums))].Val
}

func (this *RandomizedCollection) Debug() {
fmt.Println(this.Nums)
fmt.Println(this.NumM)
}

func main() {
rc := Constructor()
rc.Insert(4)
rc.Insert(3)
rc.Insert(4)
rc.Insert(2)
rc.Insert(4)
rc.Debug()
rc.Remove(4)
rc.Debug()
rc.Remove(4)
rc.Remove(4)
rc.Debug()
}

67 DONE 第一个缺失的正数

  • State "DONE" from "TODO" [2018-04-07 Sat 22:41]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func firstMissingPositive(nums []int) int {
length := len(nums)
for i := 0; i < length; i += 1 {
p := nums[i]
for p > 0 && p <= length && nums[p-1] != p {
x := nums[p-1]
nums[p-1] = p
p = x
}
}

for i := 0; i < length; i += 1 {
if nums[i] != i+1 {
return i + 1
}
}

return length + 1
}
Last Updated 2018-04-25 Wed 22:16.
Render by hexo-renderer-org with Emacs 25.3.2 (Org mode 8.2.10)