花花酱 Leetcode 100. Same Tree

By zxi on September 2, 2017

Problem:

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

bool isSameTree(TreeNode* p, TreeNode* q) {

// Both are emtry: same

if (!p && !q) return true;

// One is emtry: not the Same

if (!p || !q) return false;

// Both are not emptry, compare the root value

if (p->val != q->val) return false;

// Compare left-subtree and right-subtree recursively.

return isSameTree(p->left, q->left)

&& isSameTree(p->right, q->right);

}

};

Java

// Author: Huahua

class Solution {

public boolean isSameTree(TreeNode p, TreeNode q) {

if (p == null && q == null) return true;

if (p == null || q == null) return false;

return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

}

Python3

"""

Author: Huahua

"""

class Solution:

def isSameTree(self, p, q):

if not p and not q: return True

if not p or not q: return False

return all((p.val == q.val,

self.isSameTree(p.left, q.left),

self.isSameTree(p.right, q.right)))

Follow Up

花花酱 LeetCode 572. Subtree of Another Tree

花花酱 LeetCode 486. Predict the Winner

By zxi on March 24, 2017

Problem

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

Example 1:
Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2.
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.
Hence, player 1 will never be the winner and you need to return False.

Example 2:
Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
Note:
1 <= length of the array <= 20.
Any scores in the given array are non-negative integers and will not exceed 10,000,000.
If the scores of both players are equal, then player 1 is still the winner.

Solution 1: Recursion

Time complexity: O(2^n)

Space complexity: O(n)

// Author: Huahua

// Running time: 67 ms

class Solution {

public:

bool PredictTheWinner(vector<int>& nums) {

return getScore(nums, 0, nums.size() - 1) >= 0;

}

private:

// Max diff (my_score - op_score) of subarray nums[l] ~ nums[r].

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

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

return max(nums[l] - getScore(nums, l + 1, r),

nums[r] - getScore(nums, l, r - 1));

}

};

Solution 2: Recursion + Memoization

Time complexity: O(n^2)

Space complexity: O(n)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool PredictTheWinner(vector<int>& nums) {

m_ = vector<vector<int>>(nums.size(), vector<int>(nums.size(), INT_MIN));

return getScore(nums, 0, nums.size() - 1) >= 0;

}

private:

vector<vector<int>> m_;

// Max diff (my_score - op_score) of subarray nums[l] ~ nums[r].

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

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

if (m_[l][r] != INT_MIN) return m_[l][r];

m_[l][r] = max(nums[l] - getScore(nums, l + 1, r),

nums[r] - getScore(nums, l, r - 1));

return m_[l][r];

}

};

DP version

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool PredictTheWinner(vector<int>& nums) {

const int n = nums.size();

vector<vector<int>> dp(n, vector<int>(n, INT_MIN));

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

dp[i][i] = nums[i];

for (int l = 2; l <= n; ++l)

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

int j = i + l - 1;

dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);

}

return dp[0][n - 1] >= 0;

}

};

Related Problem

花花酱 LeetCode 877. Stone Game

花花酱 LeetCode 451. Sort Characters By Frequency

By zxi on March 18, 2017

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:

"tree"

Output:

"eert"

Explanation:

'e' appears twice while 'r' and 't' both appear once.

So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input:

"cccaaa"

Output:

"cccaaa"

Explanation:

Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.

Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:

"Aabb"

Output:

"bbAa"

Explanation:

"bbaA" is also a valid answer, but "Aabb" is incorrect.

Note that 'A' and 'a' are treated as two different characters.

Solution:

class Solution {

public:

string frequencySort(string s) {

map<char, int> f;

for(char c:s) ++f[c];

vector<pair<int,char>> v;

for(auto& kv : f)

v.push_back({kv.second, kv.first});

sort(v.rbegin(), v.rend());

stringstream ans;

for(auto& kv : v)

ans << string(kv.first, kv.second);

return ans.str();

}

};

花花酱 LeetCode 520. Detect Capital

By zxi on March 18, 2017

Given a word, you need to judge whether the usage of capitals in it is right or not.

We define the usage of capitals in a word to be right when one of the following cases holds:

All letters in this word are capitals, like “USA”.
All letters in this word are not capitals, like “leetcode”.
Only the first letter in this word is capital if it has more than one letter, like “Google”.

Otherwise, we define that this word doesn’t use capitals in a right way.

Example 1:

1 2	<b>Input:</b> "USA" <b>Output:</b> True

Example 2:

1 2	<b>Input:</b> "FlaG" <b>Output:</b> False

Note: The input will be a non-empty word consisting of uppercase and lowercase latin letters.

class Solution {

public:

bool detectCapitalUse(string word) {

int n = std::count_if(word.begin(), word.end(), ::isupper);

return n == 0 || (n == 1 && isupper(word[0])) || n == word.length();

}

};

花花酱 LeetCode 422. Find All Duplicates in an Array

By zxi on March 18, 2017

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

Input:

[4,3,2,7,8,2,3,1]

Output:

[2,3]

class Solution {

public:

vector<int> findDuplicates(vector<int>& nums) {

vector<int> ans;

for(auto num : nums) {

int index = abs(num)-1;

if (nums[index] < 0)

ans.push_back(index+1);

nums[index]*=-1;

}

return ans;

}

};

Huahua's Tech Road

花花酱 Leetcode 100. Same Tree

Problem:

Example 1:

Example 2:

Example 3:

Solution: Recursion

C++

Java

Python3

Follow Up

花花酱 LeetCode 486. Predict the Winner

Problem

Solution 1: Recursion

Solution 2: Recursion + Memoization

Related Problem

花花酱 LeetCode 451. Sort Characters By Frequency

花花酱 LeetCode 520. Detect Capital

花花酱 LeetCode 422. Find All Duplicates in an Array