Huahua’s Tech Road

花花酱 LeetCode 190. Reverse Bits

By zxi on September 30, 2019

Reverse bits of a given 32 bits unsigned integer.

Example 1:

Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10101111110010110010011101101001.

Note:

Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Follow up:

If this function is called many times, how would you optimize it?

Solution: Bit operation

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

C++

// Author: Huahua

class Solution {

public:

uint32_t reverseBits(uint32_t n) {

uint32_t ans = 0;

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

ans <<= 1;

ans |= n & 1;

n >>= 1;

}

return ans;

}

};

花花酱 LeetCode 89. Gray Code

By zxi on September 29, 2019

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

Example 1:

Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2

For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.

00 - 0
10 - 2
11 - 3
01 - 1

Example 2:

Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
             A gray code sequence of n has size = 2ⁿ, which for n = 0 the size is 2⁰ = 1.
             Therefore, for n = 0 the gray code sequence is [0].

Solution: DP

dp[0] = 0
dp[i] = dp[i – 1] + [x | 1 << (i – 1) for x in reversed(dp[i – 1])]

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

C++

// Author: Huahua

class Solution {

public:

vector<int> grayCode(int n) {

vector<vector<int>> dp(n + 1);

dp[0] = {0};

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

dp[i] = dp[i - 1];

for (int j = dp[i - 1].size() - 1; j >= 0; --j)

dp[i].push_back(dp[i - 1][j] | (1 << (i - 1)));

}

return dp[n];

}

};

Python3

# Author: Huahua

class Solution:

def grayCode(self, n: int) -> List[int]:

dp = [0]

for i in range(n):

dp = dp + [x | 1 << i for x in reversed(dp)]

return dp

花花酱 LeetCode 99. Recover Binary Search Tree

By zxi on September 29, 2019

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Example 1:

Input: [1,3,null,null,2]

   1
  /
 3
  \
   2

Output: [3,1,null,null,2]

   3
  /
 1
  \
   2

Example 2:

Input: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

Follow up:

A solution using O(n) space is pretty straight forward.
Could you devise a constant space solution?

Solution: Inorder traversal

Using inorder traversal to find two nodes that have val < prev.val

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

C++

// Author: Huahua

class Solution {

public:

void recoverTree(TreeNode *root) {

inorder(root);

swap(first->val, second->val);

}

void inorder(TreeNode* root) {

if (!root) return;

inorder(root->left);

if (prev && prev->val > root->val) {

if (!first) first = prev;

second = root;

}

prev = root;

inorder(root->right);

}

private:

TreeNode* first;

TreeNode* second;

TreeNode* prev;

};

花花酱 LeetCode 96. Unique Binary Search Trees

By zxi on September 29, 2019

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example:

Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Solution: DP

dp[i] = sum(dp[j] * dp[i – j – 1]) (0 <= j < i )

root: 1 node
left child: j nodes
right child i – j – 1 nodes

try all possible partitions

ans = dp[n]

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

C++

// Author: Huahua

class Solution {

public:

int numTrees(int n) {

vector<int> dp(n + 1);

dp[0] = 1;

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

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

dp[i] += dp[j] * dp[i - j - 1];

return dp[n];

}

};

花花酱 LeetCode 528. Random Pick with Weight

By zxi on September 29, 2019

Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight.

Note:

1 <= w.length <= 10000
1 <= w[i] <= 10^5
pickIndex will be called at most 10000 times.

Example 1:

Input: 
["Solution","pickIndex"]
[[[1]],[]]
Output: [null,0]

Example 2:

Input: 
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output: [null,0,1,1,1,0]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution‘s constructor has one argument, the array w. pickIndex has no arguments. Arguments are always wrapped with a list, even if there aren’t any.

Solution: Binary Search

Crate a cumulative weight array, random sample a “weight”, do a binary search to see which bucket that weight falls in.
e.g. w = [2, 3, 1, 4], sum = [2, 5, 6, 10]
sample 3 => index = 1
sample 7 => index = 3

Time complexity: Init: O(n) Pick: O(logn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

Solution(vector<int> w): sums_(std::move(w)) {

partial_sum(begin(sums_), end(sums_), begin(sums_));

}

int pickIndex() {

int s = rand() % sums_.back();

return upper_bound(begin(sums_), end(sums_), s) - begin(sums_);

}

private:

vector<int> sums_;

};

Huahua's Tech Road

花花酱 LeetCode 190. Reverse Bits

C++

花花酱 LeetCode 89. Gray Code

Solution: DP

C++

Python3

花花酱 LeetCode 99. Recover Binary Search Tree

Solution: Inorder traversal

C++

花花酱 LeetCode 96. Unique Binary Search Trees

Solution: DP

C++

花花酱 LeetCode 528. Random Pick with Weight

Solution: Binary Search

C++