12/1

1. Collatz Conjecture

/* If a number is odd, the next transform is 3*n+1 If a number is even, the next transform is n/2 The number is finally transformed into 1. The step is how many transforms needed for a number turned into 1. Given an integer n, output the max steps of transform number in [1, n] into 1.  */

1. 对于1到n的每一个数，都计算一遍（一个for循环）。

2. 对于每一个数，用以上公式计算step数。

3. 在每一个for循环结束前，用max来拿到/记录当前最大的步数，以及这个步数所对应的数。

4. 最后，return那个最大步数所对应的数字。

-> 边界条件，如果给的数小于1，return 0. 如果给的数等于1，return 1.

-> 这道题有两种写法，一种是iteration，一种是recursion。我自己写是用iteration写的，然后给的参考代码是用recursion写的，尽量保证两种都会。

-> 在参考代码里有一种优化写法。参考代码定义了一个hashmap作为全局变量，然后，对于每一个[1, n]中的数，都把它和它最后的step数记录到这个hashmap里。然后在recursion的计算过程中，在计算每个数之前，先check这个数是否在hashmap里有过历史记录，如果有这个历史记录，就可以直接用hashmap里的结果，而不是去再算一遍。这样以增加空间complexity为代价，略微提高了时间complexity。

 

2. Implement Queue with Limited Size of Arrays

/* implement 一个 queue，但是要求用 int[]储存，并且一次生成的 int[]长度不可以超过 5。其实这是 一个内存分配的模型，每个 int[]可以看成一个 block 的抽象，每次需要加更多元素的时候就要申 请多分配 block，remove 的时候就要回收 block。*/

问题：1. If I have a return type for poll(), what is the return value when there's no elements inside the array?

-> 在push里，如果tail的index到了fixedSize - 1 （或者fixedSize？），建一个新的list，把当前的数字加到新list里去，然后把新list加进老list里，然后让tailList指向新的list。

tailList = (List<Object>)tailList.get(tail); 然后把tail这个index设置成0. 如果没有到，就直接往tailList里面加元素。完了之后increase count，increase tail这个index。

-> 在poll里，如果count是0，return null。然后用head index得到head的value，increase head index，并且decrease count。如果head index到了一个list的临界点（参考代码给的是fixedSize - 1, 但是我觉得直接用fixedSize更好理解？），以head index的node为基础get 出一个新的list headList = (List<Object>)headList.get(head); ，把当前的headList清空，让headList指向这个新的list，然后把head index归零。最后，return那个记录下来的head value。

-> 自己想的办法：可以用一个大的list来记录每一个list的头，如果一个list结束了，抹去当前list，换到下一个？