LeetCode algorithm path array part 1

LeetCode algorithm

Most bogey, hope to do a series of articles to record the process of brushing algorithm.

At present, it is mainly based on LeetCode https://leetcode-cn.com/circle/article/48kq9d/ The module of this post will brush the questions.

The content is mainly the summary of the landlord in the post, as well as some personal experience, and the algorithm ideas of typical topics.

Array - 1

Traversal and statistics of arrays

Knowledge points

Traverse an array.

When traversing the array, record the maximum value in the array. When the number of maximum values is fixed, it passes through the corresponding number of auxiliary variables.

subject

T485 maximum number of consecutive 1

link

Description: given a binary array, calculate the maximum number of consecutive 1.

answer:

Traverse the array once, record the number of consecutive occurrences of 1, and compare it with the existing maximum length when it is not 1;

It should be noted that the comparison of the last bit cannot be lost.

func findMaxConsecutiveOnes(nums []int) int {
    ans := 0

    nums = append(nums, 0)
    idx, sum := 0, 0
    for idx < len(nums) {
        if nums[idx] == 1 {
            sum++
        } else {
            if ans < sum {
                ans = sum
            }
            sum = 0
        }
        idx++
    }

    return ans
}
T414 the third largest number

link

Description: returns the third largest number of non empty arrays. If it does not exist, it returns the largest number in the array.

answer:

In fact, the k-th largest number in the unordered array can be obtained with the time complexity of O(n) through Partition.

Here, the maximum value is recorded by setting three auxiliary variables, which can be traversed multiple times or single time;

There is - 1 < < 31 in the test case. It should be noted that I'm actually lazy here.

func thirdMax(nums []int) int {
    fMax, sMax, tMax := -(2 << 31), -(2 << 31), -(2 << 31)
    for _, v := range nums {
        if v > fMax {
            tMax = sMax
            sMax = fMax
            fMax = v
        }
        if v > sMax && v < fMax {
            tMax = sMax
            sMax = v
        }
        if v > tMax && v < sMax {
            tMax = v
        }
    }

    if tMax != -(2 << 31) {
        return tMax
    }

    return fMax
}

Count the elements in the array

Knowledge points

Count the number of elements:

  • If the range of elements is small and non negative, it is more elegant to record with an array;
  • Otherwise, you need to use map.

Count the leftmost and rightmost positions of array elements, use additional array or mapping records, scan from left to right as the leftmost, and scan from right to left as the rightmost;

If it is a single element, and the array sorting can use dichotomy to quickly locate.

Whether the statistical element appears or repeats:

  • Counting the number of elements directly requires additional auxiliary space;
  • Observe whether additional conditions are given and not used, such as element range, element sorting, etc;
  • If the space complexity requirements are high, the idea of inplace needs to be used. Generally, the operation of num [i] = = I is considered.

If the results of sorting are needed for redundant topics, consider simplifying the time complexity and do not use sorting.

subject

T645 collection of errors

link

Description: set S contains an integer of 1 - n. one element is missing and one element is repeated. Find them.

answer:

With the help of the original algorithm, the solution with space complexity of O(1) can be obtained by modifying the original array, such as exchanging num [i] with num [num [i]].

With the aid of bit operation, XOR is performed with the original 1 - n number to convert one occurrence three times, one occurrence one time and the other occurrence two times;

The solution with spatial complexity O(1) can also be obtained. See LeetCode 136 for details.

Here, a mark array is used as the map:

func findErrorNums(nums []int) []int {
    mark := make([]int, len(nums)+1)

    for _, v := range nums {
        mark[v]++
    }

    var rep, mis int
    for i := 1; i < len(mark); i++ {
        if mark[i] == 2 {
            rep = i
        }
        if mark[i] == 0 {
            mis = i
        }
    }

    return []int{rep, mis}
}
Degree of T697 array

link

Description: the degree of the array is the maximum value of the occurrence frequency of any element of the array. Find the shortest continuous sub array with the same degree.

answer:

Obviously, the shortest continuous subarray with the same degree is the continuous subarray in the leftmost and rightmost of that element, so we need to save the left and right indexes;

However, my code at that time was not particularly beautiful, but it generally meant this. It mainly needed to be able to clarify how to do it:

func findShortestSubArray(nums []int) int {
    type attr struct {
        hPos int
        tPos int
        times int
    }

    m := make(map[int]*attr)

    for i := 0; i < len(nums); i++ {
        if _, ok := m[nums[i]]; !ok {
            m[nums[i]] = &attr{-1, -1, 0}
        }
        if m[nums[i]].hPos == -1 {
            m[nums[i]].hPos = i
        }
        m[nums[i]].times++
    }
    for i := len(nums)-1; i >= 0; i-- {
        if m[nums[i]].tPos == -1 {
            m[nums[i]].tPos = i
        }
    }

    tMax := 0
    for _, v := range m {
        if tMax < v.times {
            tMax = v.times
        }
    }

    lMin := len(nums)
    for _, v := range m {
        if v.times == tMax && lMin > v.tPos-v.hPos+1 {
            lMin = v.tPos - v.hPos + 1
        }
    }
    
    return lMin
}
T448 find all missing numbers in the array

link

Description: an integer array with a specified value range. Some elements appear twice and some appear once. Find the number that does not appear.

Solution:

A typical topic with the idea of changing the array in situ realizes the spatial complexity O(1). If there is this requirement, the idea of in situ is generally considered;

The specific method is to make the index i store the elements with the value of i, and then see which bits are not stored with i:

func findDisappearedNumbers(nums []int) []int {
    for i := 0; i < len(nums); i++ {
        for nums[i] != i+1 && nums[i] != nums[nums[i]-1] {
            nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
        }
    }

    ans := make([]int, 0)
    for i := 0; i < len(nums); i++ {
        if nums[i] != i+1 {
            ans = append(ans, i+1)
        }
    }

    return ans
}

Tags: Go Algorithm leetcode

Posted by shak123 on Thu, 19 May 2022 20:46:21 +0300