leetcode刷题记录03——top100题里的6道简单+1道中等题

上一篇博客：
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;}
}