花花酱 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 899. Orderly Queue

By zxi on September 1, 2018

Problem

A string S of lowercase letters is given. Then, we may make any number of moves.

In each move, we choose one of the first K letters (starting from the left), remove it, and place it at the end of the string.

Return the lexicographically smallest string we could have after any number of moves.

Example 1:

Input: S = "cba", K = 1
Output: "acb"
Explanation: 
In the first move, we move the 1st character ("c") to the end, obtaining the string "bac".
In the second move, we move the 1st character ("b") to the end, obtaining the final result "acb".

Example 2:

Input: S = "baaca", K = 3
Output: "aaabc"
Explanation: 
In the first move, we move the 1st character ("b") to the end, obtaining the string "aacab".
In the second move, we move the 3rd character ("c") to the end, obtaining the final result "aaabc".

Note:

1 <= K <= S.length <= 1000
S consists of lowercase letters only.

Solution: Rotation or Sort?

if \(k =1\), we can only rotate the string.

if \(k > 1\), we can bubble sort the string.

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

string orderlyQueue(string S, int K) {

if (K > 1) {

sort(begin(S), end(S));

return S;

}

string ans = S;

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

ans = min(ans, S.substr(i) + S.substr(0, i));

return ans;

}

};

Java

// Author: Huahua

class Solution {

public String orderlyQueue(String S, int K) {

if (K > 1) {

char[] chars = S.toCharArray();

Arrays.sort(chars);

return new String(chars);

}

String ans = S;

for (int i = 1; i < S.length(); ++i) {

String tmp = S.substring(i) + S.substring(0, i);

if (tmp.compareTo(ans) < 0) ans = tmp;

}

return ans;

}

Python3 SC O(n^2)

# Author: Huahua 48 ms

class Solution:

def orderlyQueue(self, S, K):

if K > 1: return ''.join(sorted(S))

return min([S[i:] + S[0:i] for i in range(0, len(S))])

Python3 SC O(n)

# Author: Huahua 36 ms

class Solution:

def orderlyQueue(self, S, K):

if K > 1: return ''.join(sorted(S))

ans = S

for i in range(0, len(S)):

ans = min(ans, S[i:] + S[0:i])

return ans

花花酱 LeetCode 897. Increasing Order Search Tree

By zxi on September 1, 2018

Problem

Given a tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.

Example 1:
Input: [5,3,6,2,4,null,8,1,null,null,null,7,9]

       5
      / \
    3    6
   / \    \
  2   4    8
 /        / \ 
1        7   9

Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

 1
  \
   2
    \
     3
      \
       4
        \
         5
          \
           6
            \
             7
              \
               8
                \
                 9

Note:

The number of nodes in the given tree will be between 1 and 100.
Each node will have a unique integer value from 0 to 1000.

Solution: In-order traversal

root = 5

inorder(root.left) 之后

self.prev = 4

（1-4）已经处理完了，这时候的树是很奇怪的一个形状，3即是2的右子树，又是5的左子树。

2 5

\ / \

3 6

\ \

prev -> 4 8

/ \

7 9

—————————

5.left = None # 把5->3的链接断开

/ \

7 9

—————————–

self.prev.right = root <=> 4.right = 5

把5接到4的右子树

5 <– prev

/ \

7 9

self.prev = root <=> prev = 5

inorder(5.right) <=> inorder(6) 然后再去递归处理6（及其子树）即可。

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 64 ms

class Solution {

public:

TreeNode* increasingBST(TreeNode* root) {

TreeNode dummy(0);

prev_ = &dummy;

inorder(root);

return dummy.right;

}

private:

TreeNode* prev_;

void inorder(TreeNode* root) {

if (root == nullptr) return;

inorder(root->left);

prev_->right = root;

prev_ = root;

prev_->left = nullptr;

inorder(root->right);

}

};

Java

class Solution {

private TreeNode prev;

public TreeNode increasingBST(TreeNode root) {

TreeNode dummy = new TreeNode(0);

this.prev = dummy;

inorder(root);

return dummy.right;

}

private void inorder(TreeNode root) {

if (root == null) return;

inorder(root.left);

this.prev.right = root;

this.prev = root;

this.prev.left = null;

inorder(root.right);

}

Python3

class Solution:

def increasingBST(self, root):

dummy = TreeNode(0)

self.prev = dummy

def inorder(root):

if not root: return None

inorder(root.left)

root.left = None

self.prev.right = root

self.prev = root

inorder(root.right)

inorder(root)

return dummy.right

花花酱 LeetCode 896. Monotonic Array

By zxi on September 1, 2018

An array is monotonic if it is either monotone increasing or monotone decreasing.

An array A is monotone increasing if for all i <= j, A[i] <= A[j]. An array A is monotone decreasing if for all i <= j, A[i] >= A[j].

Return true if and only if the given array A is monotonic.

Solution:

C++

// Author: Huahua

class Solution {

public:

bool isMonotonic(vector<int>& A) {

bool inc = true;

bool dec = true;

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

inc &= A[i] >= A[i - 1];

dec &= A[i] <= A[i - 1];

}

return inc || dec;

}

};

Java

class Solution {

public boolean isMonotonic(int[] A) {

boolean inc = true;

boolean dec = true;

for (int i = 1; i < A.length; ++i) {

inc &= A[i] >= A[i - 1];

dec &= A[i] <= A[i - 1];

}

return inc || dec;

}

Python

# Author: Huahua

class Solution:

def isMonotonic(self, A):

inc = True;

dec = True;

for i in range(1, len(A)):

inc = inc and A[i] >= A[i - 1]

dec = dec and A[i] <= A[i - 1]

return inc or dec;

花花酱 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;

}

};

Huahua's Tech Road

花花酱 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 899. Orderly Queue

Problem

Solution: Rotation or Sort?

C++

Java

Python3 SC O(n^2)

Python3 SC O(n)

花花酱 LeetCode 897. Increasing Order Search Tree

Problem

Solution: In-order traversal

C++

Java

Python3

花花酱 LeetCode 896. Monotonic Array

Solution:

C++

Java

Python

花花酱 LeetCode 70. Climbing Stairs

Problem

Solution: DP

C++ O(n)

C++ O(1)