花花酱 LeetCode 507. Perfect Number

By zxi on March 22, 2018

Problem

题目大意：判断一个数的因数和是不是等于它本身。

https://leetcode.com/problems/perfect-number/description/

We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself.

Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.

Example:

Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14

Note: The input number n will not exceed 100,000,000. (1e8)

Solution: Brute Force

Try allnumbers from 1 to n – 1.

Time complexity: O(n) TLE for prime numbers

Space complexity: O(1)

Solution: Math

Try all numbers from 2 to sqrt(n).

If number i is a divisor of n then n/i is another one.

Be careful about the case when i == n/i, only one should be added to the sum.

Time complexity: O(sqrt(n))

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

bool checkPerfectNumber(int num) {

if (num <= 1) return false;

int sum = 1;

for (int i = 2; i <= sqrt(num); ++i)

if (num % i == 0) sum += i + ((i == num / i) ? 0 : num / i);

return sum == num;

}

};

花花酱 LeetCode 541. Reverse String II

By zxi on March 21, 2018

Problem

题目大意：把字符串分成块，每块长度2k，单独反转每一块的前k的字符。

https://leetcode.com/problems/reverse-string-ii/description/

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.Example:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

Restrictions:

The string consists of lower English letters only.
Length of the given string and k will in the range [1, 10000]

Solution

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

string reverseStr(string s, int k) {

const int n = s.length();

for (int i = 0; i <= n / k; i += 2)

std::reverse(s.begin() + i * k, s.begin() + min(n, (i + 1) * k));

return s;

}

};

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;

}

};

Posts tagged as “easy”

花花酱 LeetCode 507. Perfect Number

Problem

Solution: Brute Force

Solution: Math

花花酱 LeetCode 541. Reverse String II

Problem

Solution

Related Problems

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