C++笔试强训day12

server/2024/9/24 14:22:50/

目录

1.删除公共字符

2.两个链表的第一个公共结点

3.mari和shiny


1.删除公共字符

链接icon-default.png?t=N7T8https://www.nowcoder.com/practice/f0db4c36573d459cae44ac90b90c6212?tpId=182&tqId=34789&ru=/exam/oj

暴力枚举就行,也可以用哈希表,哈希更省一点时间

暴力:

#include <iostream>
#include <string>
using namespace std;
int main() {string s;string t;getline(cin, s);getline(cin, t);string ret;for (int i = 0; i < s.size(); ++i){int flag = 1;for (int j = 0; j < t.size(); ++j){if (s[i] == t[j])flag = 0;}if (flag)ret += s[i];}cout << ret << endl;return 0;
}

哈希:

#include <iostream>
#include <string>
using namespace std;
int main()
{string s, t;getline(cin, s);getline(cin, t);bool hash[300] = { 0 };for (char ch : t) hash[ch] = true;string ret;for (auto ch : s){if (!hash[ch]){ret += ch;}}cout << ret << endl;return 0;
}

2.两个链表的第一个公共结点

链接icon-default.png?t=N7T8https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=13&tqId=11189&ru=/exam/oj

我的思路是找出长度差值,然后让长的先走差值步数,这样就可以让他们同时出发,当第一次head1 == head2时,就可以返回了,如果遍历到nullptr了,那就表示无公共。

class Solution {
public:ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {int size1 = 0;int size2 = 0;ListNode* cur1 = pHead1;ListNode* cur2 = pHead2;while (cur1){size1++;cur1 = cur1->next;}while (cur2){size2++;cur2 = cur2->next;}int dif = abs(size1 - size2);cur1 = pHead1;cur2 = pHead2;if (size1 > size2)while (dif--)cur1 = cur1->next;if (size2 > size1)while (dif--)cur2 = cur2->next;while (cur1 || cur2){if (cur1 == cur2)return cur1;cur1 = cur1->next;cur2 = cur2->next;}return nullptr;}
};

3.mari和shiny

链接icon-default.png?t=N7T8https://ac.nowcoder.com/acm/problem/26226

我做的题目太少了,最多就做过两个状态的dp,结果就没有考虑dp方面。

正解为多(3)状态dp问题,处理好初始化细节就可以。

定义三个状态:

s[i] : 前 i 个数有几个s。

h[i] :前 i 个数有几个sh。

y[i] : 前 i 个数有几个shy。

s【i】:

三种状态均可以分两种情况写状态转移方程。

若第i个位置为 h 或者 y ,则需要加上前面的 s 或者 sh 个数:
比如前i - 1个位置有n个s,

则第i个位置的sh个数则为(i - 1位置的sh个数)加上(i - 1位置的s个数 * 1个h)。

以此类推y状态。

核心dp:

#include <iostream>
#include <string>
using namespace std;
#define int long long
const int N = 3e5 + 10;
int s[N];
int h[N];
int y[N];
char str[N];signed main() {int n;cin >> n;for(int i = 0; i < n;++i){cin >> str[i];}s[0] = str[0] == 's' ? 1 : 0;h[0] = y[0] = 0;for(int i = 0; i < n; ++i){if(str[i] == 's')s[i] = s[i - 1] + 1;elses[i] = s[i - 1];if(str[i] == 'h')h[i] = s[i - 1] + h[i - 1];elseh[i] = h[i - 1];if(str[i] == 'y')y[i] = h[i - 1] + y[i - 1];elsey[i] = y[i - 1];}cout << y[n - 1] << endl;return 0;
}

http://www.ppmy.cn/server/37245.html

相关文章

6.Docker端口映射与容器互联

文章目录 端口映射与容器互联1、端口映射实现容器访问1.1、从外部访问容器应用1.2 映射所有接口的地址1.3 映射到指定地址的指定端口1.4 映射到指定地址的任意端口1.5 查看映射端口配置 2、互联机制实现容器互访2.1、自定义容器名称2.2、容器互联 端口映射与容器互联 在生产实…

探索Linux中的VI编辑器:全方位命令详解与实战应用

探索Linux中的VI编辑器&#xff1a;全方位命令详解与实战应用 引言一、VI编辑器的三种模式二、VI中的翻页操作三、搜索与替换功能四、退出VI编辑器应用场景举例&#xff1a;总结 引言 VI编辑器作为Linux世界中的基石工具之一&#xff0c;其简洁高效的设计理念贯穿了多种操作系统…

质因数分解(cpp实现)--一种快速求得一个数有多少个因子的黑魔法

前言 最近机试没少吃不会质因数分解的亏&#xff0c;用传统的求得因子个数只能过一点点…(ex, 20%) 质因数分解后&#xff0c;可以将因子问题转化为 集合的组合问题&#xff0c;因此会很快&#xff0c;目测是 l o g n log n logn (n是该整数的值)。 传统解法 假设输入整数的…

附录C:招聘流程

< 回到目录 附录C&#xff1a;招聘流程 _xxx_公司的招聘 使命 只雇佣顶级人才。 他们是能够胜任工作&#xff0c;并与 _&#xff08;你的公司名称&#xff09;_ 的企业文化相匹配的超级明星。 方法 记分卡。招聘经理创建一份文件&#xff0c;详细描述此职位的工作内容…

wpf 使用DragDrop 类进行拖拽和接收

在WPF&#xff08;Windows Presentation Foundation&#xff09;中&#xff0c;DragDrop 类及其 DoDragDrop 方法用于实现拖放&#xff08;Drag and Drop&#xff09;功能。拖放是用户界面中常见的交互方式&#xff0c;允许用户通过鼠标&#xff08;或其他指针设备&#xff09;…

git 将 A 分支某次提交合并到 B 分支

在 Git 中&#xff0c;如果你想要将分支 A 上的某一次特定的提交合并到其他分支&#xff0c;但不想合并分支 A 上的其他改动&#xff0c;你可以使用 git cherry-pick 命令。这个命令允许你选择一个特定的提交&#xff0c;并将这个提交的更改应用到另一个分支上。 以下是使用 g…

值得收藏!修复Windows 10/11中找不到输出或输入设备的五种方法

序言 这篇文章主要关注处理声音输出/输入设备未发现的问题。它提供了许多可行的方法,帮助了许多Windows用户。阅读以下内容以找到你的解决方案。 最近,我将Windows 10更新到21H2,发现我的音频无法工作。当我把鼠标放在任务栏上的声音图标(上面有一个十字图标)上时,它会…

Spring Cloud Gateway的部署

不要将 Spring Cloud Gateway 部署到 Tomcat 可以将Spring Cloud Gateway打成jar包&#xff0c;并通过jar包部署&#xff0c;步骤&#xff1a; 1. 修改构建配置 确保你的pom.xml文件中的打包方式为jar。 <packaging>jar</packaging> 2 打包项目 mvn clean pack…