【数算】复习1

﹏ヽ暗。殇╰゛Y 2022-09-11 03:28 121阅读 0赞

## 2021年9月10日 ##

### 239. 滑动窗口问题 ###

> 处理窗口的滑动路径

[https://leetcode-cn.com/problems/sliding-window-maximum/][https_leetcode-cn.com_problems_sliding-window-maximum]

public int[] maxSlidingWindow(int[] nums, int k) {
        
            if( nums == null || k<1 || k > nums.length ) return null;
            int len = nums.length;
            int[] window = new int[len - k +1];
            int idx = 0;
            Deque<Integer> deque = new LinkedList<>();
    
            for(int i = 0; i<len; i++){
        
                // 非空说明里面有东西可以弹出，判断什么样的东西可以弹出
                // 进入的数字比较大，把里面的数字都弹出
                while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]){
        
                    deque.pollLast();
                }
                // 不论如何，新遇到的数字都要加进去在里面进行计算
                deque.offer(i);
                // 当前位置减去窗口大小就是过期的idx（窗口前一个元素）
                if(deque.peekFirst() == i-k) {
        
                    deque.pollFirst();
                }
                // 判断当前的i是否有效（i必须走到窗子的最右边那个元素才开始）
                if(i >= k-1) {
        
                    window[idx++] = nums[deque.peekFirst()];
                }
            }
            return window;
        }

### 最长字串问题 ###

> 中间扩撒法

[https://leetcode-cn.com/problems/longest-palindromic-substring][https_leetcode-cn.com_problems_longest-palindromic-substring]

public String longestPalindrome(String s) {
        
        if(s.length() == 1) return s;
        int len = 0;
        int resBegin = 0;
        int resLen = 1;
        int l = 0;
        int r = 0;
    
        for (int i = 0; i < s.length(); i++ ) {
        
            l = i-1;
            r = i+1;
            // 向左边扩容和向右边扩容
            while(l>=0 && s.charAt(l) == s.charAt(i)) {
        
                l--;
                len++;
            }
            while(r<s.length() && s.charAt(r) == s.charAt(i)) {
        
                r++;
                len++;
            }
            // 向两边一起扩容
            while( l>=0 && r<s.length() && s.charAt(l) == s.charAt(r) ) {
        
                l--;
                r++;
                len+=2;
            }
            if (len > resLen) {
        
                resLen = len;
                resBegin = l;
            }
            len = 1;
        }
        return s.substring(resBegin+1, resLen+resBegin+1);
    }

### 42. 接雨水 ###

双指针问题  
https://leetcode-cn.com/problems/trapping-rain-water/

class Solution {
        
        public int trap(int[] height) {
        
            if (height == null || height.length == 0) return -1;
            // 找到最高的点，接水问题最高点很重要！
            int maxIdx = 0;
            int res = 0;
            for(int i = 0; i<height.length; i++) {
            
               maxIdx = height[i] > height[maxIdx] ? i : maxIdx;
            }
            // 累加左边的水量，一个一个算
            int maxleft = 0;
            for(int i=0; i<maxIdx; i++) {
        
                if(height[i] > maxleft) {
        
                    maxleft = height[i];
                }else {
        
                    res += (maxleft - height[i]);
                }
            }
            // 累加右边的水量，一个一个算（从右边开始）
            int maxRight = 0;
            for(int i = height.length-1; i>maxIdx; i--) {
        
                if(maxRight < height[i]){
        
                    maxRight = height[i];
                }else {
        
                    res += (maxRight - height[i]);
                }
            }
    
            return res;
        }
    }

### 判断是否二叉树 后续遍历的序列 ###

链接：  
[二叉搜索树的后序遍历序列][Link 1]

class Solution {
        
        public boolean verifyPostorder(int[] postorder) {
        
            return verify(postorder, 0, postorder.length-1);
        }
    
        public static boolean verify(int[] postorder, int l, int r) {
        
            if( l >= r ) return true;
    
            // 找到前段落区域的划分点i-1，r是最右边的节点位置
            int i = 0;
            for (;i<r;i++) {
        
                if(postorder[i] > postorder[r]) break;
            }
    
            // 判断右树是否合格（右树都比根节点的数字大,遇到小的return false）
            for (int tmp = i; tmp<r; tmp++) {
        
                if(postorder[tmp] < postorder[r]) return false;
            }
            
            if(i==0 || i==r-1) {
        
                // i在两端，无法区分，只能说明最后的节点确实是根节点
                return verify(postorder, l, r-1);
            }else {
        
                // i落在中间的位置，需要将两边分开来判断
                return verify(postorder, l, i-1) && verify(postorder, i, r-1);
            }
        }
    }

## 2021年9月11日 ##

### 求二叉树的深度 ###

> dfs思想

https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/

public static int inorder(TreeNode node) {
        
        if(node == null) return 0;
        return Math.max(inorder(node.left), inorder(node.right))+1;
    }

### 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先【简单】 ###

https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/

使用set和HashMap来进行处理，就变得简单了很多

class Solution {
        
        HashMap<TreeNode, TreeNode> fatherMap = new HashMap<>();
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            // 加载好fatherMap，维护好哈希表
            loadFatherMap(root, null);
    
            // p节点的向上走的路径保存起来在HashSet的path中
            Set<TreeNode> path = new HashSet<>();
            while (fatherMap.containsKey(p)) {
        
                path.add(p);
                p = fatherMap.get(p);
            }
    
            // 找到q节点在path中的位置（一定存在，大家的父亲都是一样）
            while (!path.contains(q)) {
        
                q = fatherMap.get(q);
            }
            return q;
        }
    
        public void loadFatherMap(TreeNode cur, TreeNode father) {
        
            if (cur == null) return;
            fatherMap.put(cur, father);
            loadFatherMap(cur.left, cur);
            loadFatherMap(cur.right, cur);
        }
    }

## 2021年9月13日 ##

### 11. 盛最多水的容器 ###

![在这里插入图片描述][6afb849743eb467fb5c6a1c0e0ded722.png]

双指针思想，主要集中在找最多水的节点。  
https://leetcode-cn.com/problems/container-with-most-water/

class Solution {
        
        public int maxArea(int[] height) {
        
            int maxArea = 0;
            int l = 0;
            int r = height.length-1;
            while(l<r) {
        
                maxArea = Math.max(maxArea, (r-l) *  Math.min(height[l], height[r]));
                if(height[l] < height[r]) {
        
                    l++;
                }else {
        
                    r--;
                }
            }
            return maxArea;
        }
    }

### merge合并算法（排序算法之一）： ###

分治思想

public static void mergeSort(int[] arr, int left, int right) {
        
        //如果左边索引小于右边就可以一直分，l=r时，就是分到只剩一个数了
        if (left < right) {
        
            int mid = left + ((right - left) >> 1);
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            // 最关键的操作：合并
            merge(arr, left, mid, right);
        }
    
    }
    public static void merge(int[] arr, int l, int mid, int r) {
        
    	// 建立中转数组
        int[] temp = new int[r - l + 1];
        int tIdx = 0;
        int i = l;
        int j = mid + 1;
    
        while (i <= mid && j <= r) {
        
            temp[tIdx++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) {
        
            temp[tIdx++] = arr[i++];
        }
        while (j <= r) {
        
            temp[tIdx++] = arr[j++];
        }
    
        tIdx = 0;
        while (l <= r) {
        
            arr[l++] = temp[tIdx++];
        }
    }

### 前缀树的实现： ###

《实现搜索引擎的搜索关键词提示功能？》的很关键的算法  
通过startsWith方法可以很便捷的确认接下来可能到达的路径是否可行，Trie也叫做字典树，关键在于【前缀匹配查找】  
Trie 树的变体有很多，都可以在一定程度上解决内存消耗的问题。比如，缩点优化，就是对只有一个子节点的节点，而且此节点不是一个串的结束节点，可以将此节点与子节点合并。

1、Trie 树中用到了指针，所以，对缓存并不友好，性能上会打个折扣。  
2、要求字符串的前缀重合比较多，不然空间消耗会变大很多。  
3、但是在搜索的时候、自动补全的时候大有益处（平时的输入法就自带这个功能）

class Trie {
        
    
        public static class TrieNode{
        
            public int passCount;
            public int endCount;
            // 结点所走过的边
            public TrieNode[] paths; 
    
            public TrieNode(){
        
                passCount = 0;  
                endCount = 0;
                paths = new TrieNode[26];
            }
        }
    
        TrieNode root;
        /** Initialize your data structure here. */
        public Trie() {
        
            root = new TrieNode();
        }
        
        /** trie树中插入一个字符串 */
        public void insert(String word) {
        
            if (word == null || word.length() == 0) return;
            char[] chs = word.toCharArray();
            TrieNode cur = root;
            cur.passCount = 1;
    
            for (int i=0; i<chs.length; i++) {
        
                int idx = chs[i] - 'a';
                //不存在就铺个路，存在就往下走
                if (cur.paths[idx] == null) {
        
                    cur.paths[idx] = new TrieNode();
                }
                cur = cur.paths[idx];
                cur.passCount++;
            }
            cur.endCount++;
        }
        
        /** Returns if the word is in the trie. */
        public boolean search(String word) {
        
            if (word == null || word.length() == 0) return false;
            char[] chs = word.toCharArray();
            TrieNode cur = root;
            for (int i = 0; i<chs.length; i++ ) {
        
                int idx = chs[i] - 'a';
                if (cur.paths[idx] == null) {
        
                    return false;
                }
                cur = cur.paths[idx];
            }
            if (cur.endCount > 0 ) return true;
            return false;
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
        
            if (prefix == null) return false;
    
            char[] chs = prefix.toCharArray();
            TrieNode cur = root;
            for (int i = 0; i<chs.length; i++) {
        
                int idx = chs[i] - 'a';
                if (cur.paths[idx] == null) {
        
                    return false;
                }
                cur = cur.paths[idx];
            }
            return true;
        }
    }
    
    /**
     * Your Trie object will be instantiated and called as such:
     * Trie obj = new Trie();
     * obj.insert(word);
     * boolean param_2 = obj.search(word);
     * boolean param_3 = obj.startsWith(prefix);
     */

### 763. 划分字母区间 ###

> 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

https://leetcode-cn.com/problems/partition-labels/

class Solution {
        
        public List<Integer> partitionLabels(String s) {
        
            // 创建map，让map装载每个字母的最大限度。
            HashMap<Character, Integer> map = new HashMap<>();
            List<Integer> list = new ArrayList<>();
            for(int i =0;i<s.length(); i++) {
        
                map.put(s.charAt(i),i);
            }
            // 用start来管理下一次开始的位置，不断找寻
            int start = 0;
            int last = 0;
            for(int i = 0; i<s.length(); i++) {
        
                last = Math.max(last, map.get(s.charAt(i)));
                if(last == i) {
        
                    list.add(last - start + 1);
                    start = last + 1;
                }
            }
    
            return list;
        }
    }

小优化：讲HashMap表改为数组来作为缓存，更加节省空间

class Solution {
        
        public List<Integer> partitionLabels(String s) {
        
            // 创建map数组，让map装载每个字母的最大限度。
            int[] map = new int[26];
            List<Integer> list = new ArrayList<>();
            for(int i =0;i<s.length(); i++) {
        
                map[s.charAt(i)-'a'] = i;
            }
            // 用start来管理下一次开始的位置，不断找寻
            int start = 0;
            int last = 0;
            for(int i = 0; i<s.length(); i++) {
        
                last = Math.max(last, map[s.charAt(i)-'a']);
                if(last == i) {
        
                    list.add(last - start + 1);
                    start = last + 1;
                }
            }
    
            return list;
        }
    }

### 821、字符最短距离： ###

这题主要是两头遍历的思想，本质还是贪心算法  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16]

class Solution {
        
        public int[] shortestToChar(String s, char c) {
        
            int[] res = new int[s.length()];
            int meet = Integer.MIN_VALUE >> 1;
            for (int i = 0; i<s.length(); i++) {
        
                // 只有当遇到了才更新meet为遇到的地址
                if ( s.charAt(i) == c ) meet = i;
                res[i] = i - meet;
            } 
    
            for (int i = s.length()-1; i>=0; i--) {
        
                if ( s.charAt(i) == c ) meet = i;
                int tmp = meet - i;
                // 取二者的最小值
                res[i] = Math.min(res[i], tmp);
            }
    
            return res;
        }
    }

### 8. 字符串转换整数 (atoi) ###

巨有意思的题目：  
对于这题，要考虑到各种情况的发生，特别是数字与非数字的处理，还有数字的越界问题，分门别类处理好问题就不大

https://leetcode-cn.com/problems/string-to-integer-atoi/

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 1]

class Solution {
        
        public int myAtoi(String s) {
        
            s = s.trim();
            if(s == "" || s.length() == 0) return 0;
            long res = 0;
    
            // 处理首位，只处理“+/-”符号，再对以下的进行处理
            int flag = 1;
            int i = 0;
            if (s.charAt(0) == '+') {
        
                flag = 1; i++;
            }else if (s.charAt(0) == '-') {
        
                flag = -1; i++;
            }
    
            for (;i < s.length(); i++) {
        
                char ch = s.charAt(i);
                if (ch<='9' && ch>='0') {
        
                    // 1、属于数字：
                    res = res*10 + (ch-'0');
                }else {
        
                    // 2、输入的不属于数字
                    return (int)res*flag;
                }
                if(res > Integer.MAX_VALUE && flag == -1) {
        
                    // 1.1、 纯数字越界最大值
                    return Integer.MIN_VALUE;
                }else if (res > Integer.MAX_VALUE && flag == 1) {
        
                    // 1.2、 纯数字越界最小值 
                    return Integer.MAX_VALUE;
                }
            }
            return (int)res * flag;
        }
    }

[https_leetcode-cn.com_problems_sliding-window-maximum]: https://leetcode-cn.com/problems/sliding-window-maximum/
[https_leetcode-cn.com_problems_longest-palindromic-substring]: https://leetcode-cn.com/problems/longest-palindromic-substring
[Link 1]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
[6afb849743eb467fb5c6a1c0e0ded722.png]: /images/20220828/20643423c747483792fecab19a7714fc.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/470fa9b017504c1eb72e93281eed036e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/663ef0b05c964bc4b4b18397ebb6762d.png