花花酱 LeetCode 434. Number of Segments in a String

By zxi on March 23, 2018

Problem

题目大意：返回字符串中的非空白字符连续的字串数量。

https://leetcode.com/problems/number-of-segments-in-a-string/description/

Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.

Please note that the string does not contain any non-printable characters.

Example:

Input: "Hello, my name is John"
Output: 5

Solution

Be aware of special cases: like ” “.

Time complexity: O(n)

Space complexity: O(1)

C++

class Solution {

public:

int countSegments(string s) {

if (s.empty()) return 0;

int ans = 0;

int i = 0;

while (i < s.length()) {

while (i < s.length() && s[i] == ' ') ++i;

if (i == s.length()) break;

while (i < s.length() && s[i] != ' ') ++i;

++ans;

++i;

}

return ans;

}

};

Python3

"""

Author: Huahua

Running time: 40 ms

"""

class Solution:

def countSegments(self, s):

return len(s.split())

花花酱 LeetCode 94. Binary Tree Inorder Traversal

By zxi on March 23, 2018

Problem

Given a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree [1,null,2,3],

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

Solution: Recursion

Time complexity: O(n)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

vector<int> inorderTraversal(TreeNode* root) {

vector<int> ans;

inorderTraversal(root, ans);

return ans;

}

private:

void inorderTraversal(TreeNode* root, vector<int>& ans) {

if (root == nullptr) return;

inorderTraversal(root->left, ans);

ans.push_back(root->val);

inorderTraversal(root->right, ans);

}

};

Solution 2: Iterative

// Author: Huahua

// Running time: 3 ms

lass Solution {

public:

vector<int> inorderTraversal(TreeNode* root) {

if (root == nullptr) return {};

vector<int> ans;

stack<TreeNode*> s;

TreeNode* curr = root;

while (curr != nullptr || !s.empty()) {

while (curr != nullptr) {

s.push(curr);

curr = curr->left;

}

curr = s.top(); s.pop();

ans.push_back(curr->val);

curr = curr->right;

}

return ans;

}

};

花花酱 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 560. Subarray Sum Equals K

By zxi on March 22, 2018

Problem

题目大意：给你一个数组，问有多少子数组的和为k。

https://leetcode.com/problems/subarray-sum-equals-k/description/

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Note:

The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Solution -1: Brute Force

For every pair of i,j, check sum(nums[i:j]) in O(j-i) = O(n)

Time complexity: O(n^3) TLE

Space complexity: O(1)

Solution 0: Brute Force + Prefix sun

Precompute the prefix sum and check sum of nums[i:j] in O(1)

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 490 ms

class Solution {

public:

int subarraySum(vector<int>& nums, int k) {

const int n = nums.size();

vector<int> sums(n + 1, 0);

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

sums[i] = sums[i - 1] + nums[i - 1];

int ans = 0;

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

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

if (sums[j + 1] - sums[i] == k) ++ans;

return ans;

}

};

Solution 1: Running Prefix sum

Keep tracking the prefix sums and their counts.

s -> count: how many arrays nums[0:j] (j < i) that has sum of s

cur_sum = sum(nums[0:i])

check how many arrays nums[0:j] (j < i) that has sum (cur_sum – k)

then there are the same number of arrays nums[j+1: i] that have sum k.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 36 ms

class Solution {

public:

int subarraySum(vector<int>& nums, int k) {

if (nums.empty()) return 0;

unordered_map<int, int> counts{{0,1}};

int cur_sum = 0;

int ans = 0;

for (const int num : nums) {

cur_sum += num;

ans += counts[cur_sum - k];

++counts[cur_sum];

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 434. Number of Segments in a String

Problem

Solution

花花酱 LeetCode 94. Binary Tree Inorder Traversal

Problem

Solution: Recursion

Solution 2: Iterative

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

Problem

Solution

花花酱 LeetCode 507. Perfect Number

Problem

Solution: Brute Force

Solution: Math

花花酱 LeetCode 560. Subarray Sum Equals K

Problem

Solution -1: Brute Force

Solution 0: Brute Force + Prefix sun

Solution 1: Running Prefix sum