LeetCode 166-170

166. 分数到小数

如果分子为0，直接输出0。如果分子分母异号，添加“-”号。模拟长除法，用map记录余数出现时，res字符串的长度。当某个余数第二次出现时，一定有循环。添加左右括号结束。

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) {
            return "0";
        }
        StringBuilder res = new StringBuilder();
        if (numerator < 0 ^ denominator < 0) {
            res.append("-");
        }
        long up = Math.abs(Long.valueOf(numerator)), down = Math.abs(Long.valueOf(denominator));
        res.append(String.valueOf(up / down));
        long r = up % down;
        if (r == 0) {
            return res.toString();
        }
        res.append(".");
        Map<Long, Integer> map = new HashMap<>();
        while (r != 0) {
            if (map.containsKey(r)) {
                res.insert(map.get(r), "(");
                res.append(")");
                break;
            }
            map.put(r, res.length());
            r *= 10;
            res.append(String.valueOf(r / down));
            r %= down;
        }
        return res.toString();
    }
}

167. 两数之和 II - 输入有序数组

时间复杂度On,空间复杂度On：

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            if (map.containsKey(target - numbers[i])) {
                return new int[]{map.get(target - numbers[i]) + 1, i + 1};
            } else {
                map.put(numbers[i], i);
            }
        }
        return new int[]{-1,-1};
    }
}

双指针，时间复杂度On，空间复杂度O1：

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int lo = 0, hi = numbers.length - 1;
        while (lo < hi) {
            int sum = numbers[lo] + numbers[hi];
            if (sum > target) {
                hi--;
            } else if (sum < target) {
                lo++;
            } else {
                return new int[]{lo + 1, hi + 1};
            }
        }
        return new int[]{-1, -1};
    }
}

168. Excel表列名称

class Solution {
    public String convertToTitle(int n) {
        char[] map = {'A', 'B', 'C', 'D', 'E', 'F', 'G',
                'H', 'I', 'J', 'K', 'L', 'M', 'N',
                'O', 'P', 'Q', 'R', 'S', 'T',
                'U', 'V', 'W', 'X', 'Y', 'Z'};
        int[] z = new int[40];
        int pos = 0;
        while (n != 0) {
            n--;
            z[pos++] = n % 26;
            n /= 26;
        }
        StringBuilder res = new StringBuilder();
        for (int i = pos - 1; i >= 0; i--) {
            res.append(map[z[i]]);
        }
        return res.toString();
    }
}

169. 多数元素

使用哈希表记录出现次数。
时间复杂度On，空间复杂度On

class Solution {
    public int majorityElement(int[] nums) {
        int max = nums.length / 2;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            if (map.get(nums[i]) > max) {
                return nums[i];
            }
        }
        return -1;
    }
}

摩尔投票算法，先选第一个数为候选人，遇到相同的就加1，遇到不同的就减1，减到0就重新换个数开始计数，最后的结果一定是最多的数。

时间复杂度On，空间复杂度O1。

class Solution {
    public int majorityElement(int[] nums) {
        int res = nums[0], count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == res) {
                count++;
            } else if (--count == 0) {
                res = nums[i];
                count = 1;
            }
        }
        return res;
    }
}