Skip to content

Commit a187448

Browse files
yema-codeyema-code
committed
解决 n次 幂函数 Number 50
1 parent 705dacd commit a187448

2 files changed

Lines changed: 56 additions & 13 deletions

File tree

‎algorithmCode/src/main/java/weekThree/Number22括号生成.java‎

Lines changed: 17 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -11,13 +11,14 @@
1111
public class Number22括号生成 {
1212
public static void main(String[] args) {
1313
// recursion(0, 3, "");
14-
List<String> list = generateParenthesis(3);
15-
System.out.println(list);
14+
/* List<String> list = generateParenthesis(1);
15+
System.out.println(list);*/
16+
recursion(3,3,"");
1617

1718
}
1819

1920
public static void recursion(int n, int max, String s) {
20-
if (n >= max) {
21+
if (n <= max) {
2122
System.out.println(s);
2223
return;
2324
}
@@ -27,27 +28,32 @@ public static void recursion(int n, int max, String s) {
2728
System.out.println(s);
2829
}
2930

30-
static List<String> res = new ArrayList<>();
3131

3232
public static List<String> generateParenthesis(int n) {
33-
dfs(n, n, "");
33+
List<String> res = new ArrayList<>();
34+
dfs(n, n, "",res);
3435
return res;
3536
}
3637

37-
private static void dfs(int left, int right, String curStr) {
38+
private static void dfs(int left, int right, String curStr,List<String> res) {
3839
if (left == 0 && right == 0) { // 左右括号都不剩余了，递归终止
3940
res.add(curStr);
4041
return;
4142
}
4243
if (left > 0) { // 如果左括号还剩余的话，可以拼接左括号
43-
dfs(left - 1, right, curStr + "(");
44+
dfs(left - 1, right, curStr + "(",res);
4445
}
4546
if (right > left) { // 如果右括号剩余多于左括号剩余的话，可以拼接右括号
46-
dfs(left, right - 1, curStr + ")");
47+
dfs(left, right - 1, curStr + ")",res);
4748
}
4849
}
4950

51+
52+
5053
static class Number22括号生成2 {
54+
static List<String> res = new ArrayList<>();
55+
56+
5157
public static void main(String[] args) {
5258
List<String> list = generateParenthesis(3);
5359
System.out.println(list.toString());
@@ -88,4 +94,7 @@ private static void dfs(int left, int right, String curStr) {
8894

8995
}
9096

97+
98+
99+
91100
}

‎algorithmCode/src/main/java/weekThree/Number50Powxn即计算x的n次幂函.java‎

Lines changed: 39 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -10,28 +10,62 @@ public static void main(String[] args) {
1010
* 输出: 9.26100
1111
* */
1212
// 来进行暴露破解
13-
System.out.println(myPowOne(2.1000d, 3));
14-
System.out.println(recursionMyPow(2.1000d, 2.1000d,3-1));
13+
System.out.println(myPowOne(2.00000, 10));
14+
// System.out.println(recursionMyPow(2.1000d, 2.1000d, 3 - 1));
1515
}
1616

1717
/**
1818
* 进行暴力破解 for 循环 但是没有考虑到 负数的情况 大部分场景是可以解决的
19+
*
1920
* @param x
2021
* @param n
2122
* @return
2223
*/
2324
public static double myPowOne(double x, int n) {
24-
return recursionMyPow(x,x,n-1);
25+
if (n==0){
26+
return 1.0;
27+
}
28+
29+
double v = recursionMyPow(x, x, n>0 ? n - 1 : -n-1);
30+
return n >= 0 ? v : 1.0 / v;
2531
}
2632

27-
public static double recursionMyPow(double x, double y,int n) {
33+
public static double recursionMyPow(double x, double y, int n) {
2834
if (n == 0) {
2935
return y;
3036
}
31-
return recursionMyPow(x,x*y, n - 1);
37+
return recursionMyPow(x, x * y, n - 1);
3238
}
3339

3440

41+
/**
42+
* 官方题解
43+
*/
44+
static class Solution {
45+
public static void main(String[] args) {
46+
double v = myPow(2.00000, 10);
47+
System.out.println(v);
48+
49+
}
50+
51+
public static double myPow(double x, int n) {
52+
long N = n;
53+
// 判断 n是大于0还是小于的情况
54+
return N >= 0 ? quickMul(x, N) :
55+
1.0 / quickMul(x, -N);
56+
}
57+
58+
public static double quickMul(double x, long N) {
59+
// 设置边界情况
60+
if (N == 0) {
61+
return 1.0;
62+
}
63+
// 考虑 n 是奇数还是偶数的情况
64+
double y = quickMul(x, N / 2);
65+
return N % 2 == 0 ? y * y : y * y * x;
66+
}
67+
68+
}
3569

3670

3771

0 commit comments

Comments
 (0)