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

}

};

Posts tagged as “easy”

花花酱 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 541. Reverse String II

Problem

Solution

Related Problems