leetcode 150道題 計劃花兩個月時候刷完，今天（第四天）完成了4道(10-13)150：
10. （45. 跳躍游戲 II）題目描述：

給定一個長度為 n 的 0 索引整數數組 nums。初始位置為 nums[0]。
每個元素 nums[i] 表示從索引 i 向前跳轉的最大長度。換句話說，如果你在 nums[i] 處，你可以跳轉到任意 nums[i + j] 處:
0 <= j <= nums[i] 
i + j < n
返回到達 nums[n - 1] 的最小跳躍次數。生成的測試用例可以到達 nums[n - 1]。

第一版（這個和昨天是一樣的，就還是那樣，只是多加了一個計數器，我沒有看最優解，這個我能記住。。最優解記不住）

class Solution {public int jump(int[] nums) {// 和上一個跳躍 是一樣的//如果跳不到終點就盡可能跳到最遠int len=nums.length;int index=0;int res=0;while(index<len-1){int temp=nums[index]+index;if(temp>=len-1){return res+1;}int max=0;for(int i=index+1;i<=temp;i++){if(nums[i]==0){continue;}if(nums[i]+i>=max){index=i;max=nums[i]+i;}}// 這個應該可以不加判斷，題目應該會保證給的測試例子都可以跳到終點的。。if(max==0)return 0;res++;}return res;}
}

11. （274. H 指數）題目描述：

給你一個整數數組 citations ，其中 citations[i] 表示研究者的第 i 篇論文被引用的次數。計算并返回該研究者的 h 指數。
根據維基百科上 h 指數的定義：h 代表“高引用次數” ，一名科研人員的 h 指數 是指他（她）至少發表了 h 篇論文，并且每篇論文 至少 被引用 h 次。如果 h 有多種可能的值，h 指數 是其中最大的那個。

這個題我真的做了至少四遍了，每次都做不出來，是真的理解不了他說的，然后我去查了維基百科上的，上面就有算法（我感覺這個好理解，最優的二分法感覺記不住。。）：
可以按照如下方法確定某人的H指數：
1、將其發表的所有SCI論文按被引次數從高到低排序；
2、從前往后查找排序后的列表，只要當前的引用量大于當前的索引值，則H指數加1，最后得到的結果即為最終的H指數
第一版（按照這個維基百科算法去寫的）

class Solution {public int hIndex(int[] citations) {int hNum=0;int len=citations.length;Arrays.sort(citations);for(int i=len-1;i>=0;i--){if(citations[i]>len-i-1)hNum++;}return hNum;}
}

12. （380. O(1) 時間插入、刪除和獲取隨機元素）題目描述：

實現RandomizedSet 類：
RandomizedSet() 初始化 RandomizedSet 對象
bool insert(int val) 當元素 val 不存在時，向集合中插入該項，并返回 true ；否則，返回 false 。
bool remove(int val) 當元素 val 存在時，從集合中移除該項，并返回 true ；否則，返回 false 。
int getRandom() 隨機返回現有集合中的一項（測試用例保證調用此方法時集合中至少存在一個元素）。每個元素應該有 相同的概率 被返回。
你必須實現類的所有函數，并滿足每個函數的 平均 時間復雜度為 O(1) 。

第一版（代碼比較長，就只放一版，這個確實人家在刪除時候處理很巧妙，值得學習）

class RandomizedSet {ArrayList<Integer> list;Random random;Map<Integer,Integer> map;public RandomizedSet() {list=new ArrayList<Integer>();random = new Random();map=new HashMap<Integer,Integer>();}public boolean insert(int val) {if(map.keySet().contains(val))return false;list.add(val);map.put(val,list.size()-1);return true;}public boolean remove(int val) {if(!map.keySet().contains(val))return false;int index=map.get(val);int lastValue=list.get(list.size()-1);map.put(lastValue,index);list.set(index,lastValue);list.remove(list.size()-1);map.remove(val);return true;}public int getRandom() {int size=list.size();return list.get(random.nextInt(size));}
}

13. （238. 除自身以外數組的乘積）題目描述：

給你一個整數數組 nums，返回 數組 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘積 。
題目數據 保證 數組 nums之中任意元素的全部前綴元素和后綴的乘積都在  32 位 整數范圍內。
請 不要使用除法，且在 O(n) 時間復雜度內完成此題。

第一版（當然是暴力求解了，但是我加了一些優化以為是最優解，沒想到超時了。。）

class Solution {public int[] productExceptSelf(int[] nums) {int len=nums.length;int[] res=new int[len];for(int i=0;i<len;i++){if(nums[i]==0){// 其他為 0 res[i]=getNum(nums,i);return res;}}for(int i=0;i<len;i++){res[i]=getNum(nums,i);}return res;}public int getNum(int[] nums,int i){int temp=1;for(int j=0;j<nums.length;j++){if(j==i){continue;}if(nums[j]==0){temp=0;break;} temp*=nums[j];}return temp;}
}

第二版（看的解析，人家還是厲害啊！！）

class Solution {public int[] productExceptSelf(int[] nums) {int len=nums.length;int[] res=new int[len];int[] lAnswer=new int[len];int[] rAnswer=new int[len];lAnswer[0]=1;for(int i=1;i<len;i++){lAnswer[i]=nums[i-1]*lAnswer[i-1];}rAnswer[len-1]=1;for(int i=len-2;i>=0;i--){rAnswer[i]=nums[i+1]*rAnswer[i+1];}for(int i=0;i<len;i++){res[i]=lAnswer[i]*rAnswer[i];}return res;}
}

早日跳槽，跳槽！！！！！
真的現在待的公司感覺一點前途都沒有。。看不到未來啊。