当前位置：首页 > news >正文

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

news 2025/7/21 21:53:34

1. 整数分解 ☆

2. 二叉树的最小深度 ★★

3. 找x ★★

1. 整数分解

输入一个正整数，将其按7进制位分解为各乘式的累加和。

示例 1：

输入：49
输出：49=7^2

示例 2：

输入：720
输出：720=6*7^0+4*7^1+2*7^3

代码：

#include<stdio.h>
#define X 7int main()
{int i = 0;int mod, num;scanf("%d", &num);printf("%d=", num);while(num){mod = num % X;num /= X;if(mod > 0)printf("%d*7^%d%c", mod, i, num > 0 ? '+' : '\n');i++;}return 0;
}

输入输出：

720
720=6*7^0+4*7^1+2*7^3

2. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

树中节点数的范围在 [0, 105] 内
-1000 <= Node.val <= 1000

代码：

#include <bits/stdc++.h>
#define null INT_MIN
using namespace std;struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};class Solution
{
public:int minDepth(TreeNode *root){if (!root)return 0;int left = minDepth(root->left);int right = minDepth(root->right);return (left && right) ? 1 + min(left, right) : 1 + left + right;}
};TreeNode* buildTree(vector<int>& nums)
{TreeNode *root = new TreeNode(nums[0]);queue<TreeNode*> q;q.push(root);int i = 1;while(!q.empty() && i < nums.size()){TreeNode *cur = q.front();q.pop();if(nums[i] != null){cur->left = new TreeNode(nums[i]);q.push(cur->left);}i++;if(i < nums.size() && nums[i] != null){cur->right = new TreeNode(nums[i]);q.push(cur->right);}i++;}return root;
}int main()
{Solution s;vector<int> root = {3,9,20,null,null,15,7};TreeNode* tree = buildTree(root);cout << s.minDepth(tree) << endl;root = {2,null,3,null,4,null,5,null,6};tree = buildTree(root);cout << s.minDepth(tree) << endl;return 0;
}

输出：

2
5

3. 找x

题目描述

输入一个数n，然后输入n个数值各不相同，再输入一个值x，输出这个值在这个数组中的下标（从0开始，若不在数组中则输出-1）。

输入

测试数据有多组，输入n(1<=n<=200)，接着输入n个数，然后输入x。

输出

对于每组输入,请输出结果。

样例输入

4
1 2 3 4
3

样例输出

代码：

#include <iostream>
using namespace std;
int main()
{int n = 0;cin >> n;int *ptr = new (nothrow) int[n];for (auto i = 0; i < n; i++){cin >> ptr[i];}int x = 0;cin >> x;auto j = 0;auto status = 0;for (; j < n; ++j){if (ptr[j] == x){status = 1;break;}}if (status == 0){j = -1;}cout << j << endl;delete[] ptr;cin.get();cin.get();return 0;
}

输入输出：

4
1 2 3 4
3
2

附录

二叉树的序列化与反序列化

class Codec
{
public:
string serialize(TreeNode *root)
{
string result = "[";
queue<TreeNode *> myQue;
myQue.push(root);
while (!myQue.empty())
{
root = myQue.front();
myQue.pop();
if (root == NULL)
{
result += "null,";
continue;
}
else
{
result += to_string(root->val) + ",";
myQue.push(root->left);
myQue.push(root->right);
}
}
if (result == "[null,")
{
result.resize(result.size() - 1);
}
else
{
int endIndex = result.size() - 1;
while (result[endIndex] < '0' || result[endIndex] > '9')
{
endIndex -= 1;
}
result.resize(endIndex + 1);
}
result += "]";
return result;
}
TreeNode *deserialize(string data)
{
vector<string> dataVec;
int dataSize = data.size();
for (int index = 1; index < dataSize - 1; ++index)
{
string tempData = "";
while (index < dataSize - 1 && data[index] != ',')
{
tempData += data[index++];
}
dataVec.push_back(tempData);
}
int dataVecSize = dataVec.size();
queue<TreeNode *> myQue;
if (dataVec[0] == "null")
{
return NULL;
}
TreeNode *result = new TreeNode(atoi(dataVec[0].c_str())), *tempPtr;
myQue.push(result);
for (int index = 1; index < dataVecSize; ++index)
{
tempPtr = myQue.front();
myQue.pop();
if (dataVec[index] != "null")
{
tempPtr->left = new TreeNode(atoi(dataVec[index].c_str()));
myQue.push(tempPtr->left);
}
index += 1;
if (index < dataVecSize && dataVec[index] != "null")
{
tempPtr->right = new TreeNode(atoi(dataVec[index].c_str()));
myQue.push(tempPtr->right);
}
}
return result;
}
};