Pow(x, n) leetcode

Implement pow(x, n).
就是求x的n次方 x^n = x^(n/2) * x^(n/2)*x^(n%2)
如果n< 0 最后结果应该是1/result

public class Solution {
    public double myPow(double x, int n) {
        if (n == 0) {
            return 1.0;
        }
        if (n == 1) {
            return x;
        }
        boolean isneg = n < 0;
        if (isneg) {
            n *= -1;
        }
        double res = myPow(x, n/2);
        double result;
        if (n % 2 == 0) {
            result = res* res;
        } else {
            result =  res * res * x;
        }
        if (isneg) {
            return 1/result;
        } else {
            return result;
        }
    }
}

Divide Two Integers leetcode

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.   时间复杂 O(logn)

public class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == 0 || divisor == 0) {
            return 0;
        }
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }
        boolean isNeg = (dividend < 0 && divisor >0) || (dividend >0 && divisor < 0);
        long a = Math.abs((long) dividend);
        long b = Math.abs((long) divisor);
        if (b > a) {
            return 0;
        }
        int result = 0;
        long pow = 0;
        long sum = 0;
        while (a >= b) {
            pow = 1;
            sum = b;
            while (sum + sum < a) {
                sum += sum;
                pow += pow;
            }
            a -= sum;
            result += pow;
        }
        if (isNeg) {
            return -result;
        } else {
            return result;
        }
    }
}

Copy List with Random Pointer leetcode

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

第一种方法：用hashmap

1. 把新链表和原链表按照key: value存入hashmap， 并给每个新链表附上next指针

2. 按顺序读取hashp存储的旧链表， 然后把random指针复制给新链表（必须放在hashmap读取是因为直接读取random指针就无法按顺序）

一共扫面了两次链表 时间复杂度O(n) 空间复杂度O(n)

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null){ 
            return null;
        }
        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode newhead = new RandomListNode(head.label);
        map.put(head, newhead);
        RandomListNode node = head.next;
        RandomListNode pre = newhead;
        while (node != null){
            RandomListNode tem = new RandomListNode(node.label);
            map.put(node, tem);
            pre.next = tem;
            pre = pre.next;
            node = node.next;
        }
        node = head;
        pre = newhead;
        while (node != null){
            pre.random = map.get(node.random);
            pre = pre.next;
            node = node.next;
        }
        return newhead;
        
    }
}

第二种方法：

深度拷贝一个链表

第一步：复制链表并插入原链表原链表（1->2->3->4）新链表(1->1'->2->2'->3->3'->4->4')

第二步： 改变新链表的random指针

第三步：分离连个链表
三次线性扫描，所以时间复杂度是O(n)。空间复杂度是O(1)。

public class Solution {

    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }
        RandomListNode node = head;
        while (node != null) {
            RandomListNode tem = new RandomListNode(node.label);
            tem.next = node.next;
            node.next = tem;
            node = node.next.next;
        }
        node = head;
        while (node != null) {
            if (node.random != null) {
                node.next.random = node.random.next;
            }
            node = node.next.next;
        }
        node = head;
        RandomListNode newhead = head.next;
        while(node != null){
            RandomListNode tem = node.next;
            node.next = tem.next;
            if (tem.next != null) {
                tem.next = tem.next.next;
            }
            node = node.next;
        }
        return newhead;
    }
}