Leetcode-Explore-Google-Interview

[xiaxuantan]

Arrays and Strings

332 Longest Substring with At Most K Distinct Characters

Given a string, find the length of the longest substring T that contains at most k distinct characters.

Example 1:

Input: s = "eceba", k = 2
Output: 3
Explanation: T is "ece" which its length is 3.

Example 2:

Input: s = "aa", k = 1
Output: 2
Explanation: T is "aa" which its length is 2.

Solution Maintain the head pointer and tail pointer for the substring. Move the tail pointer. If the new substring is not legal, keep moving the head pointer until it is legal.

Notice None

454 Max Consecutive Ones

Given a binary array, find the maximum number of consecutive 1s in this array.

Example 1:

Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
The maximum number of consecutive 1s is 3.

Solution Too easy. Just scan.

455 Max Consecutive Ones II

Given a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0.

Example 1:

Input: [1,0,1,1,0]
Output: 4
Explanation: Flip the first zero will get the the maximum number of consecutive 1s.
After flipping, the maximum number of consecutive 1s is 4.

Solution Scan. Use one variable cur to store the consecutive ones, use another variable pre to store the consecutive ones that could be concatenated to cur. If a zero is read, assign cur to pre and clear cur. Remember to deal with all cases starting with 0 or 1, and ending with 0 or 1.

Time Complexity O(N) Space Complexity O(1)

[xiaxuantan]

Arrays and Strings

214 Shortest Palindrome

Given a string s, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: "abcd"
Output: "dcbabcd"

Solutions: The problem can be represented in this way, find the longest palindrome from the beginning of the string.

s‘ = s + '#' + s[::-1] and perform the construction of KMP Partial Match Table on s'

41 First Missing Positive

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

Note: Your algorithm should run in O(n) time and uses constant extra space.

Solution The crucial point is that a list with n elements are supposed to store 1 ~ n. Elements less than 0 and elements larger than n are useless.

First Unique Character in a String

Too easy

[xiaxuantan]

Dynamic Programming

91 Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Solution

It is actually another form of Fibonacci! Just notice it is not always the case that dp[i] = dp[i-1] + dp[i - 2]