Leetcode 881 - Boats to Save People

題目

Problem#

題目給你一個整數陣列 people[i] 是每個人的重量，今天要搭船過河，每條船最多載重 limit，一艘船最多載兩個人，問你最少需要幾條船。

1 <= people.length <= 5 * 10^4
1 <= people[i] <= limit <= 3 * 10^4

想法#

2022-03-24

解題區►Leetcode►Medium

Leetcode 763 - Partition Labels

題目

Problem#

給定一個字串，問你如果把字串分組，靠得近的分在同一組，組數越少越好，要你回傳分組狀態

ababcbacadefegdehijhklij => [9, 7, 8]

ababcbaca | defegde | hijhklij
^abc        ^defg     ^hijkl

想法#

2022-03-22

解題區►Leetcode►Medium

Leetcode 167 - Two Sum II - Input Array Is Sorted

題目

Problem#

題目給你一個 1-index 的整數陣列(已排序)，問你陣列裡加起來等於 target 的兩個數字 index 為何

想法#

naive $\mathcal{O}(n^2)$ 作法會超時
掃一次，對於 index i 每次去數字的右邊($[i+1, n)$)找是否有 t - n[i] 的數字存在，二分搜加速

2022-03-22

解題區►Leetcode►Medium

Leetcode 1663 - Smallest String With A Given Numeric Value

題目

Problem#

題目給你兩個數字 n 和 k 問你: 由 n 個字母組成，所有字母加起來總和為 k 且字串字典序最小。
a=1, b=2, …, z=26

想法#

最優的答案是後面都是 z 前面都是 a，先貪心找最後的 z 長度: 對於字串 Z = aa...z = 1*(a長度) + 26 假如 k 大於 Z 的話，則最後一定可以擺一個 z，亦即 k >= 1*(n-1) + 26。
接下來就都擺 a ，中間的字母(夾在 a 和 z 中間 e.g. “aa…x…zz”)，就擺 'a'+(k-1)

2022-03-21

解題區►Leetcode►Medium

Leetcode 2212 - Maximum Points in an Archery Competition

題目

Problem#

有 Alice 和 Bob 比賽射箭，每個人有 numArrows 支箭，一人各射 12 局，規則是: 如果第 $i$ 局的分數比另一個人大，$A_i \ge B_i$ 則 A 得到 $i$ 分。
今天 Alice 先射完了，他的結果是 [aliceArrows_0, aliceArrows_11] ，問你 Bob 的結果長怎樣，他的得分才會是最大的

想法#

這題有兩種做法: 爆搜和 DP。
之所以可以爆搜是因為局數只有 12 局，所以能在 $\mathcal{O}(2^12)$ 內做完，bitwise 枚舉也是一樣。DP 則是把箭數當重量、得分當價值的話，問題就變成了 0/1 背包 $\mathcal{O}(nm), n=\text{12}, m=10^5$