花花酱 LeetCode 448. Find All Numbers Disappeared in an Array

By zxi on March 23, 2018

Problem

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

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

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

Output:
[5,6]

Solution

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 128 ms (beats 93.70%)

class Solution {

public:

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

for (size_t i = 0; i != nums.size(); ++i) {

int index = abs(nums[i]) - 1;

if (nums[index] > 0) nums[index] *= -1;

}

vector<int> ans;

for (size_t i = 0; i != nums.size(); ++i)

if (nums[i] > 0) ans.push_back(i + 1);

return ans;

}

};

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

}

};

Posts tagged as “easy”

花花酱 LeetCode 448. Find All Numbers Disappeared in an Array

Problem

Solution

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