Basic Coding Problem

必背

Questions

Array

Array里面元素的type, Array是否null?（空集时返回什么值？）数据的大小0-n? 是否有负数negative? array长度?

input is n

type: string, char, int, double/f negative/positive

ListNode

structure {}, circle?

TreeNode

structure {}, searching relate: ask if it is BST?, complete tree,

LRU

难题送分题
Cache有一个TTL来决定time-to-leave，这个cache的有效时间，过了这个时间会重新去database里面更新一次
Cashe strategy有很多种，LRU，LFU（frequency）

LinkedHashMap

最好要掌握用node实现linkedlist的方法
set方法不要忘记两点：

1. 是否已存在这个key，改写value的同时要更新order
2. 是否容量已满，容量满要删除least active element

方法1： 直接extend。LinkedHashMap本身可以选择access order

<font color = red>缺点：</font>

• constructor要输入全部的param，包括默认的capacity16，loadfactor0.75f（还有可能忘记这个f），最后是true for access-order。
• 当capacity满了时，要去掉最久远访问的那一个，可以override protected boolean removeEldestEntry()不过很可能忘记或不熟练

方法2：生成一个全局用的map裹在里面用于实现方法。用默认的param，只利用insertion-order

<font color = red>优点：</font>

• 不容易记错
  The iteration order is the same as insertion order (The first is the firstly inserted (the so-called oldest in this problem))
• 需要注意的是，因为是insert order，当你get一个值时，应当remove它，然后重新put到map里面，等于时重新insert这个值，更新它的顺序
• 还有注意的是，再put时如果这个key已经存在于map中，那就意味着要更新order，此时可以使用2中的方法（也可以remove后再put？）

quick sort

先从序列中挑选一个pivot（一般挑选该序列最后一位），将所有比pivot小、比pivot大、和pivot一样的分成三个集合，对于大于和小于两个集合再重复操作；
in-place做法是：从除去pivot的序列的两边开始比较，左边应该小，右边应该大，违反规则就swap

• quicksort一般是void，可递归的method所需要的param有三个：int[] nums; int startindex; int endindex
• 每一次partition的时候，rightpointer和leftpointer会交错一位，左指针在右边，右指针在左边
• 所以开始下一次递归的时候，左半边的end等于right index；而start等于left index

merge sort

先分开，一直分到n<2后返回，然后被分开的两个子集merge，merge的时候要从小到大排列

binary search

前提是sorted & indexable sequence of elements 切记sorted！！

//iteration
while (low <= high) {
    if (mid == target) return mid;
    if (mid < target) low = mid + 1;
    if (mid > target) high = mid - 1;
}
//recursion
if (low > high) return -1;
if (mid == target) return mid;
else if (mid < target) return binarySearch(array, target, mid+1, high);
else return binarySearch(array, target, low, mid-1);

Merge K sorted lists

Merge k sorted linked lists and return it as one sorted list.

• 注意检验if (lists == null || lists.length == 0) return null;
• 用heap存储所有的ListNode（头），也就是每个ListNode后面还连着一串
• 第一次用heap添加所有ListNode时，记得检查```if(list.get(i) != null)``

• heap.poll()取出val值最小的ListNode，如果Node.next != null把Node.next放回去

• 注意heap要改写comparator，如何比较两个ListNode大小Integer.compare(l1.val, l2.val)
• @Override 要大写！！
• 在中括号中override，然后在括号闭上之后，记得写分号;

Add two numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

<font color = red>注意</font>：

• 创建一个Node pre-head用于返回
• 创建一个pointerNode ptr用于pathing
• 每一次loop，计算sum时记得加上前一次loop的carry，然后先计算这一次loop的carrycarry = sum / 10，然后再算余数sum %= sum 不要混淆！！
• while loop的条件有三个，l1 != null || l2 != null || carry != 0 一定要记得最后一位的两数相加也可能超过10，进一位！

Add two numbers II

• reverse singly LinkedList 的方法！用一个向前指针控制下一个forward = head.next，然后头部节点指向一个记忆指针last(initially = null)，变成尾节点head.next = null，然后curr指向向前指针，即向前走一步，curr = forward， 然后记忆指针储存curr，作为下一个节点的lastlast = curr
• 每一次新建node，新node放在头部，也就是说指针向左移动

    ListNode newNode = new ListNode(sum);
    newNode.next = temp;
    temp = newNode;
  

• ← Previous Post
• Next Post →