2020/03/07 [面试题59 - II. 队列的最大值]

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的时间复杂度都是O(1)。若队列为空，pop_front 和 max_value 需要返回 -1

有类似的题目是，如何在O(1)时间内获取栈的最小值。类似的思想，采用两个队列，一个存储原始数据，一个存储可能成为下一个最大值的数据，辅助队列为单调递减队列(即保持从front->rear的数据递减)。为什么要保持递减？

• 当新来的数据比前面的数据大，毫无疑问，那些比它小的数据都没有用处了。因为在它们出队列之前，最大值永远都是刚来的这个数。
• 当新来的数据比前面数据小，那么前面的数据都出队列之后，它是有可能成为最大值的。

例子：[3, 4, 4, 3, 5]，主队列A，辅助队列B

• A: [3], B: [3]
• A: [3, 4], B: [4] /* B保持从front->rear递减，故3被去掉，4入队列 */
• A: [3, 4, 4], B: [4, 4] /* 为判断B何时出队列，B非严格单调递减队列 */
• A: [3, 4, 4, 3], B: [4, 4, 3] /* 直接入队列，因为能保持递减 */
• A: [3, 4, 4, 3], B: [5]

获取队列最大值就直接从辅助队列的front取值。出队列的时候，如果出队列的值与辅助队列的front位置值相等，辅助队列也要出队列。

具体实现: (push的时候不是O(1)复杂度)

struct max_queue {
    int value[QUEUE_LEN];
    int front;
    int rear;
    int max_value[QUEUE_LEN];
    int max_front;
    int max_rear;
};
int get_queue_max_value(struct max_queue *obj)
{
    return (queue_empty(obj) ? -1 : obj->max_value[obj->max_front]);
}
void enqueue(struct max_queue *obj, int value)
{
    /* while max_value not empty, keep queue decrease */
    while (obj->max_front != obj->max_rear) {
        obj->max_rear = (obj->max_rear + QUEUE_LEN - 1) % QUEUE_LEN;
        if (value <= obj->max_value[obj->max_rear]) {
            obj->max_rear = (obj->max_rear + 1) % QUEUE_LEN;
            break;
        }
    }
    obj->max_value[obj->max_rear] = value;
    obj->max_rear = (obj->max_rear + 1) % QUEUE_LEN;

    obj->value[obj->rear] = value;
    obj->rear = (obj->rear + 1) % QUEUE_LEN;
}
int dequeue(struct max_queue *obj)
{
    int value;

    if (queue_empty(obj)) {
        return -1;
    }
    value = obj->value[obj->front];
    obj->front = (obj->front + 1) % QUEUE_LEN;

    if (value == obj->max_value[obj->max_front]) {
        obj->max_front = (obj->max_front + 1) % QUEUE_LEN;
    }
    return value;
}

2020/03/08 [322. 零钱兑换]

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

常规的深度优先搜索：

• 明确递减的方向，即amount的值
• 由于性能问题，需要用cache保存已经计算了的子问题，该子问题就是amount值对应的最少硬币数，即cache[amount].

#define MIN(a, b) ((a) < (b) ? (a) : (b))
int coin(int* coins, int coinsSize, int amount, int *cache){
    int i;
    int cost = 0, min_cost = INT_MAX;

    if (amount == 0) {
        return 0;
    }

    for (i = 0; i < coinsSize; i++) {
        if (amount - coins[i] < 0) {
            continue;
        }
        if (cache[amount - coins[i]] >= 0) {
            cost = cache[amount - coins[i]];
        } else {
            cost = coin(coins, coinsSize, amount - coins[i], cache);
        }
        if (cost < INT_MAX) {
            min_cost = MIN(cost + 1, min_cost);
        }
    }
    cache[amount] = min_cost;
    return (min_cost < INT_MAX ? min_cost : -1);
}

int compare(const void *p1, const void *p2)
{
    return (*(int *)p2 - *(int *)p1);
}
int coinChange(int* coins, int coinsSize, int amount){
    int num;
    int *cost = calloc(1, sizeof(int) * (amount + 1));

    memset(cost, -1, sizeof(int) * (amount + 1));
    qsort(coins, coinsSize, sizeof(int), compare);
    num = coin(coins, coinsSize, amount, cost);

    free(cost);
    return num;
}

2020/03/10 [543. 二叉树的直径]

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

int longest_path(struct TreeNode *root, int *longest)
{
    int left = 0, right = 0;

    if (!root) {
        return 0;
    }

    left = longest_path(root->left, longest);
    right = longest_path(root->right, longest);
    if (root->left) {
        left++;
    }
    if (root->right) {
        right++;
    }
    *longest = *longest < (left + right) ? (left + right) : *longest;
    return (left > right) ? left : right;
}

int diameterOfBinaryTree(struct TreeNode* root){
    int longest = 0;
    (void)longest_path(root, &longest);
    return longest;
}