Category: 未分类

忙于处理各种工作内外事情，没有什么可以写的，所以强行写一篇更新。

https://leetcode.com/problems/top-k-frequent-elements/description/
hash map + heap
Time complicity: O(N + logk)

struct KvPair
{
    int key = 0;
    int val = 0;
};
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> counts;
        for (int num : nums)
        {
            counts[num]++;
        }
        auto comp = [](const KvPair& lhs, const KvPair& rhs){
            return lhs.val > rhs.val;
        };
        priority_queue<KvPair, vector<KvPair>, decltype(comp)> pri_q(comp);
        for (auto& it : counts)
        {
            pri_q.push({it.first, it.second});
            if (pri_q.size() > k)
                pri_q.pop();
        }
        vector<int> results;
        while (!pri_q.empty())
        {
            results.push_back(pri_q.top().key);
            pri_q.pop();
        }
        return results;
    }
};

https://leetcode.com/problems/balanced-binary-tree/description/

/**
 * 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 maxDepth(TreeNode* root, int currDepth) {
        int left_depth = (root->left == nullptr) ? currDepth : maxDepth(root->left, currDepth + 1);
        int right_depth = (root->right == nullptr) ? currDepth : maxDepth(root->right, currDepth + 1);
        if (left_depth == -1 || right_depth == -1)
            return -1;
        if (left_depth - right_depth > 1 ||
            right_depth - left_depth > 1)
            return -1;
        return max(left_depth, right_depth);
    }
    bool isBalanced(TreeNode* root) {
        if (root == nullptr)
            return true;
        if (maxDepth(root, 0) == -1)
            return false;
        return true;
    }
};

Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.

思路

边界条件：比如被除数、除数是0，另外结果的正负号要注意。
除法可以用减法实现，不过如果干减的话会很费时间，所以要想想怎么加速。
容易知道，一个数左移一位相当于乘以2。我们可以一次次把除数乘以2试探一下，到底最多能减掉 2^n*除数 多少次，这就相当于做了2^n次除法。由于试探的时候一次次做了乘方，所以试探的次数是log级别的，比原来一个个减要快多了。

代码

class Solution {
public:
	int divide(int dividend, int divisor) {
		if (dividend == 0)
			return 0;
		if (divisor == 0)
			return INT_MAX;
		bool posResult = true;
		if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor >0))
			posResult = false;
		long long lDividend = dividend;
		if (lDividend < 0)
			lDividend = ~(lDividend-1);
		long long lDivisor = divisor;
		if (lDivisor < 0)
			lDivisor = ~(lDivisor-1);
		long long currDivisor = lDivisor;
		long long accRate = 1;
		long long result = 0;
		while (lDividend >= lDivisor) {
			while ((currDivisor << 1) < lDividend) {
				currDivisor <<= 1;
				accRate <<= 1;
			}
			while (currDivisor > lDividend) {
				currDivisor >>= 1;
				accRate >>= 1;
			}
			lDividend -= currDivisor;
			result += accRate;
		}
		if (posResult) {
			if (result > INT_MAX) {
				return INT_MAX;
			}
			else {
				return (int)result;
			}
		}
		else {
			result = -result;
			if (result < INT_MIN)
				return INT_MIN;
			else
				return (int)result;
		}
	}
};