给一堆国际象棋的queen的坐标, 和一个king的坐标, 问那些queen可以找到king.

主要是看到queen坐标的边界是63, 然后8个方向dfs找即可.

class Solution {
public:
    int dirs[8][2] = {
        {1,1},
        {1,0},
        {1,-1},
        {0,1},
        {0,-1},
        {-1,1},
        {-1,0},
        {-1,-1}
    };
    vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {
        vector<vector<int>> res;
        int maxX = 0;
        int maxY = 0;
        set<pair<int, int>> qs;
        for(auto q : queens){
            maxX = max(maxX, q[0]);
            maxY = max(maxY, q[1]);
            qs.emplace(pair<int, int>(q[0], q[1]));
        }
        for(auto d : dirs) {
            int kx = king[0];
            int ky = king[1];
            while(kx >= 0 && ky >= 0 && kx <= 63 && ky <= 63){
                kx += d[0];
                ky += d[1];
                if(qs.find(pair<int, int>(kx,ky)) != qs.end()){
                    vector<int> vv{kx,ky};
                    res.push_back(vv);
                    break;
                }
            }
        }
        return res;         
    }
};

给一个二叉树, 求任意父节点和子节点的最大差.

按个找..

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxAncestorDiff(TreeNode root) {
        
    }
}

给两个bst, 然后看是不是能做two sum.

先用inorder变成array, 然后做two sum.

/**
 * 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:
    bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
        vector<int> v; 
        inorder(root1, v); 
        return twosum(v, root2, target);
    }
    void inorder(TreeNode* root, vector<int>& v){
        if(!root)
            return;
        inorder(root->left, v);
        v.push_back(root->val);
        inorder(root->right, v);
    } 
    bool twosum(vector<int>& v, TreeNode* root, int t) {
        if(!root)
            return false;
        return binary_search(v.begin(), v.end(), t - root->val) || twosum(v, root->left, t) || twosum(v, root->right, t);;
    }
};

给一个数组和一个数字k, 求数组中k大小的subarray的不同的数字的个数.

用map当滑窗计算一下

class Solution {
public:
    vector<int> distinctNumbers(vector<int>& nums, int k) {
        vector<int> res;
        int n = nums.size();
        unordered_map<int, int> map; 
        for(int i = 0; i < n; i++){
            if(i < k){
                map[nums[i]]++;
            }else{
                res.push_back(map.size());
                map[nums[i - k]]--;
                if(map[nums[i - k]] == 0){
                    map.erase(nums[i - k]);
                }
                map[nums[i]]++;
            }
        }
        res.push_back(map.size());
        return res;
    }
};

给一个string, 里面有偶数位的字符和奇数位的数字组成, 给一个方法decode这个string, 是用字符后的数字位个字符代替数字位. 求decoded string.

class Solution {
public:
    string replaceDigits(string s) {
        int n = s.size();
        for(int i = 1; i < n; i+=2){
            char c = (char)(s[i - 1] + (s[i] - '0'));
            s[i] = c;
        }
        return s;
    }
};

设计一个座位预约系统.

用treeset,因为里面有可以直接访问第一个可用key的方法.

class SeatManager {
public:
    set<int> s;
    SeatManager(int n) {
        for(int i = 1; i <= n; i++){
            s.emplace(i);
        }
    }
    
    int reserve() {
        auto r = *s.begin();
        s.erase(*s.begin());
        return r;
    }
    
    void unreserve(int seatNumber) {
        s.emplace(seatNumber);
    }
};

/**
 * Your SeatManager object will be instantiated and called as such:
 * SeatManager* obj = new SeatManager(n);
 * int param_1 = obj->reserve();
 * obj->unreserve(seatNumber);
 */

给一个数组, 求做完下k次permutation后数组通过几个swap能变回原数组.

这题就是先做k permutation, 然后比较两个数组的不同位置, 找到同样的数字后, swap回来, 因为求的是minimum swap, 所以如果数字相同的情况下, 只要找最邻近做swap即可.

class Solution {
public:
    int getMinSwaps(string num, int k) {
        string v(num);
        while(k > 0){
            next_permutation(v.begin(), v.end());
            k--;
        }
        int res = 0;
        for(int i = 0 ; i < v.size(); i++){
            if(num[i] != v[i]){
                int j = i + 1;
                while(j < v.size()){
                    if(num[j] == v[i]){
                        break;
                    }
                    j++;
                }// find j 
                for(; j > i; j--){
                    swap(num[j], num[j - 1]);
                    res++;
                }
            }
        } 
        return res;
    }
};

给一个数组, 一个整数start和一个整数target, 求数组离start的index最近的数等于target的.

这题就是从start的index周围开始找. 注意一下边界.

class Solution {
public:
    int getMinDistance(vector<int>& nums, int target, int start) {
        int i = start;
        int j = start + 1;
        while(i >= 0){
            if(nums[i] == target)
                break;
            i--;
        }
        while(j < (int)nums.size()){
            if(nums[j] == target)
                break;
            j++;
        }
        if(i == -1)// if i out of range
            return j - start;
        if(j == (int)nums.size()) // if j out of range
            return start - i;
        if(start - i > j - start){
            return j - start;
        }else{
            return start - i;
        }
    }
};

设计一个浏览器的历史记录.

这题我用的是vector, 因为我看到题目要求的visit方法需要把某一点后边所有的历史记录全删除, 所以用cur记录当前访问的位置, 然后用resize()删除[cur+1, v.size() – 1]的范围.

class BrowserHistory {
public:
    vector<string> v;
    int cur = 0;
    BrowserHistory(string homepage) {
        v.push_back(homepage);
    }
    
    void visit(string url) {
        if(cur != v.size() - 1){
            v.resize(cur + 1); // remove [cur+1, v.size() - 1]
            v.shrink_to_fit();
        }
        v.push_back(url);
        cur++;
    }
    
    string back(int steps) {
        cur = max(cur - steps, 0);
        return v[cur];
    }
    
    string forward(int steps) {
        cur = min(cur + steps, (int)v.size() - 1);
        return v[cur];
    }
};

/**
 * Your BrowserHistory object will be instantiated and called as such:
 * BrowserHistory* obj = new BrowserHistory(homepage);
 * obj->visit(url);
 * string param_2 = obj->back(steps);
 * string param_3 = obj->forward(steps);
 */

给一个String和一个整数k, 返回k长度的没有重复字符的substring.

这题就是先找所有的没有重复字符substring, 然后看长度是不是k.

class Solution {
public:
    int numKLenSubstrNoRepeats(string S, int K) {
        int res = 0;
        unordered_map<char, int> map;
        for(int i = 0; i < S.size(); i++) {
            if(i < K){// find all substring with non-repeacted chars
                map[S[i]]++;
            }else{
                map[S[i]]++;
                map[S[i-K]]--;
                if(map[S[i-K]] == 0)
                    map.erase(S[i-K]);
            } 
            if(map.size() == K) // substring length == K
                res++;
        }
        return res;
    }
};