C/C++每日一练(20230414)

1. 寻找峰值 🌟🌟

2. 相同的树 🌟

3. 整数反转 ※

🌟 每日一练刷题专栏 🌟

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

1. 寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：

输入：nums = [1,2,3,1]

输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5 
解释：你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

提示：

1 <= nums.length <= 1000
-2^31 <= nums[i] <= 2^31 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]

出处：

https://edu.csdn.net/practice/25557635

代码：

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int findPeakElement(vector<int> &nums)
    {
        int l = 0, r = nums.size() - 1;
        while (l < r)
        {
            int mid = l + (r - l) / 2;
            if (nums[mid] > nums[mid + 1])
            {
                if (mid == 0 || nums[mid] > nums[mid - 1])
                    return mid;
                else
                    r = mid;
            }
            else
            {
                if (mid + 1 == nums.size() - 1 || nums[mid + 1] > nums[mid + 2])
                    return mid + 1;
                else
                    l = mid + 1;
            }
        }
        return l;
    }
};

int main()
{
	Solution s;
    vector<int> nums = {1,2,3,1};
    cout << s.findPeakElement(nums) << endl;
    
	nums = {1,2,1,3,5,6,4};
    cout << s.findPeakElement(nums) << endl;
	    
    return 0;
}

输出：

2
5

2. 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：

输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：

输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：

两棵树上的节点数目都在范围 [0, 100] 内
-104 <= Node.val <= 104

出处：

https://edu.csdn.net/practice/25557636

代码：

#include <bits/stdc++.h>
using namespace std;
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:
    bool isSameTree(TreeNode *p, TreeNode *q)
    {
        if (p == nullptr && q == nullptr)
        {
            return true;
        }
        if (p == nullptr || q == nullptr)
        {
            return false;
        }
        if (p->val != q->val)
        {
            return false;
        }
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

非递归：

bool isSameTree(TreeNode* p, TreeNode* q) {
std::stack<TreeNode*> stack;
stack.push(p);
stack.push(q);
while (!stack.empty()) {
p, q = stack.top(), stack.pop();
if (p == nullptr && q == nullptr) {
continue;
} else if (p == nullptr || q == nullptr) {
return false;
} else if (p->val != q->val) {
return false;
} else {
stack.push(p->left);
stack.push(q->left);
stack.push(p->right);
stack.push(q->right);
}
}
return true;
}

3. 整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：

输入：x = 123
输出：321

示例 2：

输入：x = -123
输出：-321

示例 3：

输入：x = 120
输出：21

示例 4：

输入：x = 0
输出：0

提示：

-2^31 <= x <= 2^31 - 1

出处：

https://edu.csdn.net/practice/25557637

代码：

int reverse(int x)
{
    long long int r = 0;
    while (x)
    {
        r = r * 10 + (x % 10);
        x /= 10;
    }
    if (r > 2147483647)
        return 0;
    if (r < -2147483648)
        return 0;
    return (int)r;
}

输出：

略