Posts tagged as “easy”

花花酱 LeetCode 172. Factorial Trailing Zeroes

By zxi on March 6, 2018

题目大意：求n!末尾0的个数。

Problem:

https://leetcode.com/problems/factorial-trailing-zeroes/description/

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Idea:

All trailing zeros are come from even_num x 5, we have more even_num than 5, so only count factor 5.

4! = 1x2x3x4 = 24, we haven’t encountered any 5 yet, so we don’t have any trailing zero.

5! = 1x2x3x4x5 = 120, we have one trailing zero. either 2×5, or 4×5 can contribute to that zero.

9! = 362880, we only encountered 5 once, so 1 trailing zero as expected.

10! = 3628800, 2 trailing zeros, since we have two numbers that have factor 5, one is 5 and the other is 10 (2×5)

What about 100! then?

100/5 = 20, we have 20 numbers have factor 5: 5, 10, 15, 20, 25, …, 95, 100.

Is the number of trailing zero 20? No, it’s 24, why?

Within that 20 numbers, we have 4 of them: 25 (5×5), 50 (2x5x5), 75 (3x5x5), 100 (4x5x5) that have an extra factor of 5.

So, for a given number n, we are looking how many numbers <=n have factor 5, 5×5, 5x5x5, …

Summing those numbers up we got the answer.

e.g. 1000! has 249 trailing zeros:

1000/5 = 200

1000/25 = 40

1000/125 = 8

1000/625 = 1

200 + 40 + 8 + 1 = 249

alternatively, we can do the following

1000/5 = 200

200/5 = 40

40/5 = 8

8/5 = 1

1/5 = 0

200 + 40 + 8 + 1 + 0 = 249

Solution 1: Recursion

Time complexity: O(log5(n))

Space complexity: O(log5(n))

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int trailingZeroes(int n) {

return n < 5 ? 0 : n /5 + trailingZeroes(n / 5);

}

};

Java

// Author: Huahua

// Running time: 1 ms

class Solution {

public int trailingZeroes(int n) {

return n < 5 ? 0 : n /5 + trailingZeroes(n / 5);

}

Python3

"""

Author: Huahua

Running time: 68 ms

"""

class Solution:

def trailingZeroes(self, n):

return 0 if n < 5 else n // 5 + self.trailingZeroes(n // 5)

Related Problems:

花花酱 LeetCode 793. Preimage Size of Factorial Zeroes Function

花花酱 LeetCode 696. Count Binary Substrings

By zxi on March 6, 2018

题目大意：给你一个二进制的字符串，问有多少子串的0个数量等于1的数量。

Problem:

https://leetcode.com/problems/count-binary-substrings/description/

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: "00110011"

Output: 6

Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".

Notice that some of these substrings repeat and are counted the number of times they occur.

Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.

Example 2:

Input: "10101"

Output: 4

Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

Note:

s.length will be between 1 and 50,000.
s will only consist of “0” or “1” characters.

Solution 0: Search

Try all possible substrings and check whether it’s a valid one or not.

Time complexity O(2^n * n) TLE

Space complexity: O(n)

Solution 1: Running Length

For S = “000110”, there are two virtual blocks “[00011]0” and “000[110]” which contains consecutive 0s and 1s or (1s and 0s)

Keep tracking of the running length of 0, 1 for each block

“00011” => ‘0’: 3, ‘1’:2

ans += min(3, 2) => ans = 2 (“[0011]”, “0[01]1”)

“110” => ‘0’: 1, ‘1’: 2

ans += min(1, 2) => ans = 3 (“[0011]”, “0[01]1”, “1[10]”)

We can reuse part of the running length from last block.

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 43 ms

class Solution {

public:

int countBinarySubstrings(string s) {

vector<int> lens(128, 0);

int i = 0;

int l = 0;

int ans = 0;

while (true) {

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

lens[s[l]] = i - l;

ans += min(lens['0'], lens['1']);

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

lens[s[i]] = 0;

l = i;

}

return ans;

}

};

花花酱 LeetCode 575. Distribute Candies

By zxi on March 5, 2018

题目大意：有一些不同种类的糖果，男生女生各得一半数量的糖果，问女生最多可能得到多少种不同种类的糖果。

Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain.

Example 1:

Input: candies = [1,1,2,2,3,3]

Output: 3

Explanation:

There are three different kinds of candies (1, 2 and 3), and two candies for each kind.

Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too.

The sister has three different kinds of candies.

Example 2:

Input: candies = [1,1,2,3]

Output: 2

Explanation: For example, the sister has candies [2,3] and the brother has candies [1,1].

The sister has two different kinds of candies, the brother has only one kind of candies.

Note:

The length of the given array is in range [2, 10,000], and will be even.
The number in given array is in range [-100,000, 100,000].

Solution 1: Greedy

Give all unique candies to sisters until they have n/2 candies.

Time complexity: O(n)

Space complexity: O(n)

C++ Hashset

// Author: Huahua

// Running time: 258 ms

class Solution {

public:

int distributeCandies(vector<int>& candies) {

unordered_set<int> kinds(candies.begin(), candies.end());

return min(kinds.size(), candies.size() / 2);

}

};

C++ Bitset

// Author: Huahua

// Running time: 195 ms (beats 97.61%)

class Solution {

public:

int distributeCandies(vector<int>& candies) {

constexpr int kMaxKinds = 200001;

constexpr int kOffset = 100000;

bitset<kMaxKinds> s;

for (int candy : candies)

if (!s.test(candy + kOffset))

s.set(candy + kOffset);

return std::min(s.count(), candies.size() / 2);

}

};

花花酱 LeetCode 788 Rotated Digits

By zxi on February 24, 2018

题目大意：

给一个字符串，独立旋转每个数字180°，判断得到的新字符串是否合法。

出现数字3,4,7一定不合法
新字符串 == 原来字符串不合法

X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from X. A number is valid if each digit remains a digit after rotation. 0, 1, and 8 rotate to themselves; 2 and 5 rotate to each other; 6 and 9 rotate to each other, and the rest of the numbers do not rotate to any other number.

Now given a positive number N, how many numbers X from 1 to N are good?

Example:

Input: 10

Output: 4

Explanation:

There are four good numbers in the range [1, 10] : 2, 5, 6, 9.

Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.

Note:

N will be in range [1, 10000].

Solution 1: Brute Force

Time complexity: O(nlogn)

C++

// Author: Huahua

// Running time: 21 ms

class Solution {

public:

int isValid(int n) {

string s = to_string(n);

string t(s);

for (int i = 0; i < s.length(); ++i) {

if (s[i] == '3' || s[i] == '4' || s[i] == '7')

return 0;

else if (s[i] == '2') t[i] = '5';

else if (s[i] == '5') t[i] = '2';

else if (s[i] == '6') t[i] = '9';

else if (s[i] == '9') t[i] = '6';

}

return t != s;

}

int rotatedDigits(int N) {

int ans = 0;

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

ans += isValid(i);

return ans;

}

};

Bit Operation

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int isValid(int n) {

constexpr int kInValidMask = (1 << 3) | (1 << 4) | (1 << 7);

constexpr int kValidMask = (1 << 2) | (1 << 5) | (1 << 6) | (1 << 9);

int valid = 0;

while (n > 0) {

int r = 1 << (n % 10);

if (r & kInValidMask)

return 0;

else if (r & kValidMask)

valid = 1;

n /= 10;

}

return valid;

}

int rotatedDigits(int N) {

int ans = 0;

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

ans += isValid(i);

return ans;

}

};

花花酱 LeetCode 784. Letter Case Permutation

By zxi on February 20, 2018

题目大意：给你一个字符串，每个字母可以变成大写也可以变成小写。让你输出所有可能字符串。

Given a string S, we can transform every letter individually to be lowercase or uppercase to create another string. Return a list of all possible strings we could create.

Examples:

Input: S = "a1b2"

Output: ["a1b2", "a1B2", "A1b2", "A1B2"]

Input: S = "3z4"

Output: ["3z4", "3Z4"]

Input: S = "12345"

Output: ["12345"]

Note:

S will be a string with length at most 12.
S will consist only of letters or digits.

Solution 1: DFS

Time complexity: O(n*2^l), l = # of letters in the string

Space complexity: O(n) + O(n*2^l)

C++

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

vector<string> letterCasePermutation(string S) {

vector<string> ans;

dfs(S, 0, ans);

return ans;

}

private:

void dfs(string& S, int s, vector<string>& ans) {

if (s == S.length()) {

ans.push_back(S);

return;

}

dfs(S, s + 1, ans);

if (!isalpha(S[s])) return;

S[s] ^= (1 << 5);

dfs(S, s + 1, ans);

S[s] ^= (1 << 5);

}

};

Java

// Author: Huahua

// Running time: 8 ms

class Solution {

public List<String> letterCasePermutation(String S) {

List<String> ans = new ArrayList<>();

dfs(S.toCharArray(), 0, ans);

return ans;

}

private void dfs(char[] S, int i, List<String> ans) {

if (i == S.length) {

ans.add(new String(S));

return;

}

dfs(S, i + 1, ans);

if (!Character.isLetter(S[i])) return;

S[i] ^= 1 << 5;

dfs(S, i + 1, ans);

S[i] ^= 1 << 5;

}

Python 3

"""

Author: Huahua

Running time: 92 ms

"""

class Solution:

def letterCasePermutation(self, S):

ans = []

def dfs(S, i, n):

if i == n:

ans.append(''.join(S))

return

dfs(S, i + 1, n)

if not S[i].isalpha(): return

S[i] = chr(ord(S[i]) ^ (1<<5))

dfs(S, i + 1, n)

S[i] = chr(ord(S[i]) ^ (1<<5))

dfs(list(S), 0, len(S))

return ans