LeetCode(15) -- 504, 506, 507

P504. Base 7 (Easy)

把一个整数转化为7进制。返回字符串。

我的思路

用10进制转化其他进制的基本方法，不断做除法，余数记下来。最后倒数从下往上读数即为答案。

我的代码

public class E_504_Base7 {
    public String convertToBase7(int num) {
        if (num == 0) {
            return "0";
        }
        boolean negative = false;
        if (num < 0) {
            num = -num;
            negative = true;
        }
        Stack<Integer> stack = new Stack<>();
        int division = num;
        while (division != 0) {
            stack.add(division % 7);
            division /= 7;
        }
        StringBuilder sb = new StringBuilder();
        if (negative) {
            sb.append('-');
        }
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        new E_504_Base7().convertToBase7(100);
    }
}

最后遍历stack时，一开始误用了fori循环，而stack的size是不断变小的。所有不应该用fori，最好用while。

最优解

class Solution {
    public String convertToBase7(int num) {
        return Integer.toString(num, 7);
    }
}

这就没意思了。。。

P506. Relative Ranks (Easy)

给一个数组代表每个运动员的得分。得分是唯一的。给他们排出名次，前三个分别对应”Gold Medal”, “Silver Medal”, “Bronze Medal”，其他的直接输出名次。运动员的顺序要保持不变。

我的思路

先用HashMap记录下来他们的索引，然后排序，然后从后往前遍历就是各自的排名。

我的代码

public class E_506_RelativeRanks {
    public String[] findRelativeRanks(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        Arrays.sort(nums);
        String[] res = new String[nums.length];
        for (int i = nums.length - 1; i >= 0 ; i--) {
            if (i == nums.length - 1) {
                res[map.get(nums[i])] = "Gold Medal";
            } else if (i == nums.length - 2) {
                res[map.get(nums[i])] = "Silver Medal";
            } else if (i == nums.length - 3) {
                res[map.get(nums[i])] = "Bronze Medal";
            } else {
                res[map.get(nums[i])] = String.valueOf(nums.length - i);
            }
        }
        return res;
    }
}

85%

最优解

class Solution {
    public String[] findRelativeRanks(int[] nums) {
        int maxValue = 0;
        for (int i = 0; i < nums.length; i ++) {
            if (nums[i] > maxValue) {
                maxValue = nums[i];
            }
        }

        int[] bucket = new int[maxValue+1];

        for (int i = 0; i < nums.length; i ++) {
            bucket[nums[i]] = i+1;
        }

        int place = 1;
        String[] answer = new String[nums.length];
        for (int i = bucket.length-1; i >= 0; i --) {
            if (bucket[i] != 0) {
                if (place <= 3) {
                    if (place == 3) {
                        answer[bucket[i]-1] = "Bronze Medal";
                    }
                    else if (place == 2) {
                        answer[bucket[i]-1] = "Silver Medal";
                    }
                    else {
                        answer[bucket[i]-1] = "Gold Medal";
                    }
                }
                else {
                    answer[bucket[i]-1] = place+"";
                }
                place++;
            }
        }

        return answer;
    }
}

就是自制了一个HashMap。

P507. Perfect Number (Easy)

“完美数”是指它所有的正数因子的和（不包括本身），等于它本身。

Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14

我的思路

n最大可能是1亿，所以肯定不能暴力破解。我想找出所有质因子，然后它们的任意组合，就是所有的因子。

答案

public class Solution {
    public int pn(int p) {
        return (1 << (p - 1)) * ((1 << p) - 1);
    }
    public boolean checkPerfectNumber(int num) {
        int[] primes=new int[]{2,3,5,7,13,17,19};
        for (int prime: primes) {
            if (pn(prime) == num)
                return true;
        }
        return false;
    }
}

Euclid–Euler theorem：（欧几里得-欧拉定理）

perfect number = 2^(p-1) * (2^p - 1), where p is prime and 2^p - 1 must also be prime.