Leetcode算法题笔记（3）

矩阵

101. 生命游戏

根据百度百科，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

进阶：

你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
在这里插入图片描述

解法一

非原地算法：将矩阵复制一份，遍历旧矩阵每个元素的周围8个元素，计算存活细胞数量，再根据规则在新矩阵上进行修改，返回新矩阵（一下阶段状态矩阵）。空间复杂度过高O（mn）。

解法二

原地算法：空间复杂度过高O（1）。可以找一个复合状态同时表示旧状态和新状态，例如定义：

如果细胞从活着变为死了，则复合状态为2；
如果细胞从死了变成活了，则符合状态为3；
之后便可按照算法一遍历元素，判断周围存活元素时，需要参考过去的状态，即值为1或2。最后重新遍历矩阵，将2，3变为对应的最新状态值0 ， 1

class Solution {
    public void gameOfLife(int[][] board) {
        //定义如果细胞从活着变为死了，则复合状态为2；
        //如果细胞从死了变成活了，则符合状态为3；
        int row = board.length;
        int col = board[0].length;
        int[] neighbors = {-1,0,1};

        for(int i = 0; i < row ; ++i ){
            for(int j = 0; j < col ; ++j){
                int liveCount = 0;

                for(int e = 0;  e < 3 ; ++e){
                    for(int f = 0; f < 3; ++f){
                        if(!(neighbors[e] == 0 && neighbors[f] == 0)){
                            int r = neighbors[e] + i;
                            int c = neighbors[f] + j;

                            if((r >= 0 && r < row) && (c >= 0 && c < col) && ( board[r][c] == 1 || board[r][c]  == 2)){++liveCount;}
                        }
                    }
                }
                if(board[i][j] == 1 && ( liveCount < 2 || liveCount > 3 )){
                    board[i][j] = 2;
                }else if(board[i][j] == 0 && liveCount == 3){
                    board[i][j] = 3;
                }

            }
        }

        for(int i = 0; i < row ; ++i ){
            for(int j = 0; j < col ; ++j){
                if(board[i][j] == 2) board[i][j] = 0;
                if(board[i][j] == 3) board[i][j] = 1;
            }
        }

    }
}

栈

102. 移掉 K 位数字

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
在这里插入图片描述

解法一

        单调栈+贪心算法：为了得到尽可能小的数字，其和位数以及高位上的数字大小是相关的。如果前面高位数（高到低）都是升序的，那么这个数是这些每位上的数所能排列出的最小整数，例如123 是 1，2，3能组成的最小数。因此，借鉴这一点，可以利用贪心思想，遍历字符串，每次尽可能得到最小的数，直至到末尾。
        维持一个当前最小的数需要使用一个单调栈，保证数字是升序排列。如果遇到比栈顶元素还要小的数，那么栈顶元素就应该弹出移除（且k-1），直至k为0（删除完成）或者当前元素比栈顶元素大（则需要将当前元素压栈，此时栈中又是一个升序栈）。例如124532，k = 3 ,当遍历到3时，4,5需要出栈，之后为1232，此时3需要出栈，最终结果为122
        有种可能情况：遍历完字符串后，单调栈已经是升序，但是k还不为0，依然需要删除数字，那么此时直接从最低位开始删即可，因为删除一位数字的总位数将会固定，而最低位数字最大，且能保证前面的数字依旧是排列最小的数，例如12345，删除5后，结果为1234。

class Solution {
    public String removeKdigits(String num, int k) {
        Deque<Character> list = new LinkedList<>();
        int len = num.length();
        for(int i = 0; i < len; ++i){
            char c = num.charAt(i);
            // int numi = Character.getNumericValue(c);
            while( !list.isEmpty() && k > 0 && list.peek() > c ){
                list.pop();
                k--;
            }
            list.push(c);
        }

        while(k > 0){
            list.pop();
            k--;
        }

        StringBuilder res = new StringBuilder();
        boolean flag = true;//用于判断数字最前端是否是连续0
        while(!list.isEmpty()){
            char digit = list.pollLast();
            if(flag && digit == '0'){
                continue;
            }
            flag = false;
            res.append(digit);
        }

        return res.length() == 0 ? "0" : res.toString();
    }
}

103. 去除重复字母

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的
字典序
最小（要求不能打乱其他字符的相对位置）。
在这里插入图片描述

解法一

单调栈+贪心算法：根据题目可知，要求每个字母只能出现一次，且这些字母组成的字典序最小。当字符呈升序排列（a b c d e f…）时，字典序是最小的时候，因此可以尝试采用单调栈来维持最小字典序的子串。此外，尝试将其与贪心思想结合，遍历字符串，每次均保证当前单调栈维持的就是目前字典序最小的子串，进而推导出最终字典序最小的子串。

遍历元素过程中，如果栈为空或者当前元素相较于栈顶元素是升序，则可以直接将当前元素压栈；
如果当前元素已经在栈中出现过，则可以直接丢弃当前元素。因为单调栈维持的是最小字典序的子串了，如果强行将该元素放入栈中，只可能会造成字典序增大或者无变化。例如栈中acd 当前c ，最多也只能让c 和 d 出栈，然后将当前c压栈，最后栈中为ac，得到的结果其实与原栈中acd前半部分几乎一样，但是少了d的信息。让当前c是否压栈对整体的最小字典序没有益处，并不能减小字典序，反而如果d是最后一个d了，那么d必须存在，则c无法压栈。因此当元素已经出现在栈中时，没有必要将其压栈处理。
如果出现了与单调栈栈顶元素大小顺序不符元素，即需要看情况丢弃当前元素还是丢弃栈中的元素。如果该栈顶元素在字符串后面已经不存在同样的元素了，则说明该元素不能在被丢弃了，后续直接入栈当前元元素；如果该栈顶元素在字符串后面还存在，则说明可以丢弃当前栈顶元素，由于栈中可能有连续几个比当前元素大的元素，所以可能会连续多出栈几个元素。例如 acbc ,栈中元素为ac，当前元素b，则c后面还有，因此可以弹出c ，压栈b，压栈最后一个c，即可得到比acb更小的字典序子串abc

class Solution {
    public String removeDuplicateLetters(String s) {
        Deque<Character> stack = new LinkedList<>();
        int len = s.length();
        boolean[] numVisit = new boolean[26];
        int[] count = new int[26];
        //初始化字符串中各字符的频次
        for(int i = 0; i < len ; ++i){
            count[s.charAt(i) - 'a']++;
        }

        for(int i = 0; i <len ;++i){
            char c = s.charAt(i);
            count[c - 'a']--;
            //说明元素已经存在于单调栈中，因此可以直接丢弃
            if(numVisit[c - 'a'] == true){
                continue;
            }

            //如果出现了与单调栈栈顶元素大小顺序不符元素，即需要看情况丢弃当前元素还是丢弃栈中的元素
            if(!stack.isEmpty() && stack.peek() >= c ){
                //如果元素小于栈顶元素，则说明有可能用当前元素替换栈顶元素以得到更小的字典序
                while(!stack.isEmpty() && stack.peek() > c){
                    //如果该栈顶元素在字符串后面已经不存在同样的元素了，则说明该元素不能在被丢弃了，后续直接入栈当前元素
                    if(count[stack.peek() - 'a'] == 0){
                        break;
                    }
                    //如果该栈顶元素在字符串后面还存在，则说明可以丢弃当前栈顶元素
                    numVisit[stack.poll() - 'a'] = false;
                }
                //让比之前栈顶元素更小的当前元素入栈
                stack.push(c);
                numVisit[c - 'a'] = true;
            }
            else{
                //当前元素符合单调栈中的单调性，因此直接压栈即可
                numVisit[c - 'a'] = true;
                stack.push(c);
            }
        }
        StringBuilder res = new StringBuilder();
        while(!stack.isEmpty()){
            res.append(stack.pollLast());
        }
        return res.toString();
    }
}