Posts tagged as “easy”

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

花花酱 LeetCode 771. Jewels and Stones

By zxi on February 2, 2018

题目大意：给你宝石的类型，再给你一堆石头，返回里面宝石的数量。

Problem:

You’re given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1:

Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

Input: J = "z", S = "ZZ"
Output: 0

Note:

S and J will consist of letters and have length at most 50.
The characters in J are distinct.

Solution 1: HashTable

Time complexity: O(|J| + |S|)

Space complexity: O(128) / O(|J|)

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int numJewelsInStones(string J, string S) {

std::vector<int> f(128, 0);

int ans = 0;

for (const char j : J)

f[j] = 1;

for (const char s : S)

ans += f[s] & 1;

return ans;

}

};

C++ v2

// Author: Huahua

// Running time: 10 ms

class Solution {

public:

int numJewelsInStones(const string& J, const string& S) {

std::set<char> f(J.begin(), J.end());

return std::count_if(S.begin(), S.end(),

[&f](const char c) { return f.count(c); });

}

};

Java

// Author: Huahua

// Running time: 18 ms

class Solution {

public int numJewelsInStones(String J, String S) {

int[] f = new int[128];

for (final char c : J.toCharArray())

f[c] = 1;

int ans = 0;

for (final char c : S.toCharArray())

ans += f[c];

return ans;

}

Python

"""

Author: Huahua

Running time: 43 ms

"""

class Solution(object):

def numJewelsInStones(self, J, S):

f = set(J)

return sum([s in f for s in S])

花花酱 LeetCode. 69 Sqrt(x)

By zxi on January 16, 2018

题目大意：让你实现开根号函数，只需要返回整数部分。

Problem:

Implement int sqrt(int x).

Compute and return the square root of x.

x is guaranteed to be a non-negative integer.

Example 1:

1 2	Input: 4 Output: 2

Example 2:

Input: 8

Output: 2

Explanation: The square root of 8 is 2.82842...

Solution 1: Brute force

Time complexity: sqrt(x)

C++

// Author: Huahua

// Running time: 40 ms

class Solution {

public:

int mySqrt(int x) {

if (x <= 1) return x;

for (long long s = 1; s <= x; ++s)

if (s * s > x) return s - 1;

return -1;

}

};

C++ div

// Author: Huahua

// Running time: 162 ms

class Solution {

public:

int mySqrt(int x) {

if (x <= 1) return x;

for (int s = 1; s <= x; ++s)

if (s > x / s) return s - 1;

return -1;

}

};

Java

// Author: Huahua

// Running time: 71 ms

class Solution {

public int mySqrt(int x) {

if (x <= 1) return x;

for (long s = 1; s <= x; ++s)

if (s * s > x) return (int)s - 1;

return -1;

}

Python3 TLE

"""

Author: Huahua

TLE: 602 / 1017 test cases passed.

"""

class Solution:

def mySqrt(self, x):

if x <= 1: return x

s = 1

while True:

if s*s > x: return s - 1

s += 1

return -1

Solution 2: Binary search

Time complexity: O(logn)

C++

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int mySqrt(int x) {

long l = 1;

long r = static_cast<long>(x) + 1;

while (l < r) {

long m = l + (r - l) / 2;

if (m * m > x) {

r = m;

} else {

l = m + 1;

}

// l: smallest number such that l * l > x

return l - 1;

}

};

Java

// Author: Huahua

// Running time: 47 ms

class Solution {

public int mySqrt(int x) {

int l = 1;

int r = x;

while (l <= r) {

int m = l + (r - l) / 2;

if (m > x / m) {

r = m - 1;

} else {

l = m + 1;

}

return r;

}

Python3

"""

Author: Huahua

Running time: 119 ms

"""

class Solution:

def mySqrt(self, a):

l = 1

r = a

while l <= r:

m = l + (r - l) // 2

if m * m > a:

r = m - 1

else:

l = m + 1

return r;

Solution 3: Newton’s method

C++ / float

// Author: Huahua

// Running time: 28 ms

class Solution {

public:

int mySqrt(int a) {

constexpr double epsilon = 1e-2;

double x = a;

while (x * x - a > epsilon) {

x = (x + a / x) / 2.0;

}

return x;

}

};

C++ / int

// Author: Huahua

// Running time: 27 ms

class Solution {

public:

int mySqrt(int a) {

// f(x) = x^2 - a, find root of f(x)

// Newton's method

// f'(x) = 2x

// x' = x - f(x) / f'(x) = x - (1/2*x - a/(2*x))

// = (x + a / x) / 2

int x = a;

while (x > a / x)

x = (x + a / x) / 2;

return x;

}

};

Java

// Author: Huahua

// Running time: 44 ms

class Solution {

public int mySqrt(int a) {

long x = a;

while (x * x > a)

x = (x + a / x) / 2;

return (int)x;

}

Python3

"""

Author: Huahua

Running time: 100 ms

"""

class Solution:

def mySqrt(self, a):

x = a

while x * x > a:

x = (x + a // x) // 2

return x

花花酱 LeetCode 746. Min Cost Climbing Stairs

By zxi on December 17, 2017

Problem:

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Example 1:

Input: cost = [10, 15, 20]

Output: 15

Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

Example 2:

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]

Output: 6

Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

Note:

cost will have a length in the range [2, 1000].
Every cost[i] will be an integer in the range [0, 999].

题目大意:

有一个楼梯，要离开i层需要付cost[i]的费用，每次可以爬1层或2层。问你最少花多少钱能够达到顶楼。

Solution:

C++ / Recursion + Memorization 记忆化递归

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

int minCostClimbingStairs(vector<int>& cost) {

vector<int> m(cost.size() + 1);

return dp(cost, m, cost.size());

}

private:

// min cost to climb to i-th step

int dp(vector<int>& cost, vector<int>& m, int i) {

if (i <= 1) return 0;

if (m[i] > 0) return m[i];

return m[i] = min(dp(cost, m, i - 1) + cost[i - 1],

dp(cost, m, i - 2) + cost[i - 2]);

}

};

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

int minCostClimbingStairs(vector<int>& cost) {

vector<int> m(cost.size() + 1);

return min(dp(cost, m, cost.size() - 1),

dp(cost, m, cost.size() - 2));

}

private:

// min cost before leaving i-th step

int dp(vector<int>& cost, vector<int>& m, int i) {

if (i < 0) return 0;

if (m[i] > 0) return m[i];

return m[i] = min(dp(cost, m, i - 1), dp(cost, m, i - 2)) + cost[i];

}

};

C++ / DP 动态规划

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

int minCostClimbingStairs(vector<int>& cost) {

const int n = cost.size();

vector<int> dp(n, INT_MAX); // d[i] min cost before leaving i

dp[0] = cost[0];

dp[1] = cost[1];

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

dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];

// We can reach top from either n - 1, or n - 2

return min(dp[n - 1], dp[n - 2]);

}

};

// Author: Huahua

// Runtime: 12 ms

class Solution {

public:

int minCostClimbingStairs(vector<int>& cost) {

// dp[i] : min cost to climb to n-th step

vector<int> dp(cost.size() + 1, 0);

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

dp[i] = min(dp[i - 1] + cost[i - 1],

dp[i - 2] + cost[i - 2]);

return dp[cost.size()];

}

};

O(1) Space

// Author: Huahua

// Runtime: 15 ms

class Solution {

public:

int minCostClimbingStairs(vector<int>& cost) {

int dp1 = 0;

int dp2 = 0;

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

int dp = min(dp1 + cost[i - 1], dp2 + cost[i - 2]);

dp2 = dp1;

dp1 = dp;

}

return dp1;

}

};

花花酱 LeetCode 1. Two Sum

By zxi on November 23, 2017

Problem:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Idea:

Brute force / Hashtable

Solution1:

Brute force / C++

Time complexity: O(n^2)

Space complexity: O(1)

// Author: Huahua

// Runtime: 166 ms

class Solution {

public:

vector<int> twoSum(vector<int>& nums, int target) {

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

for (int j = i + 1;j < nums.size(); ++j) {

int sum = nums[i] + nums[j];

if (sum == target) {

return {i, j};

}

return {};

}

};

Solution 2:

Hashtable / C++

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

vector<int> twoSum(vector<int>& nums, int target) {

unordered_map<int, int> indies;

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

indies[nums[i]] = i;

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

int left = target - nums[i];

if (indies.count(left) && indies[left] != i) {

return {i, indies[left]};

}

return {};

}

};