[toc]

第一题:栈的应用#

要出队或者要用到队头的时候，移动到另一个栈里，就能反向取了

class MyQueue {
    Deque<Integer> q1 = new LinkedList<>();
    Deque<Integer> q2 = new LinkedList<>();
    /** Initialize your data structure here. */
    public MyQueue() {

    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        q1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (!q2.isEmpty()) {
            return q2.pop();
        }
        while(!q1.isEmpty()) {
            q2.push(q1.pop());
        }
        return q2.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        if (!q2.isEmpty()) {
            return q2.peek();
        }
        while(!q1.isEmpty()) {
            q2.push(q1.pop());
        }
        return q2.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

第二题:bfs#

733. 图像渲染 - 力扣（LeetCode）

一个简单题，我用bfs写了半天，确实累，是不是应该搞点bfs的模板了？下次比赛直接用上。

class Solution {
    int[][] dirs = new int[][]{{1,0},{-1,0}, {0,1}, {0,-1}};
    
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        Queue<int[]> queue = new LinkedList<>();
        int ylen = image.length;
        int xlen = image[0].length;
        boolean[][] vis = new boolean[ylen][xlen];
        queue.offer(new int[]{sr,sc});
        vis[sr][sc] = true;
        int startColor = image[sr][sc];
        image[sr][sc] = color;
        while (!queue.isEmpty()) {
            int[] p = queue.poll();
            int y = p[0];
            int x = p[1];
            for (int[] dir : dirs) {
                int ny = dir[0] + y;
                int nx = dir[1] + x;
                if (nx < 0 || ny < 0 || nx >= xlen || ny >= ylen || vis[ny][nx]) {
                    continue;
                }
                if (startColor != image[ny][nx]) {
                    continue;
                }
                vis[ny][nx]= true;
                image[ny][nx] = color;
                queue.offer(new int[]{ny, nx});
            }
        }
        return image;
    }
}

第三题:哈希表以及数据范围确认习惯#

面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）

看起来很简单，直接一个数组搞定

class Solution {
    public boolean isUnique(String astr) {
        boolean[] vis = new boolean[26];
        for (char c: astr.toCharArray()) {
            if (vis[c-'a']) {
                return false;
            }
            vis[c-'a'] = true;
        }
        return true;
    }
}

但这题究竟想考察什么呢？看一下下面这段话：

如果我是面试官，会考虑主要考察什么，就我的工作经验看，大多数主要是招聘工程师的，面试者如果什么问题都没有，直接写个二重循环搞定，会首先给个50分，如果能写点判断字符串是否为null的，60分。

直接上手什么bitset，什么位运算的，我会先问他，题目中有没有交代字符串的字符一定是26个英文字母？如果是unicode环境，你是不是要准备2^16/8个字节的空间？在实际项目中，风险可控，结果可期更重要，绝大多数时候不在乎那点时间和资源。

所以我期望面试者不要急于解答，我希望他先问我问题：

字符串的字符范围，如果我告诉他，26个小写英文字母，那可能一开头直接判断如果字符长度>26, 直接返回False，做到这一点的，80分

如果我告诉他ascii字符集，然后他的代码里有边界检查，并且针对不同的范围有不同的侧重点，比如说ascii字符集，那也就是128个可能性，16个字节的位运算比较好

如果我告诉他是unicode，没有字符范围，老老实实排序再判断是比较符合我对工程师的要求的，因为算法性能稳定，没有额外资源要求，一眼看出没什么不可预见的风险，100分。

就是说，有些东西，没想到或者一时没想到根本不是问题，日常工作中稍微提示一下即可，但是缜密的思维对于程序员来说更重要。

破晓的知识屋

2022-0822

第一题:栈的应用#

第二题:bfs#

第三题:哈希表以及数据范围确认习惯#