上一篇博客：
leetcode刷題記錄01——top100題里的7道簡單題
leetcode刷題記錄02——top100題里的7道簡單題

1. 有效的括號
   看懂需要用棧了，但是不知道怎么去寫，看了題解mark下正確答案。

   class Solution {public boolean isValid(String s) {int n = s.length();if(n%2==1){return false;}Map<Character,Character> map = new HashMap<Character,Character>(){{put('}','{');put(')','(');put(']','[');}};Deque<Character> stack = new LinkedList<Character>();for(int i = 0; i< n; i++){Character ch = s.charAt(i);if(map.containsKey(ch)){if(stack.isEmpty() || stack.peek() != map.get(ch)){return false;}stack.pop();}else{stack.push(ch);}}return stack.isEmpty();}
   }
   

2. 買賣股票的最佳時機
   暴力遍歷會超時
   看了題解，記錄之前的最小價格，記錄截至當前的最大利潤。

   class Solution {public int maxProfit(int[] prices) {int minPrice = Integer.MAX_VALUE;int maxProfit = 0;for(int i = 0; i< prices.length; i++){if(prices[i] <= minPrice){minPrice = prices[i];}if(maxProfit <= prices[i]-minPrice){maxProfit = prices[i]-minPrice;}}return maxProfit;}
   }
   

3. 爬樓梯
   一看就會，一寫就廢🤦?
   這道題看著很簡單，每次爬1或者2個樓梯，10個樓梯有多少種爬法。很好理解，少的樓梯可以手撕。寫起來就不會了… 想到了遞歸，但不會寫方法；
   看了題解正確答案，這個還比較好理解；

   class Solution {public int climbStairs(int n) {int p = 1;int q = 2;if(n==1){return p;}else if(n==2){return q;}else{int r = 0;// 從第三樓開始，只有兩種上樓方式，從前一層再爬一樓和從前二層再爬兩樓。// 可以推出 f(n) = f(n -1) + f(n -2)// 直接遞歸會超時，所以用的for循環求結果for(int i =3;i<=n;i++){r = p+q;p = q;q = r;}return r;}}
   }
   

4. 楊輝三角
   可以追溯到我幸福童年小學時光的一道題，那會為了不再教室可以在外邊望望風，拿著一本奧賽題書問老師這個問題…
   比較好理解，遞歸。直接來一個二維數組或者List<List>來存儲。
   核心"j == 0 || j == i" 為1，其余的需要根據上一個行的值來計算求解： [i-1][j-1]+[i-1][j] 來獲取其值。

   class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> ret = new ArrayList<List<Integer>>();for(int i = 0;i<numRows;i++){List<Integer> row = new ArrayList<Integer>();for(int j = 0;j<=i;j++){if(j==0 || j==i){row.add(1);}else{row.add(ret.get(i-1).get(j-1)+ret.get(i-1).get(j));}}ret.add(row);}return ret;}
   }
   

5. 只出現一次的數字
   異或來自官方的答案。其實也可以排序完然后判斷是返回那個。
   任意數字與0做異或都得到該數字。

   class Solution {public int singleNumber(int[] nums) {int single = 0;for(int num: nums){single ^= num;}return single;}
   }
   

6. 多數元素
   一遍過，靈感乍現，給數組排個序，再計算count數，就可以找到了。
   還可以更簡化，因為題目中已經給定了多數元素個數超過了n/2，所以排序完直接返回 n/2下標處的元素就可以了。

7. 中等難度：字母異位詞組
   第一反應是先把倆個只有一個元素的情況兼容處理，然后對于有多個的，可以對每個詞里包含的字母按照升序排列后如果一致，那就是異位詞組。
   str.split(“”)得到字符串數組 String[]; 或者str.charAt(i)得到每一位上的數值，然后String[] 轉string， String.join(“”,strArray) 或者 StringUtils.join(strArray)； 或者 官方答案：str.toCharArray() 得到 char[]，然后Arrays.sort(char[]) , new String(char[])轉回str。

class Solution {public List<List<String>> groupAnagrams(String[] strs) {List<List<String>> list = new ArrayList<>();if(strs.length ==1){List<String> strList = new ArrayList<>();strList.add(strs[0]);list.add(strList);return list;}Map<String,List<String>> map = new HashMap<String,List<String>>();for(String str: strs){String[] chs = str.split("");Arrays.sort(chs); String strLower = String.join("",chs);if(map.containsKey(strLower)){map.get(strLower).add(str);}else{List<String> strList = new ArrayList<>();strList.add(str);map.put(strLower,strList);}}for(String key: map.keySet()){list.add(map.get(key));}return list;}
}