Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit38d642e

Browse files
add 970
1 parent8b97c7b commit38d642e

File tree

3 files changed

+137
-0
lines changed

3 files changed

+137
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -29,6 +29,7 @@ Your ideas/fixes/algorithms are more than welcome!
2929

3030
| # | Title | Solutions | Time | Space | Video | Difficulty | Tag
3131
|-----|----------------|---------------|---------------|---------------|--------|-------------|-------------
32+
|970|[Powerful Integers](https://leetcode.com/problems/powerful-integers/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_970.java) | O(?) | O(1) | |Easy| Math
3233
|966|[Vowel Spellchecker](https://leetcode.com/problems/vowel-spellchecker/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_966.java) | O(hlogn) | O(n) | |Medium| Hash Table, String
3334
|965|[Univalued Binary Tree](https://leetcode.com/problems/univalued-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_965.java)| O(n)| O(h)||Easy| DFS, recursion|
3435
|961|[N-Repeated Element in Size 2N Array](https://leetcode.com/problems/n-repeated-element-in-size-2n-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_961.java)| O(n)| O(1)||Easy|
Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
packagecom.fishercoder.solutions;
2+
3+
importjava.util.ArrayList;
4+
importjava.util.Collections;
5+
importjava.util.HashSet;
6+
importjava.util.List;
7+
importjava.util.Set;
8+
9+
/**
10+
* 970. Powerful Integers
11+
*
12+
* Given two non-negative integers x and y, an integer is powerful if it is equal to x^i + y^j for some integers i >= 0 and j >= 0.
13+
*
14+
* Return a list of all powerful integers that have value less than or equal to bound.
15+
*
16+
* You may return the answer in any order. In your answer, each value should occur at most once.
17+
*
18+
* Example 1:
19+
*
20+
* Input: x = 2, y = 3, bound = 10
21+
* Output: [2,3,4,5,7,9,10]
22+
* Explanation:
23+
* 2 = 2^0 + 3^0
24+
* 3 = 2^1 + 3^0
25+
* 4 = 2^0 + 3^1
26+
* 5 = 2^1 + 3^1
27+
* 7 = 2^2 + 3^1
28+
* 9 = 2^3 + 3^0
29+
* 10 = 2^0 + 3^2
30+
*
31+
* Example 2:
32+
*
33+
* Input: x = 3, y = 5, bound = 15
34+
* Output: [2,4,6,8,10,14]
35+
*
36+
*
37+
* Note:
38+
* 1 <= x <= 100
39+
* 1 <= y <= 100
40+
* 0 <= bound <= 10^6
41+
*/
42+
publicclass_970 {
43+
publicstaticclassSolution1 {
44+
/**This approach results in Time Limit Exceeded since it's apparently doing
45+
* redundant checks.*/
46+
publicList<Integer>powerfulIntegers(intx,inty,intbound) {
47+
Set<Integer>result =newHashSet<>();
48+
intsmall =x;
49+
intbig =y;
50+
if (x >y) {
51+
small =y;
52+
big =x;
53+
}
54+
intmaxPower =bound /small;
55+
for (inti =0;i <=maxPower+1;i++) {
56+
for (intj =0;j <=maxPower+1;j++) {
57+
intsum = (int) (Math.pow(small,i) +Math.pow(big,j));
58+
if (sum <=bound) {
59+
result.add(sum);
60+
}
61+
}
62+
}
63+
List<Integer>list =newArrayList<>(result);
64+
Collections.sort(list);
65+
returnlist;
66+
}
67+
}
68+
69+
publicstaticclassSolution2 {
70+
/** credit: https://leetcode.com/problems/powerful-integers/discuss/214212/JavaC%2B%2BPython-Brute-Force */
71+
publicList<Integer>powerfulIntegers(intx,inty,intbound) {
72+
Set<Integer>result =newHashSet<>();
73+
for (inti =1;i <bound;i *=x >1 ?x :bound +1) {
74+
for (intj =1;i +j <=bound;j *=y >1 ?y :bound +1) {
75+
result.add(i +j);
76+
}
77+
}
78+
returnnewArrayList<>(result);
79+
}
80+
}
81+
}
Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
packagecom.fishercoder;
2+
3+
importcom.fishercoder.solutions._970;
4+
importjava.util.Arrays;
5+
importjava.util.Collections;
6+
importjava.util.List;
7+
importorg.junit.BeforeClass;
8+
importorg.junit.Test;
9+
10+
importstaticorg.junit.Assert.assertEquals;
11+
12+
publicclass_970Test {
13+
privatestatic_970.Solution1solution1;
14+
privatestatic_970.Solution2solution2;
15+
16+
@BeforeClass
17+
publicstaticvoidsetup() {
18+
solution1 =new_970.Solution1();
19+
solution2 =new_970.Solution2();
20+
}
21+
22+
@Test
23+
publicvoidtest1() {
24+
assertEquals(Arrays.asList(2,3,4,5,7,9,10),solution1.powerfulIntegers(2,3,10));
25+
assertEquals(Arrays.asList(2,3,4,5,7,9,10),solution2.powerfulIntegers(2,3,10));
26+
}
27+
28+
@Test
29+
publicvoidtest2() {
30+
assertEquals(Arrays.asList(2,4,6,8,10,14),solution1.powerfulIntegers(3,5,15));
31+
assertEquals(Arrays.asList(2,4,6,8,10,14),solution2.powerfulIntegers(3,5,15));
32+
}
33+
34+
@Test
35+
publicvoidtest3() {
36+
assertEquals(Arrays.asList(2,3,5,7,8,9,10),solution1.powerfulIntegers(2,6,12));
37+
assertEquals(Arrays.asList(2,3,5,7,8,9,10),solution2.powerfulIntegers(2,6,12));
38+
}
39+
40+
@Test
41+
publicvoidtest4() {
42+
assertEquals(Arrays.asList(2,3,5,9,10,11),solution1.powerfulIntegers(2,9,12));
43+
assertEquals(Arrays.asList(2,3,5,9,10,11),solution2.powerfulIntegers(2,9,12));
44+
}
45+
46+
@Test
47+
publicvoidtest5() {
48+
assertEquals(Arrays.asList(2,91,180,8101,8190,16200,729001,729090,
49+
737100),solution1.powerfulIntegers(90,90,1000000));
50+
List<Integer>actual =solution2.powerfulIntegers(90,90,1000000);
51+
Collections.sort(actual);
52+
assertEquals(Arrays.asList(2,91,180,8101,8190,16200,729001,729090,
53+
737100),actual);
54+
}
55+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp