Posts tagged as “easy”

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

}

};

花花酱 LeetCode 681. Next Closest Time

By zxi on September 24, 2017

Problem:

https://leetcode.com/problems/next-closest-time/description/
no limit on how many times a digit can be reused.

You may assume the given input string is always valid. For example, “01:34”, “12:09” are all valid. “1:34”, “12:9” are all invalid.

Example 1:

Input: "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, 
which occurs 5 minutes later.  
It is not 19:33, because this occurs 23 hours and 59 minutes later.

Example 2:

Input: "23:59"
Output: "22:22"
Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. 
It may be assumed that the returned time is next day's time since it is smaller 
than the input time numerically.

Ads

Solution1: Brute force

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

string nextClosestTime(string time) {

set<char> s(time.begin(), time.end());

int hour = stoi(time.substr(0, 2));

int min = stoi(time.substr(3, 2));

while (true) {

if (++min == 60) {

min = 0;

(++hour) %= 24;

}

char buffer[5];

sprintf(buffer, "%02d:%02d", hour, min);

set<char> s2(buffer, buffer + sizeof(buffer));

if (includes(s.begin(), s.end(), s2.begin(), s2.end()))

return string(buffer);

}

return time;

}

};

Java

// Author: Huahua

// Running time: 85 ms

class Solution {

public String nextClosestTime(String time) {

int hour = Integer.parseInt(time.substring(0, 2));

int min = Integer.parseInt(time.substring(3, 5));

while (true) {

if (++min == 60) {

min = 0;

++hour;

hour %= 24;

}

String curr = String.format("%02d:%02d", hour, min);

Boolean valid = true;

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

if (time.indexOf(curr.charAt(i)) < 0) {

valid = false;

break;

}

if (valid) return curr;

}

Python

"""

Author: Huahua

Running time: 65 ms

"""

class Solution:

def nextClosestTime(self, time):

s = set(time)

hour = int(time[0:2])

minute = int(time[3:5])

while True:

minute += 1

if minute == 60:

minute = 0

hour = 0 if hour == 23 else hour + 1

time = "%02d:%02d" % (hour, minute)

if set(time) <= s:

return time

Solution 2: DFS

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

string nextClosestTime(string time) {

vector<int> d = {

time[0] - '0', time[1] - '0', time[3] - '0', time[4] - '0' };

int h = d[0] * 10 + d[1];

int m = d[2] * 10 + d[3];

vector<int> curr(4, 0);

int now = toTime(h, m);

int best = now;

dfs(0, d, curr, now, best);

char buff[5];

sprintf(buff, "%02d:%02d", best / 60, best % 60);

return string(buff);

}

private:

void dfs(int dep, const vector<int>& digits, vector<int>& curr, int time, int& best) {

if (dep == 4) {

int curr_h = curr[0] * 10 + curr[1];

int curr_m = curr[2] * 10 + curr[3];

if (curr_h > 23 || curr_m > 59) return;

int curr_time = toTime(curr_h, curr_m);

if (timeDiff(time, curr_time) < timeDiff(time, best))

best = curr_time;

return;

}

for (int digit : digits) {

curr[dep] = digit;

dfs(dep + 1, digits, curr, time, best);

}

int toTime(int h, int m) {

return h * 60 + m;

}

int timeDiff(int t1, int t2) {

if (t1 == t2) return INT_MAX;

return ((t2 - t1) + 24 * 60) % (24 * 60);

}

};

Solution 3: Brute force + Time library

Python3

"""

Author: Huahua

Running time: 292 ms

"""

from datetime import *

class Solution:

def nextClosestTime(self, time):

s = set(time)

while True:

time = (datetime.strptime(time, '%H:%M') +

timedelta(minutes=1)).strftime('%H:%M')

if set(time) <= s:

return time

Posts tagged as “easy”

花花酱 LeetCode 771. Jewels and Stones

Problem:

Example 1:

Example 2:

Solution 1: HashTable

C++

C++ v2

Java

Python

花花酱 LeetCode. 69 Sqrt(x)

Solution 1: Brute force

C++

C++ div

Java

Python3 TLE

Solution 2: Binary search

C++

Java

Python3

Solution 3: Newton’s method

C++ / float

C++ / int

Java

Python3

花花酱 LeetCode 746. Min Cost Climbing Stairs

花花酱 LeetCode 1. Two Sum

花花酱 LeetCode 681. Next Closest Time

Problem:

Example 1:

Example 2:

Solution1: Brute force

C++

Java

Python

Solution 2: DFS

C++

Solution 3: Brute force + Time library

Python3

Related Problems: