刷题日记——济南大学机试

2024-03-26 22:36
文章标签 刷题 日记 机试 大学 济南

本文主要是介绍刷题日记——济南大学机试，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

折戟厦大，考虑调剂济南大学，但是更想去的是杭师大，还是刷题，济南大学比厦门大学题目简单很多，因此一篇文章不多分析，直接给出代码，全部采用纯C语言编写并且AC，不用C++的stl库。
争取今天一口气刷完济南大学的机试题目！

本次博客不分段，是一篇长博文，十分硬（jian）核（dan），建议配合目录查阅

济南大学机试题目链接，请点这里哟

字符串转化

在这里插入图片描述

代码

#include <stdio.h>int main() {char num[1000];while (scanf("%s", num) != EOF) {int sum = 0;int i = 0;while (num[i] != '\0') {sum += num[i] - 'a' + 1;i++;}printf("%d\n", sum);}return 0;
}

整数去重

在这里插入图片描述

代码——列表避免暴力（空间换时间）

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>int num[20001];int main() {int n;while (scanf("%d", &n) != EOF) {int real_n = 0;bool sheet[100] = {false};for (int i = 0; i < n; i++) {int temp;scanf("%d", &temp);if (sheet[temp] == false) {num[real_n++] = temp;sheet[temp] = true;}}for (int i = 0; i < real_n; i++) {printf("%d ", num[i]);}printf("\n");}return 0;
}

本题注意事项

  • 本题有暴力方法，就是从头开始二重遍历，在后面遇到相同的元素就整体前移，这个方法十分耗时。
  • C语言使用bool类型需要使用到stdbool.h头文件，不然会报错

更多关于C标准库的知识，可以参考以下的链接，建议考前还是突击一下，不然这个不知道真的很伤

  • 常见15个C语言的标准库
  • C 标准库 - 参考手册

求斐波那契数列的第n项

在这里插入图片描述

代码

肥波的题目真的做yue了，眼睛闭上代码都能写出来。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>unsigned long long f(int n) {if (n == 0 || n == 1 ) {return 1;}return f(n - 1) + f(n - 2);
}int main() {int n;while (scanf("%d", &n) != EOF) {printf("%lld\n", f(n));}return 0;
}

进制转换问题

在这里插入图片描述

代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>int main() {int n;scanf("%d", &n);int num[100];int i = 0;while (n != 0) {num[i] = n % 2;n /= 2;i++;}for (; i >= 1; i--) {printf("%d", num[i-1]);}printf("\n");return 0;
}

奇数还是偶数

在这里插入图片描述

代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>char *f(int n) {if (n % 2 == 0) {return "even number";}return "odd number";
}int main() {int n;while (scanf("%d", &n) != EOF) {printf("%s\n", f(n));}return 0;
}

找出众数

在这里插入图片描述

代码——缝缝补补

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>int main() {int n;while (scanf("%d", &n) != EOF) {int ptr[20000] = {0};int *counts = ptr + 10000;int index[501];int single_num = 0;for (int i = 0; i < n; i++) {int temp;scanf("%d", &temp);if (counts[temp] == 0) {//首次出现需要记录下标index[single_num++] = temp;//不记录重复出现的值}counts[temp]++;//计数}//找最大counts值的index值int max = 0;int tag;for (int i = 0; i < single_num; i++) {if (max < counts[index[i]]) {max = counts[index[i]];tag = index[i];}}printf("%d\n", tag);}return 0;
}

分析——缝缝补补法

这题比较有意思，我的题解代码经过三轮迭代：

  • 第一轮：我一开始以为输入的所有数字都是1-1000，因此直接设置一个容量为1001的数组，序号是输入数字，数组值是出现次数，这样就像上面的整数去重一样，但是发现只能过三分之一的样例

  • 第二轮：还好我有大会员，看了发现是输入数字竟然是四位的，于是数组容量设置成10000，结果还是只能过83.3%的样例，再看输入，发现居然有负数输入

  • 第三轮：于是再改，直接把输入数组设置成容量为20000，同时为了最小变动，数组改名叫ptr，原来的数组名设置成为指针，指向ptr+10000的位置，这样你有负数我也不怕了

但是这样有个问题，就是，如果我提前不知道测试样例，我是不可能对第一轮的代码产生质疑的，肯定要想很久，到这里我就不得不喷N诺的开发者了，我们可以忍受你在网站上投放广告，或者要求我们帮你宣传，这些都可以，但是非要花30买小会员才能刷题（这人多也赚得够多了），非要花200才能告诉我们测试用例，复试机试就那么一两个月的事，你非要让我们200买一年真的太离谱了，一直这么玩，你不可能推广的开的

分析——全适应法（改进版：使用hash）

思路就是设置 数值-出现次数-序号 三个数据捆绑关系，这样有一个不方便的地方就是，每次判断数值是否出现时需要遍历
当然我有个粗略的改进方案，比如说把数组改成hash，模500放入，但是需要设置线性探测等避免冲突的方法。

括号匹配的问题

在这里插入图片描述

分析——数组模拟栈

使用C语言，没有栈的标准库，于是自己动手用数组模拟一个栈，需要实现pop和push，详细请看代码

代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>char stack[1000];
int size = 0;void pop() {stack[--size] = '\0';
}void push(char n) {stack[size++] = n;
}int main() {char str[1000];while (scanf("%s", str) != EOF) {//初始化size = 0;//获取长度int length = 0;while (str[length++] != '\0');//此外还可以用string.h中的int strlen(char str)获取str的长度//也可以用sizeof()int i;for (i = 0; i < length; i++) {if (str[i] == '[' || str[i] == '(') {push(str[i]);} else if (str[i] == ']') {if (stack[size - 1] == '[') {pop();} else {printf("NO");break;}} else if (str[i] == ')') {if (stack[size - 1] == '(') {//需要注意，栈顶元素的序号是size-1pop();} else {printf("NO");break;}}}if (i == length) {printf("YES");}printf("\n");}return 0;
}

单词翻转

在这里插入图片描述

代码

#include <stdio.h>
#include <string.h>char str_seq[1001][16];
char temp[10000];int main() {fgets(temp, 10000, stdin);int length = strlen(temp);int ptr = 0;int i = 0;while (ptr < length) {int j = 0;while (temp[ptr] != ' ' && temp[ptr] != '\n') {str_seq[i][j++] = temp[ptr++];}str_seq[i][j] = '\0';i++;ptr++;}for (int k = i - 1; k >= 0; k--) {printf("%s ", str_seq[k]);}printf("\n");}

注意点

在翻阅别人的题解时注意到一个可以减少思考复杂度的点：

  • 将输入字符串的最后一个’\n’字符pop出去
  • 在原有’\n’字符替换成为空格’ ’

在这里插入图片描述
但注意，这是c++语法对string的操作

喝饮料问题

在这里插入图片描述

代码

一开始当成了0-1背包问题，写出的代码只能过40%样例

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>struct drink {int mi;int wi;
};struct drink shop[1001];
double dp[1001][1001];int max(int a, int b) {if (a > b) {return a;}return b;
}int main() {int n, x;while (true) {scanf("%d %d", &x, &n);if (x == -1 && n == -1) {break;}//初始化dpfor (int i = 0; i <= n; i++) {dp[i][0] = 0;}for (int i = 0; i <= x; i++) {dp[0][i] = 0;}for (int i = 1; i <= n; i++) {scanf("%d %d", &shop[i].mi, &shop[i].wi);}//开始0-1背包for (int i = 1; i <= n; i++) {for (int j = 1; j <= x; j++) {if (shop[i].wi > j) {//装不下dp[i][j] = dp[i - 1][j];} else {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - shop[i].wi] + shop[i].mi);}}}printf("%.3f\n", dp[n][x]);}return 0;
}

后来发现根本没有背包问题复杂，就是把最实惠的饮料全部喝了，把钱全部用完就好了

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>int value[1001];
int weigh[1001];
double worth[1001];int find_max_index(int n) {double large = -1;int index;for (int i = 0; i < n; i++) {if (worth[i] > large) {index = i;large = worth[i];}}return index;
}int main() {int n, x;while (true) {scanf("%d %d", &x, &n);if (x == -1 && n == -1) {break;}for (int i = 0; i < n; i++) {scanf("%d %d", &weigh[i], &value[i]);worth[i] = (double)weigh[i] / value[i];}double result = 0;int counts = 0;while (counts != n) {int index = find_max_index(n);if (x >= value[index]) {result += weigh[index];x -= value[index];} else {result += worth[index] * x;x -= x;}counts++;worth[index] = -1;}printf("%0.3f\n", result);}return 0;
}

简单的背包问题

在这里插入图片描述

代码——这是真的背包问题了

但是与01背包问题有区别，比01背包更简单，可以将01背包的weigh和value令为相同的值

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>int weigh[1000];
int value[1000];int dp[1000][1000];int max(int a, int b) {if (a > b) {return a;} else {return b;}
}int main() {int s, n;while (scanf("%d %d", &s, &n) != EOF) {for (int i = 1; i <= n; i++) {scanf("%d", &weigh[i]);value[i] = weigh[i];}//初始化dpfor (int i = 0; i <= n; i++) {dp[i][0] = 0;}for (int i = 0; i <= s; i++) {dp[0][i] = 0;}bool flag = false;for (int i = 1; i <= n; i++) {for (int j = 1; j <= s; j++) {if (weigh[i] > j) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weigh[i]] + value[i]);}if (dp[i][j] == s) {flag = true;}}}if (flag == true) {printf("YES\n");} else {printf("NO\n");}}return 0;
}

全部AC，合影留念

在这里插入图片描述
记录一下心情，下午收到杭师大老师的回复，算是我折戟厦大后一束希望之光，下面全力冲刺杭师大调剂！争取笔试满分！

这篇关于刷题日记——济南大学机试的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/850079。

相关文章

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者：计算机编程-吉哥 🍊简介：专业从事JavaWeb程序开发，微信小程序开发，定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事，生活就是快乐的。 🍊心愿：点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能
阅读更多...
机试算法模拟题 服务中心选址

机试算法模拟题 服务中心选址

题目描述 一个快递公司希望在一条街道建立新的服务中心。公司统计了该街道中所有区域在地图上的位置，并希望能够以此为依据为新的服务中心选址：使服务中心到所有区域的距离的总和最小。 给你一个数组positions，其中positions[i] = [left, right] 表示第 i 个区域在街道上的位置，其中left代表区域的左侧的起点，right代表区域的右侧终点，假设服务中心的位置为loca
阅读更多...
【每日刷题】Day113

【每日刷题】Day113

【每日刷题】Day113 🥕个人主页：开敲🍉 🔥所属专栏：每日刷题🍍 🌼文章目录🌼 1. 91. 解码方法 - 力扣（LeetCode） 2. LCR 098. 不同路径 - 力扣（LeetCode） 3. 63. 不同路径 II - 力扣（LeetCode） 1. 91. 解码方法 - 力扣（LeetCode） //思路：动态规划。 cl
阅读更多...
华为OD机试真题-学生方阵-2024年OD统一考试（E卷）

华为OD机试真题-学生方阵-2024年OD统一考试（E卷）

题目描述 学校组织活动，将学生排成一个矩形方阵。 请在矩形方阵中找到最大的位置相连的男生数量。这个相连位置在一个直线上，方向可以是水平的，垂直的，成对角线的或者呈反对角线的。 注:学生个数不会超过10000 输入描述 输入的第一行为矩阵的行数和列数， 接下来的 n行为矩阵元素，元素间用""分隔。 输出描述 输出一个整数，表示矩阵中最长的位
阅读更多...
hot100刷题第1-9题，三个专题哈希，双指针，滑动窗口

hot100刷题第1-9题，三个专题哈希，双指针，滑动窗口

求满足条件的子数组，一般是前缀和、滑动窗口，经常结合哈希表； 区间操作元素，一般是前缀和、差分数组 数组有序，更大概率会用到二分搜索 目前已经掌握一些基本套路，重零刷起leetcode hot 100， 套路题按套路来，非套路题适当参考gpt解法。 一、梦开始的地方， 两数之和 class Solution:#注意要返回的是数组下标def twoSum(self, nums: Lis
阅读更多...
代码随想录刷题day25丨491.递增子序列 ，46.全排列 ，47.全排列 II

代码随想录刷题day25丨491.递增子序列 ，46.全排列 ，47.全排列 II

代码随想录刷题day25丨491.递增子序列 ，46.全排列 ，47.全排列 II 1.题目 1.1递增子序列 题目链接：491. 非递减子序列 - 力扣（LeetCode） 视频讲解：回溯算法精讲，树层去重与树枝去重 | LeetCode：491.递增子序列_哔哩哔哩_bilibili 文档讲解：https://programmercarl.com/0491.%E9%80%92%E
阅读更多...
【中等】保研/考研408机试-二分查找（模板题）

【中等】保研/考研408机试-二分查找（模板题）

二分查找就是在一个有序数组中查找某个值，以首端尾端的中点mid查找对比，mid与要查找的数进行对比，看落在哪个区间，在那个区间重新得到首端和尾端，进而得到新的mid值。 一、模板题 二分查找-I_牛客题霸_牛客网 class Solution {public:int search(vector<int>& nums, int target) {int left=0,right=nums.s
阅读更多...
代码随想录刷题day24丨93.复原IP地址 ，78.子集 ， 90.子集II

代码随想录刷题day24丨93.复原IP地址 ，78.子集 ， 90.子集II

代码随想录刷题day24丨93.复原IP地址 ，78.子集 ， 90.子集II 1.题目 1.1复原IP地址 题目链接：93. 复原 IP 地址 - 力扣（LeetCode） 视频讲解：回溯算法如何分割字符串并判断是合法IP？| LeetCode：93.复原IP地址_哔哩哔哩_bilibili 文档讲解：https://programmercarl.com/0093.%E5%A4%8
阅读更多...
如何快速融入大学课堂

如何快速融入大学课堂

快速融入大学课堂是适应大学生活的重要一步。以下是一些实用的建议，帮助你快速融入大学课堂并取得良好的学习效果。 ### 1. 提前准备 - **课前预习**：在上课前预习课程内容，了解基本概念和知识点，这样在课堂上更容易跟上老师的讲解。 - **准备学习材料**：带上笔记本、笔、课本和其他必要的学习材料，确保在课堂上能够及时记录和查阅。 ### 2. 积极参与课堂 - **主动提问**：在课堂上
阅读更多...
研1日记5

研1日记5

x = torch.tensor(x),numpy 转tensor 三维矩阵相加 screen -S pid 进入之前创建好的screen transpose()只能一次操作两个维度；permute()可以一次操作多维数据，且必须传入所有维度数， transpose()中的dim没有数的大小区分；permute()中的dim有数的大小区分 PyTorch 两大转置函数 trans
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2