秋招突击——算法学习——8/5——算法整体复习{两数之和、字母异位词分组、最长连续序列、移动零、盛最多水的容器、三数之和、无重复最长子串、找到字符串中所有字母异位词、和为K的子数组、二叉树的最大深度}

引言

• 今天坐高铁，十二个小时，单纯刷题，刷已经做过的题目，能刷多少刷多少！
• 在做的过程中，遇到的问题先挖个坑，等我晚上到学校了，再一个一个填上，加深一下记忆！

复习

1.两数之和

个人实现

class Solution {
   
    public int[] twoSum(int[] nums, int target) {
   
        int[] res = {
   -1,-1};
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < nums.length;i ++) map.put(nums[i],i);
        for(int i = 0;i < nums.length;i ++) {
   
            if(map.containsKey(target - nums[i]) && map.get(target - nums[i]) != i){
   
                res[0] = i;
                res[1] = map.get(target - nums[i]);
            }
        }
        return res;
    }
}

参考实现

class Solution {
   
    public int[] twoSum(int[] nums, int target) {
   
        // define hashmap to store the  value
        HashMap<Integer,Integer>   dict = new HashMap<>();
        for(int i = 0;i < nums.length;i ++){
   
            int compart = target - nums[i];
            if(dict.containsKey(compart)){
   
                return new int[] {
   i,dict.get(compart)};
            }else{
   
                dict.put(nums[i],i);
            }
        }
        return new int[] {
   -1,-1};

    }
}

• 思路基本上一致，但是这里忘记了怎么快速返回数组，具体使用如下语句

new int[]{
   a,b};

49.字母异位词分组

个人实现

• 这个是将所有字母相同的单词进行组合，判定是否包含字母，如果是string的contains方法，相当于是遍历的，时间复杂度并不低，还是使用hash表，能够降低时间复杂度。
• 不行，如果这样的话，还是比较慢，不如直接进行排序，创建一个临时的排序之后的string ，然后在比较是否相同。
• 这里又有一个问题，就是不知道怎么将string转成char型的数组，然后再将char型数组转成对应的string并不会的，这两个操作不熟悉，只能硬实现。

class Solution {
   
    public List<List<String>> groupAnagrams(String[] strs) {
   
        List<List<String>> res = new ArrayList<>();
        Map<String,Integer> map = new HashMap<>();
        for(String str :strs){
   
            char[] temp = new char[str.length()];
            for(int i = 0;i < str.length();i ++) temp[i] = str.charAt(i);
            Arrays.sort(temp);
            String tempStr = new String(temp);
            if(map.containsKey(tempStr)){
   
                res.get(map.get(tempStr)).add(str);
            } else{
   
                map.put(tempStr,res.size());
                List<String> list = new ArrayList<>();
                list.add(str);
                res.add(list);
            }
        }
        return res;
    }
}

• 到站了，第一个站台就刷了两道题，差不多十五分钟一道做过的题目。

参考实现

• 参考代码更加简洁，思路基本上一致，来人了，没有充电线，所以要等等了
• 很幸运，无锡站没人上来，一直到下一站还是继续使用充电线！

class Solution {
   
    public List<List<String>> groupAnagrams(String[] strs) {
   
        // define the res 
        List<List<String>> res = new ArrayList<>();
        Map<String,ArrayList<String>> dict = new HashMap<>();
        
        // traverse all the elements
        for(String x : strs){
   
            // sort the chars in x
            char[] temp = x.toCharArray();
            Arrays.sort(temp);
            String strTemp = String.valueOf(temp);
            if(dict.containsKey(strTemp)){
   
                dict.get(strTemp).add(x);
            }else{
   
                dict.put(strTemp,new ArrayList<String>(Arrays.asList(x)));
              
            }
        }

        // traverse the map 
        for(String x : dict.keySet()){
   
            res.add(dict.get(x));
        }
        return res;
    }
}

string转成对应的char数组

char数组转成对应的string

128.最长连续序列

个人实现

• 这道题时间复杂度要求是O(n)，所以只能进行有限次遍历，使用hash表，找到最开头的字母，然后的往下一次遍历即可！

class Solution {
   
    public int longestConsecutive(int[] nums) {
   
        int res = 0;
        Set<Integer> set = new HashSet<>();
        for(int x: nums)    set.add(x);
        for(int x :nums){
   
            if(set.contains(x - 1)) continue;
            else{
   
                int curNum = 0;
                while(set.contains(x)){
     
                    x++;
                    curNum