leetcodeweek21

1271. Hexspeak

class Solution {
public:
    string get_string_num(int a){
        if(a == 0)
            return "O";
        else if(a == 1)
            return "I";
        else if(a == 10)
            return "A";
        else if(a == 11)
            return "B";
        else if(a == 12)
            return "C";
        else if(a == 13)
            return "D";
        else if(a == 14)
            return "E";
        else if(a == 15)
            return "F";
        else
            return "X";
    }
    long long get_int_num(string num){
        long long ret = 0;
        for(int i=0; i<num.size(); i++){
            ret *= 10;
            ret += num[i]-'0';
        }
        return ret;
    }    
    string toHexspeak(string num) {
        string ret="";
        long long n = get_int_num(num);
        while(n){
            long long cur = n % 16;
            n /= 16;
            string cc = get_string_num(cur);
            if(cc == "X")
                return "ERROR";
            ret += cc;
        }
        string ret1 = "";
        for(int i=ret.size()-1; i>=0; i--){
            ret1 += ret[i];
        }
        return ret1;
    }
};

1272. Remove Interval

class Solution {
public:
    vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& t) {
        vector<vector<int>> ret;
        for(auto& a: intervals){
            if(a[0] >= t[0] && a[1] <= t[1])
                continue;
            else if(a[0] <= t[0] && a[1] <= t[1] && a[1] > t[0]){
                vector<int> cur;
                cur.push_back(a[0]);
                cur.push_back(t[0]);
                ret.push_back(cur);
            }
            else if(a[0] >= t[0] && a[0] < t[1] && a[1] >= t[1]){
                vector<int> cur;
                cur.push_back(t[1]);
                cur.push_back(a[1]);
                ret.push_back(cur);
            }
            else if(a[0] < t[0] && a[1] > t[1]){
                vector<int> cur1;
                cur1.push_back(a[0]);
                cur1.push_back(t[0]);
                ret.push_back(cur1);
                vector<int> cur2;
                cur2.push_back(t[1]);
                cur2.push_back(a[1]);
                ret.push_back(cur2);
            }
            else
                ret.push_back(a);
        }
        return ret;
    }
};

1273. Delete Tree Nodes

class Solution {
public:
    int deleteTreeNodes(int n, vector<int>& parent, vector<int>& value) {
        vector<int> res(n);
        for(int i=n-1; i>0; --i){
            value[parent[i]] += value[i];
            res[parent[i]] += value[i] ? res[i] + 1 : 0;
        }
        return value[0] ? res[0] + 1 : 0;
    }
};

1274. Number of Ships in a Rectangle

/**
 * // This is Sea's API interface.
 * // You should not implement it, or speculate about its implementation
 * class Sea {
 *   public:
 *     bool hasShips(vector<int> topRight, vector<int> bottomLeft);
 * };
 */

class Solution {
public:
    int countShips(Sea sea, vector<int> topRight, vector<int> bottomLeft) {
        return helper(sea, topRight[0], topRight[1], bottomLeft[0], bottomLeft[1]);
    }
    int helper(Sea& sea, int top, int right, int bottom, int left){
        int h = top-bottom;
        int w = right-left;
        
        if(!sea.hasShips({top, right},{bottom, left}))
            return 0;
        if(h == 0 && w == 0)
            return 1;
        if(h > w){
            int a = helper(sea, top, right, bottom+h/2+1, left);
            int b = helper(sea, bottom+h/2, right, bottom, left);
            return a + b;
        }
        else{
            int a = helper(sea, top, right, bottom, left+w/2+1);
            int b = helper(sea, top, left+w/2, bottom, left);
            return a + b;
        }
    }
};