Re: [閒聊] 每日leetcode已回收
看板Marginalman作者sustainer123 (caster )時間1年前 (2024/07/31 17:49)推噓2(2推 0噓 1→)留言3則, 3人參與討論串602/1548 (看更多)
※ 引述《oin1104 (是oin的說)》之銘言：
: 題目翻譯：
: 有一堆書 給你他們的寬跟高
: 跟一個寬shelfWidth的書架
: 每次放書都要照順序垂直放進去
: 不可以疊在一起
: 放滿了就放個隔板 然後去下一層放
: 請問最少要多少高度的書架才能裝下所有書
: 思路：
: 我原本沒看到要找順序
: 所以就sort然後從大賽到小
: 幹咧
: ```cpp
: class Solution {
: public:
: int minHeightShelves(vector<vector<int>>& books, int shelfWidth)
: {
: int n = books.size();
: sort(books.begin() , books.end() , [](vector<int> &a , vector<int> &b){
: return a[1]>b[1];
: } );
: for(int i = 0 ; i < n ; i ++)cout<<books[i][0]<<" "<<books[i][1]<<" ";
: vector<int> used(n,0);
: int now = 0;
: int h = 0;
: int nowh = 0;
: int noww = 0;
: while(now < n)
: {
: noww = 0;
: nowh = -1;
: for(int i = 0 ; i < n ; i ++)
: {
: if(used[i])continue;
: if(noww + books[i][0] > shelfWidth)continue;
: if(nowh == -1)nowh = books[i][1];
: noww += books[i][0];
: now ++;
: used[i] = 1;
: }
: h += nowh;
: }
: return h;
: }
: };
: ```
: 思路2：
: 看了提示 dp
: 把每個書都當作是最後一本書
: 往前找最後一層的書跟他們原本的高度
: 這樣就可以用dp來找所有的高度了
: 套路題= =
: 好像還有recursive 的做法
: 累累
: ```cpp
: class Solution {
: public:
: int minHeightShelves(vector<vector<int>>& books, int shelfWidth)
: {
: int n = books.size();
: vector<int> paper(n+1,99999999);
: paper[0]=0;
: for(int i = 1 ; i <= n ; i ++)
: {
: int cw = books[i-1][0];
: int allw = cw;
: int ch = books[i-1][1];
: paper[i] = paper[i-1]+ch;
: for(int j = i -1 ; j > 0 ; j --)
: {
: if(allw + books[j-1][0] > shelfWidth)break;
: allw += books[j-1][0];
: ch = max(ch , books[j-1][1]);
: paper[i] = min(paper[i] , paper[j-1] + ch);
: }
: }
: return paper[n];
: }
: };
: ```
思路:
本來想說排序 從大的開始 排完end
結果要維持原順序 幹
後來想說greedy調一下 調很久調不出來
解答 啟動
dp真的狗幹難 我去死
有空真的要找個時間刷dp study plan
Python Code:
class Solution:
def minHeightShelves(self, books: List[List[int]], shelfWidth: int) ->
int:
dp = [float("inf") for _ in range(len(books)+1)]
dp[len(books)] = 0
for i in range(len(books)-1,-1,-1):
cur_width = 0
cur_height = 0
for j in range(i,len(books)):
cur_height = max(cur_height,books[j][1])
cur_width += books[j][0]
if cur_width > shelfWidth:
break
dp[i] = min(dp[i], cur_height + dp[j+1])
return dp[0]
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.194.160.111 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722419352.A.B7B.html
推
07/31 17:52,
1年前
, 1F
07/31 17:52, 1F
→
07/31 17:56,
1年前
, 2F
07/31 17:56, 2F
推
07/31 17:58,
1年前
, 3F
07/31 17:58, 3F
討論串 (同標題文章)