Posts tagged as “medium”

花花酱 LeetCode 5. Longest Palindromic Substring

By zxi on September 12, 2018

Problem

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

Solution: DP

Try all possible i and find the longest palindromic string whose center is i (odd case) and i / i + 1 (even case).

Time complexity: O(n^2)

Space complexity: O(1)

C++

// Author: Huahua, 16 ms, 8.7 MB

class Solution {

public:

string longestPalindrome(string s) {

const int n = s.length();

auto getLen = [&](int l, int r) {

while (l >= 0 && r < n

&& s[l] == s[r]) {

--l;

++r;

}

return r - l - 1;

};

int len = 0;

int start = 0;

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

int cur = max(getLen(i, i),

getLen(i, i + 1));

if (cur > len) {

len = cur;

start = i - (len - 1) / 2;

}

return s.substr(start, len);

}

};

Java

// Author: Huahua, 6 ms， 36.5 MB

class Solution {

public String longestPalindrome(String s) {

int len = 0;

int start = 0;

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

int cur = Math.max(getLen(s, i, i),

getLen(s, i, i + 1));

if (cur > len) {

len = cur;

start = i - (cur - 1) / 2;

}

return s.substring(start, start + len);

}

private int getLen(String s, int l, int r) {

while (l >= 0 && r < s.length()

&& s.charAt(l) == s.charAt(r)) {

--l;

++r;

}

return r - l - 1;

}

Python3

# Author: Huahua, 812 ms, 12.7MB

class Solution:

def longestPalindrome(self, s: str) -> str:

n = len(s)

def getLen(l, r):

while l >= 0 and r < n and s[l] == s[r]:

l -= 1

r += 1

return r - l - 1

start = 0

length = 0

for i in range(n):

cur = max(getLen(i, i),

getLen(i, i + 1))

if cur <= length: continue

length = cur

start = i - (cur - 1) // 2

return s[start : start + length]

花花酱 LeetCode 3. Longest Substring Without Repeating Characters

By zxi on September 11, 2018

Problem

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Solution: HashTable + Sliding Window

Using a hashtable to remember the last index of every char. And keep tracking the starting point of a valid substring.

start = max(start, last[s[i]] + 1)

ans = max(ans, i – start + 1)

Time complexity: O(n)

Space complexity: O(128)

C++

// Author: Huahua

class Solution {

public:

int lengthOfLongestSubstring(string s) {

const int n = s.length();

int ans = 0;

vector<int> idx(128, -1);

for (int i = 0, j = 0; j < n; ++j) {

i = max(i,idx[s[j]] + 1);

ans = max(ans, j - i + 1);

idx[s[j]] = j;

}

return ans;

}

};

Java

// Author: Huahua

class Solution {

public int lengthOfLongestSubstring(String s) {

int[] last = new int[128];

Arrays.fill(last, -1);

int start = 0;

int ans = 0;

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

if (last[s.charAt(i)] != -1)

start = Math.max(start, last[s.charAt(i)] + 1);

last[s.charAt(i)] = i;

ans = Math.max(ans, i - start + 1);

}

return ans;

}

Python3

# Author: Huahua

class Solution:

def lengthOfLongestSubstring(self, s):

last = [-1] * 128

ans = 0

start = 0

for i, ch in enumerate(s):

if last[ord(ch)] != -1:

start = max(start, last[ord(ch)] + 1)

ans = max(ans, i - start + 1)

last[ord(ch)] = i

return ans

花花酱 LeetCode 898. Bitwise ORs of Subarrays

By zxi on September 1, 2018

Problem

We have an array A of non-negative integers.

For every (contiguous) subarray B = [A[i], A[i+1], ..., A[j]] (with i <= j), we take the bitwise OR of all the elements in B, obtaining a result A[i] | A[i+1] | ... | A[j].

Return the number of possible results. (Results that occur more than once are only counted once in the final answer.)

Example 1:

Input: [0]
Output: 1
Explanation: 
There is only one possible result: 0.

Example 2:

Input: [1,1,2]
Output: 3
Explanation: 
The possible subarrays are [1], [1], [2], [1, 1], [1, 2], [1, 1, 2].
These yield the results 1, 1, 2, 1, 3, 3.
There are 3 unique values, so the answer is 3.

Example 3:

Input: [1,2,4]
Output: 6
Explanation: 
The possible results are 1, 2, 3, 4, 6, and 7.

Note:

1 <= A.length <= 50000
0 <= A[i] <= 10^9

Solution 1: DP (TLE)

dp[i][j] := A[i] | A[i + 1] | … | A[j]

dp[i][j] = dp[i][j – 1] | A[j]

ans = len(set(dp))

Time complexity: O(n^2)

Space complexity: O(n^2) -> O(n)

C++ SC O(n^2)

// Author: Huahua

// Running time: TLE (73/83 passed).

class Solution {

public:

int subarrayBitwiseORs(vector<int>& A) {

int n = A.size();

vector<vector<int>> dp(n, vector<int>(n));

unordered_set<int> ans(begin(A), end(A));

for (int l = 1; l <= n; ++l)

for (int i = 0; i <= n - l; ++i) {

int j = i + l - 1;

if (l == 1) {

dp[i][j] = A[i];

continue;

}

dp[i][j] = dp[i][j - 1] | A[j];

ans.insert(dp[i][j]);

}

return ans.size();

}

};

C++ SC O(n)

// Author: Huahua

// Running time: TLE (75/83 passed)

class Solution {

public:

int subarrayBitwiseORs(vector<int>& A) {

int n = A.size();

vector<int> dp(A);

unordered_set<int> ans(begin(A), end(A));

for (int l = 2; l <= n; ++l)

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

ans.insert(dp[i] |= A[i + l - 1]);

return ans.size();

}

};

Solution 2: DP opted

dp[i] := {A[i], A[i] | A[i – 1], A[i] | A[i – 1] | A[i – 2], … , A[i] | A[i – 1] | … | A[0]}, bitwise ors of all subarrays end with A[i].

|dp[i]| <= 32

Proof: all the elements (in the order of above sequence) in dp[i] are monotonically increasing by flipping 0 bits to 1 from A[i].

There are at most 32 0s in A[i]. Thus the size of the set is <= 32.

证明： dp[i] = {A[i], A[i] | A[i – 1], A[i] | A[i – 1] | A[i – 2], … , A[i] | A[i – 1] | … | A[0]}，这个序列单调递增，通过把A[i]中的0变成1。A[i]最多有32个0。所以这个集合的大小 <= 32。

e.g. 举例：Worst Case 最坏情况 A = [8, 4, 2, 1, 0] A[i] = 2^(n-i)。

A[5] = 0，dp[5] = {0, 0 | 1, 0 | 1 | 2, 0 | 1 | 2 | 4, 0 | 1 | 2 | 4 | 8} = {0, 1, 3, 7, 15}.

Time complexity: O(n*log(max(A))) < O(32n)

Space complexity: O(n*log(max(A)) < O(32n)

C++

// Author: Huahua

// Running time: 456 ms

class Solution {

public:

int subarrayBitwiseORs(vector<int>& A) {

unordered_set<int> ans;

unordered_set<int> cur;

unordered_set<int> nxt;

for (int a : A) {

nxt.clear();

nxt.insert({a});

for (int b : cur) {

nxt.insert(a | b);

}

cur.swap(nxt);

ans.insert(begin(cur), end(cur));

}

return ans.size();

}

};

Java

// Author: Huahua

// Running time: 434 ms

class Solution {

public int subarrayBitwiseORs(int[] A) {

Set<Integer> ans = new HashSet<>();

Set<Integer> cur = new HashSet<>();

for (int a : A) {

Set<Integer> nxt = new HashSet<>();

nxt.add(a);

for (int b : cur)

nxt.add(a | b);

ans.addAll(nxt);

cur = nxt;

}

return ans.size();

}

Python3

# Author: Huahua

# Running time: 812 ms

class Solution:

def subarrayBitwiseORs(self, A):

cur = set()

ans = set()

for a in A:

cur = {a | b for b in cur} | {a}

ans |= cur

return len(ans)

花花酱 LeetCode 120. Triangle

By zxi on August 27, 2018

Problem

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Solution: DP

Time complexity: O(n^2)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

// [[2] [[2]

// [3, 4]] [5, 6]

// [6, 5, 7]] [11, 10, 11]

// [4, 1, 8, 3]] [15, 11, 18, 14]]

int minimumTotal(vector<vector<int>>& t) {

int n = t.size();

// t[i][j] := minTotalOf(i,j)

// t[i][j] += min(t[i - 1][j], t[i - 1][j - 1])

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

for (int j = 0; j <= i; ++j) {

if (i == 0 && j == 0) continue;

if (j == 0) t[i][j] += t[i - 1][j];

else if (j == i) t[i][j] += t[i - 1][j - 1];

else t[i][j] += min(t[i - 1][j], t[i - 1][j - 1]);

}

return *std::min_element(begin(t.back()), end(t.back()));

}

};

花花酱 LeetCode 894. All Possible Full Binary Trees

By zxi on August 26, 2018

Problem

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

Return a list of all possible full binary trees with N nodes. Each element of the answer is the root node of one possible tree.

Each node of each tree in the answer must have node.val = 0.

You may return the final list of trees in any order.

Example 1:

Input: 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
Explanation:

Note:

1 <= N <= 20

Solution: Recursion

Key observations:

n must be odd, If n is even, no possible trees
ans is the cartesian product of trees(i) and trees(n-i-1). Ans = {Tree(0, l, r) for l, r in trees(i) X trees(N – i – 1)}.

w/o cache

C++

// Author: Huahua

// Running time: 72 ms

class Solution {

public:

vector<TreeNode*> allPossibleFBT(int N) {

if (N % 2 == 0) return {};

if (N == 1) return {new TreeNode(0)};

vector<TreeNode*> ans;

for (int i = 1; i < N; i += 2) {

for (const auto& l : allPossibleFBT(i))

for (const auto& r : allPossibleFBT(N - i - 1)) {

auto root = new TreeNode(0);

root->left = l;

root->right = r;

ans.push_back(root);

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 20 ms

class Solution {

public List<TreeNode> allPossibleFBT(int N) {

List<TreeNode> ans = new ArrayList<>();

if (N % 2 == 0) return ans;

if (N == 1) {

ans.add(new TreeNode(0));

return ans;

}

for (int i = 1; i < N; i += 2) {

for (TreeNode l : allPossibleFBT(i))

for (TreeNode r : allPossibleFBT(N - i - 1)) {

TreeNode root = new TreeNode(0);

root.left = l;

root.right = r;

ans.add(root);

}

return ans;

}

Python

"""

Author: Huahua

Running time: 396 ms

"""

class Solution:

def allPossibleFBT(self, N):

if N % 2 == 0: return []

if N == 1: return [TreeNode(0)]

ans = []

for i in range(1, N, 2):

for l in self.allPossibleFBT(i):

for r in self.allPossibleFBT(N - i - 1):

root = TreeNode(0)

root.left = l

root.right = r

ans.append(root)

return ans

w/cache

C++

// Author: Huahua

// Running time: 68 ms

static constexpr int kMaxN = 20 + 1;

static array<vector<TreeNode*>, kMaxN> m;

class Solution {

public:

vector<TreeNode*> allPossibleFBT(int N) {

return trees(N);

}

private:

vector<TreeNode*>& trees(int N) {

if (m[N].size() > 0) return m[N];

vector<TreeNode*>& ans = m[N];

if (N % 2 == 0) return ans = {};

if (N == 1) ans = {new TreeNode(0)};

for (int i = 1; i < N; i += 2) {

for (const auto& l : trees(i))

for (const auto& r : trees(N - i - 1)) {

auto root = new TreeNode(0);

root->left = l;

root->right = r;

ans.push_back(root);

}

return ans;

}

};

Python

using itertools.product w/ cache

"""

Author: Huahua

Running time: 188 ms

"""

m = [[] for _ in range(21)]

class Solution:

def allPossibleFBT(self, N):

if N % 2 == 0: return []

if N == 1: return [TreeNode(0)]

if len(m[N]) > 0: return m[N]

ans = []

for i in range(1, N, 2):

for l, r in itertools.product(self.allPossibleFBT(i),

self.allPossibleFBT(N - i - 1)):

root = TreeNode(0)

root.left = l

root.right = r

ans.append(root)

m[N] = ans

return ans

C++

// Author: Huahua

// Running time: 100 ms

class Solution {

public:

vector<TreeNode*> allPossibleFBT(int N) {

if (N % 2 == 0) return {};

vector<vector<TreeNode*>> dp(N + 1);

dp[1] = {new TreeNode(0)};

for (int i = 3; i <= N; i += 2)

for (int j = 1; j < i; j += 2) {

int k = i - j - 1;

for (const auto& l : dp[j])

for (const auto& r : dp[k]) {

auto root = new TreeNode(0);

root->left = l;

root->right = r;

dp[i].push_back(root);

}

return dp[N];

}

};

Benchmark

No-cache vs cached

C++

#include <iostream>

#include <vector>

#include <array>

#include <ctime>

#include <cstdio>

using namespace std;

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

static constexpr int kMaxN = 101 + 1;

static array<vector<TreeNode*>, kMaxN> m;

class NoCache {

public:

vector<TreeNode*> allPossibleFBT(int N) {

if (N % 2 == 0) return {};

if (N == 1) return {new TreeNode(0)};

vector<TreeNode*> ans;

for (int i = 1; i < N; i += 2) {

for (const auto& l : allPossibleFBT(i))

for (const auto& r : allPossibleFBT(N - i - 1)) {

auto root = new TreeNode(0);

root->left = l;

root->right = r;

ans.push_back(root);

}

return ans;

}

};

class Cached {

public:

vector<TreeNode*> allPossibleFBT(int N) {

return trees(N);

}

private:

vector<TreeNode*>& trees(int N) {

if (m[N].size() > 0) return m[N];

vector<TreeNode*>& ans = m[N];

if (N % 2 == 0) return ans = {};

if (N == 1) ans = {new TreeNode(0)};

for (int i = 1; i < N; i += 2) {

for (const auto& l : trees(i))

for (const auto& r : trees(N - i - 1)) {

auto root = new TreeNode(0);

root->left = l;

root->right = r;

ans.push_back(root);

}

return ans;

}

};

int main(int argc, char** argv) {

printf("N\tno-cache\tcached\n");

for (int i = 1; i <= 35; i += 2) {

printf("%02d\t", i);

{

auto start = clock();

(void)(NoCache().allPossibleFBT(i));

printf("%8.4f\t", static_cast<double>(clock() - start) / CLOCKS_PER_SEC);

}

{

// Clear the cache.

for (int j = 0; j < kMaxN; ++j)

m[i].clear();

auto start = clock();

(void)(Cached().allPossibleFBT(i));

printf("%8.4f\n", static_cast<double>(clock() - start) / CLOCKS_PER_SEC);

}

return 0;

}