/
_0343_IntegerBreak.java
43 lines (41 loc) · 1.33 KB
/
_0343_IntegerBreak.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
package com.diguage.algorithm.leetcode;
/**
* = 343. Integer Break
* <p>
* https://leetcode.com/problems/integer-break/[Integer Break - LeetCode^]
*
* @author D瓜哥, https://www.diguage.com/
* @since 2020-04-26 16:38
*/
public class _0343_IntegerBreak {
/**
* Runtime: 0 ms, faster than 100.00% of Java online submissions for Integer Break.
* Memory Usage: 38.1 MB, less than 14.29% of Java online submissions for Integer Break.
*
* Copy from: https://leetcode-cn.com/problems/jian-sheng-zi-lcof/solution/mian-shi-ti-14-i-jian-sheng-zi-tan-xin-si-xiang-by/[面试题14- I. 剪绳子(数学推导 / 贪心思想,清晰图解) - 剪绳子 - 力扣(LeetCode)]
*/
public int integerBreak(int n) {
if (n < 2) {
return 0;
}
if (n == 2) {
return 1;
}
if (n == 3) {
return 2;
}
int timeOf3 = n / 3;
int mod = n % 3;
if (mod == 0) {
return (int) Math.pow(3, timeOf3);
}
if (mod == 1) {
return (int) Math.pow(3, timeOf3 - 1) * (3 + 1);
}
return (int) Math.pow(3, timeOf3) * 2;
}
public static void main(String[] args) {
_0343_IntegerBreak solution = new _0343_IntegerBreak();
System.out.println(solution.integerBreak(10));
}
}