大一下考核题解

2024-04-21 04:12
文章标签 考核 题解 一下

本文主要是介绍大一下考核题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

大一下考核题解

125. 验证回文串

本题思路是我们要先去掉所有的非字母数字字符,然后大写转小写,再去判断正着和反着是否相同就可以了。

下面是代码:

bool isPalindrome(char* s) {int len = strlen(s);int l = 0;int r = 0;while (r < len) {if (s[r] >= 'A' && s[r] <= 'Z')s[r] = s[r] + 'a' - 'A';if ((s[r] >= 'a' && s[r] <= 'z') || (s[r] >= '0' && s[r] <= '9')) {s[l++] = s[r++];} else {r++;}}r = l - 1;l = 0;while (l <= r) {if (s[l++] != s[r--])return false;}return true;
}

其中我对去电非数字字母字符这一操作用了双指针的方法,左边l指针负责记录合法字符,右边r指针负责遍历完成所有的字符,遇到符合题意的就令s[l++]=s[r++],反之直接r++就可以了。这样最后0~l-1就是所有的小写字母与数字,然后再判断就可以了。

73. 矩阵置零

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

下面是代码:

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;}}}
}

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;}
}

147. 对链表进行插入排序

本题具体思路是:

  • 先创建一个虚拟头结点方便之后的插入;
  • cur为要插入的节点,用last和pre去寻找要插入的位置,pre是前一个位置,last是后一个位置。
  • 初始化last为head,cur为head->next,用last去找比cur数值大的第一个数;
  • 然后创建pre指向newhead->next,去寻找比cur数值小的最后一个位置;
  • 进行插入,更新cur进行下一次插入。

下面是代码:

struct ListNode* insertionSortList(struct ListNode* head) {if (head == NULL) {return head;}struct ListNode* newhead = malloc(sizeof(struct ListNode));newhead->val = 0;newhead->next = head;struct ListNode* last = head;struct ListNode* cur = head->next;while (cur) {if (last->val <= cur->val) {last = last->next;} else {struct ListNode* pre = newhead;while (pre->next->val <= cur->val) {pre = pre->next;}last->next = cur->next;cur->next = pre->next;pre->next = cur;}cur = last->next;}return newhead->next;
}

309. 买卖股票的最佳时机含冷冻期

先来看代码:

int maxProfit(int* prices, int pricesSize) {if (pricesSize == 0) {return 0;}int f[pricesSize][3];f[0][0] = -prices[0];f[0][1] = f[0][2] = 0;for (int i = 1; i < pricesSize; ++i) {f[i][0] = fmax(f[i - 1][0], f[i - 1][2] - prices[i]);f[i][1] = f[i - 1][0] + prices[i];f[i][2] = fmax(f[i - 1][1], f[i - 1][2]);}return fmax(f[pricesSize - 1][1], f[pricesSize - 1][2]);
}

一共分为三种情况。

其中: f[i] [0]: 手上持有股票的最大收益
f[i] [1]: 手上不持有股票,并且处于冷冻期中的累计最大收益
f[i] [2]: 手上不持有股票,并且不在冷冻期中的累计最大收益

初始化第0天一种情况是买票,为-prices[0],其他情况为没买,初始化为0;

从第一天开始:

  • 对于f[i] [0],目前有的股票是在第i-1天就已经拥有的或者是第i天买入的并且第i-1天不能处于冷冻期;
  • 对于f[i] [1],我们第i天之后处于冷冻期证明我们在这一天卖出了股票,说明在第i-1天必须有一张股票;
  • 对于f[i] [2],我们在第i天结束之后不持有任何股票并且不处于冷冻期,说明第i-1天时不持有任何股票;
  • 如果处于冷冻期,对应的状态为 f[i−1] [1];如果不处于冷冻期,对应的状态为 f[i−1] [2];
  • 最后一天我们手上不能留有股票,所以最后对f[pricesSize - 1] [1], f[pricesSize - 1] [2]取最大值就可以了。

35. 搜索插入位置

本题是一道简单的二分查找题。

主要思路就是当nums[mid]>=target,令right=mid,反之令left=mid+1。

之所以将nums[mid]==target归于第一类,是因为目标数字可能不存在。把等于归于第一类,我们会在最后的情况下left和right刚好落在大于或等于目标值的第一个位置,该下标就为目标值或者插入位置。

下面是代码:

int searchInsert(int* nums, int numsSize, int target) {int left = 0;int right = numsSize;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] >= target)right = mid;else if (nums[mid] < target)left = mid + 1;}return right;
}

61. 旋转链表

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

下面是代码:

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;
}

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

已经到底啦!!

这篇关于大一下考核题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/922134

相关文章

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题,笔试真题 会在第一时间跟新 🍄 题面描述等均已改编,如果和你笔试题看到的题面描述

【详细介绍一下GEE】

GEE(Google Earth Engine)是一个强大的云计算平台,它允许用户处理和分析大规模的地球科学数据集,如卫星图像、气候模型输出等。以下是对GEE用法的详细介绍: 一、平台访问与账户设置 访问GEE平台: 用户可以通过访问Google Earth Engine的官方网站来开始使用GEE。 创建账户: 用户需要注册并登录Google账户,然后申请访问GEE平台。申请过程可能需要提

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

P2858 [USACO06FEB] Treats for the Cows G/S 题解

P2858 题意 给一个数组。每天把最左或者最右的东西卖掉,第 i i i个东西,第 d a y day day天卖出的价格是 a [ i ] ∗ d a y a[i]*day a[i]∗day。 记忆化搜索 void dfs(int l,int r,int day,ll sum){if(v[l][r]>=sum)return;v[l][r]=sum;if(l>r)//这就是dp答案{

【C++题解】1272. 郭远摘苹果

欢迎关注本专栏《C++从零基础到信奥赛入门级(CSP-J)》 问题:1272. 郭远摘苹果 类型:二维数组 题目描述: 郭远有一天走到了一片苹果林,里面每颗树上都结有不同数目的苹果,郭远身上只能拿同一棵树上的苹果,他每到一棵果树前都会把自己身上的苹果扔掉并摘下他所在树上的苹果并带走(假设郭远会走过每一棵苹果树),问在郭远摘苹果的整个过程中,他身上携带的最多苹果数与最小苹果数的差是多少?

【最新华为OD机试E卷-支持在线评测】机器人活动区域(100分)多语言题解-(Python/C/JavaScript/Java/Cpp)

🍭 大家好这里是春秋招笔试突围 ,一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-E/D卷的三语言AC题解 💻 ACM金牌🏅️团队| 多次AK大厂笔试 | 编程一对一辅导 👏 感谢大家的订阅➕ 和 喜欢💗 🍿 最新华为OD机试D卷目录,全、新、准,题目覆盖率达 95% 以上,支持题目在线评测,专栏文章质量平均 94 分 最新华为OD机试目录: https://blog.