花花酱 LeetCode 598. Range Addition II

By zxi on March 20, 2018

Problem

https://leetcode.com/problems/range-addition-ii/description/

Given an m * n matrix M initialized with all 0‘s and several update operations.

Operations are represented by a 2D array, and each operation is represented by an array with two positiveintegers a and b, which means M[i][j] should be added by one for all 0 <= i < a and 0 <= j < b.

You need to count and return the number of maximum integers in the matrix after performing all the operations.

Example 1:

Input: 
m = 3, n = 3
operations = [[2,2],[3,3]]
Output: 4
Explanation: 
Initially, M = 
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]

After performing [2,2], M = 
[[1, 1, 0],
 [1, 1, 0],
 [0, 0, 0]]

After performing [3,3], M = 
[[2, 2, 1],
 [2, 2, 1],
 [1, 1, 1]]

So the maximum integer in M is 2, and there are four of it in M. So return 4.

Note:

The range of m and n is [1,40000].
The range of a is [1,m], and the range of b is [1,n].
The range of operations size won’t exceed 10,000.

Solution:

Time Complexity: O(n)

Space Complexity: O(1)

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int maxCount(int m, int n, vector<vector<int>>& ops) {

for (const auto& range : ops) {

m = min(m, range[0]);

n = min(n, range[1]);

}

return m * n;

}

};

花花酱 LeetCode 594. Longest Harmonious Subsequence

By zxi on March 20, 2018

Problem

https://leetcode.com/problems/longest-harmonious-subsequence/description/

题目大意：找一个最长子序列，要求子序列中最大值和最小值的差是1。

We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.

Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.

Example 1:

Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

Note: The length of the input array will not exceed 20,000.

Solution1: HashTable

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

// Running time: 127 ms

class Solution {

public:

int findLHS(vector<int>& nums) {

unordered_map<int, int> counts;

int ans = 0;

for (int num : nums) {

++counts[num];

int l = counts[num - 1];

int h = counts[num + 1];

if (l || h)

ans = max(ans, counts[num] + max(l, h));

}

return ans;

}

};

// Running time: 109 ms

class Solution {

public:

int findLHS(vector<int>& nums) {

unordered_map<int, int> counts;

int ans = 0;

for (int num : nums) {

const int c = ++counts[num];

auto it1 = counts.find(num - 1);

auto it2 = counts.find(num + 1);

if (it1 != counts.end())

ans = max(ans, c + it1->second);

if (it2 != counts.end())

ans = max(ans, c + it2->second);

}

return ans;

}

};

// Author: Huahua

// Running time: 102 ms

class Solution {

public:

int findLHS(vector<int>& nums) {

unordered_map<int, int> counts;

int ans = 0;

for (int num : nums)

++counts[num];

for (const auto& p : counts) {

auto it1 = counts.find(p.first - 1);

auto it2 = counts.find(p.first + 1);

if (it1 != counts.end())

ans = max(ans, p.second + it1->second);

if (it2 != counts.end())

ans = max(ans, p.second + it2->second);

}

return ans;

}

};

花花酱 LeetCode 572. Subtree of Another Tree

By zxi on March 19, 2018

Problem

题目大意：判断一棵树是不是另外一棵树的子树。

https://leetcode.com/problems/subtree-of-another-tree/description/

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

/ \

4 5

/ \

1 2

Given tree t:

/ \

1 2

Return true, because t has the same structure and node values with a subtree of s.

Example 2:
Given tree s:

/ \

4 5

/ \

1 2

Given tree t:

/ \

1 2

Return false.

Solution: Recursion

Time complexity: O(max(n, m))

Space complexity: O(max(n, m))

C++

// Author: Huahua

// Running time: 29 ms

class Solution {

public:

bool isSubtree(TreeNode* s, TreeNode* t) {

if (t == nullptr) return true;

if (s == nullptr) return false;

if (isSameTree(s, t)) return true;

return isSubtree(s->left, t) || isSubtree(s->right, t);

}

private:

bool isSameTree(TreeNode* s, TreeNode* t) {

if (s == nullptr && t == nullptr) return true;

if (s == nullptr || t == nullptr) return false;

return (s->val == t->val)

&& isSameTree(s->left, t->left)

&& isSameTree(s->right, t->right);

}

};

Problem

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 2³¹.

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

The above arrows point to positions where the corresponding bits are different.

Solution: Bit Operation

Time complexity: O(logn)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

int hammingDistance(int x, int y) {

int ans = 0;

int t = x^y;

while (t) {

ans += t & 1;

t >>=1;

}

return ans;

}

};

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int hammingDistance(int x, int y) {

return __builtin_popcount(x ^ y);

}

};

Problem

https://leetcode.com/problems/add-one-row-to-tree/description/

Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1.

The adding rule is: given a positive integer depth d, for each NOT null tree nodes N in depth d-1, create two tree nodes with value v as N's left subtree root and right subtree root. And N's original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root’s left subtree.

Example 1:

Input: 
A binary tree as following:
       4
     /   \
    2     6
   / \   / 
  3   1 5   

v = 1

d = 2

Output: 
       4
      / \
     1   1
    /     \
   2       6
  / \     / 
 3   1   5

Example 2:

Input: 
A binary tree as following:
      4
     /   
    2    
   / \   
  3   1    

v = 1

d = 3

Output: 
      4
     /   
    2
   / \    
  1   1
 /     \  
3       1

Note:

The given d is in range [1, maximum depth of the given tree + 1].
The given binary tree has at least one tree node.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 19 ms (beats 90.85%)

class Solution {

public:

TreeNode* addOneRow(TreeNode* root, int v, int d) {

if (root == nullptr) return nullptr;

// Special case.

if (d == 1) {

TreeNode* new_root = new TreeNode(v);

new_root->left = root;

return new_root;

}

if (d == 2) {

TreeNode* l = root->left;

root->left = new TreeNode(v);

root->left->left = l;

TreeNode* r = root->right;

root->right = new TreeNode(v);

root->right->right = r;

} else {

addOneRow(root->left, v, d - 1);

addOneRow(root->right, v, d - 1);

}

return root;

}

};

花花酱 LeetCode 598. Range Addition II

Problem

Solution:

花花酱 LeetCode 594. Longest Harmonious Subsequence

Problem

Solution1: HashTable

花花酱 LeetCode 572. Subtree of Another Tree

Problem

Solution: Recursion

Related Problems

花花酱 LeetCode 461. Hamming Distance

Problem

Solution: Bit Operation

Related Problems

花花酱 LeetCode 623. Add One Row to Tree

Problem

Solution: Recursion

Huahua's Tech Road

花花酱 LeetCode 598. Range Addition II

Problem

Solution:

花花酱 LeetCode 594. Longest Harmonious Subsequence

Problem

Solution1: HashTable

花花酱 LeetCode 572. Subtree of Another Tree

Problem

Solution: Recursion

Related Problems

花花酱 LeetCode 461. Hamming Distance

Problem

Solution: Bit Operation

Related Problems

花花酱 LeetCode 623. Add One Row to Tree

Problem

Solution: Recursion