笔试刷题Day—1

记录一下笔试刷题。

数组中的重复的数字

题解：使用哈希表，遍历nums数组然后存入哈希表，如果哈希表中的数大于2，返回该数字。

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {

     unordered_map<int,int> map;

        for(int num : nums){
            map[num]++;
            if(map[num] >= 2) return num;
        }
        return nums[nums.size() - 1];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

用两个栈实现队列

class MyQueue {
    stack<int>in,out;
public:
    MyQueue() {

    }
    
    void push(int x) {
        in.push(x);
    }
    
    int pop() {
        in2out();
        int x= out.top();
        out.pop();
        return x;
    }
    
    int peek() {
        in2out();
        return out.top();
    }
    
    void in2out(){
        if(out.empty()){
            while(!in.empty()){
                int x = in.top();
                in.pop();
                out.push(x);
            }
        }
    }

    bool empty() {  
            return in.empty()&&out.empty();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

方法2 值得细细品味

class CQueue{
private:
    stack<int> inStack,outStack;//创建入栈和出栈

    void in2Out(){
        while(!inStack.empty()){//当入栈的栈不为空的时候
            outStack.push(inStack.top());//出栈的栈就入 入栈的元素的栈顶元素
            inStack.pop();//入栈的栈顶元素就出栈
        }
    }

public:

    CQueue() {}

    void appendTail(int val){
        inStack.push(val);
    }

    int deleteHead(){
        if(outStack.empty()){//出栈的栈为空的话，
            if(inStack.empty()){//如果入栈的栈为空的话
                return -1;//返回-1
            }
            in2Out();//入栈的栈元素里面的栈顶元素就加入到出栈的栈中
        }
        
        int val = outStack.top();//定义出栈的栈元素为出栈的栈顶元素。
        outStack.pop();//执行出栈操作
        return val;//返回出栈元素
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

有点难的

这题只能看了答案之后再说吧。超过我的技术范围了。哈哈

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stk;
        int n = tokens.size();
        for (int i = 0; i < n; i++) {
            string& token = tokens[i];
            if (isNumber(token)) {
                stk.push(atoi(token.c_str()));
            } else {
                int num2 = stk.top();
                stk.pop();
                int num1 = stk.top();
                stk.pop();
                switch (token[0]) {
                    case '+':
                        stk.push(num1 + num2);
                        break;
                    case '-':
                        stk.push(num1 - num2);
                        break;
                    case '*':
                        stk.push(num1 * num2);
                        break;
                    case '/':
                        stk.push(num1 / num2);
                        break;
                }
            }
        }
        return stk.top();
    }

    bool isNumber(string& token) {
        return !(token == "+" || token == "-" || token == "*" || token == "/");
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

删除排序链表中的重复元素

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {

         if (!head) {
            return head;
        }
        ListNode *p = head;

        while(p->next){
            if(p->val == p->next->val){
                p->next = p->next->next;
            }
            else {
                p = p->next;
            }
        }
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20