实验室暑假学习第五周算法总结

女爷i 2022-11-26 07:47 265阅读 0赞

## LeetCode 268. 缺失数字 ##

**难度** 简单

给定一个包含`0, 1, 2, ..., n`中`n`个数的序列，找出`0 .. n`中没有出现在序列中的那个数。

**示例1**

输入: [3,0,1]
    输出: 2

**示例2**

输入: [9,6,4,2,3,5,7,0,1]
    输出: 8

--------------------

**解法1** HashMap  
语言：C

int missingNumber(int* nums, int numsSize) { 
        int ret = 0;
        bool flag[numsSize + 1];
        memset(flag, 0, sizeof(bool) * (numsSize + 1));
        for (int i = 0; i < numsSize; i++)
            flag[nums[i]] = 1;
        for (int i = 0; i < numsSize + 1; i++)
            if (!flag[i]) { 
                ret = i;
                break;
            }
        return ret;
    }

**解法2** 位运算  
语言：C

int missingNumber(int* nums, int numsSize) { 
        int ret = numsSize;
        for (int i = 0; i < numsSize; i++)
            ret ^= i ^ nums[i];
        return ret;
    }

## LeetCode 946. 验证栈序列 ##

**难度** 中等

给定`pushed`和`popped`两个序列，每个序列中的**值都不重复**，只有当它们可能是在最初空栈上进行的推入push和弹出pop操作序列的结果时，返回`true`；否则，返回`false`。

**示例1**

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
    输出：true
    解释：我们可以按以下顺序执行：
    push(1), push(2), push(3), push(4), pop() -> 4,
    push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

**示例2**

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
    输出：false
    解释：1 不能在 2 之前弹出。

**提示**

1.  `0 <= pushed.length == popped.length <= 1000`
2.  `0 <= pushed[i], popped[i] < 1000`
3.  `pushed`是`popped`的排列。

--------------------

**解法** 数组模拟栈  
语言：C

bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize) { 
        int* stack = (int*)malloc(sizeof(int) * pushedSize);
        int stackSize = 0;
        for (int i = 0, j = 0; i < pushedSize; i++) { 
            stack[stackSize] = pushed[i];
            stackSize++;
            while (stackSize && stack[stackSize - 1] == popped[j]) { 
                j++;
                stackSize--;
            }
        }
        return stackSize == 0;
    }