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)