给一个robot的api, 问如何清洁一个room.

这题是设计题, 主要还是考虑怎么设计robot的走位, 肯定是dfs没错, 因为room的大小不知道, 所以要按照一定顺序走, 因为robot开始的时候是向上的, 所以按照上右下左开始顺时针走, 并且记录路径. 然后在走不通的时候, 应该统一向一个方向转, 这里选择向右.

/**
 * // This is the robot's control interface.
 * // You should not implement it, or speculate about its implementation
 * class Robot {
 *   public:
 *     // Returns true if the cell in front is open and robot moves into the cell.
 *     // Returns false if the cell in front is blocked and robot stays in the current cell.
 *     bool move();
 *
 *     // Robot will stay in the same cell after calling turnLeft/turnRight.
 *     // Each turn will be 90 degrees.
 *     void turnLeft();
 *     void turnRight();
 *
 *     // Clean the current cell.
 *     void clean();
 * };
 */

class Solution {
public:
    int dirs[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};// up(default), right, down, left
    unordered_map<int,   unordered_map<int, bool>> v;
    void cleanRoom(Robot& robot) {
        dfs(0,0,0,robot);
    } 
    void dfs(int x, int y, int cur, Robot& robot){
        if(v[x][y]) // if visited
            return;
        robot.clean();
        v[x][y] = 1;
        for(int i = 0; i < 4; i++){
            if(robot.move()){
                int dd = (i + cur) % 4;
                dfs(x + dirs[dd][0], y + dirs[dd][1], dd, robot);
                robot.turnLeft();
                robot.turnLeft(); // 180 degree
                robot.move();
                robot.turnRight();
                robot.turnRight();
            }
            robot.turnRight();
        }
    }
};

给一个string数组和一个pattern string, 求满足这个pattern的string.

因为是pattern, 所以用两个map互相把里面的char建立mapping即可.

class Solution {
public:
    vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
        vector<string> res;
        for(auto w : words){
            if(w.size() != pattern.size()) // must be same length
                continue;
            unordered_map<char, char> map;
            unordered_map<char, char> rmap;
            bool add = true;
            for(int i = 0; i < w.size(); i++){
                if(map.find(pattern[i]) != map.end() || rmap.find(w[i]) != map.end()){
                    if(map[pattern[i]] != w[i] || rmap[w[i]] != pattern[i]){
                        add = false;
                        break;
                    }
                }else{
                    map[pattern[i]] = w[i];
                    rmap[w[i]] = pattern[i];
                }
            }
            if(add)
                res.push_back(w);
        }
        return res;
    }
};

给一个二叉树, 里面的label是zigzag的, 给一个val, 求val到root路径.

这题看似求路径, 实测是二进制的题,因为是zigzag的. 所以从val本身出发看, 比如val是例题的14, 那么14的二进制是1110, 14上一个node是4, 4的二进制是100, 可以看出规律是 1110 先右移 变成111, 然后翻转除了第一个digit外的所有digit. 可以随便拿别的node验证一下这个算法.

class Solution {
public:
    vector<int> pathInZigZagTree(int label) {
        vector<int> res;
        while(label > 0){
            res.push_back(label);
            int m = (int)log2(label); // m是label的二进制位数-1
            for(int i = 0; i < m; i++) {
                label = (label ^ (1 << i)); //flip
            }
            label = label >> 1;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

给一个2d数组, 里面是0和1, 问怎么反转row和column, 值得所有row的和的值最大.

这题是贪婪算法, 首先找第一列中有0的, 翻转, 然后找第二列后边, 每列1比0少的, 翻转即可.

class Solution {
public:
    int matrixScore(vector<vector<int>>& A) {
        int n = A.size();
        int m = A[0].size();
        int res = 0;
        for(int i = 0; i < n; i++) {
            if(!A[i][0]){ // if the first column is zero
                for(int j = 0; j < m; j++){
                    A[i][j] = !A[i][j]; // flip rest numbers
                }
            }
        }
        for(int j = 1; j < m; j++) { // from second column
            int one = 0;
            int zero = 0;
            for(int i = 0; i < n; i++){
                if(A[i][j])
                    one++;
                else
                    zero++;
            }
            if(one < zero){ // if one less than zero
                for(int i = 0; i < n; i++){
                    A[i][j] = !A[i][j]; // flip
                }
            }
         }
        for(int i = 0; i < n; i++) { // calculate the result.
            int num = 0;
             for(int j = 0; j < m; j++){
                 num = (num << 1) | A[i][j] ;
             }
            res += num;
         }
        return res;
    }
};

给一个bst, 插入val.

模板题

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(!root){
            return new TreeNode(val);;
        }
        if(root->val < val){
            root->right = insertIntoBST(root->right, val);
        }else{
            root->left =insertIntoBST(root->left, val);
        }
        return root;
    }
};

给一个数组, 里面是各种unique的数字, 代表卡牌, 给一系列规则,一直翻上边的数字, 然后把后边的数字放到最后, 求如何改变使得原数组生成递增的序列.

这题就是从后往前想, 模拟一下过程即可.

class Solution {
public:
    vector<int> deckRevealedIncreasing(vector<int>& deck) {
        sort(deck.begin(), deck.end());
        deque<int> tmp;
        for(int i = deck.size() - 1; i >= 0; i--) {
            if(tmp.size() == 0){
                tmp.push_back(deck[i]);
            }else{
                int t = tmp.back();
                tmp.pop_back();
                tmp.push_front(t);
                tmp.push_front(deck[i]);
            }
        }
        vector<int> res;
        for(auto tt : tmp){
            res.push_back(tt);
        }
        return res;
    }
};

给一个DAG, 求最小的set, 里面的点组成的路径可以到达所有点. 这题必有答案, 而且答案唯一

因为最后一句话, 所以直接找入度为0的点即可.

class Solution {
public:
    vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
        vector<int> res;
        unordered_set<int> set;
        for(auto v : edges) {
            set.emplace(v[1]);
        }
        for(int i = 0; i < n; i++){
            if(set.find(i) == set.end())
                res.push_back(i);
        }
        return res;
    }
};

给一个数字n, 表示n个team, 每次规定一个比赛是最强的打最弱的, 依次比赛, 求比赛队伍的输出.

模拟运行一下就行.

class Solution {
public:
    string findContestMatch(int n) {
        deque<string> dq;
        for(int i = 1; i <= n; i++){
            dq.push_back(to_string(i));
        }
        while(dq.size() != 1) {
            int size = dq.size();
            deque<string> tmp;
            for(int i = 0; i < size / 2; i++) {
                string a = dq.front();
                string b = dq.back();
                dq.pop_front();
                dq.pop_back();
                tmp.push_back("(" + a + "," + b + ")");
            }
            dq = tmp;
        }
        return dq.front();
    }
};

给一个string, 问里面的字符能组成多少种string.

简单的组合问题.直接dfs

class Solution {
public:
    int res = 0;
    int numTilePossibilities(string tiles) {
        vector<int> count(26, 0);
        for(auto c : tiles){
            count[c - 'A']++;
        }
        dfs(count);
        return res;
    }
    void dfs(vector<int>& count){
        for(int i = 0; i < count.size(); i++) {
            if(count[i] != 0){
                count[i]--;
                res++;
                dfs(count);
                count[i]++;
            }
        }
    }
     
};

给一个2d数组, 里面每个row都是严格递增排序的, 求最小的row公共元素.

排序所以用二叉搜索, 正好std::binary_search返回的是true/false.

class Solution {
public:
    int smallestCommonElement(vector<vector<int>>& mat) {
        int n = mat.size();
        int res = 0;
        for(int i = 0; i < mat[0].size(); i++){
            bool found = true;
            for(int j = 1; j < n; j++){
                if(!binary_search(mat[j].begin(), mat[j].end(), mat[0][i])){
                    found = false;
                    break;
                }
            }
            if(found)
                return mat[0][i];
        }
        return -1;
    }
};