91 algorithm

[littlemoon-zh]

day 1

简单粗暴的解法：

class Solution:
    def addToArrayForm(self, num: List[int], k: int) -> List[int]:
        n = 0
        for number in num:
            n = n * 10 + number
        return [int(ch) for ch in str(k + n)]

复杂度：O(n)

[littlemoon-zh]

day 2

两次扫的做法，每次维护一个last表示最近一次看见的目标字符位置，时间复杂度为O(n)：

class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        res = [float('inf')] * len(s)
        last = None
        
        for i in range(len(s)):
            if s[i] == c:
                last = i
                res[i] = 0
            
            elif last != None:
                res[i] = abs(last-i)
        
        last = None
        for i in range(len(s) - 1, -1, -1):
            if s[i] == c:
                last = i
            elif last != None:
                res[i] = min(res[i], abs(last-i))
        return res

[littlemoon-zh]

day3

由于题目中说了incr操作比较多，push和pop操作比较少；因而应该尽量让incr操作简单，其余操作复杂一些也没关系；

我的策略是，使用一个inc的map来记录每次的对前k个元素的更改，在每次pop的时候遍历这些增加值，得到真正的返回值；此外在pop时，有时会需要更新inc的map，因为比如本来是对前5个元素增加1，在pop完了之后，就只剩4个元素了，这就要修改inc的map。

代码如下：

class CustomStack:

    def __init__(self, maxSize: int):
        self.max = maxSize
        self.stack = []
        self.inc = collections.Counter()

    def push(self, x: int) -> None:
        if self.max == len(self.stack):
            return
        self.stack.append(x)

    def pop(self) -> int:
        if len(self.stack) == 0:
            return -1
        
        pos = len(self.stack)
        res = self.stack.pop(-1)
        
        for k, v in list(self.inc.items()):
            if pos <= k:
                res += v
            
            if k == pos:
                self.inc[k] = 0
                if (k-1) > 0:
                    self.inc[k-1] += v
                
        return res

    def increment(self, k: int, val: int) -> None:
        k = min(k, len(self.stack))
        self.inc[k] += val
        


# Your CustomStack object will be instantiated and called as such:
# obj = CustomStack(maxSize)
# obj.push(x)
# param_2 = obj.pop()
# obj.increment(k,val)

[littlemoon-zh]

day 4

Leetcode 394 Decode String

这题还是有些难度的，用到了stack，其实也是一种递归的思维，因为递归就是栈。然后再根据题目要求，写出满足的逻辑即可。

由于题目说明了，所有的格式都是规范的，不会出现3a这种情况，所以我们只要按照规则做就行了。

• 遇到数字时，将其压入数字栈中；
• 遇到[和其他字母时，压入符号栈中；
• 遇到]时，表示我们可以进行一个字符串拼接了；
  • 拼接的字符串来自符号栈中，不断出栈，直到遇到第一个[，表示当前的字符串完毕；
  • 接着从数字栈中弹出一个元素，表示将刚才的字符串重复若干遍；
  • 再将重复过的字符串压入符号栈中，继续上述过程；

最后符号栈中的各个字符串都是并列的关系，比如4[a]3[cd]，最终的结果是 ['aaaa', 'cdcdcd']，使用join函数将它们拼接到一起就可以了。

代码如下：

class Solution:
    def decodeString(self, s: str) -> str:
        i = 0
        num = []
        ch = []

        while i < len(s):
            if s[i].isdigit():
                n = 0
                while s[i].isdigit():
                    n = n * 10 + int(s[i])
                    i += 1
                num.append(n)
            elif s[i] == ']':
                ss = []
                while ch[-1] != '[':
                    ss.insert(0, ch.pop(-1))
                ch.pop(-1)
                ch.append(''.join(ss) * num.pop(-1))
                i += 1
            else:
                ch.append(s[i])
                i += 1
                
        # print(ch)
        return ''.join(ch)

[littlemoon-zh]

day 5

232 Implement Queue using Stacks

Stack is FILO and queue is FIFO. In order to implement FIFO using FILO, we need two stacks.

When we add a new element, we push it into stack1. When we retrieve the element, it's at the bottom of stack1. Then we pop all the elements from stack1 to stack2, then the desired element is on the top of stack2.

Next time we want to push an element, just push it to stack 1. If we want to retrieve an elements, it has two cases, 1 if stack2 is not empty, pop from it, 2 if stack 2 is empty, we pop all the elements from stack1 to stack2, then we pop from stack2.

class MyQueue {
    LinkedList<Integer> s1;
    LinkedList<Integer> s2;
    
    public MyQueue() {
        s1 = new LinkedList<>();
        s2 = new LinkedList<>();
    }
    
    public void push(int x) {
        s1.push(x);
    }
    
    public int pop() {
        if (s2.isEmpty()) {
            while (!s1.isEmpty())
                s2.push(s1.pop());
        }
        
        return s2.pop();
    }
    
    public int peek() {
        if (s2.isEmpty()) {
            while (!s1.isEmpty())
                s2.push(s1.pop());
        }
        
        return s2.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

[littlemoon-zh]

day 6

769 Max Chunks To Make Sorted
这题简单的地方在于，元素不重复，并且在[0, n)的范围内，最开始想到的是先创建一个拷贝，然后进行排序，然后同时扫描两个数组，如果发现元素刚好重合，就算一个划分；

后来发现，可以不用排序，在i位置时，如果之前遇到的所有元素都小于i，表示可以形成一个划分，代码中的rightMost表示到目前位置遇到的最大元素；

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int rightMost = 0;
        int res = 0;
        
        for(int i = 0; i < arr.length; i++) {
            rightMost = Math.max(rightMost, arr[i]);
            if (rightMost <= i) {
                res++;
            }
        }
        return res;
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

768 Max Chunks To Make Sorted II

三种解法：

使用map

class Solution {
    public int maxChunksToSorted(int[] arr) {
        Map<Integer, Integer> m1 = new HashMap();
        Map<Integer, Integer> m2 = new HashMap();
        int ans = 0;
        int[] sorted = Arrays.copyOf(arr, arr.length);
        Arrays.sort(sorted);
        
        for (int i = 0; i < arr.length; i++) {
            m1.put(arr[i], m1.getOrDefault(arr[i], 0) + 1);
            m2.put(sorted[i], m2.getOrDefault(sorted[i], 0) + 1);
            
            if (m1.equals(m2)) {
                // m1.clear();
                // m2.clear();
                ans++;
            }
        }
        return ans;
        
    }
}

使用辅助数组 左右看

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int max = Integer.MIN_VALUE;
        int[] maxLeft = new int[arr.length];
        
        int min = Integer.MAX_VALUE;
        int[] minRight = new int[arr.length];
        
        for (int i = 0 ; i < arr.length; i++) {
            maxLeft[i] = (max = Math.max(max, arr[i]));
        }
        
        for (int i = arr.length - 1; i >= 0; i--) {
            minRight[i] = (min = Math.min(min, arr[i]));
        }
        
        int ans = 1;
        for (int i = 0 ; i < arr.length - 1; i++)
            if (maxLeft[i] <= minRight[i+1])
                ans++;
            
        return ans;
        
    }
}

使用单调栈

class Solution {
    public int maxChunksToSorted(int[] arr) {
        Deque<Integer> s = new LinkedList<>();
        
        for (int num : arr) {
            if (!s.isEmpty() && num < s.peek()) {
                int t = s.pop();
                while (!s.isEmpty() && num < s.peek())
                    s.pop();
                
                s.push(t);
            } else {
                s.push(num);
            }
            
        }
        
        return s.size();
    }
}

[littlemoon-zh]

day 7

61 Rotate List

思路并不难，改变指向时需要多多注意，以及小心边界情况。

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null)
            return head;
        int n = 0;
        ListNode cur = head;
        // O(n)
        ListNode last = null;
        while (cur != null) {
            n++;
            if (cur.next == null)
                last = cur;
            cur = cur.next;
        }
        
        k = k % n;
        if (k == 0)
            return head;
        k = n - k;
        cur = head;
        while (--k > 0) {
            cur = cur.next;
        }
        
        ListNode ans = cur.next;
        cur.next = null;
        last.next = head;
        
        return ans;
            
    }
}

[littlemoon-zh]

day 8

递归方法，两两改变指针指向；

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode a = head, b = head.next;
        ListNode t = b.next;
        b.next = a;
        a.next = swapPairs(t);
        return b;
    }
}

[littlemoon-zh]

day 9

109 Convert Sorted List to Binary Search Tree

找到链表中间，递归建树。

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null)
            return null;
        if (head.next == null)        
            return new TreeNode(head.val);
        
        ListNode slow = head, fast = head;
        ListNode pre = null;
        
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        
        pre.next = null;
        TreeNode root = new TreeNode(slow.val);
        
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);
        return root;
    }
}

[littlemoon-zh]

day 10

160. Intersection of Two Linked Lists

简单的思路是用Set；
O(1) space的思路是，先找两个链表的长度差diff，然后让长的那个先走diff步，接着两个同时走，如果途中有相等，说明遇到重合节点；

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA, b = headB;
        
        while (a != null && b != null) {
            a = a.next;
            b = b.next;
        }
        
        int diff = 0;
        
        if (b != null) {
            a = b;
            ListNode t = headA;
            headA = headB;
            headB = t;
        }
        
        while (a != null) {
            a = a.next;
            diff++;
        }

        a = headA;
        b = headB;
        
        while (diff-- > 0) {
            a = a.next;
        }
        while (a != null && b != null) {
            if (a == b)
                return a;
            a = a.next;
            b = b.next;
        }
        
        return null;       
    }
}

[littlemoon-zh]

day 11

142. Linked List Cycle II

Floyd's Cycle Detection Algorithm

public class Solution {
    public ListNode getMeetPoint(ListNode slow, ListNode fast) {
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow)
                return fast;
        } 
        return null;
    }
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        fast = getMeetPoint(slow, fast);
        if (fast == null)
            return null;
        
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

[littlemoon-zh]

day 12

146. LRU Cache

class LRUCache {
    class Node {
        int val;
        int key;
        Node pre;
        Node next;
        public Node(int k, int v) {
            this.val = v;
            this.key = k;
            this.pre = null;
            this.next = null;
        }
    }
    
    Node start = new Node(0,0);
    Node end = new Node(0,0);
    
    int capacity;
    int size;
    Map<Integer, Node> kvs;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.kvs = new HashMap<>();
        start.next = this.end;
        end.pre = this.start;
        this.size = 0;
    }
    
    public Node remove(Node node) {
        Node a = node.pre;
        Node b = node.next;
        a.next = b;
        b.pre = a;
        size--;
        return node;
    }
    
    public void addFirst(Node node) {
        size++;
        node.next = this.start.next;
        this.start.next.pre = node;
        node.pre = this.start;
        this.start.next = node;
    }
    
    public int get(int key) {
        if (!this.kvs.containsKey(key))
            return -1;
        Node node = this.kvs.get(key);
        remove(node);
        addFirst(node);
        return node.val;
    }
    
    
    public void put(int key, int value) {
        Node node = new Node(key, value);
        
        if (this.kvs.containsKey(key)) {
            remove(kvs.get(key));
        }
        addFirst(node);
        this.kvs.put(key, node);
        if (this.size > this.capacity) {
            node = remove(this.end.pre);
            this.kvs.remove(node.key);
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

day 13

104. Maximum Depth of Binary Tree

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null)
            return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

day 14

100. Same Tree

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null)
            return true;
        else if (p != null && q != null)
            return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        return false;            
    }
}

[littlemoon-zh]

day 15

129. Sum Root to Leaf Numbers

class Solution {
    int ans = 0;
    
    public void getSum(TreeNode root, int cur) {
        if (root == null)
            return;
        if (root.left == null && root.right == null) {
            ans += cur * 10 + root.val;
            return;            
        }
        getSum(root.left, cur * 10 + root.val);
        getSum(root.right, cur * 10 + root.val);
        
    }
    public int sumNumbers(TreeNode root) {
        getSum(root, 0);
        return this.ans;
    }
}

day 16

513. Find Bottom Left Tree Value

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int ans = 0;
        Deque<TreeNode> q = new LinkedList<>();
        q.addLast(root);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.pollFirst();
                if (i == 0)
                    ans = node.val;
                if (node.left != null)
                    q.addLast(node.left);
                if (node.right != null)
                    q.addLast(node.right);
            }
        }
        return ans;
    }
}

[littlemoon-zh]

day 17

297. Serialize and Deserialize Binary Tree

public class Codec {
    
    public StringBuilder sb = new StringBuilder();
    
    public void encoder(TreeNode root) {
        if (root == null) {
            sb.append(" ,");
            return;
        }
        sb.append(root.val+",");
        encoder(root.left);
        encoder(root.right);
    }
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        encoder(root);
        return sb.toString();
    }
    int t = 0;
    public TreeNode decoder(String[] s) {
        if (t == s.length)
            return null;
        
        if (s[t].equals(" "))
            return null;
        TreeNode root = new TreeNode(Integer.parseInt(s[t]));
        ++t;
        root.left = decoder(s);
        ++t;
        root.right = decoder(s);
        return root;
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] s = data.split(",");
        return decoder(s);
    }
}

day 18

987. Vertical Order Traversal of a Binary Tree

其实就是自定义排序，如果col相同按照row排，如果row也相同再按照val排，最后按照col的值group一下输出结果，看到有人用TreeMap + PriorityQueue来做，可以但没必要吧。

class Solution {
    
    List<Integer[]> list = new LinkedList<>();
    
    public void dfs(TreeNode root, int row, int col) {
        if (root == null)
            return;
        
        list.add(new Integer[]{col, row, root.val});
        dfs(root.left, row+1, col-1);
        dfs(root.right, row+1, col+1);
    }
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        dfs(root, 0, 0);
        list.sort(new Comparator<Integer[]>() {
            public int compare(Integer[] o1, Integer[] o2) {
                for (int i = 0; i < 3; i++)
                    if (o1[i] != o2[i])
                        return Integer.compare(o1[i],o2[i]);
                return 0;
            }
        });
        
        List<List<Integer>> res = new LinkedList<>();
        
        int last = list.get(0)[0];
        List<Integer> line = new LinkedList<>();
        
        for (Integer[] li : list) {
            if (last != li[0]) {
                res.add(line);
                last = li[0];
                line = new LinkedList<>();
                line.add(li[2]);
            } else {
                line.add(li[2]);
            }
        }
        res.add(line);
        return res;
    }
}

[littlemoon-zh]

day 19

two sum

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

[littlemoon-zh]

day 20

347. Top K Frequent Elements

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        c = collections.Counter(nums)
        return [ v[0] for v in c.most_common(k)]

day 21

447. Number of Boomerangs

class Solution:
    def numberOfBoomerangs(self, ps: List[List[int]]) -> int:
        def dis(a, b):
            return (a[0]-b[0]) ** 2 + (a[1]-b[1]) ** 2
        m = collections.Counter()
        
        for i in range(len(ps)):
            for j in range(i+1, len(ps)):
                d = dis(ps[i], ps[j])
                m[i, d] += 1
                m[j, d] += 1
        
        res = 0
        for k, v in m.items():
            res += v * (v - 1)
        return res