Huahua’s Tech Road

花花酱 LeetCode Ultimate DP Study Plan Day 7

By zxi on December 5, 2021

1014. Best Sightseeing Pair

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n)

class Solution:

def maxScoreSightseeingPair(self, values: List[int]) -> int:

# score = (values[i] + i) + (values[j] - j)

@cache

def dp(j: int) -> Tuple[int, int]:

"""Returns:

1) Max score of values[0..j]

2) Largest values[i] + i (i <= j)."""

if j < 0: return 0, 0

s, v = dp(j - 1)

return max(s, v + values[j] - j), max(v, values[j] + j)

return dp(len(values) - 1)[0]

121. Best Time to Buy and Sell Stock

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n)

class Solution:

def maxProfit(self, prices: List[int]) -> int:

@cache

def dp(i: int) -> Tuple[int, int]:

"""Returns:

1) max profit of prices[0:i].

2) min price of prices[0:i]."""

if i < 0: return 0, 10**9

max_profit, min_price = dp(i - 1)

return max(max_profit, prices[i] - min_price), min(min_price, prices[i])

return dp(len(prices) - 1)[0]

122. Best Time to Buy and Sell Stock II

Python3

# Author: Huahua

# Time complexity: O(n)

# Space complexity: O(n)

class Solution:

def maxProfit(self, prices: List[int]) -> int:

@cache

def dp(i: int) -> Tuple[int, int]:

"""Returns:

1) Max profit after i-th day. Holding no stocks. Can buy.

2) Max balance after i-th day. Holding a stock. Can sell.

"""

if i < 0: return 0, -10**9

profit, balance = dp(i - 1)

return (max(profit, balance + prices[i]), # do nothing, sell

max(balance, profit - prices[i])) # do nothing, buy

return dp(len(prices) - 1)[0]

花花酱 LeetCode 219. Contains Duplicate II

By zxi on December 5, 2021

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

Constraints:

1 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
0 <= k <= 10⁵

Solution: Sliding Window + Hashtable

Hashtable to store the last index of a number.

Remove the number if it’s k steps behind the current position.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

bool containsNearbyDuplicate(vector<int>& nums, int k) {

unordered_map<int, int> m; // num -> last index

for (int i = 0; i < nums.size(); ++i) {

if (i > k && m[nums[i - k - 1]] < i - k + 1)

m.erase(nums[i - k - 1]);

if (m.count(nums[i])) return true;

m[nums[i]] = i;

}

return false;

}

};

花花酱 LeetCode 215. Kth Largest Element in an Array

By zxi on December 5, 2021

Given an integer array nums and an integer k, return the k^th largest element in the array.

Note that it is the k^th largest element in the sorted order, not the k^th distinct element.

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

Constraints:

1 <= k <= nums.length <= 10⁴
-10⁴ <= nums[i] <= 10⁴

Solution: Quick selection

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int findKthLargest(vector<int>& nums, int k) {

nth_element(nums.begin(), nums.begin() + k - 1, nums.end(), std::greater<int>());

return nums[k - 1];

}

};

花花酱 LeetCode 211. Design Add and Search Words Data Structure

By zxi on December 5, 2021

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

WordDictionary() Initializes the object.
void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

Example:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]
Explanation 
WordDictionary wordDictionary = new WordDictionary(); 
wordDictionary.addWord("bad"); 
wordDictionary.addWord("dad"); 
wordDictionary.addWord("mad"); 
wordDictionary.search("pad"); // return False 
wordDictionary.search("bad"); // return True 
wordDictionary.search(".ad"); // return True 
wordDictionary.search("b.."); // return True

Constraints:

1 <= word.length <= 500
word in addWord consists lower-case English letters.
word in search consist of '.' or lower-case English letters.
At most 50000 calls will be made to addWord and search.

Solution: Hashtables

The first hashtable stores all the words, if there is no dot in the search pattern. Do a full match.

There are also per length hashtable to store words of length k. And do a brute force match.

Time complexity: Init: O(n*l)
search: best: O(l) worst: O(n*l)

C++

// Author: Huahua

class WordDictionary {

public:

// Adds a word into the data structure.

void addWord(string word) {

words.insert(word);

ws[word.length()].insert(word);

}

// Returns if the word is in the data structure. A word could

// contain the dot character '.' to represent any one letter.

bool search(string word) {

if (word.find(".") == string::npos)

return words.count(word);

for (const string& w : ws[word.length()])

if (match(word, w)) return true;

return false;

}

bool match(const string& p, const string& w) {

for (int i = 0; i < p.length(); ++i) {

if (p[i] == '.') continue;

if (p[i] != w[i]) return false;

}

return true;

}

private:

unordered_set<string> words;

unordered_map<int, unordered_set<string>> ws;

};

花花酱 LeetCode 205. Isomorphic Strings

By zxi on December 5, 2021

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.

Example 1:

Input: s = "egg", t = "add"
Output: true

Example 2:

Input: s = "foo", t = "bar"
Output: false

Example 3:

Input: s = "paper", t = "title"
Output: true

Constraints:

1 <= s.length <= 5 * 10⁴
t.length == s.length
s and t consist of any valid ascii character.

Solution: Counting

The # of distinct pairs e.g. (s[i], t[i]), should be equal to the # of distinct chars in s and t.
ex1:
set of pairs: {(e, a), (g,d)}
set of s: {e, g}
set of t: {a, d}
For s, we can replace e with a, and replace g with d.
ex2:
set of pairs: {(f, b), (o, a), (o, r)}
set of s: {f, o}
set of t: {b, a, r}
o can not pair with a, r at the same time.
ex3:
set of pairs: {(p, t), (a, i), (e, l), (r, e)}
set of s: {p, a, e, r}
set of t: {t, i, l, e}

Time complexity: O(n)
Space complexity: O(256*256)

C++

// Author: Huahua

class Solution {

public:

bool isIsomorphic(string s, string t) {

const int n = s.length();

unordered_set<int> s1;

for (int i = 0; i < n; ++i)

s1.insert((s[i] << 8) | t[i]);

unordered_set<int> s2(begin(s), end(s));

unordered_set<int> s3(begin(t), end(t));

return s1.size() == s2.size() && s2.size() == s3.size();

}

};

Huahua's Tech Road

花花酱 LeetCode Ultimate DP Study Plan Day 7

1014. Best Sightseeing Pair

Python3

121. Best Time to Buy and Sell Stock

Python3

122. Best Time to Buy and Sell Stock II

Python3

花花酱 LeetCode 219. Contains Duplicate II

C++

花花酱 LeetCode 215. Kth Largest Element in an Array

Solution: Quick selection

C++

花花酱 LeetCode 211. Design Add and Search Words Data Structure

Solution: Hashtables

C++

花花酱 LeetCode 205. Isomorphic Strings

Solution: Counting

C++