作者oin1104 (是oin的說)
看板Marginalman
標題Re: [閒聊] 每日leetcode
時間Tue Aug 6 11:36:57 2024
今天每日寫過了
所以再來一題
2998.
Minimun Number of Jiwp Buy a Reimu figure
to oin
題目:
給你x跟y
你可以對x做四種操作讓他變成y
整除的話除以11
整除的話除以5
或是+1
或是-1
問你最小的操作次數是多少
思路:
用一般的dp
dp過去會發現之前的數字被改變了
所以是不行的
仔細想想
這x每次能變成的數字有限
讓他用步數+1來bfs下次能走到的地方
這樣就可以很有效率的用最小步數
找他能到的地方
```cpp
class Solution {
public:
int minimumOperationsToMakeEqual(int x, int y)
{
if(x<=y)return y-x;
vector<int> paper(10001,931104);
queue<pair<int,int>> go;
go.push({x,0});
paper[x] = 0;
while(!go.empty())
{
pair<int,int> n = go.front();
if(n.first==y)return n.second;
go.pop();
if(n.first+1 <= 10000 && paper[n.first+1] > n.second+1)
{
paper[n.first+1] = n.second+1 ;
go.push({n.first+1,n.second+1});
}
if(n.first-1 >= 0 && paper[n.first-1] > n.second+1)
{
paper[n.first-1] = n.second+1 ;
go.push({n.first-1,n.second+1});
}
if(n.first%11==0 && paper[n.first/11] > n.second+1)
{
paper[n.first/11] = n.second+1 ;
go.push({n.first/11,n.second+1});
}
if(n.first%5==0 && paper[n.first/5] > n.second+1)
{
paper[n.first/5] = n.second+1 ;
go.push({n.first/5,n.second+1});
}
}
return paper[y];
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.129.159 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722915419.A.F46.html
推 JIWP: 我好崇拜你 08/06 11:37
→ Wardyal: 說真的 你這樣每天寫莉的扣的 好佩服你 08/06 11:39
→ oin1104: 我也很佩服我自己可以每天跟jiwp乞討 08/06 11:41
推 amsmsk: 你有什麼用 08/06 11:53
推 Chricey: 鋅功效 08/06 11:53