游戏网站的设计方案,如何制作免费永久网站,如何做小程序推广,nginx怎么做多个网站一周周五#xff0c;总结一下本周的算法学习#xff0c;从本周开始重新学习许久未见的算法#xff0c;当然不同于大一时使用的 C 语言以及做过的简单题#xff0c;现在是每天一题 C 和 JavaScript#xff08;还在学#xff0c;目前只写了一题#xff09;
题单是代码随想…一周周五总结一下本周的算法学习从本周开始重新学习许久未见的算法当然不同于大一时使用的 C 语言以及做过的简单题现在是每天一题 C 和 JavaScript还在学目前只写了一题
题单是代码随想录JS和面试 150 题C, 括号中是我所用的解题语言。
令我印象最深的不是题目的难度而是 leecode 的提交方式与我所用过的学校 oj 还有洛谷都不同它所提交的是核心代码一开始我都是使用 ai 帮我浓缩成核心代码样式后面发现其实只需要补充 public 中的函数就可以了…… 我还一直在想 leecode 的输入格式到底是什么样的话不多说开始总结
代码随想录
移除链表元素
给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 示例 1 输入head [1,2,6,3,4,5,6], val 6
输出[1,2,3,4,5]示例 2
输入head [], val 1
输出[]示例 3
输入head [7,7,7,7], val 7
输出[]提示
列表中的节点数目在范围 [0, 104] 内1 Node.val 500 val 50
这题是我觉得比较简单的一道题复习一下链表知识就好
var removeElements function (head, val) {// 创建一个虚拟头节点const dummy new ListNode(0);dummy.next head;let current dummy; // 从虚拟头节点开始遍历while (current.next ! null) {if (current.next.val val) {// 跳过当前值等于 val 的节点//跳过了就再也不存在这个地址相当于删除这个元素current.next current.next.next;} else {// 否则继续移动到下一个节点current current.next;}}// 返回新的头节点return dummy.next;
};// 定义链表节点的结构
class ListNode {constructor(val 0, next null) {this.val val;this.next next;}
}面试 150
多数元素
给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的并且给定的数组总是存在多数元素。
示例 1
输入nums [3,2,3]
输出3
示例 2
输入nums [2,2,1,1,1,2,2]
输出2提示
n nums.length1 n 5 * 104-109 nums[i] 109
进阶尝试设计时间复杂度为 O (n)、空间复杂度为 O (1) 的算法解决此问题。
这题看上去很难想明白了就很简单简单来说是要找到出现最多的那个元素但是要想明白怎么找最省力我们假设找出一种生物用一个计数器为 0当这个生物遇到同类 1遇到其他生物就会 - 1当 cnt 为 0 时说明这个生物数量不够自然就 dead 了以此类推如果走到最后这个生物的数量没有为 0则证明它是最多的一类如果前面都不存在这种生物那留在最后的自然而然就是最多的
class Solution {
public:int majorityElement(vectorint nums) {int temp;int cnt 0;for(int i 0; i nums.size();i){if(cnt 0)temp nums[i];cnt (nums[i] temp) ? 1 : -1;}return temp;}
}; 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。
注意最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。
示例 1
输入nums1 [1,2,3,0,0,0], m 3, nums2 [2,5,6], n 3
输出[1,2,2,3,5,6]
解释需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] 其中斜体加粗标注的为 nums1 中的元素。示例 2
输入nums1 [1], m 1, nums2 [], n 0
输出[1]
解释需要合并 [1] 和 [] 。
合并结果是 [1] 。示例 3
输入nums1 [0], m 0, nums2 [1], n 1
输出[1]
解释需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意因为 m 0 所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。提示
nums1.length m nnums2.length n0 m, n 2001 m n 200-109 nums1[i], nums2[j] 109
这题也简单只需要从后往前查找比较 nums1 和 nums2 的大小如果 nums1 大于 nums2 就往后放反之就往前放如果有多nums1 未放完的自然都在前面nums2 潍坊玩的只需要接着仿就行
#include vector
using namespace std;class Solution {
public:void merge(vectorint nums1, int m, vectorint nums2, int n) {int i m - 1; // nums1 的有效元素索引int j n - 1; // nums2 的有效元素索引int k m n - 1; // 合并后数组的最后一个索引// 从数组的最后一位开始查找while (i 0 j 0) {if (nums1[i] nums2[j]) {// 将较大的放到合并数组的末尾nums1[k] nums1[i];i--;} else {nums1[k] nums2[j];j--;}k--;}// 将 nums2 剩余的元素复制到 nums1 中while (j 0) {nums1[k] nums2[j];j--;k--;}// nums1 的剩余元素不需要复制因为它们已经在正确的位置上}
};罗马数字转整数
罗马数字包含以下七种字符: I V X LCD 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如 罗马数字 2 写做 II 即为两个并列的 1 。12 写做 XII 即为 X II 。 27 写做 XXVII, 即为 XX V II 。
通常情况下罗马数字中小的数字在大的数字的右边。但也存在特例例如 4 不写做 IIII而是 IV。数字 1 在数字 5 的左边所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况
I 可以放在 V (5) 和 X (10) 的左边来表示 4 和 9。X 可以放在 L (50) 和 C (100) 的左边来表示 40 和 90。 C 可以放在 D (500) 和 M (1000) 的左边来表示 400 和 900。
给定一个罗马数字将其转换成整数。
示例 1:
输入: s III
输出: 3
示例 2:
输入: s IV
输出: 4
示例 3:
输入: s IX
输出: 9
示例 4:
输入: s LVIII
输出: 58
解释: L 50, V 5, III 3.示例 5:
输入: s MCMXCIV
输出: 1994
解释: M 1000, CM 900, XC 90, IV 4.
提示
1 s.length 15s 仅含字符 (I, V, X, L, C, D, M)题目数据保证 s 是一个有效的罗马数字且表示整数在范围 [1, 3999] 内题目所给测试用例皆符合罗马数字书写规则不会出现跨位等情况。IL 和 IM 这样的例子并不符合题目要求49 应该写作 XLIX999 应该写作 CMXCIX 。关于罗马数字的详尽书写规则可以参考 罗马数字 – 百度百科。
这题需要学习一下关于 unordered_map这里简单讲一下就是他可以存放名字value这样方便查找数字。思路是使用 for 循环遍历使用 current 存储当前字母的数字再用 next 去判断是否存在下一数字只要存在就存入下一个字符的数字不存在就入 0然后进行比较如果当前数字小于下一数字就减去当前数字否则就加上当前数字相等也要加上当前数字IIII 这种情况最后直接返回就行
class Solution {
public:int romanToInt(string s) {// 罗马数字字符与整数的映射unordered_mapchar, int romanMap {{I, 1}, {V, 5}, {X, 10}, {L, 50},{C, 100}, {D, 500}, {M, 1000}};int total 0;int n s.length();for (int i 0; i n; i) {// 获取当前字符和下一个字符的数字int current romanMap[s[i]];int next (i 1 n) ? romanMap[s[i 1]] : 0;// 如果当前数字小于下一个数字执行减法if (current next) {total - current;} else {// 否则执行加法total current;}}return total;}
}; 买卖股票的最佳时机
给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。
示例 1
输入[7,1,5,3,6,4]
输出5
解释在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出最大利润 6-1 5 。注意利润不能是 7-1 6, 因为卖出价格需要大于买入价格同时你不能在买入前卖出股票。示例 2
输入prices [7,6,4,3,1]
输出0
解释在这种情况下, 没有交易完成, 所以最大利润为 0。提示
1 prices.length 1050 prices[i] 104
这题假设第一天是最低买入价格将最大利润设置成 0不能为负不然不是利润遍历数组持续更新最低买入价格要是比这个最低价格高就说明可能会存在最大利润使用 max 函数比较最大利润用当前价钱减去最低价格
class Solution {
public:int maxProfit(vectorint prices) {if (prices.empty()) return 0; // 防止空数组访问int minPrice prices[0]; // 最低买入价格int maxProfit 0; // 最大利润for (int i 1; i prices.size(); i) {if (prices[i] minPrice) {minPrice prices[i]; // 更新最低买入价格} else {maxProfit max(maxProfit, prices[i] - minPrice); // 计算当前利润}}return maxProfit;
}}; 删除有序数组中的重复项
给你一个 非严格递增排列 的数组 nums 请你 原地 删除重复出现的元素使每个元素 只出现一次 返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k 你需要做以下事情确保你的题解可以被通过
更改数组 nums 使 nums 的前 k 个元素包含唯一元素并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。返回 k 。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums [...]; // 输入数组
int[] expectedNums [...]; // 长度正确的期望答案int k removeDuplicates(nums); // 调用assert k expectedNums.length;
for (int i 0; i k; i) {assert nums[i] expectedNums[i];
}
如果所有断言都通过那么您的题解将被 通过。
示例 1
输入nums [1,1,2]
输出2, nums [1,2,_]
解释函数应该返回新的长度 2 并且原数组 nums 的前两个元素被修改为 1, 2
。
不需要考虑数组中超出新长度后面的元素。 示例 2
输入nums [0,0,1,1,1,2,2,3,3,4]
输出5, nums [0,1,2,3,4]
解释函数应该返回新的长度 5 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。提示
1 nums.length 3 * 104-104 nums[i] 104nums 已按 非严格递增 排列
这题开始时我没想清楚从前开始算这个比较应该是后一位与前一位比较如果不相同就将该元素赋值到一个新数组再 cntcnt 就是新数组长度新数组是在原数组基础上添加如果不相同那么添加的位置与原位置也相同如果元素相同则删除一个元素不管怎么样在原数组基础上增删都不会超过原数组长度而且节省了空间
class Solution {
public:int removeDuplicates(vectorint nums) {if (nums.empty()) return 0; // 如果数组为空返回 0int count 1; // count 用来追踪唯一元素的个数for (int i 1; i nums.size(); i) {if (nums[i] ! nums[i - 1]) { // 如果当前元素和前一个不同nums[count] nums[i]; // 将当前元素移动到不重复部分的末尾}}return count; // 返回不重复元素的个数}
};移除元素
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k要通过此题您需要执行以下操作
更改 nums 数组使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。返回 k。
用户评测
评测机将使用以下代码测试您的解决方案
int[] nums [...]; // 输入数组
int val ...; // 要移除的值
int[] expectedNums [...]; // 长度正确的预期答案。// 它以不等于 val 的值排序。int k removeElement(nums, val); // 调用你的实现assert k expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i 0; i actualLength; i) {assert nums[i] expectedNums[i];
}
如果所有的断言都通过你的解决方案将会 通过。
示例 1
输入nums [3,2,2,3], val 3
输出2, nums [2,2,_,_]
解释你的函数函数应该返回 k 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要因此它们并不计入评测。
示例 2
输入nums [0,1,2,2,3,0,4,2], val 2
输出5, nums [0,1,4,0,3,_,_,_]
解释你的函数应该返回 k 5并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要因此它们并不计入评测。提示
0 nums.length 1000 nums[i] 500 val 100
与代码随想录题目相同从 js 改成了 c
class Solution {
public:int removeElement(vectorint nums, int val) {int newLength 0; // 用于记录新数组的有效长度// 遍历 nums 数组for (int i 0; i nums.size(); i) {if (nums[i] ! val) {nums[newLength] nums[i]; // 将非 val 元素放到前面newLength; // 更新新数组的长度}}return newLength; // 返回新数组的长度}
};本周题解就到这里结束下周见。
