Re: [閒聊] 每日leetcode
看板Marginalman作者smart0eddie (smart0eddie)時間1年前 (2024/08/19 14:19)推噓0(0推 0噓 1→)留言1則, 1人參與討論串736/1548 (看更多)
2024-08-19
650. 2 Keys Keyboard
There is only one character 'A' on the screen of a notepad. You can perform
one of two operations on this notepad for each step:
Copy All: You can copy all the characters present on the screen (a
partial copy is not allowed).
Paste: You can paste the characters which are copied last time.
Given an integer n, return the minimum number of operations to get the
character 'A' exactly n times on the screen.
泥板大師不是用DP就是數學姊
只剩我只會暴力解了
反正就是從1開始貼到n
中間如果發現多複製一次比較快就多複製一次
class Solution {
public:
int minSteps(int n) {
if (n < 2) {
return 0;
}
int curMaxNum = n;
int curOpNum = 1;
int curScreen = 1;
int curCopied = 1;
while (curScreen < (n / 2 + 1)) {
if ((n - curScreen) % curScreen == 0) {
if ((n - curScreen) / curScreen + curOpNum + 1 < curMaxNum) {
curMaxNum = (n - curScreen) / curScreen + curOpNum + 1;
curOpNum++;
curCopied = curScreen;
}
}
curOpNum++;
curScreen += curCopied;
}
return curMaxNum;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.173.211.221 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724048372.A.9E5.html
→
08/19 14:20,
1年前
, 1F
08/19 14:20, 1F
討論串 (同標題文章)
完整討論串 (本文為第 736 之 1548 篇)：