264. Ugly Number II

Let us generate the nth ugly number in the sequence. 看看有没有规律！每个数都可以由前面的数乘以{2，3，5}得到 只是位置在哪的区别 而从这些结果中我们要选一个最小的排入 每次从已有队列中选取最小的和Prime相乘加入队列 一直到队列的大小等于N~

然而这个做法有些太慢了！虽然我们还是用到了Priority Queue 这道题比较好的想法是用DP做 列出前面几个式子是怎么形成的 然后可以观察到指针的区别 不过这个题我感觉如果在onsite碰到估计还是会想到Queue的做法

public class Solution {
 public int nthUglyNumber(int n) {
        // Write your code here
        PriorityQueue<Long> q = new PriorityQueue<Long>();
        HashSet<Long> set = new HashSet<Long>();
        long[] primes = {Long.valueOf(2),Long.valueOf(3),Long.valueOf(5)};
        q.add(Long.valueOf(1));
        Long number = Long.valueOf(1);
        int count = 0;
        while(count < n){
            number = q.poll();
            for (int j = 0; j < 3; j++) {
                long val = primes[j] * number;
                if(!set.contains(val)){
                    q.offer(val);
                    set.add(val);
                }
            }
            count++;
        }
        return number.intValue();
    }
}

数字加减进位

168. Excel Sheet Column Title

数字处理 从后面开始append 余数对应了一个字母 然后最后把所得的翻转

public class Solution {
    public String convertToTitle(int n) {
        StringBuilder bd = new StringBuilder();
        while(n > 0){
            n--;
            int r = n%26;
            bd.append((char)('A'+ r));
            n = n/26;
        }
        return bd.reverse().toString();
    }
}

2. Add Two Numbers

对于多余部分的处理 While循环里面用的是||还是&&判断使得代码简洁好多 如果用||并且用一个变量sum代表每一对数字的和 每次形成一位之后清0 只要非Null才加入sum 这样可以免去很多讨论 比如相同的长度下相加还有进位 那么有剩余元素的链表就不能很简单的接到已有的结果

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        ListNode p1 = l1;
        ListNode p2 = l2;
        int sum = 0;
        int carry = 0;
        while(p1 != null || p2 != null){
            sum += carry;
            if(p1 != null){
                sum += p1.val;
                p1 = p1.next;
            }
            if(p2 != null){
                sum += p2.val;
                p2 = p2.next;
            }
            ListNode newNode = new ListNode(sum%10);
            carry = sum / 10;
            p.next = newNode;
            p = p.next;
            sum = 0;
        }
        if(carry > 0){
            p.next = new ListNode(carry);
        }
        //The case when there are moreover 

        return dummy.next;
    }
}

数字比较

165. Compare Version Numbers

一位一位的比较 如果出现有一位不一样返回比较结果 用到了Split..

public class Solution {
   public int compareVersion(String version1, String version2) {
    String[] levels1 = version1.split("\\.");
    String[] levels2 = version2.split("\\.");

    int length = Math.max(levels1.length, levels2.length);
    for (int i = 0; i < length; i++) {
        Integer v1 = i < levels1.length ? Integer.parseInt(levels1[i]) : 0;
        Integer v2 = i < levels2.length ? Integer.parseInt(levels2[i]) : 0;
        int compare = v1.compareTo(v2);
        if (compare != 0) {
            return compare;
        }
    }
    return 0;
   }
}

sort accordingly

386. Lexicographical Numbers

相当于把数字看成String排序 按照位排 可以想想每一步后面加什么

给定prev 有以下几种按照顺序考虑 如果 <= n

1. prev * 10

2. prev + 1

3. 考虑进位 如果结尾一个9 比如5009不用变 （5010就是下一个）如果超过一个9

5099 -- 5100 是不对的 应该史5010 所以如果结尾有两个9 消除9直到结尾的9的

个数不大于2

public class Solution {
    //找规律的一道题 
    public List<Integer> lexicalOrder(int n) {
        int k = 1;
        List<Integer> res = new ArrayList<Integer>();
        while(res.size() < n){
            res.add(k);
            //first check prev * 10
            if(k * 10 <= n){
                k = k * 10;
            }
            //next check prev + 1 if prev is not ended with 9
            else if(k % 10 != 9 && (k + 1) <= n){
                k++;
            }
            //finally if prev is ended with 9 wipe away the 9 509 6099 610
            else{
                while((k / 10) % 10 == 9){
                    k = k / 10;
                }
                k = k / 10 + 1;
            }
        }
        return res;
    }
}

除法运算

166. Fraction to Recurring Decimal

--> 分数变循环小数

按照正常的除法规则找到pattern就可以 这个题corner case挺多的。。主要一个是溢出 一个是符号的判断。还有一个算法怎么设计能让代码更加好写 比如怎么发现有重复的pattern?
怎么加括号？首先我们先计算出整数部分 如果没有余数就可以直接返回了 但如果有余数 则要继续
乘以10进行计算 然后用一个哈希表记录每个余数出现的index 这样如果有数字之前出现过了则说明
进行了循环。这时停止计算在相应的位置加上"(" 和 ")"就好 啦

public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if(numerator == 0){
            return "0";
        }
        StringBuilder bd = new StringBuilder();
        if((numerator > 0) ^ (denominator > 0))bd.append('-');
        //since when we compute the result we need positive values! so we need to use Math.abs but consider every
        //possible overflow!! 
        long num = Math.abs((long)numerator);
        long deno = Math.abs((long)denominator);

        long v1 = num / deno;
        bd.append(v1);
        long r = num % deno;
        //if no leftover just return right away
        if(r == 0){
            return bd.toString();
        }

        bd.append(".");
        //continue to multiply by ten and detect the duplicate!
        //<剩余的数，对应的index>
        HashMap<Long,Integer> map = new HashMap<Long,Integer>();
        map.put(r,bd.length());

        while(r > 0){
            r = r * 10;
            long val = r / deno;
            bd.append(val);
            //the next round 
            r = r % deno; 
            if(map.containsKey(r)){
                int idx = map.get(r);
                bd.insert(idx,"(");
                bd.append(")");
                break;
            }
            else{
                map.put(r,bd.length());
            }
        }
        return bd.toString();
    }
}