推 Meaverzt: 這題看懂題目花超久 02/15 22:18
→ Rushia: 我直接看例子反推題目在講什麼 差低 02/15 22:18
https://leetcode.com/problems/find-the-punishment-number-of-an-integer/description
2698. Find the Punishment Number of an Integer
給你一個數字n，找出1~n之間的懲罰數字和，懲罰數字被定義為 i * i = 切分後拼接
(i * i)，例如: 36 * 36 = 1296 = 1 + 29 + 6。
思路:
1.對數字1~n用DFS窮舉所有的可能和，如果其中一種拆分方式滿足的話就加總。
Java Code:
-----------------------------------
class Solution {
public int punishmentNumber(int n) {
int res = 0;
for (int i = 1; i <= n; i++) {
int punishment = i * i;
if (dfs(i, 0, punishment)) {
res += punishment;
}
}
return res;
}
boolean dfs(int i, int sum, int left) {
if (i == sum + left) {
return true;
}
int temp = sum;
int r = 1;
while (left != 0) {
temp += (left % 10) * r;
left /= 10;
r *= 10;
if (dfs(i, temp, left)) {
return true;
}
}
return false;
}
}
-----------------------------------
--
你跟我說這個我有什麼辦法
https://i.imgur.com/wb5zrOy.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.158.101.161 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1739629017.A.12F.html