花花酱 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 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 70. Climbing Stairs

By zxi on August 27, 2018

Problem

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Solution: DP

Time complexity: O(n)

Space complexity: O(n)

C++ O(n)

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

int climbStairs(int n) {

// f[i] = climbStairs(i)

vector<int> f(n + 1, 0);

f[0] = f[1] = 1;

// f[i] = f[i-1] + f[i-2]

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

f[i] = f[i - 1] + f[i - 2];

return f[n];

}

};

C++ O(1)

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

int climbStairs(int n) {

int two = 1;

int one = 1;

int curr = 1;

// curr = two + one

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

curr = two + one;

two = one;

one = curr;

}

return curr;

}

};

花花酱 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 303. Range Sum Query – Immutable

By zxi on August 17, 2018

Problem

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:

You may assume that the array does not change.
There are many calls to sumRange function.

Solution: Prefix sum

sums[i] = nums[0] + nums[1] + … + nums[i]

sumRange(i, j) = sums[j] – sums[i – 1]

Time complexity: pre-compute: O(n), query: O(1)

Space complexity: O(n)

// Author: Huahua

// Running time: 112 ms

class NumArray {

public:

NumArray(vector<int> nums): sums_(nums) {

if (nums.empty()) return;

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

sums_[i] += sums_[i - 1];

}

int sumRange(int i, int j) {

if (i == 0) return sums_[j];

return sums_[j] - sums_[i-1];

}

private:

vector<int> sums_;

};

Posts published in “Dynamic Programming”

花花酱 LeetCode 5. Longest Palindromic Substring

Problem

Solution: DP

C++

Java

Python3

花花酱 LeetCode 898. Bitwise ORs of Subarrays

Problem

Solution 1: DP (TLE)

C++ SC O(n^2)

C++ SC O(n)

Solution 2: DP opted

C++

Java

Python3

花花酱 LeetCode 70. Climbing Stairs

Problem

Solution: DP

C++ O(n)

C++ O(1)

花花酱 LeetCode 120. Triangle

Problem

Solution: DP

C++

花花酱 LeetCode 303. Range Sum Query – Immutable

Problem

Solution: Prefix sum