Leetcode 1

第一道题是Two Sum，我的想法根暴力解法一样，没有考虑到时间和空间的复杂性，所以很浪费时间和空间。（因为每次都需要把整个列表循环一次，所以时间复杂性(Time complexity)为O(n^2)
空间复杂性O(1) 因为没有用多余的列表来存储？

第一道题

看了解法2 之后才发现自己cs61b上课的东西真的是一点没记住😂，里面讲hash map的时候我脑子里没法直接构建出老师上课讲的时候画的图，说明自己还不够清楚hash table如何工作，我觉得leetcode根cs61b一起学会非常有效。
一会吃午饭重新看一下cs61b里面对hashtable的讲解。然后才结合这个解法巩固一下这个概念。
hash table : Data is converted by a hash function into an integer representation called a hash code.
The hash code is then reduced to a valid index, usually using the modulus operator, e.g. 2348762878 % 10 = 8

就是说哈希表实际上就是因为所有的character因为overflow的原因不能全部放在一个列表里，所以用hash function算出这个character的哈希值之后在用modulus（余数）来存放在一个列表里。这样随着这个列表的大小变化，它的look up time complexity 是O(1) 因为每次你的threshold超过了设定值，你就可以重新扩大或者缩小这个表。O(N/M) = O(1) 因为N/M是常数。但是由于最大的一行还有可能是N（就是你hash code正好把所有的char放到了一行里面），所以time complexity 还是O(n)

cs61b hash table

在java里面用hash table就需要用 java.util.HashMap 和 java.util.HashSet 来调用
*.put 就是把char放进hashmap 里面， *.containsKey 就是寻找这个hashmap里面有没有你想要找的东西。 *.get 就是得到这个数对应的key

解法2

小记：一开始还想用enhanced for loop来写这段……结果老是没法compile，最后直接用原始的for loop了。

第二题
Reverse integer
这道题刚开始没思路，所以先看解题思路了。
Approach 1: Pop and Push Digits & Check before Overflow
We can build up the reverse integer one digit at a time. While doing so, we can check before hand whether or not appending another digit would cause overflow.
Algorithm
reversing an integer can be done similarly to reversing a string.
We want to repeatedly "pop"(冒泡法？) the last digit off of x and "push" it to the back of the rev. In the end, rev will be the reverse of the x.

To "pop" and "push" digits without the help of some auxiliary stack/array, we can use math.

pop = x%10;
x/=10;
temp = rev *10 +pop;
rev = temp;

啊，这里是先mod 10然后拿到最后一位数，再除以10把最后一位数删掉，一次无限循环知道整个数被算完。这里有个视频讲解得挺好的reverse_int

class Solution {
public int reverse(int x) {
int rev = 0;
while (x != 0) {
int pop = x % 10;
x /= 10;
if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
rev = rev * 10 + pop;
}
return rev;
}
}