class Solution {
public:
int minDays(int n) {
}
};
1553. 吃掉 N 个橘子的最少天数
厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：
n 能被 2 整除，那么你可以吃掉 n/2 个橘子。n 能被 3 整除，那么你可以吃掉 2*(n/3) 个橘子。每天你只能从以上 3 种方案中选择一种方案。
请你返回吃掉所有 n 个橘子的最少天数。
示例 1：
输入：n = 10 输出：4 解释：你总共有 10 个橘子。 第 1 天：吃 1 个橘子，剩余橘子数 10 - 1 = 9。 第 2 天：吃 6 个橘子，剩余橘子数 9 - 2*(9/3) = 9 - 6 = 3。（9 可以被 3 整除） 第 3 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。 第 4 天：吃掉最后 1 个橘子，剩余橘子数 1 - 1 = 0。 你需要至少 4 天吃掉 10 个橘子。
示例 2：
输入：n = 6 输出：3 解释：你总共有 6 个橘子。 第 1 天：吃 3 个橘子，剩余橘子数 6 - 6/2 = 6 - 3 = 3。（6 可以被 2 整除） 第 2 天：吃 2 个橘子，剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。（3 可以被 3 整除） 第 3 天：吃掉剩余 1 个橘子，剩余橘子数 1 - 1 = 0。 你至少需要 3 天吃掉 6 个橘子。
示例 3：
输入：n = 1 输出：1
示例 4：
输入：n = 56 输出：6
提示：
1 <= n <= 2*10^9原站题解
javascript 解法, 执行用时: 64 ms, 内存消耗: 51 MB, 提交时间: 2024-05-12 08:10:45
/**
* @param {number} n
* @return {number}
*/
var minDays = function(n) {
const memo = new Map();
function dfs(i) {
if (i <= 1) {
return i;
}
if (memo.has(i)) { // 之前计算过
return memo.get(i);
}
const res = Math.min(dfs(Math.floor(i / 2)) + i % 2, dfs(Math.floor(i / 3)) + i % 3) + 1;
memo.set(i, res); // 记忆化
return res;
}
return dfs(n);
};
javascript 解法, 执行用时: 84 ms, 内存消耗: 55.6 MB, 提交时间: 2024-05-12 08:10:25
/**
* @param {number} n
* @return {number}
*/
var minDays = function(n) {
const dis = new Map();
dis.set(n, 0);
const pq = new MinPriorityQueue({priority: x => x[0]});
pq.enqueue([0, n]);
while (true) {
const [dx, x] = pq.dequeue().element;
if (x <= 1) {
return dx + x;
}
if (dx > dis.get(x)) {
continue;
}
for (let d = 2; d <= 3; d++) {
const y = Math.floor(x / d);
const dy = dx + x % d + 1;
if (dy < (dis.get(y) ?? Infinity)) {
dis.set(y, dy);
pq.enqueue([dy, y]);
}
}
}
};
rust 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2024-05-12 08:10:10
use std::collections::BinaryHeap;
use std::collections::HashMap;
impl Solution {
pub fn min_days(n: i32) -> i32 {
let mut dis = HashMap::new();
dis.insert(n, 0);
let mut h = BinaryHeap::new();
h.push((0, n));
loop {
let (dx, x) = h.pop().unwrap();
let dx = -dx;
if x <= 1 {
return dx + x;
}
if dx > *dis.get(&x).unwrap() {
continue;
}
for d in [2, 3] {
let y = x / d;
let dy = dx + x % d + 1;
if dy < *dis.get(&y).unwrap_or(&i32::MAX) {
dis.insert(y, dy);
h.push((-dy, y)); // 取负号变最小堆
}
}
}
}
}
rust 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2024-05-12 08:10:02
use std::collections::HashMap;
impl Solution {
pub fn min_days(n: i32) -> i32 {
fn dfs(i: i32, memo: &mut HashMap<i32, i32>) -> i32 {
if i <= 1 {
return i;
}
if let Some(&v) = memo.get(&i) { // 之前计算过
return v;
}
let res = (dfs(i / 2, memo) + i % 2).min(dfs(i / 3, memo) + i % 3) + 1;
memo.insert(i, res); // 记忆化
res
}
let mut memo = HashMap::new();
dfs(n, &mut memo)
}
}
golang 解法, 执行用时: 4 ms, 内存消耗: 3.5 MB, 提交时间: 2023-09-04 23:26:35
func minDays(n int) int {
memory := make(map[int]int)
memory[0] = 0
memory[1] = 1
var helper func(n int) int
helper = func(n int) int {
if days, ok := memory[n]; ok {
return days
}
memory[n] = min(helper(n/2)+n%2+1, helper(n/3)+n%3+1)
return memory[n]
}
return helper(n)
}
func min(a, b int) int { if a < b { return a }; return b }
python3 解法, 执行用时: 68 ms, 内存消耗: 16.1 MB, 提交时间: 2023-09-04 23:25:31
class Solution:
def minDays(self, n: int) -> int:
@lru_cache(None)
def getHeuristicValue(rest: float) -> int:
return 0 if rest == 0 else \
int(math.log(rest) / math.log(3.0)) + 1
q = [(getHeuristicValue(n), 0, n)]
visited = set()
ans = 0
while True:
expected, days, rest = heapq.heappop(q)
if rest in visited:
continue
visited.add(rest)
if rest == 1:
ans = days + 1
break
heapq.heappush(q, (
days + rest % 2 + 1 + getHeuristicValue(rest // 2),
days + rest % 2 + 1,
rest // 2
))
heapq.heappush(q, (
days + rest % 3 + 1 + getHeuristicValue(rest // 3),
days + rest % 3 + 1,
rest // 3
))
return ans
python3 解法, 执行用时: 56 ms, 内存消耗: 16 MB, 提交时间: 2023-09-04 23:25:09
# 最短路
class Solution:
def minDays(self, n: int) -> int:
q = [(0, n)]
visited = set()
ans = 0
while True:
days, rest = heapq.heappop(q)
if rest in visited:
continue
visited.add(rest)
if rest == 1:
ans = days + 1
break
heapq.heappush(q, (days + rest % 2 + 1, rest // 2))
heapq.heappush(q, (days + rest % 3 + 1, rest // 3))
return ans
java 解法, 执行用时: 9 ms, 内存消耗: 41.2 MB, 提交时间: 2023-09-04 23:24:50
class Solution {
public int minDays(int n) {
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] daysRest1, int[] daysRest2) {
if (daysRest1[0] != daysRest2[0]) {
return daysRest1[0] - daysRest2[0];
} else {
return daysRest1[1] - daysRest2[1];
}
}
});
Set<Integer> visited = new HashSet<Integer>();
queue.offer(new int[]{0, n});
int ans = 0;
while (true) {
int[] daysRest = queue.poll();
int days = daysRest[0], rest = daysRest[1];
if (visited.contains(rest)) {
continue;
}
visited.add(rest);
if (rest == 1) {
ans = days + 1;
break;
}
queue.offer(new int[]{days + rest % 2 + 1, rest / 2});
queue.offer(new int[]{days + rest % 3 + 1, rest / 3});
}
return ans;
}
}
cpp 解法, 执行用时: 12 ms, 内存消耗: 7.6 MB, 提交时间: 2023-09-04 23:24:33
using PII = pair<int, int>;
class Solution {
public:
int minDays(int n) {
priority_queue<PII, vector<PII>, greater<PII>> q;
unordered_set<int> visited;
q.emplace(0, n);
int ans = 0;
while (true) {
auto [days, rest] = q.top();
q.pop();
if (visited.count(rest)) {
continue;
}
visited.insert(rest);
if (rest == 1) {
ans = days + 1;
break;
}
q.emplace(days + rest % 2 + 1, rest / 2);
q.emplace(days + rest % 3 + 1, rest / 3);
}
return ans;
}
};
cpp 解法, 执行用时: 12 ms, 内存消耗: 9.3 MB, 提交时间: 2023-09-04 23:24:22
class Solution {
private:
unordered_map<int, int> memo;
public:
int minDays(int n) {
if (n <= 1) {
return n;
}
if (memo.count(n)) {
return memo[n];
}
return memo[n] = min(n % 2 + 1 + minDays(n / 2), n % 3 + 1 + minDays(n / 3));
}
};
java 解法, 执行用时: 3 ms, 内存消耗: 40.1 MB, 提交时间: 2023-09-04 23:23:58
class Solution {
Map<Integer, Integer> memo = new HashMap<Integer, Integer>();
public int minDays(int n) {
if (n <= 1) {
return n;
}
if (memo.containsKey(n)) {
return memo.get(n);
}
memo.put(n, Math.min(n % 2 + 1 + minDays(n / 2), n % 3 + 1 + minDays(n / 3)));
return memo.get(n);
}
}
python3 解法, 执行用时: 60 ms, 内存消耗: 18.3 MB, 提交时间: 2023-09-04 23:23:36
class Solution:
@lru_cache(None)
def minDays(self, n: int) -> int:
if n <= 1:
return n
return min(n % 2 + 1 + self.minDays(n // 2), n % 3 + 1 + self.minDays(n // 3))