LeetCode day3

2020-04-27 5 minutes read

views 1047 words

38. Count and Say

Topic: String

The count-and-say sequence is the sequence of integers with the first five terms as following:

1. 1
2. 11
3. 21
4. 1211
5. 111221

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"

Example 2:

Input: 4
Output: "1211"

依次递推后一项以前一项为基础

比如说6是在5的基础上得到，三个一，二个二，一个一

Approach1

Brute Force:

def countAndSay(self, n: int) -> str:
    s = '1'
    for _ in range(n - 1): # range(4) <==> 0 -- 3
        count = 1
        temp = ''
        
        for i in range(len(s)):
            if i != len(s)-1 and s[i] == s[i+1]:
                count += 1
            else:
                temp = temp+str(count)
                temp = temp + str(s[i])
                count = 1
        s = temp
    return s

Approach2

def countAndSay(self, n):
    s = '1'
    for _ in range(n - 1):
        s = re.sub(r'(.)\1*', lambda m: str(len(m.group(0))) + m.group(1), s)
    return s
    
# ----------

def countAndSay(self, n):
    s = '1'
    for _ in range(n - 1):
        s = ''.join(str(len(group)) + digit
                    for group, digit in re.findall(r'((.)\2*)', s))
    return s

Approach3

Groupby

def countAndSay(self, n):
    s = '1'
    for _ in range(n - 1):
        s = ''.join(str(len(list(group))) + digit
                    for digit, group in itertools.groupby(s))
    return s

Approach4

loop

def countAndSay(n: int) -> str:
    prev_person = '1'
    for i in range(1,n):
        next_person, num, count = '', prev_person[0], 1
        for j in range(1,len(prev_person)):
            if prev_person[j] == num:
                count += 1
            else:
                next_person += str(count) + num
                num = prev_person[j]
                count = 1
        next_person += str(count) + num
        prev_person = next_person
    return prev_person

53. Maximum Subarray

Topic: Array, Divide and Conquer, Dynamic Programming

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Approach1

DP:

def maxSubArray(self, nums: List[int]) -> int:
    # nums = [-2,1,-3,4,-1,2,1,-5,4]
    temp = [nums[0]]
    for i in range(1,len(nums)):
        temp.append(max(nums[i],nums[i]+temp[i-1]))
        print(i,res)
            '''
1 [-2, 1]
2 [-2, 1, -2]
3 [-2, 1, -2, 4]
4 [-2, 1, -2, 4, 3]
5 [-2, 1, -2, 4, 3, 5]
6 [-2, 1, -2, 4, 3, 5, 6]
7 [-2, 1, -2, 4, 3, 5, 6, 1]
8 [-2, 1, -2, 4, 3, 5, 6, 1, 5]
            '''
    return max(temp)

For the dynamic programming approach, this is O(n). Let’s think about the example [2, -1, 3, -2]. In the base case, [2] is the smallest subarray possible (starting from index 0). Its maximum subarray sum is the sole element itself, 2. The next subproblem is [2, 1]. You could either have [2, -1]->(sum=1) or [-1]->(sum=-1). Since the sum for the former is greater, we store 1 as the maximum subarray sum. Just by going through this example, we’ve discovered the recurrence relation! You could either start a new subarray for a maximum sum at index i, or you could tack on the element at index i to the previous subproblem.
https://www.youtube.com/watch?v=2MmGzdiKR9Y

Approach2

Divide and Conquer

def maxSubArrayHelper(self,nums, l, r):
    if l > r:
        return -2147483647
    m = (l+r) // 2
    print(m)

    leftMax = sumNum = 0
    for i in range(m - 1, l - 1, -1):
        sumNum += nums[i]
        leftMax = max(leftMax, sumNum)

    rightMax = sumNum = 0
    for i in range(m + 1, r + 1):
        sumNum += nums[i]
        rightMax = max(rightMax, sumNum)

    leftAns = self.maxSubArrayHelper(nums, l, m - 1)
    rightAns = self.maxSubArrayHelper(nums, m + 1, r)

    return max(leftMax + nums[m] + rightMax, max(leftAns, rightAns))

def maxSubArray(self, nums):
    return self.maxSubArrayHelper(nums, 0, len(nums) - 1)

66. Plus One

Topic: Array

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

题解：简单的高精度加法，要注意[9]这种输入，要多一位

Approach1

def plusOne(self, digits: List[int]) -> List[int]:
    if len(digits) == 1 and digits[0] ==9: 
        return [1,0]
    
    for i in range(len(digits),0,-1):
        if digits[i-1] != 9:
            digits[i-1] += 1
            return digits                
        else:
            digits[i-1] = 0
    return [1]+digits

Approach2

def plusOne(self, digits: List[int]) -> List[int]:
    if len(digits) == 1 and digits[0] == 9:
        return [1, 0]

    if digits[-1] != 9:
        digits[-1] += 1
        return digits
    else:
        digits[-1] = 0
        digits[:-1] = self.plusOne(digits[:-1])
        return digits

Approach3

把数组转成数字加1再转回数组

def plusOne(digits):
    num = 0
    for i in range(len(digits)):
    	num += digits[i] * pow(10, (len(digits)-1-i))
    return [int(i) for i in str(num+1)]

Approach 4

def plusOne(digits):
    for i in range(1,len(digits)+1):
        if digits[-i] != 9:
            digits[-i] += 1
            return digits
        digits[-i] = 0
    digits.insert(0,1)
    return digits

69. Sqrt(x)

Topic: Math, Binary Search

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

Approach1

def mySqrt(self, x: int) -> int:
    tem = pow(x,0.5)
    return int(tem)

Approach2

Binary Search:

def mySqrt(self, x):
    lo, hi = 0, x
    
    while lo <= hi:
        mid = (lo + hi) // 2
        
        if mid * mid > x:
            hi = mid - 1
        elif mid * mid < x:
            lo = mid + 1
        else:
            return mid
    
    # When there is no perfect square, hi is the the value on the left of where it would have been (rounding down). If we were rounding up, we would return lo
    return hi

Approach3

Newton Method:

def sqrt(self, x):
	i=1.0;
	while(True):
		j=(i+x/i)/2.0;
		if(abs(i-j)< 0.000000000005):
			break;
		i=j;
	return int(j);