大一上考核题解

news/2024/5/19 21:59:53/ 标签: 学习, 算法

文章目录

    • [238. 除自身以外数组的乘积](https://leetcode.cn/problems/product-of-array-except-self/)
        • 代码
        • 题解
    • [73. 矩阵置零](https://leetcode.cn/problems/set-matrix-zeroes/)
        • 代码
        • 题解
    • [394. 字符串解码](https://leetcode.cn/problems/decode-string/)
        • 代码
        • 题解
    • [23. 合并 K 个升序链表](https://leetcode.cn/problems/merge-k-sorted-lists/)
        • 代码
        • 题解
    • [232. 用栈实现队列](https://leetcode.cn/problems/implement-queue-using-stacks/)
        • 代码
        • 题解
    • [61. 旋转链表](https://leetcode.cn/problems/rotate-list/)
        • 代码
        • 题解
    • [392. 判断子序列](https://leetcode.cn/problems/is-subsequence/)
        • 代码
        • 题解

238. 除自身以外数组的乘积

代码
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {int* arr1 = (int*)malloc(sizeof(int) * (numsSize + 1));int* arr2 = (int*)malloc(sizeof(int) * (numsSize + 1));for (int i = 0; i < numsSize; i++) {if (i == 0)arr1[i] = nums[i];elsearr1[i] = nums[i] * arr1[i - 1];}for (int i = numsSize - 1; i >= 0; i--) {if (i == numsSize - 1)arr2[i] = nums[i];elsearr2[i] = nums[i] * arr2[i + 1];}int* ans = (int*)malloc(sizeof(int) * (numsSize + 1));for (int i = 0; i < numsSize; i++) {if (i == 0)ans[i] = arr2[i + 1];else if (i == numsSize - 1)ans[i] = arr1[i - 1];elseans[i] = arr1[i - 1] * arr2[i + 1];}*returnSize = numsSize;return ans;
}
题解

本题主要思路就是重新创建两个数组,一个用来记录下标为i左边数字的乘积和,一个用来记录下标为i右边数字的乘积和,这样子当我们统计的除nums[i]之外个元素的乘积就是arr1[i-1]*arr2[i+1]。

下面是具体思路:

  • 我们开辟两个数组arr1和arr2,分别正序与逆序遍历整个数组去给arr1和arr2赋值;
  • 正序遍历nums数组,当i==0时我们直接让arr1[i]=nums[i]就可以了,后面的我们就需要令arr1[i]等于nums[i]*arr[i-1];
  • 逆序遍历nums数组和正序遍历一样统计后面的乘积就可以了;
  • 最后我们统计ans数组数值,我们只需要让ans[i]=arr1[i-1]*arr[i+1](两个边界特殊处理)就可以了。

73. 矩阵置零

代码
void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {int hash[201][201] = {0};for (int i = 0; i < matrixSize; i++) {for (int j = 0; j < *matrixColSize; j++) {if (matrix[i][j] == 0)hash[i][j] = 1;}}for (int i = 0; i < 201; i++) {for (int j = 0; j < 201; j++) {if (hash[i][j] == 1) {int hang = i;int lie = j;for (int p = 0; p < *matrixColSize; p++)matrix[hang][p] = 0;for (int p = 0; p < matrixSize; p++)matrix[p][lie] = 0;}}}
}
题解

因为我们直接在原数组中进行修改会无法判断数组中的0是原题还是修改之后的,所以本题的最直接的思路就是我们直接重新创建一个二维数组进行标记原数组为0的位置,然后重新遍历一遍新创建的数组,当遇到之前标记的位置,我们就把数组对应的行和列全部设置为0,就可以实现本题了。

394. 字符串解码

代码
char* decodeString(char* s) {char* a = (char*)malloc(sizeof(char) * 10000);int m = -1;int len = strlen(s);for (int i = 0; i < len; i++) {if (s[i] == ']') {int rightzimu = m;int leftzimu = m;while (a[leftzimu] != '[') {leftzimu--;}leftzimu++;int rightshuzi = leftzimu - 2;int leftshuzi = rightshuzi;while (leftshuzi >= 0 && a[leftshuzi] >= '0' && a[leftshuzi] <= '9')leftshuzi--;if (leftshuzi != 0)leftshuzi++;char arr[3000] = {0}; // 记录要重复的元素int arr_num = 0;for (int h = leftzimu; h <= rightzimu; h++) {arr[arr_num++] = a[h];}int num = 0; // 记录重复次数for (int h = leftshuzi; h <= rightshuzi; h++) {num *= 10;num = num + a[h] - '0';}m = leftshuzi - 1;while (num--) {for (int z = 0; z < arr_num; z++)a[++m] = arr[z];}} else {a[++m] = s[i];}}char* ans = (char*)malloc(sizeof(char) * 10000);for (int i = 0; i <= m; i++)ans[i] = a[i];ans[m + 1] = '\0';return ans;
}
题解

本题我的大概思路就是开辟一个栈去存放原字符串,当遇到非 ']' 字符时直接存进去就可以了,如果遇到了 ']' 我们就要开始进行操作了。我们需要找出所有的字母与 '[' 前的数字M,然后我们重复M次存放进栈中就可以了,最后用ans重新读取,返回答案。

具体思路如下:

  • 我们创建了一个a进行字符的存放,设置栈顶m=-1,然后遍历字符串s;
  • 当没有遇到’]‘直接存放,当遇到了’]'我们便要开始进行操作;
  • 我们令rightzimu,leftzimu等于m,此时rightzimu指的就是最后一个字母;
  • 然后我们向前遍历栈a,令leftzimu–,直到遇到’['停止,我们再令leftzimu++,此时我们rightzimu,leftzimu中间夹的就是所有的字母;
  • 然后我们令rightshuzi=leftzimu-2,因为字母与前面的数字中间有个’[';
  • 令leftshuzi=rightshuzi,再次向前遍历,令leftshuzi–,满足leftshuzi >= 0 && a[leftshuzi] >= ‘0’ && a[leftshuzi] <= ‘9’,这里有两个停止条件,一个是遍历到不是数字了,另一个是遍历到栈底停止,所以我们要进行判断:如果leftshuzi != 0,我们才需要leftshuzi++,此时我们leftshuzi和rightshuzi中间夹的就是所有的数字;
  • 然后我们统计出要重复的元素arr和重复次数num,还要将num位置更新到leftshuzi-1的位置重新开始存储;
  • 我们再循环num次,将arr中所有元素再次存放进栈中;
  • 遍历完所有s元素之后我们申请一个ans用来存放答案就可以了。

23. 合并 K 个升序链表

代码
struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {if (l1 == NULL)return l2;if (l2 == NULL)return l1;if (l1->val > l2->val) {l2->next = merge(l1, l2->next);return l2;} else {l1->next = merge(l1->next, l2);return l1;}
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {if (listsSize == 0)return NULL;if (listsSize == 1)return lists[0];for (int i = 1; i < listsSize; i++) {lists[0] = merge(lists[0], lists[i]);}return lists[0];
}
题解

本题是 21. 合并两个有序链表 这道题的升级版,合并多个有序链表。

所以我们只要会了上面这一道题,那么实现本题就很简单了。

如果是合并两个有序链表,我们用递归很容易就可以实现:

  • 如果list1为空,直接返回list2;
  • 如果list2为空,直接返回list1;
  • 后面我们就需要进行递归了;
  • 如果list1数值大于list2,那么我们就需要保存此时的list2节点并且将list1与list2->next继续进行合并并且用list2->next进行接收;
  • 反之将list2与list1->next继续进行合并并用list1->next进行接收;
  • 返回list1或list2。

下面是具体代码:

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if (list1 == NULL)return list2;if (list2 == NULL)return list1;if (list1->val > list2->val) {list2->next = mergeTwoLists(list1, list2->next);return list2;} else {list1->next = mergeTwoLists(list1->next, list2);return list1;}
}

会了上面这一道题,本题只需要进行遍历整个lists并用lists[0]与list[i] (i!=0)进行合并就可以了。

下面是本题代码:

struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {if (l1 == NULL)return l2;if (l2 == NULL)return l1;if (l1->val > l2->val) {l2->next = merge(l1, l2->next);return l2;} else {l1->next = merge(l1->next, l2);return l1;}
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {if (listsSize == 0)return NULL;if (listsSize == 1)return lists[0];for (int i = 1; i < listsSize; i++) {lists[0] = merge(lists[0], lists[i]);}return lists[0];
}

232. 用栈实现队列

代码
typedef struct MyQueue {int stackIntop, stackOuttop;int stackIn[100], stackOut[100];
} MyQueue;MyQueue* myQueueCreate() {MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));queue->stackIntop = 0;queue->stackOuttop = 0;return queue;
}void myQueuePush(MyQueue* obj, int x) { obj->stackIn[(obj->stackIntop)++] = x; }int myQueuePop(MyQueue* obj) {int inTop = obj->stackIntop;int outTop = obj->stackOuttop;if (outTop == 0) {while (inTop > 0) {obj->stackOut[outTop++] = obj->stackIn[--inTop];}}int top = obj->stackOut[--(outTop)];while (outTop > 0) {obj->stackIn[inTop++] = obj->stackOut[--outTop];}obj->stackIntop = inTop;obj->stackOuttop = outTop;return top;
}int myQueuePeek(MyQueue* obj) { return obj->stackIn[0]; }bool myQueueEmpty(MyQueue* obj) {if (obj->stackIntop == 0)return true;return false;
}void myQueueFree(MyQueue* obj) {obj->stackIntop = 0;obj->stackOuttop = 0;
}
题解
  • myQueueCreate 需要我们开辟空间,大小为MyQueue,并且将queue->stackIntop和queue->stackOuttop都初始化为0;
  • myQueuePush 直接给stackIn中存储数据并且令obj->stackIntop ++;
  • myQueuePop 需要用两个栈去实现,第一个栈是之前存数据的栈,另一个栈只是一个工具,我们需要把stackIn中的数据存储进stackOut中,这样就刚好将stackIn中栈底的元素放到了stackOut的栈顶位置,直接弹出就可以了,把剩余元素重新存入stackIn中;
  • myQueuePeek 直接返回栈底元素就可以了;
  • myQueueEmpty 若stackIntop是0,则证明没有元素,反之则有元素;
  • myQueueFree 直接将stackIntop和stackOuttop置零就可以了。

61. 旋转链表

代码
struct ListNode* rotateRight(struct ListNode* head, int k) {if (head == NULL)return head;if (head->next == NULL)return head;int len = 0;struct ListNode* cur = head;while (cur) {cur = cur->next;len++;}k %= len;while (k--) {cur = head;struct ListNode* pre = cur;while (cur->next) {pre = cur;cur = cur->next;}cur->next = head;head = cur;pre->next = NULL;}return head;
}
题解

本题我们需要先求出链表的长度len,用k进行取模(因为移动len次相当于没有移动,反倒会增加运行时间,导致超时),然后我们需要进行循环,每一次循环都找到最后一个节点,将该节点的next指向头结点,然后将最后一个节点的前一个节点pre的next指向NULL,这样就实现了一次旋转,我们循环k次就可以了。

392. 判断子序列

代码
bool isSubsequence(char* s, char* t) {int n = strlen(s), m = strlen(t);int i = 0, j = 0;while (i < n && j < m) {if (s[i] == t[j]) {i++;}j++;}if (i == n)return true;return false;
}
题解

我们用双指针可以很容易地实现本题。

  • 我们令i指向s第一个元素,j指向t第一个元素;
  • 让j向后移动,如果s[i]==t[j],让i也向后移动;
  • 遍历完t后若果i移动到了最后一个,则证明存在子序列,反之不存在。

以上就是大一上考核题解!

已经到底啦!!


http://www.ppmy.cn/news/1426853.html

相关文章

Yarn--npm Windows安装使用

Yarn简介及Windows 在现代的Web开发中&#xff0c;JavaScript项目的依赖管理是一个复杂而重要的任务。幸运的是&#xff0c;我们有多种工具可以帮助我们处理这些依赖&#xff0c;其中之一就是Yarn。Yarn是一个由Facebook、Google、Tilde和Exponent联合开发的跨平台包管理工具&a…

NLP_知识图谱_三元组实战

文章目录 三元组含义如何构建知识图谱模型的整体结构基于transformers框架的三元组抽取baselinehow to use预训练模型下载地址训练数据下载地址 结构图代码及数据bertconfig.jsonvocab.txt datadev.jsonschemas.jsontrain.jsonvocab.json 与bert跟data同个目录model.pytrain.py…

竞争性自适应加权抽样结合偏最小二乘回归(CARS-PLS)在多变量分析中的应用(附MATLAB软件包)

竞争性自适应加权抽样结合偏最小二乘回归(CARS-PLS)在多变量分析中的应用 引言 在现代科学研究中,高维数据分析是一个日益重要的课题。由光谱学、色谱学和其他高通量测量技术产生的数据集通常包含大量的冗余和噪声,这给模型建立和预测带来了挑战。竞争性自适应加权抽样结…

LM Studio:一个桌面应用程序,旨在本地计算机上运行大型语言模型(LLM),它允许用户发现、下载并运行本地LLMs

LM Studio是一个桌面应用程序,旨在本地计算机上运行大型语言模型(LLM)。它允许用户发现、下载并运行本地LLMs,支持在Windows、Linux和Mac等PC端部署2510。LM Studio的安装过程涉及访问其官网并选择相应操作系统的版本进行下载安装。安装成功后,用户可以通过该软件选择并运…

【Gradle如何安装配置及使用的教程】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…

vue 3 中i18n字符串 转义问题

文章目录 前言原因分析解决方案1. 特殊字符的转义2. 占位符与变量插值3. HTML标记4. 多行字符串 前言 本地没有问题&#xff0c;打包就有问题&#xff0c;最后排查是i18n问题&#xff0c;这里记录下 原因分析 特殊符号被误解析&#xff1a;某些特殊符号可能在字符串解析时被特…

怎么用3ds MAX制作蜂窝状模型?

1、新建多边形&#xff1a;打开3ds MAX软件&#xff0c;在样条线中新建一个多边形。 2、设置参数&#xff1a;切换到顶视图&#xff0c;设置多边形的参数&#xff0c;例如半径为10&#xff0c;变数为6&#xff0c;以形成一个六边形的基础。 3、复制并形成圆柱状&#xff1a;打开…

【MATLAB源码-第25期】基于matlab的8QAM调制解调仿真,手动实现未调用内置函数,星座图展示。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 8QAM调制&#xff08;8 Quadrature Amplitude Modulation&#xff09;是一种数字调制技术&#xff0c;它可以在有限带宽内传输更多的信息比特。在8QAM调制中&#xff0c;每个符号可以携带3个比特的信息。QAM调制是将数字信号…

双链表的实现

我们知道链表其实有很多种&#xff0c;什么带头&#xff0c;什么双向啊&#xff0c;我们今天来介绍双向带头循环链表&#xff0c;了解了这个其他种类的链表就很简单了。冲冲冲&#xff01;&#xff01;&#xff01; 链表的简单分类 链表有很多种&#xff0c;什么带头循环链表&…

【C语言】贪吃蛇项目(2)- 实现代码详解

文章目录 前言一、游戏开始界面设计首先 - 打印环境界面其次 - 游戏地图、蛇身及食物的设计1、地图2、蛇身设置及打印3、食物 二、游戏运行环节蛇的上下左右移动等功能蛇的移动 三、结束游戏代码 前言 在笔者的前一篇博客中详细记载了贪吃蛇项目所需的一些必备知识以及我们进行…

【算法刷题day28】Leetcode:93. 复原 IP 地址、78. 子集、90. 子集 II

文章目录 Leetcode 93. 复原 IP 地址解题思路代码总结 Leetcode 78. 子集解题思路代码总结 Leetcode 90. 子集 II解题思路代码总结 草稿图网站 java的Deque Leetcode 93. 复原 IP 地址 题目&#xff1a;93. 复原 IP 地址 解析&#xff1a;代码随想录解析 解题思路 “.”参数初…

ORACLE错误提示概述

OceanBase分布式数据库-海量数据 笔笔算数 保存起来方便自己查看错误代码。 ORA-00001: 违反唯一约束条件 (.) ORA-00017: 请求会话以设置跟踪事件 ORA-00018: 超出最大会话数 ORA-00019: 超出最大会话许可数 ORA-00020: 超出最大进程数 () ORA-00021: 会话附属于其它某些进程…

改进前后端交互实例

前后端交互实例(javaweb05)-CSDN博客 在这之前我假设大家都已经学完了IOC和DI 不明白的这里我也解释一下,首先是两个概念 1.控制反转:对象的创建控制权由程序自身转到外部(容器) 2.依赖注入:容器为程序提供运行时所依赖的资源 Bean对象:IOC容器中创建,关联的对象,称之为be…

生活中的洪特规则

不知道你还记不记得高中物理所学的一个奇特的物理规则&#xff1a;洪特规则。 洪特规则是德国人弗里德里希洪特&#xff08;F.Hund&#xff09;根据大量光谱实验数据总结出的一个规律&#xff0c;它指出电子分布到能量简并的原子轨道时&#xff0c;优先以自旋相同的方式分别占…

JavaWeb-登录校验

会话技术 浏览器使用的是http协议&#xff0c;多次请求间数据是不能共享的&#xff0c;例如我们要去访问用户数据的接口&#xff0c;但这时候用户是否已经登入了呢&#xff1f;是不知道的&#xff0c;为了解决这个问题&#xff0c;于是引入了会话跟踪技术。 会话&#xff1a;…

Windows如何安装JDK

JDK和JRE简介 JDK&#xff1a;Java Development ToolKit java开发工具包&#xff0c;包含JRE针对java程序开发者 JRE&#xff1a;Java Runtime Environment java程序的运行环境针对java使用者来说 下载JDK&#xff0c;进入官网下载 Oracle官网 双击下载好之后的exe文件&#…

论文笔记:Are Human-generated Demonstrations Necessary for In-context Learning?

iclr 2024 reviewer 评分 6668 1 intro 大型语言模型&#xff08;LLMs&#xff09;已显示出在上下文中学习的能力 给定几个带注释的示例作为演示&#xff0c;LLMs 能够为新的测试输入生成输出然而&#xff0c;现行的上下文学习&#xff08;ICL&#xff09;范式仍存在以下明显…

【算法刷题 | 回溯思想 06】4.17(子集、子集||)

文章目录 9.子集9.1题目9.2解法&#xff1a;回溯9.2.1回溯思路&#xff08;1&#xff09;函数返回值以及参数&#xff08;2&#xff09;终止条件&#xff08;3&#xff09;遍历过程 9.2.2代码实现 10.子集 ||10.1题目10.2解法&#xff1a;回溯10.2.1回溯思路10.2.2代码实现 9.子…

R:UpSet韦恩图制作

#安装UpSetR install.packages("UpSetR") library(UpSetR) #install.packages("UpSetR") library(UpSetR) library(Cairo) # 从CSV文件中读取数据 setwd("C:/Users/fordata/Desktop/研究生/第二个想法(16s肠型&#xff0b;宏基因组功能)/第二篇病毒组…

Jenkins 的构建时执行时间问题

我们希望我的项目能够在特定的时间自动执行&#xff0c;我们需要设定一个定时任务。 Jenkins 的定时任务是通过 Cron 任务来实现的&#xff0c;但是由有点不一样。 H/2 * * * * 比如说上面的设置就是每 2 分钟执行一次。 希望每分钟执行一次 Jenkins 的每分钟执行一次的设置…