Cinte's Leetcode Record

class Solution {
public:
    vector<double> dicesProbability(int n) {
        vector<double> pre(6, 1 / 6.0); // 初始化一个骰子的情况
        for(int i = 2; i <= n; ++i) // 从第二个骰子开始
        {
            vector<double> tmp(5 * i + 1, 0); // i个骰子可能的情况共有5n+1种
            for(int j = 0; j < pre.size(); ++j) // 对i-1个骰子情况中可能的取值进行遍历，表示递推式中的x
                for(int k = 0; k < 6; ++k) // 对i-1个骰子可能的取值加上1到6，就是i个骰子情况，由于前面取值加上1到6可能会有重复情况，而把这些重复情况概率加起来就是最终概率。
                    tmp[k + j] += pre[j] * 1 / 6.0;
            pre = tmp;
        }
        return pre;
    }
};

class MaxQueue {
public:
    MaxQueue() {

    }
    
    int max_value() {
        if(nodes.empty())
            return -1;
        return helper.front();
    }
    
    void push_back(int value) {
        while(!helper.empty() && value > helper.back())
            helper.pop_back();
        helper.push_back(value);
        nodes.push_back(value);
    }
    
    int pop_front() {
        if(nodes.empty())
            return -1;
        if(helper.front() == nodes.front())
            helper.pop_front();
        auto ret = nodes.front();
        nodes.pop_front();
        return ret;
    }
private:
    deque<int> nodes; // 其实这个直接用queue也行
    deque<int> helper;
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */

class Solution {
public:
    int add(int a, int b) {
        int c;
        while(b)
        {
            c = (unsigned int)(a & b) << 1; // leetcode的编译环境问题导致这里负数左移会报错，g++中则测试正常c = (a & b) << 1
            a ^= b;
            b = c;
        }
        return a;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int kthLargest(TreeNode* root, int k) {
        stack<TreeNode*> q;
        while(!q.empty() || root)
        {
            while(root)
            {
                q.push(root);
                root = root->right;
            }
            root = q.top();
            q.pop();
            if(--k == 0)
                return root->val;
            root = root->left;
        }
        return 0;
    }
};

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> set;
        int begin = 0, end = 0;
        int ret = 0;
        while(end < s.size())
        {
            if(set.find(s[end]) == set.end())
                set.insert(s[end]);
            else
            {
                while(s[begin] != s[end])
                    set.erase(s[begin++]);
                ++begin;
            }          
            ret = max(ret, end - begin + 1);
            ++end;
        }
        return ret;
    }
};

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> map;
        int ret = 0;
        int now = 0;
        for(int i = 0; i < s.size(); ++i)
        {
            if(map.find(s[i]) != map.end() && map[s[i]] >= i - now)
                now = i - map[s[i]];
            else
                now = now + 1;
            map[s[i]] = i;
            ret = max(now, ret);
        }
        return ret;
    }
};

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; ++i)
            if(nums[i] != i)
                return i;
        return n;
    }
};

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int lo = 0, hi = n; // 这里hi不能是n-1，当所有数字全在范围内时，hi不会改变，这样一来lo会像hi靠近，这样返回的hi还是n，符合结果
        while(lo < hi)
        {
            int mid = lo + ((hi - lo) >> 1);
            if(nums[mid] != mid)
                hi = mid;
            else
                lo = mid + 1;
        }
        return hi;
    }
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ret(nums.size());
        ret.front() = 1;
        for(int i = 1; i < nums.size(); ++i)
            ret[i] = ret[i - 1] * nums[i - 1];
        int right = 1;
        for(int i = nums.size() - 2; i >= 0; --i)
        {
            ret[i] *= right * nums[i + 1];
            right *= nums[i + 1];
        }
        return ret;
    }
};