Press "Enter" to skip to content

Posts tagged as “easy”

花花酱 LeetCode 1221. Split a String in Balanced Strings

By zxi on October 13, 2019

Balanced strings are those who have equal quantity of ‘L’ and ‘R’ characters.

Given a balanced string s split it in the maximum amount of balanced strings.

Return the maximum amount of splitted balanced strings.

Example 1:

Input: s = "RLRRLLRLRL"
Output: 4
Explanation: s can be split into "RL", "RRLL", "RL", "RL", each substring contains same number of 'L' and 'R'.

Example 2:

Input: s = "RLLLLRRRLR"
Output: 3
Explanation: s can be split into "RL", "LLLRRR", "LR", each substring contains same number of 'L' and 'R'.

Example 3:

Input: s = "LLLLRRRR"
Output: 1
Explanation: s can be split into "LLLLRRRR".

Constraints:

  • 1 <= s.length <= 1000
  • s[i] = 'L' or 'R'

Solution: Greedy

Time complexity: O(n)
Space complexity: O(1)

C++

花花酱 LeetCode 122. Best Time to Buy and Sell Stock II

By zxi on October 9, 2019

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Solution: Greedy

Time complexity: O(n)
Space complexity: O(1)

C++

花花酱 LeetCode 1217. Play with Chips

By zxi on October 5, 2019

There are some chips, and the i-th chip is at position chips[i].

You can perform any of the two following types of moves any number of times (possibly zero) on any chip:

  • Move the i-th chip by 2 units to the left or to the right with a cost of 0.
  • Move the i-th chip by 1 unit to the left or to the right with a cost of 1.

There can be two or more chips at the same position initially.

Return the minimum cost needed to move all the chips to the same position (any position).

Example 1:

Input: chips = [1,2,3]
Output: 1
Explanation: Second chip will be moved to positon 3 with cost 1. First chip will be moved to position 3 with cost 0. Total cost is 1.

Example 2:

Input: chips = [2,2,2,3,3]
Output: 2
Explanation: Both fourth and fifth chip will be moved to position two with cost 1. Total minimum cost will be 2.

Constraints:

  • 1 <= chips.length <= 100
  • 1 <= chips[i] <= 10^9

Solution: Math

We can choose either:
1. move all odd positions to an arbitrary even position and move the rest to the same position
2. move all even positions to an arbitrary odd position and move the rest to the same position
ans = min(# of odd pos, # of even pos)

Time complexity: O(n)
Space complexity: O(1)

C++

花花酱 LeetCode 83. Remove Duplicates from Sorted List

By zxi on September 30, 2019

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example 1:

Input: 1->1->2
Output: 1->2

Example 2:

Input: 1->1->2->3->3
Output: 1->2->3

Solution:

Time complexity: O(n)
Space complexity: O(1)

C++

花花酱 LeetCode 58. Length of Last Word

By zxi on September 30, 2019

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

Example:

Input: "Hello World"
Output: 5

Solution:

There can be tailing spaces, e.g. “abc “, we need to trim the string first and then scan the string in reverse order until a space or reach the beginning of the string.

Time complexity: O(n)
Space complexity: O(1)

C++