from typing import *
def check(result, expected):
assert result == expected, f"Got {result}, Expected {expected}"
Question
Given the array nums consisting of 2n elements in the form [x1,x2,...,xn,y1,y2,...,yn].
Return the array in the form [x1,y1,x2,y2,...,xn,yn].
Example 1:
Input: nums = [2,5,1,3,4,7], n = 3 Output: [2,3,5,4,1,7] Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7]. Example 2:
Input: nums = [1,2,3,4,4,3,2,1], n = 4 Output: [1,4,2,3,3,2,4,1] Example 3:
Input: nums = [1,1,2,2], n = 2 Output: [1,2,1,2]
Constraints:
1 <= n <= 500 nums.length == 2n 1 <= nums[i] <= 10^3
- Split into two lists
xandy, starting at0andn - Pair up each list by index,
(x0,y0), (x1,y1), ... (xn,yn) - Flatten list of tuple
class Solution:
def shuffle(self, nums: List[int], n: int) -> List[int]:
return [val for (x,y) in zip(nums[:n], nums[n:]) for val in (x,y)]
%%timeit
assert Solution().shuffle([2,5,1,3,4,7], 3) == [2,3,5,4,1,7]
assert Solution().shuffle([1,2,3,4,4,3,2,1], 4) == [1,4,2,3,3,2,4,1]
assert Solution().shuffle([1,1,2,2], 2) == [1,2,1,2]
Question
There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0.
You are given an integer array gain of length n where gain[i] is the net gain in altitude between points i and i + 1 for all (0 <= i < n). Return the highest altitude of a point.
Example 1:
Input: gain = [-5,1,5,0,-7] Output: 1 Explanation: The altitudes are [0,-5,-4,1,1,-6]. The highest is 1. Example 2:
Input: gain = [-4,-3,-2,-1,4,3,2] Output: 0 Explanation: The altitudes are [0,-4,-7,-9,-10,-6,-3,-1]. The highest is 0.
Constraints:
n == gain.length 1 <= n <= 100 -100 <= gain[i] <= 100
Each step is a delta. Cumulatively sum up the deltas and return the max
- Time: O(n)
- Mem: O(n)
class Solution:
def largestAltitude(self, gain: List[int]) -> int:
altitude = [0]
for i, g in enumerate(gain):
cumsum = altitude[i] + g
altitude.append(cumsum)
return max(altitude)
%%timeit
assert Solution().largestAltitude([-5,1,5,0,-7]) == 1
assert Solution().largestAltitude([-4,-3,-2,-1,4,3,2]) == 0
Slightly more performant:
- Time: O(n)
- Mem: O(1)
class Solution:
def largestAltitude(self, gain: List[int]) -> int:
altitude = 0
highest_altitude = 0
for i, g in enumerate(gain):
altitude = altitude + g
highest_altitude = max(highest_altitude, altitude)
return highest_altitude
%%timeit
assert Solution().largestAltitude([-5,1,5,0,-7]) == 1
assert Solution().largestAltitude([-4,-3,-2,-1,4,3,2]) == 0
1347. Minimum Number of Steps to Make Two Strings Anagram
Question
Given two equal-size strings s and t. In one step you can choose any character of t and replace it with another character.
Return the minimum number of steps to make t an anagram of s.
An Anagram of a string is a string that contains the same characters with a different (or the same) ordering.
Example 1:
Input: s = "bab", t = "aba" Output: 1 Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s. Example 2:
Input: s = "leetcode", t = "practice" Output: 5 Explanation: Replace 'p', 'r', 'a', 'i' and 'c' from t with proper characters to make t anagram of s. Example 3:
Input: s = "anagram", t = "mangaar" Output: 0 Explanation: "anagram" and "mangaar" are anagrams. Example 4:
Input: s = "xxyyzz", t = "xxyyzz" Output: 0 Example 5:
Input: s = "friend", t = "family" Output: 4
Constraints:
1 <= s.length <= 50000 s.length == t.length s and t contain lower-case English letters only.
- Find the number of different characters in each string. (delta)
- Pair up the different chars and count the number of pairs sum(delta.values()) // 2
from collections import Counter
class Solution:
def minSteps(self, s: str, t: str) -> int:
c1 = Counter(s)
c2 = Counter(t)
keys = set((*c1.keys(), *c2.keys()))
delta = {k: abs(c1[k] - c2[k]) for k in keys}
return sum(delta.values()) // 2
%%timeit
assert Solution().minSteps('bab', 'aba') == 1
assert Solution().minSteps('leetcode', 'practice') == 5
assert Solution().minSteps('mangaar', 'anagram') == 0
assert Solution().minSteps('xxyyzz', 'xxyyzz') == 0
assert Solution().minSteps('friend', 'family') == 4
767. Reorganize String
Question
Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.
If possible, output any possible result. If not possible, return the empty string.
Example 1:
Input: S = "aab" Output: "aba" Example 2:
Input: S = "aaab" Output: "" Note:
S will consist of lowercase letters and have length in range [1, 500].
class Solution:
def reorganizeString(self, S: str) -> str:
pass
assert Solution().reorganizeString('aab') == 'aba'
assert Solution().reorganizeString('aaab') == ''