吹拉弹唱


  • Home
  • Archive
  • Categories
  • Tags
  • Books
  •  

© 2022 Kleon

Theme Typography by Makito

Proudly published with Hexo

Code - Array

Posted at 2022-05-05Updated at 2022-05-05 interview  interview algorithm 

  • LeetCode
    • 9. Palindrome Number
    • 125. Valid Palindrome
    • 680. Valid Palindrome II
    • 60. Permutation Sequence
    • 31. Next Permutation
    • 1793. Maximum Score of a Good Subarray
    • 4. Median of Two Sorted Arrays
    • 6. Zigzag Conversion
    • 11. Container With Most Water
    • 12. Integer to Roman
    • 13. Roman to Integer
    • 14. Longest Common Prefix
    • 551. Student Attendance Record I
    • 15. 3Sum
    • 16. 3Sum Closest
    • 17. Letter Combinations of a Phone Number
    • 401. Binary Watch
    • 18. 4Sum
    • 454. 4Sum II
    • 560. Subarray Sum Equals K
    • 523. Continuous Subarray Sum
    • 88. Merge Sorted Array
    • 977. Squares of a Sorted Array
    • 26. Remove Duplicates from Sorted Array
    • 80. Remove Duplicates from Sorted Array II
    • 27. Remove Element
    • 83. Remove Duplicates from Sorted List
    • 1023. Camelcase Matching
    • 66. Plus One
    • 283. Move Zeroes

# LeetCode

# 9. Palindrome Number

leetcode

According to the examples, a negative number is not palindromic. And the reverse of the number counting 0.

We can use two pointers to check if it’s a palindrome.

1
2
3
4
5
6
7
8
9
func isPalindrome(x int) bool {
    s := fmt.Sprintf("%v", x)
    for i, j := 0, len(s) - 1; i < j; i, j = i+1, j-1 {
        if (s[i] != s[j]) {
            return false
        }
    }
    return true
}

# 125. Valid Palindrome

leetcode

Similar to 5. But first remove all non-alphanumeric characters.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func isPalindrome(s string) bool {
    s = strings.ToLower(s)
    reg, err := regexp.Compile("[^a-z0-9]+")
    if err != nil {
        log.Fatal(err)
    }
    s = reg.ReplaceAllString(s, "")
    for i, j := 0, len(s) - 1; i < j; i, j = i+1, j-1 {
        if (s[i] != s[j]) {
            return false
        }
    }
    return true
}

# 680. Valid Palindrome II

leetcode

Similar to 5. But there is only one chance of unmatching. There are two possible situation, therefore we must validate each substring.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func validPalindrome(s string) bool {
    valid, low, high := compare(s, 0, len(s) - 1)
    if valid {
        return true
    }
    validLeft, _, _ := compare(s, low + 1, high)
    if validLeft {
        return true
    }
    validRight, _, _ := compare(s, low, high-1)
    return validRight
}

func compare(s string, low, high int) (bool, int, int) {
    for i, j := low, high; i < j; i, j = i+1, j-1 {
        if (s[i] != s[j]) {
            return false, i, j
        }
    }
    return true, 0, 0
}

# 60. Permutation Sequence

leetcode

A straight forward idea is divide k-1 by (n-1)!, because the n! are divided into (n-1)! interval, therefore we could find the interval number which is exactly the first number. For the rest of number, it’s quite similar. Remove the first number out of the sequence and get the interval and the next corresponding number.

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
func getPermutation(n int, k int) string {
    numbers := make([]int, n)
    for i := 1; i <= n; i++ {
        numbers[i-1] = i
    }
    fact := make([]int, n)
    fact[0] = 1
    for i := 1; i < n; i++ {
        fact[i] = fact[i-1]*i
    }
    
    k--
    
    output := ""
    for i := n - 1; i >= 0; i-- {
        index := k / fact[i]
        output += fmt.Sprintf("%v", numbers[index])
        k %= fact[i]
        remove(numbers, index)
    }
    return output
}

func remove(slice []int, s int) []int {
    return append(slice[:s], slice[s+1:]...)
}

# 31. Next Permutation

leetcode

This is quite different from 60. This is for a general situation.

Wikipedia
According to Wikipedia, a man named Narayana Pandita presented the following simple algorithm to solve this problem in the 14th century.

  • Find the largest index k such that nums[k] < nums[k + 1]. If no such index exists, just reverse nums and done.
  • Find the largest index l > k such that nums[k] < nums[l].
  • Swap nums[k] and nums[l].
  • Reverse the sub-array nums[k + 1:].
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 nextPermutation(nums []int)  {
    n := len(nums)
    k := 0
    l := 0
    for k = n - 2; k >= 0; k-- {
        if nums[k] < nums[k + 1] {
            break
        }
    }
    if k < 0 {
        reverse(nums)
    } else {
        for l = n - 1; l > k; l-- {
            if nums[l] > nums[k] {
                break
            }
        } 
        nums[l], nums[k] = nums[k], nums[l]
        reverse(nums[k+1:]);
    }
}

func reverse(s []int) {
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        s[i], s[j] = s[j], s[i]
    }
}

# 1793. Maximum Score of a Good Subarray

leetcode

Two pointer

We start with two pointers, left = right = k and the area = nums[k]
When increment the size of window, we want to reduce the min(nums[i]…nums[j]) slowly.
To do this, we can check the values on both sides of the window.
If A[i - 1] < A[j + 1], we do j = j + 1
If A[i - 1] >= A[j + 1], we do i = i - 1

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 maximumScore(nums []int, k int) int {
    left, right := k, k
    maxScore := nums[k]
    min := nums[k]
    count := 1
    for left > 0 || right < len(nums) - 1 {
        element := 0
        if right >= len(nums) - 1 {
            left--
            element = nums[left]
        } else if left <= 0 {
            right++
            element = nums[right]
        } else if nums[left - 1] < nums[right + 1] {
            right++
            element = nums[right]
        } else {
            left--
            element = nums[left]
        }
        if element < min {
            min = element
        }
        count++
        score := min * count
        if score > maxScore {
            maxScore = score
        }
    }
    return maxScore
}

# 4. Median of Two Sorted Arrays

leetcode

Brute Force

Time Complexity O(M+N), Space Complexity O(M+N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    nums := make([]int, 0, len(nums1)+len(nums2))
    i, j := 0, 0
    for i < len(nums1) && j < len(nums2) {
        if nums1[i] <= nums2[j] {
            nums = append(nums, nums1[i])
            i++
        } else {
            nums = append(nums, nums2[j])
            j++
        }
    }
    if i < len(nums1) {
        nums = append(nums, nums1[i:]...)
    } else if j < len(nums2) {
        nums = append(nums, nums2[j:]...)
    }
    return float64(nums[(len(nums)-1)/2] + nums[len(nums)/2])/2
}

Binary Search

A common solution for get kth element from two array:

  1. get median elements k/2 from each array
  2. if a > b, get (k - k/2)th element from a, b[k/2:]

generalized get kth element from 3 array is the same.

1
2
3
4
4            2         1
[1,3,4,5] -> [4,5]   ->[4,5]
[2]       -> [2]     ->[]
[6,7,8]   -> [6,7,8] ->[6,7,8]
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
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    m, n := len(nums1), len(nums2)
    l := (m + n + 1)/2
    r := (m + n + 2)/2
    return float64(getKth(nums1, nums2, l) + getKth(nums1, nums2, r))/2
}

func getKth(a, b []int, k int) int {
    // fmt.Printf("%v %v %v\n", k, a, b)
    if len(a) == 0 {
        return b[k - 1]
    }
    if len(b) == 0 {
        return a[k - 1]
    }
    if k == 1 {
        return min(a[0], b[0])
    }
    
    aMid, bMid := math.MaxInt32, math.MaxInt32
    m := k/2
    if m <= len(a) {
        aMid = a[m - 1]
    }
    if m <= len(b) {
        bMid = b[m - 1]
    }
    if aMid < bMid {
        return getKth(a[m:], b, k-m)
    } else {
        return getKth(a, b[m:], k-m)
    }
}

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

# 6. Zigzag Conversion

leetcode

Simple Simulation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func convert(s string, numRows int) string {
    vs := make([][]byte, numRows)
    n := len(s)
    i := 0
    for i < n {
        for j := 0; j < numRows && i < n; j++ {
            vs[j] = append(vs[j], s[i])
            i++
        }
        for j := numRows - 2; j >= 1 && i < n; j-- {
            vs[j] = append(vs[j], s[i])
            i++
        }
    }
    results := ""
    for _, v := range vs {
        results += string(v)
    }
    return results
}

# 11. Container With Most Water

leetcode

Try to find a higher line than the the first two lines.

How could you solve with 42.

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 maxArea(height []int) int {
    water := 0
    l, r := 0, len(height) - 1
    for l < r {
        h := min(height[l], height[r])
        water = max(water, (r - l) * h)
        for height[l] <= h && l < r{
            l++
        }
        for height[r] <= h && l < r {
            r--
        }
    }
    return water
}

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

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

# 12. Integer to Roman

leetcode

1
2
3
4
5
6
7
func intToRoman(num int) string {
    M := []string{"", "M", "MM", "MMM"};
    C := []string{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    X := []string{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    I := []string{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
    return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10];
}

# 13. Roman to Integer

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func romanToInt(s string) int {
    translations := map[rune]int{
            'I': 1,
            'V': 5,
            'X': 10,
            'L': 50,
            'C': 100,
            'D': 500,
            'M': 1000,
        }
    number := 0
    s = strings.ReplaceAll(s, "IV", "IIII")
    s = strings.ReplaceAll(s, "IX", "VIIII")
    s = strings.ReplaceAll(s, "XL", "XXXX")
    s = strings.ReplaceAll(s, "XC", "LXXXX")
    s = strings.ReplaceAll(s, "CD", "CCCC")
    s = strings.ReplaceAll(s, "CM", "DCCCC")
    for _, char := range s {
            number += translations[char]
    }
    return number    
}

# 14. Longest Common Prefix

leetcode

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 longestCommonPrefix(strs []string) string {
    if len(strs) == 0 {
        return ""
    }
    if len(strs) == 1 {
        return strs[0]
    }
    res := ""
    i := 0
    for i < len(strs[0]) {
        c := strs[0][i];
        for j := 1; j < len(strs); j++ {
            if i == len(strs[j]) {
                return res
            }
            if strs[j][i] != c {
                return res
            }
        }
        res += string(c)
        i++
    }
    return res
}

# 551. Student Attendance Record I

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func checkRecord(s string) bool {
    absent, late := 0, 0
    var lastLate byte = 'P'
    for i := range s {
        switch s[i] {
        case 'P':
        case 'A': 
            absent++
        case 'L': 
            if lastLate == 'L' {
                late++
            } else {
                late = 0
            }
            if late == 2 {
                return false
            }
        }
        lastLate = s[i]
    }
    return absent < 2
}

# 15. 3Sum

leetcode

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
func threeSum(nums []int) [][]int {
    res := [][]int{}
    sort.Ints(nums)
    
    for i := 0; i < len(nums)-2; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        l, r := i+1, len(nums)-1
        for l < r {
            s := nums[i] + nums[l] + nums[r]
            if s < 0 {
                l++ 
            } else if s > 0 {
                r--
            } else {
                res = append(res, []int{nums[i], nums[l], nums[r]})
                for l < r && nums[l] == nums[l+1] {
                    l++
                }
                for l < r && nums[r] == nums[r-1] {
                    r--
                }
                l++
                r--
            }
        }
    }
    return res    
}

# 16. 3Sum Closest

leetcode

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 threeSumClosest(nums []int, target int) int {
    if len(nums) < 3 {
        return 0
    }
    sort.Ints(nums)
    closest := math.MaxInt32
    absClosest := math.MaxInt32
    
    for i := 0; i < len(nums)-2; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        l, r := i+1, len(nums)-1
        for l < r {
            s := nums[i] + nums[l] + nums[r]
            // fmt.Printf("%v %v\n", abs(target - s), s)
            if abs(target - s) < absClosest {
                absClosest = abs(target - s)
                closest = s
            }
            if(s > target) {
                r--
            } else {
                l++
            }
        }
    }
    return closest 
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

# 17. Letter Combinations of a Phone Number

leetcode

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
func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }
    d := [][]string{
        []string{"a", "b", "c"},
        []string{"d", "e", "f"},
        []string{"g", "h", "i"},
        []string{"j", "k", "l"},
        []string{"m", "n", "o"},
        []string{"p", "q", "r", "s"},
        []string{"t", "u", "v"},
        []string{"w", "x", "y", "z"},
    }
    results := []string{""}
    for _, digit := range digits {
        newResults := []string{}
        for _, result := range results {
            for _, char := range d[digit - '2'] {
                newResults = append(newResults, result + char)
            }
        }
        results = newResults
    }
    return results
}

# 401. Binary Watch

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func readBinaryWatch(turnedOn int) []string {
    times := []string{}
    for h := 0; h < 12; h++ {
        for m := 0; m < 60; m++ {
            if (bitCount(h * 64 + m) == turnedOn) {
                times = append(times, fmt.Sprintf("%d:%02d", h, m))
            }
        }
    }
    return times
}
    
func bitCount(n int) int {
   count := 0
   for n !=0{
      count += n &1
      n >>= 1
   }
   return count
}

# 18. 4Sum

leetcode

TC O(N^3)
SC O(1)

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 fourSum(nums []int, target int) [][]int {
    if len(nums) < 4 {
        return [][]int{}
    }
    sort.Ints(nums)
    res := [][]int{}
    
    for i := 0; i < len(nums)-2; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        for j := i+1; j < len(nums)-2; j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }
            l, r := j+1, len(nums)-1
            for l < r {
                s := nums[i] + nums[j] + nums[l] + nums[r]
                if(s > target) {
                    r--
                } else if s < target {
                    l++
                } else {
                    res = append(res, []int{nums[i], nums[j], nums[l], nums[r]})
                    for l < r && nums[l] == nums[l+1] {
                        l++
                    }
                    for l < r && nums[r] == nums[r-1] {
                        r--
                    }
                    l++
                    r--
                }
            }
        }
    }
    return res    
}

# 454. 4Sum II

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
    count := 0
    mp := map[int]int{}
    
    for _, n1 := range nums1 {
        for _, n2 := range nums2 {
            mp[n1+n2]++
        }
    }
    for _, n3 := range nums3 {
        for _, n4 := range nums4 {
            if mp[0-n3-n4] > 0 {
                count += mp[0-n3-n4]
            }
        }
    }

    return count
}

# 560. Subarray Sum Equals K

leetcode

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 subarraySum(nums []int, k int) int {
    mp := map[int]int{}
    sum, ans := 0, 0
    mp[sum] = 1
    for _, n := range nums {
        sum += n
        find := sum - k
        if v, exists := mp[find]; exists {
            ans += v
        }
        mp[sum]++
    }
    return ans 
}

// [1, 1, 1]
// mp[0] = 1
// sum = 0
// iter 1
// sum = 1
// find = -1
// mp[1] = 1
// iter 2
// sum = 2
// find = 0
// mp[2] = 1
// ans += 1 = 1
// iter 3
// sum = 3
// find = 1
// ans += 1 = 2

# 523. Continuous Subarray Sum

leetcode

(a+(n*x))%x is same as (a%x)

For e.g. in case of the array [23,2,6,4,7] the running sum is [23,25,31,35,42] and the remainders are [5,1,1,5,0]. We got remainder 5 at index 0 and at index 3. That means, in between these two indexes we must have added a number which is multiple of the k. Hope this clarifies your doubt 😃

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func checkSubarraySum(nums []int, k int) bool {
    m := map[int]int{0:-1}
    s := 0
    for i := 0; i < len(nums); i++ {
        s += nums[i]
        if k != 0 {
            s %= k
        }
        if prev, exists := m[s]; exists {
            if i - prev > 1 {
                return true
            }
        } else {
            m[s] = i
        }
    }
    return false
}

// (a + n*x)%x = a % x

# 88. Merge Sorted Array

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func merge(nums1 []int, m int, nums2 []int, n int)  {
    i, j, k := m - 1, n - 1, m + n - 1
    for i >= 0 && j >= 0 {
         if nums1[i] < nums2[j] {
             nums1[k] = nums2[j]
             k--
             j--
         } else {
             nums1[k] = nums1[i]
             k--
             i--
         }
     }
     for j >= 0 {
         nums1[k] = nums2[j]
         k--
         j--
     }
}

# 977. Squares of a Sorted Array

leetcode

1
2
3
4
5
6
7
func sortedSquares(nums []int) []int {
    for i := range nums {
        nums[i] = nums[i] * nums[i]
    }
    sort.Ints(nums)
    return nums
}

# 26. Remove Duplicates from Sorted Array

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    count := 1
    l := 1
    for i := 1; i < len(nums); i++ {
        if nums[i] == nums[i - 1] {
            continue
        }
        nums[l] = nums[i]
        l++
        count++
    }
    return count
}

# 80. Remove Duplicates from Sorted Array II

leetcode

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)
    }
    l := 2
    lastEqual := math.MaxInt32
    if nums[0] == nums[1] {
        lastEqual = nums[0]
    }
    for i := 2; i < len(nums); i++ {
        if nums[i] == nums[i - 1] {
            if nums[i] == lastEqual {
                continue
            } else {
                lastEqual = nums[i]
            }
        }
        nums[l] = nums[i]
        l++
    }
    return l
}

#

# 27. Remove Element

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func removeElement(nums []int, val int) int {
    if len(nums) == 0 {
        return 0
    }
    l := 0
    for i := 0; i < len(nums); i++ {
        if nums[i] == val {
            continue
        }
        nums[l] = nums[i]
        l++
    }
    return l
}

# 83. Remove Duplicates from Sorted List

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
  if head == nil {
    return nil
  }
  dummyHead := head

  for head.Next != nil {
    if head.Val == head.Next.Val {
      head.Next = head.Next.Next
      continue
    }
    head = head.Next
  }
  return dummyHead    
}

# 1023. Camelcase Matching

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func camelMatch(queries []string, pattern string) []bool {
    res := []bool{}
    for i := range queries {
        res = append(res, match(queries[i], pattern))
    }
    return res
}

func match(query string, pattern string) bool {
    j := 0
    for i := 0; i < len(query); i++ {
        if j < len(pattern) && query[i] == pattern[j] {
            j++
        } else if query[i] >= 'A' && query[i] <= 'Z' {
            return false
        }
    }

    return j == len(pattern)
}

# 66. Plus One

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func plusOne(digits []int) []int {
    if len(digits) == 0 {
        return []int{1}
    }
    c := 1
    for i := len(digits) - 1; i >= 0; i-- {
        digits[i] += c
        c = digits[i] / 10
        digits[i] %= 10
    }
    if c == 1 {
        digits = append([]int{1}, digits...)
    }
    return digits
}

# 283. Move Zeroes

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func moveZeroes(nums []int)  {
    slow, fast := 0, 0
    for fast < len(nums) {
        if nums[fast] != 0 {
            nums[slow] = nums[fast]
            slow++
        }
        fast++
    }
    for slow < len(nums) {
        nums[slow] = 0
        slow++
    }
}

Share 

 Previous post: Code - String Next post: Code - Dynamic Programming 

© 2022 Kleon

Theme Typography by Makito

Proudly published with Hexo