考研复试C++ | leedcode经典题

目录

• x的平方根
• • 题目
  • 代码
• 爬楼梯
• • 题目：
  • 代码：
• 删除单链表的重复元素
• • 题目：
  • 代码：
• 合并两个有序数组
• • 题目：
  • 代码：
• 二叉树的中序遍历
• • 题目
  • 代码

x的平方根

欣赏不来答案的做法，直接调用sqrt就可以过

题目

代码

class Solution {
public:
    int mySqrt(int x) {
        int ans = sqrt(x);
        return ans;
    }
};
           

爬楼梯

题目：

代码：

递归会溢出

#include<cmath>
#include<iostream>

using namespace std;

//substr 左右都是闭区间 

int main(){
	int n;
	scanf("%d",&n);
	
	// r表示爬几级台阶 p q初始为0 
	int p=0,q=0,r=1;
	for(int i=1;i<=n;i++){
		p = q;
		q = r;
		r = p+q; 
	}
	return r;
} 
           

删除单链表的重复元素

题目：

代码：

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) {
            return head;
        }

        ListNode* cur = head;
        while (cur->next) {
            if (cur->val == cur->next->val) {
                cur->next = cur->next->next;
            }
            else {
                cur = cur->next;
            }
        }

        return head;
    }
};

           

合并两个有序数组

题目：

代码：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for (int i = 0; i != n; ++i) {
            nums1[m + i] = nums2[i];
        }
        sort(nums1.begin(), nums1.end());
    }
};


           

二叉树的中序遍历

题目

代码

二叉树中序遍历的递归模板需要背诵

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void inorder(TreeNode* root, vector<int>& res) {
        if (!root) {
            return;
        }
        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right, res);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root, res);
        return res;
    }
};