提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

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

C++ 每日
2023-09-14 09:01:29 时间

目录

1. 约分  ★

2. 逆波兰表达式求值  ★★

3. 环形链表 II  ★★

🌟 每日一练刷题专栏 🌟

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

1. 约分

编写程序，要求用户输入一个分数，然后将其约分为最简式。如：

输入一个分数：8/12
最简分式：2/3

代码：

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int a, b, x, y, c;
    printf("输入一个分式：");
    scanf("%d/%d", &a, &b);
    if (a < b)
    {
		x = b;
		y = a;
	}
	else
	{
		x = a;
		y = b;
	}
	c = x % y;
    while (c)
    {
        x = y;
        y = c;
        c = x % y;
    }
    if (b / y != 1)
        printf("最简分式为：%d/%d", a / y, b / y);
    else
        printf("最简分式为：%d", a / y);
    return 0;
}

输入输出：

输入一个分式：8/12
最简分式为：2/3

2. 逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

  • 整数除法只保留整数部分。
  • 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：
该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：

  • 1 <= tokens.length <= 10^4
  • tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

  • 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
  • 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

  • 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
  • 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

代码：

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int evalRPN(vector<string> &tokens)
    {
        stack<int> num;
        for (int i = 0; i < tokens.size(); ++i)
        {
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
            {
                int j;
                int a = num.top();
                num.pop();
                int b = num.top();
                num.pop();
                if (tokens[i] == "+")
                    j = b + a;
                else if (tokens[i] == "-")
                    j = b - a;
                else if (tokens[i] == "*")
                    j = b * a;
                else
                    j = b / a;
                num.push(j);
            }
            else
            {
                num.push(stoi(tokens[i]));
            }
        }
        return num.top();
    }
};

int main()
{
	Solution s;
	vector<string> tokens = {"2","1","+","3","*"};
	cout << s.evalRPN(tokens) << endl;
	
	tokens = {"4","13","5","/","+"};
	cout << s.evalRPN(tokens) << endl;
	
	tokens = {"10","6","9","3","+","-11","*","/","*","17","+","5","+"};
	cout << s.evalRPN(tokens) << endl;

    return 0;
}

输出：

9
6
22

3. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：

  • 你是否可以使用 O(1) 空间解决此题？

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

  • 链表中节点的数目范围在范围 [0, 10^4] 内
  • -10^5 <= Node.val <= 10^5
  • pos 的值为 -1 或者链表中的一个有效索引

代码：

#include <bits/stdc++.h>
using namespace std;
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution
{
public:
    ListNode *detectCycle(ListNode *head)
    {
        ListNode *slow, *fast, *p;
        slow = fast = p = head;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast)
            {
                while (p != slow)
                {
                    p = p->next;
                    slow = slow->next;
                }
                return p;
            }
        }
        return nullptr;
    }
};

ListNode* cycleLinkedList(vector<int>& nums, size_t pos) {
    if (nums.empty() || (int)pos == -1) return NULL;
    ListNode *head = new ListNode(nums[0]);
    ListNode *rear = head;
    ListNode *cyclePos = head;
    for (size_t i = 1; i < nums.size(); ++i) {
        rear->next = new ListNode(nums[i]);
        rear = rear->next;
        if (i == pos) cyclePos = rear;
    }
    if (cyclePos) rear->next = cyclePos;
    return head;
}
 
string LList2String(ListNode* head, int nodes = 10) {
    ListNode* curNode = head;
    int size = 0;
    string res = "[";
    while (curNode != NULL && size < nodes) {
		res += size++ > 0 ? "," : "";
        res += to_string(curNode->val);
        curNode = curNode->next;
    }
    return res + "]";
}
 
int main()
{
	Solution s;
	vector<int> nums = {3,2,0,-4};
	ListNode* head = cycleLinkedList(nums, 1);
	cout << LList2String(head) << endl;
	ListNode* ring = s.detectCycle(head);
	cout << LList2String(ring) << endl;
	
	nums = {1,2,3};
	head = cycleLinkedList(nums, 0);
	cout << LList2String(head) << endl;
	ring = s.detectCycle(head);
	cout << LList2String(ring, 12) << endl;
	
	return 0;
}

输出：

[3,2,0,-4,2,0,-4,2,0,-4]
[2,0,-4,2,0,-4,2,0,-4,2]
[1,2,3,1,2,3,1,2,3,1]
[1,2,3,1,2,3,1,2,3,1,2,3]

说明：

创建带环单链表：

ListNode* cycleLinkedList(vector<int>& nums, size_t pos)

遍历带环单链表：

因为遍历无限循环，所以设置默认遍历前10个节点：

string LList2String(ListNode* head, int nodes = 10)

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

Golang每日一练 专栏

Python每日一练 专栏

C/C++每日一练 专栏

Java每日一练 专栏

相关文章