Blog | Autzoko Lang

You are given an integer array nums consisting of $ n$ elements, and an integer $ k$. Find a contiguous subarray whose length is equal to $ k$ that has the maximum average value and return this value. Any answer with a calculation error less than 10⁻⁵ will be accepted.

Example:

1
2

Input: nums = [1, 12, -5, -6, 50, 3], k = 4;
Output: 12.75000;

1
2

Input: nums = [5], k = 1;
Output: 5.00000;

Constraints:

• n = len(nums)
• 1 ≤ k ≤ n ≤ 1−⁵
• −10⁴ ≤ nums_i ≤ 10⁴

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    using LL = long long;
    double findMaxAverage(vector<int>& nums, int k) {
        LL sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        LL maxSum = sum;
        for (int i = 0, j = k; j < nums.size(); i++, j++) {
            sum = sum - nums[i] + nums[j];
            maxSum = max(maxSum, sum);
        }
        return (double)maxSum / (double)k;
    }
}

Explanation:

This problem uses the Sliding Window technique. To reduce the calculation when sliding, first we do not compute the average each time, we can only calculate the sum of the window and divide it at last when return. Since the length of the window is fixed, so each step it move we just need to subtract the left margin value and add the value next to the right margin then the new sum of the window is get. Slide it step by step and update the maxSum to find the maximum value of the array.

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i^th line are (i, 0) and (i, height_i).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of the water a container can store.

Examples:

1
2

Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7];
Output = 49;

1
2

Input: height = [1, 1];
Output = 1;

Constraints:

• n = len(height)
• 2 ≤ n ≤ 10⁵
• 0 ≤ height_i ≤ 10⁴

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    using LL = long long;
    int maxArea(vector<int>& height) {
        LL left = 0, right = height.size() - 1;
        LL maxA = 0;

        while (left < right) {
            LL currentArea = min(height[left], height[right]) * (right - left);
            maxA = max(maxA, currentArea);

            if (height[left] < height[right]) left++;
            else right--;
        }
        
        return maxA;
    }
}

Explanation:

To solve this problem the two pointers technique is adopted. The left pointer starting at the index 0 and the right pointer starts at the end of the vector. Use maxA to keep track of the maximum area found. Then calculate the current area of the container and update it to the maxA. And we need to move the two pointers inwards to find the global maximum area. The method for moving inwards the pointers is to always move the smaller one (low one) the seeking a greater value that may increase the area.

The basic pattern of a binary search problem is to find a target element in an orderly list.

The model problem is Leetcode 704

Here are two points that would make mistakes:

• The boundary conditions for the loop
• The redefinition of search interval boundaris

To the boundary conditions for the loop

1

while (left < right)

or

1

while (left <= right)

we need to know when conditions can make the left and right boundary values equal and when not.

To the value of search interval boundaris

1

right = mid;

or

1

right = mid + 1;

we need to know how to redefine the boundary values of left and right.

Loop Invariant

The loop invariant is a property (or expression) that always be true within every iteration of the loop. For the binary search problem, the loop invariant here is the search interval, aka. the value of boundaries left and right.

Here we discuss this search interval should be left-closed, right-open or left-closed, right-closed.

Left-closed Right-closed Interval

Since this is a closed interval, both the left and right boundary values of the interval should be valid (i.e., legitimate values). There for, at that time, the left pointer will point to 0, and the right pointer will point to nums.size()-1.

1

int left = 0, right = nums.size() - 1;

For the loop condition, since both the left and right boundaris can be included in a closed interval, it is reasonable for the left and right boundaries to be equal. Therefore, the condition for the while loop should be left <= right.

When updating the boundary values in this case, we should notice that the right boundary is closed, thus the new right boudary is mid − 1 when nums[mid] > target and left boundary is mid + 1 when nums[mid] < target.

Left-closed Right-open Interval

Similar to the left-closed right-closed interval, the boundary values are updated in the same way. However, in this case, since the right boundary is open, the condition of the while loop should be left < right here. And when updating boundary values, the right one should be $ mid$ rather than mid + 1 because the boundary value is included by the interval.

Given an integer array nums, move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Note that it must be done in-place without making a copy of the array.

Example:

1
2

Input: nums = [0, 1, 0, 3, 12];
Output: [1, 3, 12, 0, 0];

1
2

Input: nums = [0];
Output: [0];

Constraints:

• 1 ≤ len_nums ≤ 10⁴
• −2³¹ ≤ nums_i ≤ 2³² − 1

Solution

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int left = 0;
        for (int right = 0; right < nums.size(); right++) {
            if (nums[right] != 0) {
                swap(nums[right], nums[left]);
                left++;
            }
        }
    }
}

Explanation: The solution use two pointers to separatly point to a non-zero value and a zero value. Initialy, these two point both point to the index 0. And if the right pointer is not 0, two pointers will be moved to their next index simultaneously. When the left point meets a zero value, it will stay on it, and swap the value with the right pointer. In other words, the zeroes with move to the tail of the vector like bulbles (imagine the bulble sort algorithm).

Given an array of characters chars, compress it using following algorithm:

Begin with an empty string s. For each group of consecutive repeating characters in chars:

• If the group length is 1, append the character to s.
• Otherwise, append the charactoer followed by the group’s length.

The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.

After modifying the input array, return the new length of the array.

Example:

1
2

Input: chars = ["a","a","b","b","c","c","c"];
Output: 6, ["a","2","b","2","c","3"];

1
2

Input: chars = ["a"];
Output: 1, ["a"];

1
2

Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"];
Output: 4, ["a","b","1","2"];

Constraints:

• $ 1 l_{chars} $
• chars_i is a lower case English letter, uppercase English letter, digit, or symbol.

Solution

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

class Solution {
public:
    int compress(vector<char>& chars) {
        int ans = 0;

        for (int i = 0; i < chars.size();) {
            const char letter = chars[i];
            int count = 0;

            while (i < chars.size() && chars[i] == letter) {
                count++;
                i++;
            }

            chars[ans++] = letter;

            if (count > 1) {
                for (const char c : to_string(count)) {
                    chars[ans++] = c;
                }
            }
        }
        return ans;
    }
}

Explanation:

Using two pointers to iterate original string and trach generated new string. Here, use i to iterate whole string and count the length of each group. Once a group’s length is detected, use another pointer ans to write on the original string.

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

"aabbccc"
 ^              <-- i = 0
 ^              <-- ans = 0

"aabbccc"
  ^             <-- i++
 ^

"aabbccc"
   ^            <-- i++, n = 2, letter = a
 ^

"aabbccc"
   ^
  ^             <-- chars[ans++] = a

"a2bbccc"
   ^
   ^            <-- chars[ans++] = 2

"a2bbccc"
    ^           <-- i++, n = 1
   ^

"a2bbccc"
     ^          <-- i++, n = 2, letter = b
   ^

"a2bbccc"
     ^
    ^           <-- chars[ans++] = b

"a2b2ccc"
     ^
     ^          <-- chars[ans++] = 2

"a2b2ccc"
      ^         <-- i++
     ^

"a2b2ccc"
       ^        <-- i++, n = 3, letter = c
     ^

"a2b2ccc"
       ^
      ^         <-- chars[ans++] = c

"a2b2c3c"
       ^
       ^        <-- chars[ans++] = 3

Given an integer array nums, return true if there exists a triple of indices $\[i, j, k\]$ such that $ i j k$ and nums_i < nums_j < nums_k. If no such indices exists, return false.

Example:

1
2

Input: nums = [1, 2, 3, 4, 5];
Output: true;

1
2

Input: nums = [5, 4, 3, 2, 1];
Output: false;

1
2

Input: nums = [2, 1, 5, 0, 4, 6];
Output: true;

Constraints: - $ 1 l_{nums} ^5 $ - $ -2^{31} nums_i ^{31}-1$

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        if (nums.size() < 3) return false;

        int i = INT_MAX, j = INT_MAX;

        for (int num : nums) {
            if (num <= i) {
                i = num;
            } else if (num <= j) {
                j = num;
            } else {
                return true;
            }
        }
        return false;
    }
};

Explanation: The solution is based on keeping track of two minimum values, i and j, while iterating through the array.

• Initialize two variables, i and j, to INT_MAX.
• • If the element is less than or equal to i, update i with the element.
• • If the element if greater than i but less than or equal to j, update j with the element.
• • If the element is greater than both i and j, it means an increasing triplet is found, and the function returns true.
• If the loop completes without finding an increasing triplet, return false.

The time complexity is O(n) and the space complexity is O(1).

You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots.

Given an integer array flowerbed containing 0s and 1s, where 0 means empty and 1 means not empty, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent flowers rule and false otherwise.

Example:

1
2

Input: flowerbed = [1, 0, 0 ,0 ,1], n = 1;
Output: true;

1
2

Input: flowerbed = [1, 0, 0, 0, 1], n = 2;
Output: false;

Constraints:

• 1 ≤ len_flowerbed ≤ 2 × 10⁴
• $flowerbed_i = 1 \or 0$
• 0 ≤ nlelen_flowerbed
• There are no two adjacent flowers in flowerbed.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        for (int i = 0; i < flowerbed.size(); i++) {
            bool left = i == 0 || flowerbed[i - 1] == 0;
            bool right = i == flowerbed.size() - 1 || flowerbed[i + 1] == 0;

            if (left && right && flowerbed[i] == 0) {
                flowerbed[i] = 1;
                n--;
            }
        }

        return n <= 0;
    }
};

Explanation:

The basic idea of this solution is very simple: traverse the whole array, figure out that whether current place is legal for planting a new flower by looking left and looking right at each plot. If a plot is 0 and its left and right plots are both 0 either, it would a legal plot to plant, then we plant a new flower here by marking 1 and, accordingly, the total amount of flowers should be lessen. Also, here are two exceptional conditons, the boarder plots. So we need to judge them separatedly by looking right at the left margin and looking left at the right margin, the logic is same as other plots.

At last, we just need to simply check that whether all of the flowers have been planted, if yes return true, otherwise return false.

For two strings s and t. We say t divides s if and only $ s = t + t + … + t $ (i.e., t is concatenated with itself one or more times).

Given two strings str1 and str2, return the largest string x such that x divides boths str1 and str2.

Example:

1
2

Input: str1 = "ABABC", str2 = "ABC"
Ouput: "ABC"

1
2

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

1
2

Input: str1 = "LEET", str2 = "CODE"
Output: ""

Constraints:

• $ 1 len_{str1}, len_{str2} $
• str1 and str2 consist of English uppercase letters.

Solution

1
2
3
4
5
6
7

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        return (str1 + str2 == str2 + str1) ?
                str1.substr(0, gcd(size(str1), size(str2))) : "";
    }
};

Explanation: For two strings, if they are consisted by the same substrings (or same ingradient), their combination in opposite order should be the same. For example, is string A is ababab, string b is abab, it’s obvious that they have the same ingradient ab, so let’s combine them as $ a + b $ and $ b + a $, their results should be same. So, after we make sure that both two strings are made of the same ingradient, we can use gcd to find their greatest common division.

Proof: Assume str₁ = nX and str₂ = mX where X represents the common divisor of these two strings. Thus, the concatenated string str₁ + str₂ equals (n + m)X. We get substring of length gcd(len₁, len₂), if this length equals the size of str₂, which means the size of str₂ is divisible by str₁, any division should be equal when divised by gcd(str₁, str₂). The core is that str₁ + str₂ = str₂ + str₁.

General Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    bool check(string t, string s) {
        int lenx = (int)s.length() / (int)t.length();
        string ans = "";
        for (int i = 0; i < lenx; i++) {
            ans = ans + t;
        }
        return ans == s;
    }
public:
    string gcdOfStrings(string str1, string str2) {
        int len1 = (int)str1.length(), len2 = (int)str2.length();
        for (int i = min(len1, len2); i >= 1; i--) {
            if (len1 % i == 0 && len2 % i == 0) {
                string X = str1.substr(0, i);
                if (check(X, str1) && check(X, str2)) return X;
            }
        }
        return "";
    }
}

Given a integer n, return the number of structurally unique BST’s (binary search trees) which has exactly n nodes of unique values from 1 to n.

Example:

1
2

Input: n = 3;
Output: 5;

Constraints:

1 ≤ n ≤ 19

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class UniqueBinarySearchTrees {
public:
    int numTrees(int n) {
        int *dp = new int[n + 1];
        fill_n(dp, n + 1, 0);
        dp[0] = dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
};

Explanation:

Assume that the number of BSTs of n nodes is G(n), and f(i) denotes the number of BSTs whose root value is i, thus:

$$ G(n)=\sum_{i=1}^n f(i) $$

And when i is the root node, the number of nodes of its left subtree is i − 1, and the number of nodes of its right subtree is n − i, thus

f(i) = G(i − 1) × G(n − i)

Fusing above two equations, the Catalan Number Equation is deduced:

$$ G(n)=\sum_{i=0}^n G(i)\times G(n-1-i) $$

從京城的西直門出發，沿著曾經詹天佑修建的京張鐵路，經過張家口，便徹底離開了偌大的華北平原，進入了山與高原交錯的地界了。

大同府

大同府坐落在三晉大地的大同盆地之中，雁門関北，自古屬雲州轄，是為山外所植。大同府自古是溝通中原與北方游牧諸族的要會，北魏於此建都平城，於此開啓鮮卑漢化的歷史進程。宋代這裏也屬北宋未曾接管的燕雲十六州。與此毗鄰的代、朔、應、忻等地向來是邊境前綫所在。

大同在現今山西省的北端，往北走去便是内蒙古草原地帶，往南有太岳、呂梁、太行三山橫亙，擋住了前往中原的通路，只有幾條山中狹徑供軍民使用。

在群山懷抱之中，大同得天獨厚的地理條件是的南下的游牧民族政權都會優先選擇這裏作爲一個重要的城市，無論是鮮卑之平成，還是契丹之西京，這裏是游牧民族南下的第一步，是漢地十八省的北部前哨。所以大同府的歷史也是一個充滿軍事鐵血與戰爭血淚的歷史。