花花酱 LeetCode 840. Magic Squares In Grid

By zxi on July 8, 2018

Problem

A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.

Given an grid of integers, how many 3 x 3 “magic square” subgrids are there? (Each subgrid is contiguous).

Example 1:

Input: [[4,3,8,4],
        [9,5,1,9],
        [2,7,6,2]]
Output: 1
Explanation: 
The following subgrid is a 3 x 3 magic square:
438
951
276

while this one is not:
384
519
762

In total, there is only one magic square inside the given grid.

Note:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
0 <= grid[i][j] <= 15

Solution

Time complexity: O(m*n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

int numMagicSquaresInside(vector<vector<int>>& grid) {

int m = grid.size();

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

int ans = 0;

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

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

ans += magic(grid, j, i);

return ans;

}

private:

int magic(const vector<vector<int>>& grid, int x, int y) {

vector<int> rows(3);

vector<int> cols(3);

vector<int> exps{15, 15, 15};

int dig = 0;

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

for (int j = 0; j < 3; ++j) {

int v = grid[y + i][x + j];

if (v <= 0 || v > 9) return 0; // must between 1 and 9

rows[i] += v;

cols[j] += v;

if (i == j) dig += v;

}

return rows == exps && cols == exps && dig == 15;

}

};

花花酱 LeetCode 865. Smallest Subtree with all the Deepest Nodes

By zxi on July 8, 2018

Problem

Given a binary tree rooted at root, the depth of each node is the shortest distance to the root.

A node is deepest if it has the largest depth possible among any node in the entire tree.

The subtree of a node is that node, plus the set of all descendants of that node.

Return the node with the largest depth such that it contains all the deepest nodes in it’s subtree.

Example 1:

Input: [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation:



We return the node with value 2, colored in yellow in the diagram.
The nodes colored in blue are the deepest nodes of the tree.
The input "[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]" is a serialization of the given tree.
The output "[2, 7, 4]" is a serialization of the subtree rooted at the node with value 2.
Both the input and output have TreeNode type.

Note:

The number of nodes in the tree will be between 1 and 500.
The values of each node are unique.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

TreeNode* subtreeWithAllDeepest(TreeNode* root) {

return depth(root).second;

}

private:

pair<int, TreeNode*> depth(TreeNode* root) {

if (root == nullptr)

return {-1, nullptr};

auto l = depth(root->left);

auto r = depth(root->right);

int dl = l.first;

int dr = r.first;

return { max(dl, dr) + 1,

dl == dr ? root : (dl > dr) ? l.second : r.second};

}

};

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

TreeNode* subtreeWithAllDeepest(TreeNode* root) {

TreeNode* ans;

depth(root, &ans);

return ans;

}

private:

int depth(TreeNode* root, TreeNode** s) {

if (root == nullptr)

return -1;

TreeNode* sl;

TreeNode* sr;

int l = depth(root->left, &sl);

int r = depth(root->right, &sr);

*s = (l == r) ? root : ((l > r) ? sl : sr);

return max(l, r) + 1;

}

};

Python3

"""

Author: Huahua

Running time: 40 ms

"""

class Solution:

def subtreeWithAllDeepest(self, root):

def solve(root):

if not root: return (-1, None)

dl, sl = solve(root.left)

dr, sr = solve(root.right)

if dl == dr: return (dl + 1, root)

return (dl + 1, sl) if dl > dr else (dr + 1, sr)

return solve(root)[1]

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

}

};

Posts published in July 2018

花花酱 LeetCode 840. Magic Squares In Grid

Problem

Solution

花花酱 LeetCode 865. Smallest Subtree with all the Deepest Nodes

Problem

Solution: Recursion

花花酱 LeetCode 867. Prime Palindrome

Problem

Solution: Math

花花酱 LeetCode 867. Transpose Matrix

Solution: Brute Force

C++

花花酱 LeetCode 441. Arranging Coins

Problem

Solution: Math