花花酱 LeetCode 91. Decode Ways

By zxi on November 9, 2017

题目大意：

给你一个加密的数字字符串，问你一共有多少种不同的解密方式。

Problem:

A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ -> 1

‘B’ -> 2

…

‘Z’ -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

Idea:

Dynamic Programming

Solution:

C++

Time complexity: O(n^2)

Space complexity: O(n^2)

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

int numDecodings(string s) {

if(s.length() == 0) return 0;

m_ways[""] = 1;

return ways(s);

}

private:

int ways(const string& s) {

if (m_ways.count(s)) return m_ways[s];

if (s[0] == '0') return 0;

if (s.length() == 1) return 1;

int w = ways(s.substr(1));

const int prefix = stoi(s.substr(0, 2));

if (prefix <= 26)

w += ways(s.substr(2));

m_ways[s] = w;

return w;

}

unordered_map<string, int> m_ways;

};

C++

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

int numDecodings(string s) {

if(s.length() == 0) return 0;

return ways(s, 0, s.length() - 1);

}

private:

int ways(const string& s, int l, int r) {

if (m_ways.count(l)) return m_ways[l];

if (s[l] == '0') return 0;

if (l >= r) return 1; // Single digit or empty.

int w = ways(s, l + 1, r);

const int prefix = (s[l] - '0') * 10 + (s[l + 1] - '0');

if (prefix <= 26)

w += ways(s, l + 2, r);

m_ways[l] = w;

return w;

}

// Use l as key.

unordered_map<int, int> m_ways;

};

C++

Time complexity: O(n)

Space complexity: O(1)

class Solution {

public:

int numDecodings(string s) {

if (s.empty() || s[0] == '0') return 0;

if (s.length() == 1) return 1;

const int n = s.length();

int w1 = 1;

int w2 = 1;

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

int w = 0;

if (!isValid(s[i]) && !isValid(s[i - 1], s[i])) return 0;

if (isValid(s[i])) w = w1;

if (isValid(s[i - 1], s[i])) w += w2;

w2 = w1;

w1 = w;

}

return w1;

}

private:

bool isValid(const char c) { return c != '0'; }

bool isValid(const char c1, const char c2) {

const int num = (c1 - '0')*10 + (c2 - '0');

return num >= 10 && num <= 26;

}

};

Related Problems:

[解题报告] LeetCode 639. Decode Ways II – 花花酱

花花酱 LeetCode 4. Median of Two Sorted Arrays

By zxi on November 8, 2017

题目大意：求两个已经排序的数组的中位数（如果合并后）。

Problem:

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]

nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]

nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Idea:

Binary Search

Time complexity: O(log(min(n1,n2)))

Space complexity: O(1)

Solution: Binary Search

C++

// Author: Huahua

// Runtime: 52 ms

class Solution {

public:

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

const int n1 = nums1.size();

const int n2 = nums2.size();

// Make sure n1 <= n2

if (n1 > n2) return findMedianSortedArrays(nums2, nums1);

const int k = (n1 + n2 + 1) / 2;

int l = 0;

int r = n1;

while (l < r) {

const int m1 = l + (r - l) / 2;

const int m2 = k - m1;

if (nums1[m1] < nums2[m2 - 1])

l = m1 + 1;

else

r = m1;

}

const int m1 = l;

const int m2 = k - l;

const int c1 = max(m1 <= 0 ? INT_MIN : nums1[m1 - 1],

m2 <= 0 ? INT_MIN : nums2[m2 - 1]);

if ((n1 + n2) % 2 == 1)

return c1;

const int c2 = min(m1 >= n1 ? INT_MAX : nums1[m1],

m2 >= n2 ? INT_MAX : nums2[m2]);

return (c1 + c2) * 0.5;

}

};

Java

// Author: Huahua

// Runtime: 66 ms

class Solution {

public double findMedianSortedArrays(int[] nums1, int[] nums2) {

int n1 = nums1.length;

int n2 = nums2.length;

if (n1 > n2)

return findMedianSortedArrays(nums2, nums1);

int k = (n1 + n2 + 1) / 2;

int l = 0;

int r = n1;

while (l < r) {

int m1 = l + (r - l) / 2;

int m2 = k - m1;

if (nums1[m1] < nums2[m2 - 1])

l = m1 + 1;

else

r = m1;

}

int m1 = l;

int m2 = k - l;

int c1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE : nums1[m1 - 1],

m2 <= 0 ? Integer.MIN_VALUE : nums2[m2 - 1]);

if ((n1 + n2) % 2 == 1)

return c1;

int c2 = Math.min(m1 >= n1 ? Integer.MAX_VALUE : nums1[m1],

m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]);

return (c1 + c2) * 0.5;

}

Related Problem:

[解题报告] LeetCode 295. Find Median from Data Stream O(logn) + O(1)

花花酱 LeetCode 169. Majority Element

By zxi on November 4, 2017

题目大意：给你一个数组，其中一个数出现超过n/2次，问你出现次数最多的那个数是什么？

Problem:

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Ideas:

Solution 1:

Hash table O(n) / O(n)

// Author: Huahua

// Runtime : 23 ms

class Solution {

public:

int majorityElement(vector<int>& nums) {

unordered_map<int, int> count;

const int n = nums.size();

for (const int num : nums)

if (++count[num] > n / 2) return num;

return -1;

}

};

Solution 2:

BST O(nlogk) / O(n)

// Author: Huahua

// Runtime : 19 ms

class Solution {

public:

int majorityElement(vector<int>& nums) {

map<int, int> count;

const int n = nums.size();

for (const int num : nums)

if (++count[num] > n / 2) return num;

return -1;

}

};

Solution 3:

Randomization O(n) / O(1)

// Author: Huahua

// Runtime: 19 ms

class Solution {

public:

int majorityElement(vector<int>& nums) {

srand(time(nullptr));

const int n = nums.size();

while (true) {

const int index = rand() % n;

const int majority = nums[index];

int count = 0;

for (const int num : nums)

if (num == majority && ++count > n/2) return num;

}

return -1;

}

};

Solution 4:

Bit voting O(n) / O(1)

class Solution {

public:

int majorityElement(vector<int>& nums) {

const int n = nums.size();

int majority = 0;

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

int mask = 1 << i;

int count = 0;

for (const int num : nums)

if ((num & mask) && (++count > n /2)) {

majority |= mask;

break;

}

return majority;

}

};

Solution 5:

Moore Voting O(n) / O(1)

class Solution {

public:

int majorityElement(vector<int>& nums) {

int majority = nums.front();

int count = 0;

for (const int num : nums) {

if (num == majority) ++count;

else if (--count == 0) {

count = 1;

majority = num;

}

return majority;

}

};

Solution 6:

Full sorting O(nlogn) / O(1)

class Solution {

public:

int majorityElement(vector<int>& nums) {

std::sort(nums.begin(), nums.end());

return nums[nums.size()/2];

}

};

Solution 7:

Partial sorting O(n) / O(1)

class Solution {

public:

int majorityElement(vector<int>& nums) {

nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());

return nums[nums.size() / 2];

}

};

Solution 8:

Divide and conquer O(nlogn) / O(logn)

class Solution {

public:

int majorityElement(vector<int>& nums) {

return majorityElement(nums, 0, nums.size() - 1);

}

private:

int majorityElement(const vector<int>& nums, int l, int r) {

if (l == r) return nums[l];

const int m = l + (r - l) / 2;

const int ml = majorityElement(nums, l, m);

const int mr = majorityElement(nums, m + 1, r);

if (ml == mr) return ml;

return count(nums.begin() + l, nums.begin() + r + 1, ml) >

count(nums.begin() + l, nums.begin() + r + 1, mr)

? ml : mr;

}

};

Divide and conquer O(nlogn) / O(logn)

class Solution {

public:

int majorityElement(vector<int>& nums) {

return majorityElement(nums, 0, nums.size() - 1).first;

}

private:

pair<int, int> majorityElement(const vector<int>& nums, int l, int r) {

if (l == r) return {nums[l], 1};

int mid = l + (r - l) / 2;

auto ml = majorityElement(nums, l, mid);

auto mr = majorityElement(nums, mid + 1, r);

if (ml.first == mr.first) return { ml.first, ml.second + mr.second };

if (ml.second > mr.second)

return { ml.first, ml.second + count(nums.begin() + mid + 1, nums.begin() + r + 1, ml.first) };

else

return { mr.first, mr.second + count(nums.begin() + l, nums.begin() + mid + 1, mr.first) };

}

};

花花酱 LeetCode 216. Combination Sum III

By zxi on November 3, 2017

题目大意：输出所有用k个数的和为n的组合。可以使用的元素是1到9。

Problem:

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

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

Idea:

DFS + backtracking

bit

Solution:

C++

// Author: Huahua

// Runtime: 0 ms

class Solution {

public:

vector<vector<int>> combinationSum3(int k, int n) {

vector<vector<int>> ans;

vector<int> cur;

dfs(k, n, 1, cur, ans);

return ans;

}

private:

// Use k numbers (>= s) to sum up to n

void dfs(int k, int n, int s,

vector<int>& cur, vector<vector<int>>& ans) {

if (k == 0) {

if (n == 0) ans.push_back(cur);

return;

}

for (int i = s; i <= 9; ++i) {

if (i > n) return;

cur.push_back(i);

dfs(k - 1, n - i, i + 1, cur, ans);

cur.pop_back();

}

};

C++ / binary

class Solution {

public:

vector<vector<int>> combinationSum3(int k, int n) {

vector<vector<int>> ans;

// 2^9, generate all combinations of [1 .. 9]

for (int i = 0; i < (1 << 9); ++i) {

vector<int> cur;

int sum = 0;

// Use j if (j - 1)-th bit is 1

for (int j = 1; j <= 9; ++j)

if (i & (1 << (j - 1))) {

sum += j;

cur.push_back(j);

}

if (sum == n && cur.size() == k)

ans.push_back(cur);

}

return ans;

}

};

Python

class Solution:

def combinationSum3(self, k, n):

def dfs(k, n, s, cur, ans):

if k == 0 and n == 0:

ans.append(list(cur))

for i in range(s, min(n + 1, 10)):

dfs(k - 1, n - i, i + 1, cur + [i], ans)

ans = []

dfs(k, n, 1, [], ans)

return ans

Related problems:

花花酱 LeetCode 719. Find K-th Smallest Pair Distance

By zxi on October 29, 2017

题目大意：给你一个数组，返回所有数对中，绝对值差第k小的值。

Problem:

Given an integer array, return the k-th smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.

Example 1:

Input:

nums = [1,3,1]

k = 1

Output: 0

Explanation:

Here are all the pairs:

(1,3) -> 2

(1,1) -> 0

(3,1) -> 2

Then the 1st smallest distance pair is (1,1), and its distance is 0.

Note:

2 <= len(nums) <= 10000.
0 <= nums[i] < 1000000.
1 <= k <= len(nums) * (len(nums) - 1) / 2.

Idea

Bucket sort

Binary search / dp

Solution

C++ / binary search

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

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

std::sort(nums.begin(), nums.end());

int n = nums.size();

int l = 0;

int r = nums.back() - nums.front();

while (l <= r) {

int cnt = 0;

int j = 0;

int m = l + (r - l) / 2;

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

while (j < n && nums[j] - nums[i] <= m) ++j;

cnt += j - i - 1;

}

cnt >= k ? r = m - 1 : l = m + 1;

}

return l;

}

};

C++ / bucket sort w/ vector O(n^2)

// Author: Huahua

// Runtime: 549 ms

class Solution {

public:

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

std::sort(nums.begin(), nums.end());

const int N = nums.back();

vector<int> count(N + 1, 0);

const int n = nums.size();

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

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

++count[nums[j] - nums[i]];

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

k -= count[i];

if (k <= 0) return i;

}

return 0;

}

};

Related Problems:

Huahua's Tech Road

花花酱 LeetCode 91. Decode Ways

花花酱 LeetCode 4. Median of Two Sorted Arrays

Solution: Binary Search

C++

Java

Related Problem:

花花酱 LeetCode 169. Majority Element

花花酱 LeetCode 216. Combination Sum III

花花酱 LeetCode 719. Find K-th Smallest Pair Distance