Tags » Linked List

[LeetCode] Fraction to Recurring Decimal

题目:
模拟整数除法,并且找到循环小数的部分。
https://leetcode.com/problems/fraction-to-recurring-decimal/

解法:
难题。
找循环小数的原理和找链表的cycle一个道理,可以用hashmap存曾经出现过的被除数(链表的节点),如果这个被除数之后又出现了,那么就出现了cycle,这个被除数就是cycle的起点。

Java代码:

public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) {
            return "0";
        }
        
        StringBuilder sb = new StringBuilder();
        if ((numerator < 0) ^ (denominator < 0)) {
            sb.append("-");
        }
       
        long dividend = Math.abs((long)numerator);
        long divisor = Math.abs((long)denominator);
        
        sb.append(dividend / divisor);
        dividend %= divisor;
        if (dividend == 0) {
            return sb.toString();
        }
        
        Map<Long, Integer> index = new HashMap<>();
        sb.append(".");
        while(dividend != 0) {
            if (index.containsKey(dividend)) {
                // detect repeating pattern when the number to be divided is seen before
                int idx = index.get(dividend);
                sb.insert(idx, '(').append(')');
                break;
            }
            index.put(dividend, sb.length());
            dividend *= 10;
            sb.append(dividend / divisor);
            dividend %= divisor;
        }
        
        return sb.toString();
    }
}

[LeetCode] Reverse Nodes in k-Group

题目:
将链表k个k个依次reverse,最后一段不足k个,就不用reverse
https://leetcode.com/problems/reverse-nodes-in-k-group/

解法:
挺不好写的,用递归可以省去很多变量的维护,使得代码整洁

Java代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null || k < 2) {
            return head;
        }
        
        // find a k-group
        ListNode cur = head;
        for(int i = 0; i < k; i++) {
            if (cur == null) {
                return head;
            }
            cur = cur.next;
        }
        
        ListNode newHead = reverse(head, cur);
        head.next = reverseKGroup(cur, k);
        
        return newHead;
    }
    
    // reverse , and return head of revsersed list
    private ListNode reverse(ListNode head, ListNode tail) {
        ListNode prev = tail;
        while(head != tail) {
            ListNode tmpNext = head.next;
            head.next = prev;
            prev = head;
            head = tmpNext;
        }
        return prev;
    }
}

Print Tree by column order

Problem statement:

Given a binary containing integers, you’re asked to print this tree by column from left to right, top to bottom. 303 more words

Linked List

[LeetCode] Sort List

题目:
排序一个链表,要求时间复杂度O(nlogn),常数空间
https://leetcode.com/problems/sort-list/

解法:
merge sort,divide and conquer
需要用快慢指针找到中点

如果不考虑递归的stack frame带来的space,那就是常数空间。

Java代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    // accepted, 7ms, 1 time AC
    public ListNode sortList(ListNode head) {
        // base case
        if (head == null || head.next == null) {
            return head;
        }
        
        // find mid point
        ListNode slow, fast;
        slow = fast = head;
        while(fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode rightHead = slow.next;
        slow.next = null;
        
        // divide and conquer
        return merge(sortList(head), sortList(rightHead));
    }
    
    private ListNode merge(ListNode left, ListNode right) {
        ListNode p = left, q = right;
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        
        while(p != null && q != null) {
            if(p.val < q.val) {
                prev.next = p;
                prev = p;
                p = p.next;
            } else {
                prev.next = q;
                prev = q;
                q = q.next;
            }
        }
        
        if (p != null) {
            prev.next = p;
        } else if (q != null) {
            prev.next = q;
        }
        
        return dummy.next;
    }
}

[LeetCode] Copy List with Random Pointer

题目:
给定一个链表,每个node都有个random pointer,指向链表的任意一个节点,请deep copy这个链表
https://leetcode.com/problems/copy-list-with-random-pointer/

解法:
1) 显而易见的是hashmap,存node的对应关系,空间复杂度O(n)
2) 巧妙的办法是,把1->2->3,先变成1->1′->2->2′->3->3’,如果1的random指向3,那么1’的random也指向3′,然后再split成两个链表。注意,原链表的结构不可改变。这个空间复杂度是O(1)

Java代码:

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        return copyRandomList_ConstantSpace(head);
    }
    
    // accepted 2ms
    private RandomListNode copyRandomList_ConstantSpace(RandomListNode head) {
        if (head == null) {
            return null;
        }
        
        // duplicate the node
        RandomListNode cur = head;
        while(cur != null) {
            RandomListNode newNode = new RandomListNode(cur.label);
            newNode.next = cur.next;
            cur.next = newNode;
            cur = newNode.next;
        }
        
        // copy random pointer
        cur = head;
        while(cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        
        // split two lists
        RandomListNode newHead = head.next;
        cur = head;
        while(cur != null) {
            RandomListNode tmp = cur.next;
            cur.next = tmp.next;
            cur = cur.next;
            if (tmp.next != null) {
                tmp.next = tmp.next.next;
            }
        }
        return newHead;
    }
    
    
    // accepted
    private RandomListNode copyRandomList_HashMap(RandomListNode head) {
        if (head == null) {
            return null;
        }
        
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode cur = head, prev = dummy;
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        
        while(cur != null) {
            // append new node to list
            RandomListNode newNode = new RandomListNode(cur.label);
            newNode.random = cur.random;
            prev.next = newNode;
            
            // put mapping for node
            map.put(cur, newNode);
            
            prev = newNode;
            cur = cur.next;
        }
        
        cur = dummy.next;
        while(cur != null) {
            if (cur.random != null) {
                cur.random = map.get(cur.random);
            }
            cur = cur.next;
        }
        
        return dummy.next;
    }
}

[LeetCode] LRU Cache

题目:
实现LRU cache的get,set方法
https://leetcode.com/problems/lru-cache/

解法:
为了实现O(1) access,可以用hashmap+双向链表
写了快一百行,不简单

Java代码:

class Node {
    int key;
    int value;
    Node prev;
    Node next;
    
    public Node(int key, int value) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

class MyList {
    Node head;
    Node tail;
    
    public MyList() {
        head = null;
        tail = null;
    }
    
    public void append(Node node) {
        if (head == null) {
            head = tail = node;
        } else {
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
    }
    
    public void remove(Node node) {
        Node prevNode = node.prev;
        Node nextNode = node.next;
        
        if (prevNode == null && nextNode == null) {
            head = tail = null;
        } else if (prevNode == null && nextNode != null) {
            nextNode.prev = null;
            node.next = null;
            head = nextNode;
        } else if (prevNode != null && nextNode == null) {
            prevNode.next = null;
            node.prev = null;
            tail = prevNode;
        } else {
            prevNode.next = nextNode;
            nextNode.prev = prevNode;
            node.prev = node.next = null;
        }
    }
    
    public int removeHead() {
        if (head == null) {
            return -1;
        }
        
        int oldKey = head.key;
        remove(head);
        return oldKey;
    }
}

public class LRUCache {
    private int capacity;
    private MyList cache;
    private Map<Integer, Node> map;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new MyList();
        map = new HashMap<>();
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        
        int value = map.get(key).value;
        removeFromCache(key);
        addToCache(key, value);
        
        return value;
    }
    
    public void set(int key, int value) {
        if (map.containsKey(key)) {
            removeFromCache(key);
        } else if (map.size() == capacity) {
            int leastRecentKey = cache.removeHead();
            map.remove(leastRecentKey);
        }
        
        addToCache(key, value);
    }
    
    private void addToCache(int key, int value) {
        Node newNode = new Node(key, value);
        cache.append(newNode);
        map.put(key, newNode);
    }
    
    private void removeFromCache(int key) {
        Node node = map.get(key);
        cache.remove(node);
        map.remove(node.key);
    }
}

Maximum Sum Path

Problem statement:

Given a Balance Tree, you’re asked to find the path that has the sum of value is maximized. 72 more words

Google Interview Question