Re: [閒聊] 每日leetcode
今天每日寫過了
所以再來一題
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
推
08/06 11:37,
1年前
, 1F
08/06 11:37, 1F
→
08/06 11:39,
1年前
, 2F
08/06 11:39, 2F
→
08/06 11:41,
1年前
, 3F
08/06 11:41, 3F
推
08/06 11:53,
1年前
, 4F
08/06 11:53, 4F
→
08/06 12:09,
1年前
, 5F
08/06 12:09, 5F
討論串 (同標題文章)
完整討論串 (本文為第 649 之 1548 篇)：