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

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。

相关文章

大学湖北中医药大学法医学试题及答案，分享几个实用搜题和学习工具 #微信#学习方法#职场发展

大学湖北中医药大学法医学试题及答案，分享几个实用搜题和学习工具 #微信#学习方法#职场发展

今天分享拥有拍照搜题、文字搜题、语音搜题、多重搜题等搜题模式，可以快速查找问题解析，加深对题目答案的理解。 1.快练题 这是一个网站 找题的网站海量题库,在线搜题,快速刷题~为您提供百万优质题库,直接搜索题库名称,支持多种刷题模式:顺序练习、语音听题、本地搜题、顺序阅读、模拟考试、组卷考试、赶快下载吧! 2.彩虹搜题 这是个老公众号了 支持手写输入，截图搜题，详细步骤，解题必备
阅读更多...
大学四年三年技术旅途

大学四年三年技术旅途

近三年前从接触技术以来，尝试过许多成熟的技术，最新的技术，高端技术，当然是从低端技术起步的（ps:现在明白能解决问题的技术最重要，没有所谓的技术等级，你用arm开发系统，而别人就用51单片机就解决问了，这很明显），对于新技术的热爱花费了大量时间，造成了不专业，不精通，最后发现最喜欢的是嵌入式系统研制与开发，其次是实时视觉处理以及运动控制。但好处是视野很广，思维变得更加灵活，我发现对于一个问题
阅读更多...
刷题——比较版本号

刷题——比较版本号

比较版本号_牛客题霸_牛客网 int compare(string version1, string version2){int len1 = version1.size();int len2 = version2.size();int i=0,j=0;while(i<len1 || j <len2){long num1 =0 ;while(i <len1 && version1.charAt
阅读更多...
leetcode刷题（46）——236. 二叉树的最近公共祖先

leetcode刷题（46）——236. 二叉树的最近公共祖先

这道题比235略难一些 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4] 示例 1: 输入:
阅读更多...
leetcode刷题（45）——35. 二叉搜索树的最近公共祖先

leetcode刷题（45）——35. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5] 示例 1: 输入: root = [
阅读更多...
leetcode刷题（44）——242. 有效的字母异位词

leetcode刷题（44）——242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。 示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true 示例 2: 输入: s = “rat”, t = “car” 输出: false 说明: 你可以假设字符串只包含小写字母。 进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
阅读更多...
leetcode刷题（43）——239. 滑动窗口最大值

leetcode刷题（43）——239. 滑动窗口最大值

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。 示例: 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值------------
阅读更多...
leetcode刷题（42）——703. 数据流中的第K大元素

leetcode刷题（42）——703. 数据流中的第K大元素

设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。 你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。 示例: int k = 3;int[] arr = [4,5,8,2];KthLargest kthLar
阅读更多...
leetcode刷题（41）——232. 用栈实现队列

leetcode刷题（41）——232. 用栈实现队列

使用栈实现队列的下列操作： push(x) – 将一个元素放入队列的尾部。 pop() – 从队列首部移除元素。 peek() – 返回队列首部的元素。 empty() – 返回队列是否为空。 示例: MyQueue queue = new MyQueue();queue.push(1);queue.push(2); queue.peek(); // 返回 1queue.pop();
阅读更多...
leetcode刷题（40）——83. 删除排序链表中的重复元素

leetcode刷题（40）——83. 删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。 示例 1: 输入: 1->1->2 输出: 1->2 示例 2: 输入: 1->1->2->3->3 输出: 1->2->3 平时我们删除一个链表中的某个元素，一般都是以下的写法： temp.next = temp.next.next; 这样temp.next就被删除了 此题解法如下： class Solution
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2