6.24号刷题

发表于 | 分类于 | 0 comments

第一题 231. Power of Two

题目描述

给定一个整数，编写函数判断它是否是2的幂。

算法

正常算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class isPowerOfTwo231 {
    public boolean isPowerOfTwo(int n) {
        if (n == 1) return true;
        else if (n <= 0) return false;
        if (n % 2 == 1) return false;
        int remain = 0, num = n;
        while (num != 0) {
            num = num / 2;
            remain = num % 2;
            if (remain == 1) return false;
        }
        return true;
    }
}
Bit

如果是2的幂，那么最高位数字的最高位是1，且只有一个1

1
2
3
4
5
6
7
public class isPowerOfTwo231 {
    public boolean isPowerOfTwo2(int n) {
        return n > 0 && Integer.bitCount(n) == 1;
    }
}

第二题 342. Power of Four

题目描述

给定一个整数（32位有符号），编写函数判断它是否是4的幂。

测试用例如题目描述。

进一步思考：你可以不用循环/递归解决问题吗？

算法

如果这个数为4的幂，那么其满足3个条件:

  1. 0

  2. 是2的幂 (num & (num - 1)) == 0 或 Integer.bitCount(num) == 1
  3. (num - 1) % 3 == 0

对于第三条证明

对于 2^n - 1 如果 n为偶数，那么2^n就是4的幂，如果n为奇数，就不是。
如果n为偶那么：
2^n - 1 = (2^(n/2) + 1)*(2^(n/2) - 1)对于三个连续的数，(2^(n/2) + 1),2^(n/2),(2^(n/2) - 1)必有一个能被3整除
如果n为奇数
那么2^(n/2) + 1是个小数，必然不能被3整除。
即，如果(num - 1) % 3 == 0, 那么n为偶，num为4的幂

1
2
3
4
5
public class isPowerOfFour342 {
    public boolean isPowerOfFour(int num) {
        return num > 0 && Integer.bitCount(num) == 1 && (num - 1) % 3 == 0;
    }
}

第三题 326. Power of Three

题目描述

给定一个整数，编写函数判断它是否是3的幂。

进一步思考：

你可以不用循环/递归解出本题吗？

算法

1
2
3
4
5
6
7
public class isPowerOfThree326 {
    public boolean isPowerOfThree(int n) {
        if (n > 1)
            while (n % 3 == 0) n /= 3;
        return n == 1;
    }
}

第四题 247. Strobogrammatic Number II

题目描述

找出所有长度为n且这个数字旋转180°等于本身的数字

算法

直接计算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class findStrobogrammatic247 {
    public List<String> findStrobogrammatic(int n) {
        List<String> res = new ArrayList<>();
        if (n == 0) return res;
        int countend = (int) Math.pow(10, n);
        int countStart = (int) Math.pow(10, n - 1);
        if (countStart == 1) countStart = 0;
        for (int i = countStart; i < countend; i++) {
            String num = String.valueOf(i);
            int left = 0, right = num.length() - 1;
            while (left <= right) {
                if (!"00 11 88 696".contains(num.charAt(left) + "" + num.charAt(right)))
                    break;
                else
                    left++; right--;
            }
            if (left > right) {
                res.add(num);
            }
        }
        return res;
    }
}
利用单双对称（非递归）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class findStrobogrammatic247 {
    public List<String> findStrobogrammatic2(int n) {
        List<String> odd = Arrays.asList("0", "1", "8"),
                even = Arrays.asList(""),
                r = even;
        if (n % 2 == 1) r = odd;
        for (int i = 0; i < n / 2; i ++) {
            List<String> temp = new ArrayList<>();
            for (String str : r) {
                if (i != n / 2 - 1) {
                    temp.add("0" + str + "0");
                }
                temp.add("1" + str + "1");
                temp.add("6" + str + "9");
                temp.add("8" + str + "8");
                temp.add("9" + str + "6");
            }
            r = temp;
        }
        return r;
    }
}
利用单双对称 (递归)
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
public class Solution {
    public List<String> findStrobogrammatic(int n) {
        return recur(n, n);
    }
    public List<String> recur(int n, int m) {
        if (n == 0)
            return new ArrayList<String>(Arrays.asList(""));
        if (n == 1)
            return new ArrayList<String>(Arrays.asList("0", "1", "8"));
        List<String> list = recur(n - 2, m);
        List<String> temp = new ArrayList<>();
        
        for (String str : list) {
            if (n != m) {
                temp.add("0" + str + "0");
            }
            temp.add("1" + str + "1");
            temp.add("6" + str + "9");
            temp.add("8" + str + "8");
            temp.add("9" + str + "6");
        }
        return temp;
    }
}

第五题 248. Strobogrammatic Number III

题目描述

给定数字的起始和结束，统计这个区间中，满足数字旋转180°等于本身的数字

算法

由于有时间复杂度的限制，不能直接循环，我们可以通过上一题的递归方法，在加上循环，进行统计。

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
44
45
46
47
48
public class Solution {
    public int strobogrammaticInRange(String low, String high) {
        int end = high.length();
        int start = low.length();
        int count = 0;
        for (int i = start; i <= end; i++) {
            List<String> res = recur(i, i);
            count += getCount(res, Long.valueOf(low), Long.valueOf(high));
        }
        return count;
    }
    public int getCount(List<String> res1, long low, long high) {
        int count = 0;
        for (int i = 0; i < res1.size(); i++){
            String str = res1.get(i);
            long num = Long.valueOf(str);
            if (num >= low && num <= high) {
                count++;
            }
        }
        return count;
    }
    public List<String> recur(int n, int m) {
        if (n == 0)
            return new ArrayList<String>(Arrays.asList(""));
        if (n == 1)
            return new ArrayList<String>(Arrays.asList("0", "1", "8"));
        List<String> list = recur(n - 2, m);
        List<String> temp = new ArrayList<>();
        for (String str : list) {
            if (n != m) {
                temp.add("0" + str + "0");
            }
            temp.add("1" + str + "1");
            temp.add("6" + str + "9");
            temp.add("8" + str + "8");
            temp.add("9" + str + "6");
        }
        return temp;
    }        
}

第六题 263. Ugly Number

题目描述

编写程序判断一个给定的数字是否为“丑陋数” ugly number

丑陋数是指只包含质因子2, 3, 5的正整数。例如，6, 8是丑陋数而14不是，因为它包含额外的质因子7

注意，数字1也被视为丑陋数

算法

1
2
3
4
5
6
7
8
9
10
11
public class isUgly263 {
    public boolean isUgly(int num) {
        while (num > 1) {
            if (num % 2 == 0) num /= 2;
            else if (num % 3 == 0) num /= 3;
            else if (num % 5 == 0) num /= 5;
            else break;
        }
        return num == 1;
    }
}

第七题 264. Ugly Number II

题目描述

编写程序寻找第n个“丑陋数” ugly number

丑陋数是指只包含质因子2, 3, 5的正整数。例如，1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前10个丑陋数。

注意，数字1也被视为丑陋数

算法

利用数组循环找出当前最小值，并指定3个指针分别指向当前2，3，5所在的位置，不断循环。知道找到第k个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class nthUglyNumber264 {
    public int nthUglyNumber(int n) {
        int[] res = new int[n];
        int two = 0, three = 0, five = 0;
        res[0] = 1;
        for (int i = 1; i < n; i++) {
            res[i] = Math.min(Math.min(res[two] * 2, res[three] * 3), res[five] * 5);
            if (res[i] == res[two] * 2) two++;
            if (res[i] == res[three] * 3) three++;
            if (res[i] == res[five] * 5) five++;
        }
        return res[n - 1];
    }
}

第八题 313. Super Ugly Number

题目描述

编写程序寻找第n个“超级丑陋数”

超级丑陋数是指只包含给定的k个质因子的正数。例如，给定长度为4的质数序列primes = [2, 7, 13, 19]，前12个超级丑陋数序列为：[1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]

注意：

(1) 1 被认为是超级丑陋数，无论给定怎样的质数列表.

(2) 给定的质数列表以升序排列.

(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.

算法

与之前的找到第n个一样，只是现在换成矩阵形式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class nthSuperUglyNumber313 {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] res = new int[n];
        res[0] = 1;
        int[] point = new int[primes.length];
        for (int i = 1; i < n; i++) {
            int min = primes[0] * res[point[0]];
            for (int j = 1; j < primes.length; j++) {
                min = Math.min(min, primes[j] * res[point[j]]);
            }
            res[i] = min;
            for (int j = 0; j < primes.length; j++) {
                if (res[i] == primes[j] * res[point[j]]) point[j]++;
            }
        }
        return res[n - 1];
    }
}

第九题 69. Sqrt(x)

题目描述

求平方根

算法

牛顿法和二分法

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
public class mySqrt69 {
    //NewTon
    public int mySqrt(int x) {
        if (x == 0) return 0;
        long r = x;
        while (r * r > x) {
            r = (r + x / r) / 2;
        }
        return (int) r;
    }
    //Binary
    public int mySqrt2(int x) {
        if (x == 0) return 0;
        int left = 1, right = x, ans = 0;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            if (mid * mid <= x) {
                left = (int)mid + 1;
                ans = (int) mid;
            } else {
                right = (int) mid - 1;
            }
        }
        return ans;
    }
}

第十题 367. Valid Perfect Square

题目描述

给定一个正整数num，编写函数：如果num是完全平方数，返回True，否则返回False。

注意：不要使用任何内建函数，例如sqrt。

测试用例如题目描述。

算法

同样利用之前的两种算法进行计算

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
public class isPerfectSquare367 {
    public boolean isPerfectSquare(int num) {
        if (num == 0) return false;
        long r = num;
        while (r * r > num) {
            r = (r + num / r) / 2;
        }
        if (r * r == num) return true;
        else return false;
    }
    public boolean isPerfectSquare2(int num) {
        if (num == 0) return false;
        int low = 1, high = num, ans = 0;
        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (mid * mid <= num) {
                low = (int) mid + 1;
                ans = (int) mid;
            } else {
                high = (int) mid - 1;
            }
        }
        if (ans * ans == num) return true;
        else return false;
    }
}