Posts tagged as “easy”

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

Idea: DFS

Use DFS to find a connected component (an island) and mark all the nodes to 0.

Time complexity: O(mn)

Space complexity: O(mn)

Solution

C++

// Author: Huahua

// Time complexity: O(mn)

// Running time: 6 ms

class Solution {

public:

int numIslands(vector<vector<char>>& grid) {

if (grid.empty()) return 0;

int m = grid.size();

int n = grid[0].size();

int ans = 0;

for (int y = 0; y < m; ++y)

for (int x = 0; x < n; ++x) {

ans += grid[y][x] - '0';

dfs(grid, x, y, m, n);

}

return ans;

}

private:

void dfs(vector<vector<char>>& grid, int x, int y, int m, int n) {

if (x < 0 || y < 0 || x >= n || y >= m || grid[y][x] == '0')

return;

grid[y][x] = '0';

dfs(grid, x + 1, y, m, n);

dfs(grid, x - 1, y, m, n);

dfs(grid, x, y + 1, m, n);

dfs(grid, x, y - 1, m, n);

}

};

Java

// Author: Huahua

// Time Complexity: O(mn)

// Running time: 13 ms

class Solution {

public int numIslands(char[][] grid) {

int m = grid.length;

if (m == 0) return 0;

int n = grid[0].length;

int ans = 0;

for (int y = 0; y < m; ++y)

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

if (grid[y][x] == '1') {

++ans;

dfs(grid, x, y, n, m);

}

return ans;

}

private void dfs(char[][] grid, int x, int y, int n, int m) {

if (x < 0 || y < 0 || x >= n || y >= m || grid[y][x] == '0')

return;

grid[y][x] = '0';

dfs(grid, x + 1, y, n, m);

dfs(grid, x - 1, y, n, m);

dfs(grid, x, y + 1, n, m);

dfs(grid, x, y - 1, n, m);

}

Python

"""

Author: Huahua

Time Complexity: O(mn)

Running Time: 102 ms

"""

class Solution(object):

def numIslands(self, grid):

"""

:type grid: List[List[str]]

:rtype: int

"""

m = len(grid)

if m == 0: return 0

n = len(grid[0])

ans = 0

for y in xrange(m):

for x in xrange(n):

if grid[y][x] == '1':

ans += 1

self.__dfs(grid, x, y, n, m)

return ans

def __dfs(self, grid, x, y, n, m):

if x < 0 or y < 0 or x >=n or y >= m or grid[y][x] == '0':

return

grid[y][x] = '0'

self.__dfs(grid, x + 1, y, n, m)

self.__dfs(grid, x - 1, y, n, m)

self.__dfs(grid, x, y + 1, n, m)

self.__dfs(grid, x, y - 1, n, m)

Posts tagged as “easy”

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

花花酱 LeetCode 200. Number of Islands

Idea: DFS

Solution

C++

Java

Python

Related Problems

花花酱 LeetCode 680. Valid Palindrome II