leetcode 3.15-3.21

2021-03-19

1603 设计停车系统
2 两数相加
面试题04.05 合法二叉搜索树

1603. 设计停车系统

请你给一个停车场设计一个停车系统。停车场总共有三种不同大小的车位：大，中和小，每种尺寸分别有固定数目的车位。

请你实现 ParkingSystem 类：

ParkingSystem(int big, int medium, int small) 初始化 ParkingSystem 类，三个参数分别对应每种停车位的数目。
bool addCar(int carType) 检查是否有 carType 对应的停车位。 carType 有三种类型：大，中，小，分别用数字 1， 2 和 3 表示。一辆车只能停在 carType 对应尺寸的停车位中。如果没有空车位，请返回 false ，否则将该车停入车位并返回 true 。

示例 1：

输入：
[“ParkingSystem”, “addCar”, “addCar”, “addCar”, “addCar”]
[[1, 1, 0], [1], [2], [3], [1]]
输出：
[null, true, true, false, false]

解释：
ParkingSystem parkingSystem = new ParkingSystem(1, 1, 0);
parkingSystem.addCar(1); // 返回 true ，因为有 1 个空的大车位
parkingSystem.addCar(2); // 返回 true ，因为有 1 个空的中车位
parkingSystem.addCar(3); // 返回 false ，因为没有空的小车位
parkingSystem.addCar(1); // 返回 false ，因为没有空的大车位，唯一一个大车位已经被占据了

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/design-parking-system
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

过于简单

AC代码：

class ParkingSystem {
public:
    ParkingSystem(int big, int medium, int small) {
        _big = big;
        _medium = medium;
        _small = small;
    }
    
    bool addCar(int carType) {
        if (carType == 1) {
            if (_big > 0) {
                _big--;
                return true;
            } else {
                return false;
            }
        } else if (carType == 2) {
            if (_medium > 0) {
                _medium--;
                return true;
            } else {
                return false;
            }
        } else {
            if (_small > 0) {
                _small--;
                return true;
            } else {
                return false;
            }
        }
    }

private:
    int _big{0};
    int _medium{0};
    int _small{0};
};

2. 两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

1 2	输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：逐个节点相加即可，注意进位。

AC代码：

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr)
            return l2;
        if (l2 == nullptr)
            return l1;
        
        int carry = 0;
        carry = l1->val + l2->val;
        ListNode* head = new ListNode(carry % 10);
        ListNode* r = head;
        carry /= 10;
        ListNode* p1 = l1->next;
        ListNode* p2 = l2->next;
        while (p1 && p2) {
            carry += (p1->val + p2->val);
            ListNode* tmp = new ListNode(carry % 10);
            r->next = tmp;
            r = tmp;
            p1 = p1->next;
            p2 = p2->next;
            carry /= 10;
        }
        while (p1) {
            carry += p1->val;
            ListNode* tmp = new ListNode(carry % 10);
            r->next = tmp;
            r = tmp;
            p1 = p1->next;
            carry /= 10;
        }
        while (p2) {
            carry += p2->val;
            ListNode* tmp = new ListNode(carry % 10);
            r->next = tmp;
            r = tmp;
            p2 = p2->next;
            carry /= 10;
        }
        if (carry) {
            ListNode* tmp = new ListNode(carry);
            r->next = tmp;
        }
        return head;
    }
};

面试题04.05. 合法二叉搜索树

实现一个函数，检查一棵二叉树是否为二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

思路：中序遍历，遍历顺序应该是从小到大，如果遍历过程中检查到当前数字比之前遍历的数字小，则不是合法二叉搜索树。需要注意边界条件，如两个一样的节点、INT_MIN等。

AC代码：

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (!root)
            return true;
        stack<TreeNode*> st;
        TreeNode* p = root;
        vector<int> visit;
        do {
            while(p) {
                st.push(p);
                p = p->left;
            }
            p = st.top();
            st.pop();
            // visit.push_back(p->val);
            if (visit.size() > 0 && p->val <= visit[visit.size()-1])  return false;
            else visit.push_back(p->val);
            p = p->right;
        } while(!(p == NULL && st.empty()));
        return true;
    }
};