每日算法--2023.2.26

1.面试题59-II 队列的最大值

class MaxQueue {
    //该题的重点在于以o（1）的时间复杂度找到队列中最大的元素，如果只单纯维护当前队列一个最大的值，当该值出队后第二大的值找不到，所以应该维护一个递减队列
    //这里我们通过双端队列去维护这个递减队列，其逻辑如下：
    //如果我们要加入一个元素，在这个元素之前并且比这个元素小的值移除，并将该值放在双端队列最后
    //我们出队一个元素的时候，判断当前值是否与双端队列最大值相同，若相同则移除该值
    Deque<Integer> deque;
    Queue<Integer> queue;
    public MaxQueue() {
        deque = new LinkedList<>();
        queue = new LinkedList<>();
    }

    public int max_value() {
        if(deque.isEmpty()){
            return -1;
        }
        return deque.getFirst();
    }
    
    public void push_back(int value) {
        queue.offer(value);
        while(!deque.isEmpty()&&value>deque.getLast()){
            deque.removeLast();
        }
        deque.addLast(value);
    }
    
    public int pop_front() {
        if(queue.isEmpty()){
            return -1;
        }
        int res = queue.poll();
        if(res == deque.getFirst()){
            deque.removeFirst();
        }
        return res;
    }
}

2.面试题67--把字符串换成整数

class Solution {
    public int strToInt(String str) {
        int n = str.length();
        if(n == 0){
            return 0;
        }
        int i = 0;
        long res = 0;
        boolean flag = false;
        while(i<n&&str.charAt(i) == ' '){
            i++;
        }
        if(i == n){
            return 0;
        }
        if(str.charAt(i) == '-'){
            flag = true;
            i++;
        }else if(str.charAt(i) == '+'){
            i++;
        }  
        for(;i<n;i++){
            int cur = str.charAt(i) - '0';
            if(cur<0||cur>9){
                break;
            }
            else {
                res = res * 10 + cur;
            }
            if(res>Integer.MAX_VALUE){
                if(flag == false){
                    return Integer.MAX_VALUE;
                }else{
                    return Integer.MIN_VALUE;
                }
            }
        }
        if(flag == true){
            res = -res;
        }
        return (int)res;
    }
}

3.剑指offer12--矩阵中的最短路径

class Solution {
    public boolean[][] flag;
    public int[] dx = new int[]{1,0,-1,0};
    public int[] dy = new int[]{0,1,0,-1};
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        flag = new boolean[m][n];
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                if(word.charAt(0) == board[i][j]){
                    flag[i][j] = true; 
                    if(dfs(i,j,1,board,word)){
                        return true;
                    }
                    flag[i][j] = false;
              }
            }
        }
    return false;    
    }
    public boolean dfs(int i, int j, int k, char[][] board, String word){
        //System.out.println(k);
        if(k == word.length()){
            return true;
        }

        for(int p = 0;p<4;p++){
            int xx = i + dx[p], yy = j + dy[p];
            if(xx>=0&&xx<board.length&&yy>=0&&yy<board[0].length&&board[xx][yy] == word.charAt(k)&&flag[xx][yy] == false){
                flag[xx][yy] = true;
                boolean flag1 = dfs(xx,yy,k+1,board,word);
                flag[xx][yy] = false;
                if(flag1 == true){
                    return true;
                }
            }
        }
        return false;
    }
}