Ranking: 606 / 8175 ๐๐๐ญ
Q1. 5177. Reformat Date
Given a date string in the form Day Month Year, where:
Day is in the set {โ1stโ, โ2ndโ, โ3rdโ, โ4thโ, โฆ, โ30thโ, โ31stโ}.
Month is in the set {โJanโ, โFebโ, โMarโ, โAprโ, โMayโ, โJunโ, โJulโ, โAugโ, โSepโ, โOctโ, โNovโ, โDecโ}.
Year is in the range [1900, 2100].
Convert the date string to the format YYYY-MM-DD, where:YYYY denotes the 4 digit year.
MM denotes the 2 digit month.
DD denotes the 2 digit day.
Note
Very straight forward. Just do the string conversion.
1 | class Solution: |
Q2. 5445. Range Sum of Sorted Subarray Sums
Given the array nums consisting of n positive integers. You computed the sum of all non-empty continous subarrays from the array and then sort them in non-decreasing order, creating a new array of n * (n + 1) / 2 numbers.
Return the sum of the numbers from index left to index right (indexed from 1), inclusive, in the new array. Since the answer can be a huge number return it modulo 10^9 + 7.
Note
Use prefix-sum to generate the list of sum of all non-empty continous subarrys.
1 | # Time O(N^2) Space O(N^2) |
Q3. 5446. Minimum Difference Between Largest and Smallest Value in Three Moves
Given an array nums, you are allowed to choose one element of nums and change it by any value in one move.
Return the minimum difference between the largest and smallest value of nums after perfoming at most 3 moves.
Note
OMG, this problem is killing me! Spent more than 40 minutes here.
This is kind of a brute force solution.
Just try to exhaust it in a nicer way.
1 | def minDifference(self, A): |
Q4. 5447. Stone Game IV
Alice and Bob take turns playing a game, with Alice starting first.
Initially, there are n stones in a pile. On each playerโs turn, that player makes a move consisting of removing any non-zero square number of stones in the pile.
Also, if a player cannot make a move, he/she loses the game.
Given a positive integer n. Return True if and only if Alice wins the game otherwise return False, assuming both players play optimally
Note
- Typical 1-D DP
- Top-down DP will cause stack overflow
1 | # Time O(N^1.5) |
Summary
- Brute force might be OK. Exhaust all possible case in a nice way.