米哈游客户端

米哈游客户端凉经

2020-10-24

https://www.nowcoder.com/discuss/548291?type=2&order=0&pos=22&page=1&ncTraceId=&channel=-1&source_id=discuss_tag_nctrack

STL和虚函数

红黑树

项目

算法题：

剑指offer 10.青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

class Solution 
{
    public:
        int numWays(int n) 
        {
            int a = 0, b = 1, sum = 0;
            for(int i = 0; i <= n; ++i)
            {
                a = b;
                b = sum;
                sum = (a + b) % 1000000007;
            }
            return sum;
        }
};

225.两个队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

class MyStack {
public:
    queue<int> queue1;
    queue<int> queue2;

    /** Initialize your data structure here. */
    MyStack() {

    }

    /** Push element x onto stack. */
    void push(int x) {
        queue2.push(x);
        while(!queue1.empty())
        {
            queue2.push(queue1.front());
            queue1.pop();
        }
        swap(queue1, queue2);
    }

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int res = queue1.front();
        queue1.pop();
        return res;
    }

    /** Get the top element. */
    int top() {
        int res = queue1.front();
        return res;
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return queue1.empty();
    }
};

448.找到数组中消失的数字

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

class Solution 
{
    public:
        vector<int> findDisappearedNumbers(vector<int>& nums) 
        {
            int n = nums.size();
            for(auto& num : nums)
            {
                int x = (num - 1) % n;
                nums[x] += n;
            }

            vector<int> res;
            for(int i = 0; i < n; ++i)
            {
                if(nums[i] <= n)
                {
                    res.push_back(i+1);
                }
            }

            return res;
        }
};

米哈游一面+二面+三面凉经

数据结构

1.数组和链表的区别？

数组连续，链表不连续；数组访问容易，链表访问困难，数组非尾端插入困难，链表插入删除简单。

2.栈和队列的区别？

3.map

4.红黑树怎么保持平衡？怎么实现节点插入？

算法

快排？快排的边界？

快排的时间复杂度？什么时候排的块？

cpp

指针和引用的区别？

内联函数？内联函数和宏定义有什么区别？

A *a = new A的内存分配是怎么样的？

i++和++i

多态

重载和重写

虚函数怎么实现