花花酱 LeetCode 415. Add Strings

By zxi on March 17, 2018

Problem

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

The length of both num1 and num2 is < 5100.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

Solution: Brute Force

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

string addStrings(string num1, string num2) {

if (num1.length() < num2.length()) swap(num1, num2);

num1 = "0" + num1;

int l1 = num1.length();

int l2 = num2.length();

for (int i = 0; i < l1 - 1; ++i) {

if (i < l2) num1[l1 - i - 1] += (num2[l2 - i - 1] - '0');

if (num1[l1 - i - 1] > '9') {

num1[l1 - i - 1] -= 10;

++num1[l1 - i - 2];

}

return (num1[0] != '0') ? num1 : num1.substr(1);

}

};

花花酱 LeetCode 414. Third Maximum Number

By zxi on March 17, 2018

Problem

https://leetcode.com/problems/third-maximum-number/description/

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:

Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.

Example 2:

Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

Solution: Set

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int thirdMax(vector<int>& nums) {

set<int> s;

for (int num : nums) {

s.insert(num);

if (s.size() > 3) s.erase(s.begin());

}

return s.size() != 3 ? *s.rbegin() : *s.begin();

}

};

Python3

"""

Author: Huahua

Running time: 52 ms

"""

class Solution:

def thirdMax(self, nums):

s = set()

for num in nums:

s.add(num)

if len(s) > 3: s.remove(min(s))

return min(s) if len(s) == 3 else max(s)

花花酱 LeetCode 413. Arithmetic Slices

By zxi on March 17, 2018

题目大意：返回所有子数组中等差数列的个数。

Problem

https://leetcode.com/problems/arithmetic-slices/description/

A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequence:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], …, A[Q – 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.

Example:

A = [1, 2, 3, 4]

return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

Solution 0: Reduction

Reduce the problem to # of all 1 sub arrays.

B[i – 2] = is_slice(A[i], A[i+1], A[i+2])

Time Complexity: O(n)

Space Complexity: O(n)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int numberOfArithmeticSlices(vector<int>& A) {

if (A.size() < 3) return 0;

vector<int> B(A.size() - 2, 0);

for (int i = 2; i < A.size() ; ++i) {

if (A[i - 1] - A[i - 2] == A[i] - A[i - 1])

B[i - 2] = 1;

}

return all1SubArrays(B);

}

private:

// return number of arrays whose values are all ones.

int all1SubArrays(const vector<int>& A) {

int sum = 0;

int curr = 0;

for (int i = 0; i < A.size(); ++i)

if (A[i]) sum += ++curr;

else curr = 0;

return sum;

}

};

Solution 1: Combined

C++

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int numberOfArithmeticSlices(vector<int>& A) {

int sum = 0;

int curr = 0;

for (int i = 2; i < A.size() ; ++i) {

if (A[i - 1] - A[i - 2] == A[i] - A[i - 1]) {

sum += ++curr;

} else {

curr = 0;

}

return sum;

}

};

Problem:

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads “3:25”.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

Note:

The order of output does not matter.
The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.

Solution 1:

Time complexity: O(11*59*n)

C++

// Author: Huahua

// Running time: 2 ms (beats 100%)

class Solution {

public:

vector<string> readBinaryWatch(int num) {

vector<string> ans;

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

for (int h : nums(i, 12))

for (int m : nums(num - i, 60))

ans.push_back(to_string(h) + (m < 10 ? ":0" : ":") + to_string(m));

return ans;

}

private:

// Return numbers in [0,r) that has b 1s in their binary format.

vector<int> nums(int b, int r) {

vector<int> ans;

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

if (__builtin_popcount(n) == b) ans.push_back(n);

return ans;

}

};

花花酱 LeetCode 415. Add Strings

Problem

Solution: Brute Force

花花酱 LeetCode 414. Third Maximum Number

Problem

Solution: Set

花花酱 LeetCode 413. Arithmetic Slices

Problem

Example:

Solution 0: Reduction

Solution 1: Combined

Related Problems:

花花酱 LeetCode 401. Binary Watch

Problem:

Solution 1:

Huahua's Tech Road

花花酱 LeetCode 415. Add Strings

Problem

Solution: Brute Force

花花酱 LeetCode 414. Third Maximum Number

Problem

Solution: Set

花花酱 LeetCode 413. Arithmetic Slices

Problem

Example:

Solution 0: Reduction

Solution 1: Combined

Related Problems:

花花酱 LeetCode 401. Binary Watch

Problem:

Solution 1:

花花酱 LeetCode 382. Linked List Random Node

Problem:

Solution: