leetcode 389~399 solution

本次题解包括:

389 Find the Difference
390 Elimination Game
391 Perfect Rectangle
392 Is Subsequence
393 UTF-8 Validation
394 Decode String
395 Longest Substring with At Least K Repeating Characters
396 Rotate Function
397 Integer Replacement
398 Random Pick Index
399 Evaluate Division

Find the Difference

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:
1
2
3
4
5
6
7
8
9
Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.

传送门：leetcode Find the Difference

题意：给定只包含小写字母的两个字符串s和t，t是将s随机打乱并添加一个字母x组成。字母x

思路：

直接计数看看不相等的即可。当然python可以 one line

class Solution(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        return list((collections.Counter(t) - collections.Counter(s)).keys())[0]

390. Elimination Game

There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.

Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n.

Example:
1
2
3
4
5
6
7
8
9
Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

Output:
6

传送门：leetcode Elimination Game

题意：给定一个数n，要求每次轮流从左到右、从右到左删除剩下的数（间隔一个删除一个），求最后剩下的数

思路：用链表模拟的话O(nlogn)，但是可以直接计算出每次开头和结尾的地方，复杂度O(logn)

注意到每次删除上一轮之后，可以看成是下一次的步长step *= 2（初始为2，所以删除1，3，5，7....）

记录左右两个端点left和right，

若是从左到右，发现 left + (right - left) // step * step == right，则需要更新右端点。
若从右到左，right - (right - left) // step * step == left 则更新左端点。
上面的//是整除的意思

Python

class Solution(object):
    def lastRemaining(self, n):
        """
        :type n: int
        :rtype: int
        """
        left, right = 1, n
        remain = n
        step = 2
        left_to_right = True
        while remain != 1:
            if left_to_right:
                if left + (right - left) // step * step == right:
                    right -= (step >> 1)
                left += (step >> 1)
            else:
                if right - (right - left) // step * step == left:
                    left += (step >> 1)
                right -= (step >> 1)
            remain >>= 1
            step <<= 1
            left_to_right = not left_to_right
        return right if left_to_right else left

391. Perfect Rectangle

Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Example 1:
1
2
3
4
5
6
7
8
9
rectangles = [
[1,1,3,3],
[3,1,4,2],
[3,2,4,4],
[1,3,2,4],
[2,3,3,4]
]

Return true. All 5 rectangles together form an exact cover of a rectangular region.
Example 2:
1
2
3
4
5
6
7
8
rectangles = [
>[1,1,2,3],
[1,3,2,4],
[3,1,4,2],
[3,2,4,4]
]

Return false. Because there is a gap between the two rectangular regions.
Example 3:
1
2
3
4
5
6
7
8
rectangles = [
>[1,1,3,3],
[3,1,4,2],
[1,3,2,4],
[3,2,4,4]
]

Return false. Because there is a gap in the top center.
Example 4:
1
2
3
4
5
6
7
8
9
rectangles = [
>[1,1,3,3],
[3,1,4,2],
[1,3,2,4],
[2,2,4,4]
]

Return false. Because two of the rectangles overlap with each other.

传送门：leetcode Perfect Rectangle

题意：给定一些矩形，求这些矩形是否能恰好组成一个矩形面积。

思路：

合法的矩形区域有什么条件呢？

参考 https://discuss.leetcode.com/topic/55923/o-n-solution-by-counting-corners-with-detailed-explaination

上图中蓝色的点只能出现1次
绿色的点有2个矩形的某个顶点一致
红色的有4个矩形某个顶点一致

首先，遍历所有的矩形，对其四个端点进行编号（左下1，右下2，右上4，左上8，编号为1，2，4，8是为了方便位运算）。然后对于每个点（比如左上角），如果在之前的矩形中，同样也是作为左上角出现，那么说明重复了，返回False。具体的操作是用位运算(看下面的check函数)

最后判断蓝色的点是否为4个，还有总面积是否相等。

Python

class Solution(object):
    def isRectangleCover(self, rectangles):
        """
        :type rectangles: List[List[int]]
        :rtype: bool
        """
        m = collections.defaultdict(int)
        min_x = min_y = 0x7fffffff
        max_x = max_y = 0
        area = 0
        for rec in rectangles:
            min_x = min(min_x, rec[0])
            min_y = min(min_y, rec[1])
            max_x = max(max_x, rec[2])
            max_y = max(max_y, rec[3])
            area += (rec[3] - rec[1]) * (rec[2] - rec[0])
            if self.check(m, str(rec[0]) + ',' + str(rec[1]), 1): return False
            if self.check(m, str(rec[2]) + ',' + str(rec[1]), 2): return False
            if self.check(m, str(rec[2]) + ',' + str(rec[3]), 4): return False
            if self.check(m, str(rec[0]) + ',' + str(rec[3]), 8): return False
        cnt = 0
        for value in m.values():
            if value == 1 or value == 2 or value == 4 or value == 8: cnt += 1
        return cnt == 4 and area == (max_y - min_y) * (max_x - min_x)

    def check(self, m, key, mask):
        if m[key] & mask: return True
        m[key] = mask
        return False

下面的这种方法从上面的改进，由于绿色出现2次，红色4次，那么用一个Hash记录即可，若当前点不存在，添加，存在则删除。最后剩下的只可能是4个蓝色的点，并且总面积要相等。

Python

class Solution(object):
    def isRectangleCover(self, rectangles):
        """
        :type rectangles: List[List[int]]
        :rtype: bool
        """
        m = set()
        min_x = min_y = 0x7fffffff
        max_x = max_y = 0
        area = 0
        for rec in rectangles:
            min_x = min(min_x, rec[0])
            min_y = min(min_y, rec[1])
            max_x = max(max_x, rec[2])
            max_y = max(max_y, rec[3])
            area += (rec[3] - rec[1]) * (rec[2] - rec[0])
            a = str(rec[0]) + ',' + str(rec[1])
            b = str(rec[2]) + ',' + str(rec[1])
            c = str(rec[2]) + ',' + str(rec[3])
            d = str(rec[0]) + ',' + str(rec[3])
            for x in (a, b, c, d):
                if x in m:
                    m.remove(x)
                else:
                    m.add(x)
        a = str(min_x) + ',' + str(min_y)
        b = str(min_x) + ',' + str(max_y)
        c = str(max_x) + ',' + str(min_y)
        d = str(max_x) + ',' + str(max_y)
        for x in (a, b, c, d):
            if x not in m:
                return False
        return len(m) == 4 and area == (max_y - min_y) * (max_x - min_x)

392. Is Subsequence

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).

Example 1: s = "abc", t = "ahbgdc"

Return true.

Example 2: s = "axc", t = "ahbgdc"

Return false.

Follow up: If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

传送门：leetcode Is Subsequence

题意：给定字符串s和很长的字符串t，判断s是否是t的子串。比如ace是abcde子串，而aec不是。

思路：双指针，一个指向s一个指向t，当s[i] == t[j]则继续判断s的下一个字符和j之后的是否匹配。这样的正确性在于as是b的子串，它的相对顺序是不变的。

C++

class Solution {
public:
	bool isSubsequence(string s, string t) {
		if (s.size() > t.size()) return false;
		int i = 0, j = 0, n = s.size(),m = t.size();
		for (; i < n && j < m;j++) {
			if (s[i] == t[j])
				i++;
		}
		return i == n;
	}
};

Java

class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s.length() > t.length()  s.length() == t.length() && !s.equals(t)) return false;
        int i = 0, j = 0;
        int n = s.length(), m = t.length();
        for (; i < n && j < m; j++) {
            if (s.charAt(i) == t.charAt(j))
                i++;
        }
        return i == n;
    }
}

Python

class Solution(object):
    def isSubsequence(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if len(s) > len(t): return False
        i = j = 0
        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1
            j += 1
        return i == len(s)

393. UTF-8 Validation

A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

For 1-byte character, the first bit is a 0, followed by its unicode code.

For n-bytes character, the first n-bits are all one's, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.

This is how the UTF-8 encoding would work:
1
2
3
4
5
6
7
Char. number range          UTF-8 octet sequence
     (hexadecimal)                  (binary)
  --------------------+---------------------------------------------
  0000 0000-0000 007F  0xxxxxxx
  0000 0080-0000 07FF  110xxxxx 10xxxxxx
  0000 0800-0000 FFFF  1110xxxx 10xxxxxx 10xxxxxx
  0001 0000-0010 FFFF  11110xxx 10xxxxxx 10xxxxxx 10xxxxxx 
Given an array of integers representing the data, return whether it is a valid utf-8 encoding.

Note: The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.

Example 1:
1
2
3
4
5
6
data = [197, 130, 1], which represents the octet sequence: 11000101 10000010 00000001.

Return true.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.
Example 2:
1
2
3
4
5
6
7
8
data = [235, 140, 4], which represented the octet sequence: 11101011 10001100 00000100.

Return false.
The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character.
The next byte is a continuation byte which starts with 10 and that's correct.
But the second continuation byte does not start with 10, so it is invalid.

传送门：leetcode UTF-8 Validation

题意：给定一个数组，数组中每个数字为UTF8的4个byte的编码。判断该数组是否是合法的UTF-8序列。合法的序列如下表。

Char. number range          UTF-8 octet sequence
     (hexadecimal)                  (binary)
  --------------------+---------------------------------------------
  0000 0000-0000 007F  0xxxxxxx
  0000 0080-0000 07FF  110xxxxx 10xxxxxx
  0000 0800-0000 FFFF  1110xxxx 10xxxxxx 10xxxxxx
  0001 0000-0010 FFFF  11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

比如以1110开头的，后面需要有2个10开头的数字。

思路：直接扫描判断需要有几个10开头的数字即可，然后看看是否足够。

Python

class Solution(object):
    def validUtf8(self, data):
        """
        :type data: List[int]
        :rtype: bool
        """
        n = len(data)
        i = 0

        def check(s, k, n):
            if s + k > n: return False
            for i in range(s + 1, s + k):
                if (data[i] >> 6) != 0b10: return False
            return True

        while i < n:
            if (data[i] >> 3) == 0b11110:
                step = 4
            elif (data[i] >> 4) == 0b1110:
                step = 3
            elif (data[i] >> 5) == 0b110:
                step = 2
            elif (data[i] >> 7) == 0b0:
                step = 1
            else: return False
            if not check(i, step, n): return False
            i += step
        return True

394. Decode String

Given an encoded string, return it's decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won't be input like 3a or 2[4].

Examples:
1
2
3
s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

传送门：leetcode Decode String

题意：给定一个缩略表示法的字符串，要求将其展开。比如s = "3[a]表示有3个a 应该展开为aaa。题目保证输入串合法，无额外的空格。

思路：用栈，碰到数字就算一下，碰到字母就放进当前的字符串，碰到[则压入栈，碰到]则从栈顶弹出并更新当前字符串。

Python

class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        q = []
        cur = ''
        repeat = 0
        for c in s:
            if c == '[':
                q.append([repeat, cur])
                repeat = 0
                cur = ''
            elif c == ']':
                t = q.pop()
                cur = t[1] + cur * t[0]
                repeat = 0
            elif c.isdigit():
                repeat = repeat * 10 + int(c)
            else:
                cur += c
        return cur

395. Longest Substring with At Least K Repeating Characters

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:
1
2
3
4
5
6
7
Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.
Example 2:
1
2
3
4
5
6
7
Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

传送门：leetcode Longest Substring with At Least K Repeating Characters

题意：给定一个字符串s和k，求字符串最长的子串T，在T中的所有字符至少出现k次。

思路:

枚举起点和终点，对于满足条件的进行计算。(貌似还可以分治？过阵子看看)

Python

class Solution(object):
    def longestSubstring(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        max_len =i= 0
        n = len(s)
        while i + k <= n:
            cnt = [0] * 26
            max_last = i
            for j in range(i, n):
                _id = ord(s[j]) - 97
                cnt[_id] += 1
                flag = True
                for cur_cnt in cnt:
                    if cur_cnt != 0 and cur_cnt < k:
                        flag = False
                        break
                if flag:
                    max_len = max(max_len, j - i + 1)
                    max_last = j
            i = max_last + 1
        return max_len

但是由于是小写字母，所以可以用位运算来快速的判断是否符合条件。（上面的是每次扫整个hash表）

Python

class Solution(object):
    def longestSubstring(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        max_len = i = 0
        n = len(s)
        while i + k <= n:
            max_last = i
            cnt = [0] * 26
            mask = 0
            for j in range(i, n):
                _id = ord(s[j]) - 97
                cnt[_id] += 1
                if cnt[_id] < k: mask = (1 << _id)
                else: mask &= ~(1 << _id)
                if mask == 0:
                    max_len = max(max_len, j - i + 1)
                    max_last = j
            i = max_last + 1
        return max_len

C++

class Solution {
public:
    int longestSubstring(string s, int k) {
       int max_len = 0;
       for (int first = 0; first+k <= s.size();) {
           int count[26] = {0};
           int mask = 0;
           int max_last = first;
           for (int last = first; last < s.size(); ++last) {
               int i = s[last] - 'a';
               count[i]++;
               if (count[i]<k) mask = (1 << i);
               else   mask &= (~(1 << i));
               
               if (mask == 0) {
                   max_len = max(max_len, last-first+1);
                   max_last = last;
               }
           }
           first = max_last + 1;
       }
       return max_len;
    }
};

396. Rotate Function

Given an array of integers A and let n to be its length.

Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a "rotation function" F on A as follow:

F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].

Calculate the maximum value of F(0), F(1), ..., F(n-1).

Note: n is guaranteed to be less than 105.

Example:
1
2
3
4
5
6
7
8
A = [4, 3, 2, 6]

F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26

So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

传送门：leetcode Rotate Function

题意：给定数组A, 将A进行循环右移，每次分别计算 F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].（B为循环右移K次的值），求max(F(k))

思路：先求出和以及F(0)。然后每次循环右移的时候，显然是上一次的结果+s - n*A[i]（这个已经到第0个位置，清除掉）

Python

class Solution(object):   
    def maxRotateFunction(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        max_f = s = 0
        for i, x in enumerate(A):
            max_f += i * x
            s += x

        n = len(A)
        last = max_f
        for i in range(n - 1, -1, -1):
            last = last + s - n * A[i]
            max_f = max(max_f,last)
        return max_f

397. Integer Replacement

Given a positive integer n and you can do operations as follow:

If n is even, replace n with _n_/2.

If n is odd, you can replace n with either _n_ + 1 or _n_ - 1.

What is the minimum number of replacements needed for n to become 1?

Example 1:
1
2
3
4
5
6
7
8
Input:
8

Output:
3

Explanation:
8 -> 4 -> 2 -> 1
Example 2:
1
2
3
4
5
6
7
8
9
10
Input:
7

Output:
4

Explanation:
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1

传送门：leetcode Integer Replacement

题意：给定一个数n，若n为奇数可以加一或者减一，若n为偶数，则/2，求把它变为1至少需要几步？

思路：直接递归暴力求值。

Python

class Solution(object):
    def integerReplacement(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1: return 0
        if n & 1:
            return min(self.integerReplacement(n + 1), self.integerReplacement(n - 1)) + 1
        else:
            return self.integerReplacement(n >> 1) + 1

要让其有最少的步数，就要尽量在n为奇数的时候减少1的个数。

例如15，二进制为1111

1111->10000->1000->100->10->1
1111->1110->111->110->11->10->1

如果一个数以0b11结尾，那么，+1显然是更好的选择（因为加一会至少消掉2个1），否则可以-1。当然，3是例外。

Python

class Solution(object):
    def integerReplacement(self, n):
        """
        :type n: int
        :rtype: int
        """
        cnt = 0
        while n != 1:
            cnt += 1
            if n & 1:
                if (n + 1) & 0b11 == 0 and n != 3:  # (n+1) %4 ==0
                    n += 1
                else:
                    n -= 1
            else:
                n >>= 1
        return cnt

398. Random Pick Index

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note: The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:
1
2
3
4
5
6
7
8
int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

传送门：leetcode Random Pick Index

题意：给定一个数组，每次给定一个数x，要求随机返回数组中x的下标（等概率）

思路：用hash + list MLE了。那就类似于之前的 382. Linked List Random Node。

扫描数组，若当前数字等于x，则有 1/cnt的概率取代它（cnt为当前出现了多少次x）

Python

class Solution(object):
    def __init__(self, nums):
        """

        :type nums: List[int]
        :type numsSize: int
        """
        self.nums = nums

    def pick(self, target):
        """
        :type target: int
        :rtype: int
        """
        cnt = ans = -1
        for i, x in enumerate(self.nums):
            if x == target:
                cnt += 1
                if random.randint(0, cnt) == 0:
                    ans = i
        return ans

399. Evaluate Division

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example: Given a / b = 2.0, b / c = 3.0. queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? . return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , whereequations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.

According to the example above:
1
2
3
equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

传送门：leetcode Evaluate Division

题意：给定一些表达式和它对应的值，然后要求求解一些表达式的值，如果不存在则返回-1.

思路：

用图的思想来做。对于x/y = v，建立(x,y,v)和(y,x,1/v)两条边，表示x->y值为v，y->x值为1/v，（v!=0)

对于求解a/b，若有解，我们只需要能找到这样的路径，从a出发，经过若干个点之后，到达b。则它们路途中的值相称就是对应的解。

比如有边(a,c) (c,d) (d,b) 表示a/c ，c/d， d/b，相乘即可。

于是建立好图之后，进行DFS，并沿路求积。

Python

class Solution(object):
    def calcEquation(self, equations, values, queries):
        """
        :type equations: List[List[str]]
        :type values: List[float]
        :type queries: List[List[str]]
        :rtype: List[float]
        """
        edges = collections.defaultdict(list)
        _id = 0
        for i, (x, y) in enumerate(equations):
            edges[x].append((_id, y, values[i]))
            _id += 1
            if values[i] != 0:
                edges[y].append((_id, x, 1.0 / values[i]))
                _id += 1

        ans = []
        vis = [False] * (_id + 1)
        for x, y in queries:
            if x not in edges or y not in edges:
                ans.append(-1.0)
            elif x == y:
                ans.append(1.0)
            else:
                t = self.dfs(1, x, y, edges, vis)
                ans.append(t if t else -1.0)
        return ans

    def dfs(self, val, _from, _to, edges, vis):
        for _id, y, c_val in edges[_from]:
            if vis[_id]: continue
            if y == _to: return val * c_val
            vis[_id] = True
            t = self.dfs(val * c_val, y, _to, edges, vis)
            vis[_id] = False
            if t:
                return t
        return None

这是leetcode 389~399的题解，更多题解可以查看：https://www.hrwhisper.me/leetcode-algorithm-solution/