花花酱 LeetCode 539. Minimum Time Difference

By zxi on March 21, 2018

Problem

Given a list of 24-hour clock time points in “Hour:Minutes” format, find the minimum minutes difference between any two time points in the list.

Example 1:

Input: ["23:59","00:00"]
Output: 1

Note:

The number of time points in the given list is at least 2 and won’t exceed 20000.
The input time is legal and ranges from 00:00 to 23:59.

Solution

Time complexity: O(nlog1440)

Space complexity: O(n)

C++

// Author: huahua

// Running time: 16 ms

class Solution {

public:

int findMinDifference(vector<string>& timePoints) {

constexpr int kMins = 24 * 60;

set<int> seen;

for (const string& time : timePoints) {

int m = stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3));

if (!seen.insert(m).second) return 0;

}

int ans = (*seen.begin() - *seen.rbegin() + kMins) % kMins;

const int* l = nullptr;

for (const int& t : seen) {

if (l) ans = min(ans, t - *l);

l = &t;

}

return ans;

}

};

花花酱 LeetCode 538. Convert BST to Greater Tree

By zxi on March 21, 2018

Problem

题目大意：把二叉搜索树的每个节点加上比他大的节点的和。

https://leetcode.com/problems/convert-bst-to-greater-tree/description/

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Example:

Input: The root of a Binary Search Tree like this:
              5
            /   \
           2     13

Output: The root of a Greater Tree like this:
             18
            /   \
          20     13

Solution: reversed inorder traversal

in a BST, we can visit every node in the decreasing order. Using a member sum to track the sum of all visited nodes.

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 56 ms

class Solution {

public:

TreeNode* convertBST(TreeNode* root) {

sum = 0;

inorder(root);

return root;

}

private:

int sum;

void rinorder(TreeNode* root) {

if (root == nullptr) return;

rinorder(root->right);

root->val = (sum += root->val);

rinorder(root->left);

}

};

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

}

};

Posts tagged as “easy”

花花酱 LeetCode 539. Minimum Time Difference

Problem

Solution

花花酱 LeetCode 538. Convert BST to Greater Tree

Problem

Solution: reversed inorder traversal

花花酱 LeetCode 598. Range Addition II

Problem

Solution:

花花酱 LeetCode 572. Subtree of Another Tree

Problem

Solution: Recursion

Related Problems

花花酱 LeetCode 461. Hamming Distance

Problem

Solution: Bit Operation

Related Problems