Posts tagged as “easy”

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

}

};

花花酱 LeetCode 893. Groups of Special-Equivalent Strings

By zxi on August 26, 2018

Problem

You are given an array A of strings.

Two strings S and T are special-equivalent if after any number of moves, S == T.

A move consists of choosing two indices i and j with i % 2 == j % 2, and swapping S[i] with S[j].

Now, a group of special-equivalent strings from A is a non-empty subset S of A such that any string not in S is not special-equivalent with any string in S.

Return the number of groups of special-equivalent strings from A.

Example 1:

Input: ["a","b","c","a","c","c"]
Output: 3
Explanation: 3 groups ["a","a"], ["b"], ["c","c","c"]

Example 2:

Input: ["aa","bb","ab","ba"]
Output: 4
Explanation: 4 groups ["aa"], ["bb"], ["ab"], ["ba"]

Example 3:

Input: ["abc","acb","bac","bca","cab","cba"]
Output: 3
Explanation: 3 groups ["abc","cba"], ["acb","bca"], ["bac","cab"]

Example 4:

Input: ["abcd","cdab","adcb","cbad"]
Output: 1
Explanation: 1 group ["abcd","cdab","adcb","cbad"]

Note:

1 <= A.length <= 1000
1 <= A[i].length <= 20
All A[i] have the same length.
All A[i] consist of only lowercase letters.

Solution: Signature

All Special-Equivalent Strings should have the same signature if we sort all the odd-index characters and all the even-index characters.

E.g. [“abcd”,”cdab”,”adcb”,”cbad”] are all in the same graph.

“abcd”: odd “ac”, even: “bd”
“cdab”: odd “ac”, even: “bd”
“adcb”: odd “ac”, even: “bd”
“cbad”: odd “ac”, even: “bd”

We can concatenate the odd and even strings to create a hashable signature.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int numSpecialEquivGroups(vector<string>& A) {

unordered_set<string> s;

for (const string& a : A) {

string odd;

string even;

for (int i = 0; i < a.size(); ++i) {

if (i % 2)

odd += a[i];

else

even += a[i];

}

sort(begin(odd), end(odd));

sort(begin(even), end(even));

s.insert(odd + even);

}

return s.size();

}

};

Java

// Author: Huahua

// Running time: 16 ms

class Solution {

public int numSpecialEquivGroups(String[] A) {

Set<String> groups = new HashSet<>();

for (String a: A) {

char[] odd = new char[(a.length() + 1) / 2];

char[] even = new char[(a.length() + 1) / 2];

for (int i = 0; i < a.length(); ++i) {

if (i % 2 == 0)

even[i / 2] = a.charAt(i);

else

odd[i / 2] = a.charAt(i);

}

Arrays.sort(odd);

Arrays.sort(even);

String s = new String(odd) + new String(even);

groups.add(s);

}

return groups.size();

}

Python

"""

Author: Huahua

Running time: 56 ms

"""

class Solution:

def numSpecialEquivGroups(self, A):

s = set()

for a in A:

odd = ""

even = ""

for i, c in enumerate(a):

if i % 2 == 0:

odd += c

else:

even += c

s.add(''.join(sorted(odd) + sorted(even)))

return len(s)

Python (1-linear)

"""

Author: Huahua

Running time: 56 ms

"""

class Solution:

def numSpecialEquivGroups(self, A):

return len(set([''.join(sorted(a[0::2]) + sorted(a[1::2])) for a in A]))

花花酱 LeetCode 892. Surface Area of 3D Shapes

By zxi on August 26, 2018

Problem

On a N * N grid, we place some 1 * 1 * 1 cubes.

Each value v = grid[i][j] represents a tower of v cubes placed on top of grid cell (i, j).

Return the total surface area of the resulting shapes.

Example 1:

Input: [[2]]
Output: 10

Example 2:

Input: [[1,2],[3,4]]
Output: 34

Example 3:

Input: [[1,0],[0,2]]
Output: 16

Example 4:

Input: [[1,1,1],[1,0,1],[1,1,1]]
Output: 32

Example 5:

Input: [[2,2,2],[2,1,2],[2,2,2]]
Output: 46

Note:

1 <= N <= 50
0 <= grid[i][j] <= 50

Solution: Geometry

3D version of 花花酱 LeetCode 463. Island Perimeter

Ans = total faces – hidden faces.

each pile with height h has the surface area of 2 (top/bottom) + 4*h (sides)

\(ans = ans + 2 + 4 * h\)

if a cube has a neighbour, reduce the total surface area by 1

For each pile, we check 4 neighbours, the number of total hidden faces of this pile is sum(min(h, neighbour’s h)).

\(ans = ans – \Sigma min(h, n.h)\)

Time complexity: O(mn)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

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

static const vector<int> dirs{0, -1, 0, 1, 0};

int m = grid.size();

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

int ans = 0;

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

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

int h = grid[i][j];

if (h == 0) continue;

ans += 2 + 4 * h;

for (int k = 0; k < 4; k++) {

int tx = j + dirs[k];

int ty = i + dirs[k + 1];

if (tx < 0 || tx >= n || ty < 0 || ty >= m) continue;

int th = grid[ty][tx];

ans -= (th <= 0 ? 0 : min(h, th));

}

return ans;

}

};

C++ (opt)

Since the neighbor relationship is symmetric, we can only consider the top and left neighbors and double the hidden faces.

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

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

int m = grid.size();

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

int ans = 0;

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

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

int h = grid[i][j];

if (h == 0) continue;

ans += 2 + 4 * h;

if (i) ans -= 2 * min(h, grid[i - 1][j]);

if (j) ans -= 2 * min(h, grid[i][j - 1]);

}

return ans;

}

};

花花酱 LeetCode 112. Path Sum

By zxi on August 25, 2018

Problem

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool hasPathSum(TreeNode* root, int sum) {

if (!root) return false;

if (!root->left && !root->right) return root->val==sum;

int new_sum = sum - root->val;

return hasPathSum(root->left, new_sum) || hasPathSum(root->right, new_sum);

}

};

Posts tagged as “easy”

花花酱 LeetCode 896. Monotonic Array

Solution:

C++

Java

Python

花花酱 LeetCode 70. Climbing Stairs

Problem

Solution: DP

C++ O(n)

C++ O(1)

花花酱 LeetCode 893. Groups of Special-Equivalent Strings

Problem

Solution: Signature

C++

Java

Python

Python (1-linear)

花花酱 LeetCode 892. Surface Area of 3D Shapes

Problem

Solution: Geometry

C++

C++ (opt)

花花酱 LeetCode 112. Path Sum

Problem

Solution: Recursion

Related Problems