力扣随机解题

118. 杨辉三角

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> nums;
        for(int i=1; i<=numRows; i++) {
            nums.push_back(vector<int>(i, 0));
        }
        for(int i=0; i<numRows; i++) {
            for(int j=0; j<=i; j++) {
                if (j == 0 || j == i) {
                    nums[i][j] = 1;
                } else {
                    nums[i][j] = nums[i-1][j-1] + nums[i-1][j];
                }
            }
        }
        return nums;
    }
};

119. 杨辉三角 II

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> nums(rowIndex+1, 1);
        for(int i=0; i<rowIndex; i++) {
            for(int j=i; j>0; j--) {
                nums[j] += nums[j-1];
            }
        }
        return nums;
    }
};

94. 二叉树的中序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root == NULL) return res;
        stack<TreeNode*> s;
        TreeNode *p = root;

        while(p || !s.empty()) {
            while(p) {
                s.push(p);
                p = p -> left;
            }
            p = s.top();
            s.pop();
            res.push_back(p -> val);
            p = p -> right;
        }
        return res;
    }
};

704. 二分查找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.size() == 0)
            return -1; 
        int s = 0;
        int e = nums.size() - 1;
        while(s <= e) {
            int m = (s + e) / 2;
            if (nums[m] == target)
                return m;
            else if(nums[m] < target) {
                s = m + 1;
            } else {
                e = m - 1;
            }
        }
        return -1;
    }
};

21. 合并两个有序链表

终止条件：两条链表分别名为 l1 和 l2，当 l1 为空或 l2 为空时结束
返回值：每一层调用都返回排序好的链表头
本级递归内容：如果 l1 的 val 值更小，则将 l1.next 与排序好的链表头相接，l2 同理

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1)
            return l2;
        if (!l2)
            return l1;
        if(l1 -> val <= l2 -> val) {
            l1 -> next = mergeTwoLists(l1 -> next, l2);
            return l1;
        } else {
            l2 -> next = mergeTwoLists(l1, l2 -> next);
            return l2;
        }
    }
};