花花酱 LeetCode 867. Prime Palindrome

By zxi on July 8, 2018

Problem

Find the smallest prime palindrome greater than or equal to N.

Recall that a number is prime if it’s only divisors are 1 and itself, and it is greater than 1.

For example, 2,3,5,7,11 and 13 are primes.

Recall that a number is a palindrome if it reads the same from left to right as it does from right to left.

For example, 12321 is a palindrome.

Example 1:

Input: 6
Output: 7

Example 2:

Input: 8
Output: 11

Example 3:

Input: 13
Output: 101

Note:

1 <= N <= 10^8
The answer is guaranteed to exist and be less than 2 * 10^8.

Solution: Math

All odd digits palindromes have a factor 11, they are not prime except 11 itself.

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int primePalindrome(int N) {

if (N <= 2) return 2;

if (N % 2 == 0) ++N;

while (true) {

if (reverse(N) == N && isPrime(N))

return N;

N += 2;

if (N > 11 & (int)log10(N) % 2 == 1)

// 13 -> 101

// 1001 -> 10001

N = pow(10, (int)log10(N) + 1) + 1;

}

return -1;

}

private:

int reverse(int n) {

int r = 0;

while (n) {

r = 10 * r + n % 10;

n /= 10;

}

return r;

}

bool isPrime(int n) {

if (n <= 1) return false;

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

if (n % i == 0) return false;

return true;

}

};

花花酱 LeetCode 867. Transpose Matrix

By zxi on July 8, 2018

Given a matrix A, return the transpose of A.

The transpose of a matrix is the matrix flipped over it’s main diagonal, switching the row and column indices of the matrix.

Example 1:

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

Example 2:

Input: [[1,2,3],[4,5,6]]
Output: [[1,4],[2,5],[3,6]]

Note:

1 <= A.length <= 1000
1 <= A[0].length <= 1000

Solution: Brute Force

Time complexity: O(mn)

Space complexity: O(mn)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

vector<vector<int>> transpose(vector<vector<int>>& A) {

int m = A.size();

int n = A[0].size();

vector<vector<int>> ans(n, vector<int>(m));

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

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

ans[j][i] = A[i][j];

return ans;

}

};

花花酱 LeetCode 441. Arranging Coins

By zxi on July 7, 2018

Problem

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly kcoins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:

n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.

Example 2:

n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.

Solution: Math

Time complexity: O(sqrt(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int arrangeCoins(int n) {

for (long i = sqrt(n) * 2 + 1; i >= 0; --i)

if (i * (i + 1) / 2 <= n) return i;

return -1;

}

};

Time complexity: O(1)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int arrangeCoins(int n) {

// x * (1 + x) / 2 <= n

// x^2 + x - 2n <= 0

// x <= (-1 + sqrt(1 + 8n)) / 2

return (-1 + sqrt(1 + static_cast<long>(n) * 8)) / 2;

}

};

花花酱 LeetCode 410. Split Array Largest Sum

By zxi on July 3, 2018

Problem

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note:
If n is the length of array, assume the following constraints are satisfied:

1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)

Examples:

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

Solution: DP

Time complexity: O(n^2*m)

Space complexity: O(n*m)

C++ / Recursion + Memorization

// Author: Huahua

// Running time: 111 ms

class Solution {

public:

int splitArray(vector<int>& nums, int m) {

const int n = nums.size();

sums_ = vector<int>(n);

mem_ = vector<vector<int>>(n, vector<int>(m + 1, INT_MAX));

sums_[0] = nums[0];

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

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

return splitArray(nums, n - 1, m);

}

private:

vector<vector<int>> mem_;

vector<int> sums_;

// min of largest sum of spliting nums[0] ~ nums[k] into m groups

int splitArray(const vector<int>& nums, int k, int m) {

if (m == 1) return sums_[k];

if (m > k + 1) return INT_MAX;

if (mem_[k][m] != INT_MAX) return mem_[k][m];

int ans = INT_MAX;

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

ans = min(ans, max(splitArray(nums, i, m - 1), sums_[k] - sums_[i]));

return mem_[k][m] = ans;

}

};

C++ / DP

// Author: Huahua

// Running time: 90 ms

class Solution {

public:

int splitArray(vector<int>& nums, int m) {

const int n = nums.size();

vector<int> sums(n);

// dp[i][j] := min of largest sum of splitting nums[0] ~ nums[j] into i groups.

vector<vector<int>> dp(m + 1, vector<int>(n, INT_MAX));

sums[0] = nums[0];

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

sums[i] = sums[i - 1] + nums[i];

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

dp[1][i] = sums[i];

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

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

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

dp[i][j] = min(dp[i][j], max(dp[i - 1][k], sums[j] - sums[k]));

return dp[m][n - 1];

}

};

Solution: Binary Search

Time complexity: O(log(sum(nums))*n)

Space complexity: O(1)

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

int splitArray(vector<int>& nums, int m) {

long l = *max_element(begin(nums), end(nums));

long r = accumulate(begin(nums), end(nums), 0L) + 1;

while (l < r) {

long limit = (r - l) / 2 + l;

if (min_groups(nums, limit) > m)

l = limit + 1;

else

r = limit;

}

return l;

}

private:

int min_groups(const vector<int>& nums, long limit) {

long sum = 0;

int groups = 1;

for (int num : nums) {

if (sum + num > limit) {

sum = num;

++groups;

} else {

sum += num;

}

return groups;

}

};

花花酱 LeetCode 863. All Nodes Distance K in Binary Tree

By zxi on June 30, 2018

Problem

题目大意：给你一棵二叉树（根结点root）和一个target节点。返回所有到target的距离为K的节点。

We are given a binary tree (with root node root), a target node, and an integer value K.

Return a list of the values of all nodes that have a distance K from the target node. The answer can be returned in any order.

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
Output: [7,4,1]
Explanation: 
The nodes that are a distance 2 from the target node (with value 5)
have values 7, 4, and 1.

Note that the inputs "root" and "target" are actually TreeNodes.
The descriptions of the inputs above are just serializations of these objects.

Note:

The given tree is non-empty.
Each node in the tree has unique values 0 <= node.val <= 500.
The target node is a node in the tree.
0 <= K <= 1000.

Solution1: DFS + BFS

Use DFS to build the graph, and use BFS to find all the nodes that are exact K steps from target.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {

buildGraph(nullptr, root);

vector<int> ans;

unordered_set<TreeNode*> seen;

queue<TreeNode*> q;

seen.insert(target);

q.push(target);

int k = 0;

while (!q.empty() && k <= K) {

int s = q.size();

while (s--) {

TreeNode* node = q.front(); q.pop();

if (k == K) ans.push_back(node->val);

for (TreeNode* child : g[node]) {

if (seen.count(child)) continue;

q.push(child);

seen.insert(child);

}

++k;

}

return ans;

}

private:

unordered_map<TreeNode*, vector<TreeNode*>> g;

void buildGraph(TreeNode* parent, TreeNode* child) {

if (parent) {

g[parent].push_back(child);

g[child].push_back(parent);

}

if (child->left) buildGraph(child, child->left);

if (child->right) buildGraph(child, child->right);

}

};

Array version

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {

constexpr int kMaxN = 500 + 1;

g = vector<vector<int>>(kMaxN);

buildGraph(nullptr, root);

vector<int> ans;

vector<int> seen(kMaxN);

queue<int> q;

seen[target->val] = 1;

q.push(target->val);

int k = 0;

while (!q.empty() && k <= K) {

int s = q.size();

while (s--) {

int node = q.front(); q.pop();

if (k == K) ans.push_back(node);

for (int child : g[node]) {

if (seen[child]) continue;

q.push(child);

seen[child] = 1;

}

++k;

}

return ans;

}

private:

vector<vector<int>> g;

void buildGraph(TreeNode* parent, TreeNode* child) {

if (parent) {

g[parent->val].push_back(child->val);

g[child->val].push_back(parent->val);

}

if (child->left) buildGraph(child, child->left);

if (child->right) buildGraph(child, child->right);

}

};

Solution 2: Recursion

Recursively compute the distance from root to target, and collect nodes accordingly.

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 5 ms

class Solution {

public:

vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {

ans.clear();

dis(root, target, K);

return ans;

}

private:

vector<int> ans;

// Returns the distance from root to target.

// Returns -1 if target does not in the tree.

int dis(TreeNode* root, TreeNode* target, int K) {

if (root == nullptr) return -1;

if (root == target) {

collect(target, K);

return 0;

}

int l = dis(root->left, target, K);

int r = dis(root->right, target, K);

// Target in the left subtree

if (l >= 0) {

if (l == K - 1) ans.push_back(root->val);

// Collect nodes in right subtree with depth K - l - 2

collect(root->right, K - l - 2);

return l + 1;

}

// Target in the right subtree

if (r >= 0) {

if (r == K - 1) ans.push_back(root->val);

// Collect nodes in left subtree with depth K - r - 2

collect(root->left, K - r - 2);

return r + 1;

}

return -1;

}

// Collect nodes that are d steps from root.

void collect(TreeNode* root, int d) {

if (root == nullptr || d < 0) return;

if (d == 0) ans.push_back(root->val);

collect(root->left, d - 1);

collect(root->right, d - 1);

}

};

Huahua's Tech Road

花花酱 LeetCode 867. Prime Palindrome

Problem

Solution: Math

花花酱 LeetCode 867. Transpose Matrix

Solution: Brute Force

C++

花花酱 LeetCode 441. Arranging Coins

Problem

Solution: Math

花花酱 LeetCode 410. Split Array Largest Sum

Problem

Solution: DP

Solution: Binary Search

花花酱 LeetCode 863. All Nodes Distance K in Binary Tree

Problem

Solution1: DFS + BFS

Solution 2: Recursion