网站建设找 三尾狐,设计师服务平台素材羊,上海官网建设教程,正规seo关键词排名哪家专业C第二阶段——数据结构和算法#xff0c;之前学过一点点数据结构#xff0c;当时是基于Python来学习的#xff0c;现在基于C查漏补缺#xff0c;尤其是树的部分。这一部分计划一个月#xff0c;主要利用代码随想录来学习#xff0c;刷题使用力扣网站#xff0c;不定时更… C第二阶段——数据结构和算法之前学过一点点数据结构当时是基于Python来学习的现在基于C查漏补缺尤其是树的部分。这一部分计划一个月主要利用代码随想录来学习刷题使用力扣网站不定时更新欢迎关注 文章目录 一、移除元素力扣27二、反转字符串力扣344三、替换数字卡码网 54四、翻转字符串里的单词力扣151五、反转链表力扣206六、删除链表的倒数第 N 个结点力扣19七、链表相交力扣面试题 02.07八、环形链表 II力扣142九、三数之和力扣15十、四数之和力扣18 一、移除元素力扣27 给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。 不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 说明: 为什么返回数值是整数但输出的答案是数组呢? 请注意输入数组是以「引用」方式传递的这意味着在函数里修改输入数组对于调用者是可见的。 你可以想象内部操作如下: // nums 是以“引用”方式传递的。也就是说不对实参作任何拷贝 int len removeElement(nums, val); // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。 for (int i 0; i len; i) { print(nums[i]); } class Solution {
public:int removeElement(vectorint nums, int val) {// 利用快慢指针进行删除// 1. 判断是否只有零个或一个元素防止索引超出数组长度if(nums.size()1){if(nums[0]val){return 0;}else{return 1;}}if (nums.size()0){return 0;}int slow 0;for(int fast0;fastnums.size();fast){if(nums[fast]!val){nums[slow] nums[fast];slow;}}return slow;}
};二、反转字符串力扣344 编写一个函数其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。 不要给另外的数组分配额外的空间你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 示例 1 输入s [“h”,“e”,“l”,“l”,“o”] 输出[“o”,“l”,“l”,“e”,“h”] 示例 2 输入s [“H”,“a”,“n”,“n”,“a”,“h”] 输出[“h”,“a”,“n”,“n”,“a”,“H”] 提示 1 s.length 105 s[i] 都是 ASCII 码表中的可打印字符 class Solution {
public:void reverseString(vectorchar s) {// 双指针解决int begin 0;int end s.size()-1;while(beginend){// 交换char temp s[begin];s[begin] s[end];s[end] temp;begin;end--;}}
};三、替换数字卡码网 54 题目描述 给定一个字符串 s它包含小写字母和数字字符请编写一个函数将字符串中的字母字符保持不变而将每个数字字符替换为number。 例如对于输入字符串 “a1b2c3”函数应该将其转换为 “anumberbnumbercnumber”。 输入描述 输入一个字符串 s,s 仅包含小写字母和数字字符。 输出描述 打印一个新的字符串其中每个数字字符都被替换为了number 输入示例 a1b2c3 输出示例 anumberbnumbercnumber 提示信息 数据范围 1 s.length 10000。 #include iostream
using namespace std;int main() {string inputS;cin inputS;int count 0;// 遍历原来数组,记录其中数字的个数for (int i 0; i inputS.length(); i) {if (inputS[i] 9 inputS[i]0) {count;}}int FLength inputS.length();// resize 原来的字符串inputS.resize(FLength count * 5);// 替换原来字符串中的字符从后向前替换int j inputS.length()-1;for (int i FLength - 1; ji; i--,j--) {if (inputS[i] 9 inputS[i]0) {// 是数字要替换inputS[j] r;inputS[j-1] e;inputS[j-2] b;inputS[j-3] m;inputS[j-4] u;inputS[j-5] n;j - 5;}else {inputS[j] inputS[i];}}cout inputS endl;system(pause);return 0;}四、翻转字符串里的单词力扣151 给定一个字符串逐个翻转字符串中的每个单词。 示例 1 输入: “the sky is blue” 输出: “blue is sky the” 示例 2 输入: hello world! 输出: “world! hello” 解释: 输入字符串可以在前面或者后面包含多余的空格但是反转后的字符不能包括。 示例 3 输入: “a good example” 输出: “example good a” 解释: 如果两个单词间有多余的空格将反转后单词间的空格减少到只含一个。 class Solution {
public:string reverseWords(string s) {// 去除空格removeSpace(s);// // 翻转整个句子reverse(s.begin(), s.end());// 翻转每个单词// 首先找到每个单词的位置int slow0;for(int fast0;fasts.length();fast){if(s[fast1] || fasts.length()-1){reverseWord(s,slow,fast);slow fast2;}}return s;}// 翻转每个单词void reverseWord(string s, int begin, int end) {while (begin end) {swap(s[begin], s[end]);begin;end--;}}// 去除字符串中多余的空格void removeSpace(string s) {// 快慢指针去除空格int slow 0;for (int fast 0; fast s.length(); fast) {if (s[fast] ! ) {// 不为空格才进行下面的操作// 添加每个单词之间的空格句子开头不加if (slow ! 0) {s[slow] ;slow;}while (fasts.size() s[fast] ! ) {s[slow] s[fast];slow;fast;}}}s.resize(slow);}};五、反转链表力扣206 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {if(headNULL||head-nextNULL){// 只有一个结点return head;}// 定义两个指针一个指前面的一指后面的ListNode *pre NULL;ListNode *cur head;while(cur!NULL){// 用一个值去接收curListNode *temp cur-next;cur-next pre;pre cur;cur temp;}return pre;}};六、删除链表的倒数第 N 个结点力扣19 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {if (headNULL){return head;}ListNode * dummyNode new ListNode(0);dummyNode-next head;// 使用快慢指针ListNode* fast dummyNode;ListNode* slow dummyNode;while(n--){// 快指针先走n个fast fast-next;}while(fast!NULLfast-next!NULL){fast fast-next;slow slow-next;}// 删除元素ListNode * temp slow-next;slow-next slow-next-next;delete temp; // 删除return dummyNode-next;}
};七、链表相交力扣面试题 02.07 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {// 实际上是找相等的结点不是值相等而是 是同一个结点// 将两个链表右对齐// 求两个链表的长度if(headANULL||headBNULL){return NULL;}int lenA 1;int lenB 1;ListNode * curA headA;ListNode * curB headB;while(curA-next!NULL){lenA;curA curA-next;}while(curB-next!NULL){lenB;curB curB-next;}// 找最短的链表int minLen min(lenA,lenB);// AB需要移动的长度int needA lenA-minLen;int needB lenB - minLen;// 右对齐两个节点while(needA--){headA headA-next;}while(needB--){headB headB-next;}// 比较之后的链表是否相同while(headA!NULL||headB!NULL){if(headA headB){return headA;}else{headA headA-next;headB headB -next;}}return NULL;}
};八、环形链表 II力扣142 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode * first head;ListNode * slow head;while(first!NULLfirst-next!NULL){first first-next-next;slow slow-next;if(firstslow){// 此时相遇ListNode * index1 first;ListNode * index2 head;// 找入环口while(index1!index2){index1 index1-next;index2 index2-next;}return index1;}}return NULL;}
};九、三数之和力扣15 给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意答案中不可以包含重复的三元组。 示例 1 输入nums [-1,0,1,2,-1,-4] 输出[[-1,-1,2],[-1,0,1]] 解释 nums[0] nums[1] nums[2] (-1) 0 1 0 。 nums[1] nums[2] nums[4] 0 1 (-1) 0 。 nums[0] nums[3] nums[4] (-1) 2 (-1) 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意输出的顺序和三元组的顺序并不重要。 示例 2 输入nums [0,1,1] 输出[] 解释唯一可能的三元组和不为 0 。 示例 3 输入nums [0,0,0] 输出[[0,0,0]] 解释唯一可能的三元组和为 0 。 class Solution {
public:vectorvectorint threeSum(vectorint nums) {// 先对数组排序sort(nums.begin(),nums.end());// 定义结果数组vectorvectorint result;// 剪枝操作if(nums[0]0){return {}; // 第一个元素都大于0了说明不可能加起来等于0直接返回空}for(int i0;inums.size();i){// 定义两个指针int begin i1;int end nums.size()-1;// 去重操作if(i0nums[i]nums[i-1]){// 当前的i和i-1的元素是一样的continue; // 跳过当前循环}while(beginend){if((nums[i]nums[begin]nums[end])0){result.push_back({nums[i],nums[begin],nums[end]});while(beginendnums[begin]nums[begin1]){begin;}while(beginendnums[end]nums[end-1]){end--;}begin;end--;}else if((nums[i]nums[begin]nums[end])0){end--;}else{begin;}}}return result;}
};十、四数之和力扣18 给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复 0 a, b, c, d n a、b、c 和 d 互不相同 nums[a] nums[b] nums[c] nums[d] target 你可以按 任意顺序 返回答案 。 示例 1 输入nums [1,0,-1,0,-2,2], target 0 输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] 示例 2 输入nums [2,2,2,2,2], target 8 输出[[2,2,2,2]] 提示 1 nums.length 200 -109 nums[i] 109 -109 target 109 class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {// 先排序sort(nums.begin(),nums.end());// 定义最终返回数组vectorvectorint result;// 类似于三数之和多了一层循环for (int i0;inums.size();i){// 剪枝if(nums[0]0nums[0]target){break;}// 去重if(i0nums[i]nums[i-1]){continue;}for(int ji1;jnums.size();j){// 剪枝if(nums[i]nums[j]targetnums[j]0){break;}// 去重if(ji1nums[j]nums[j-1]){continue;}// 类似于三数之和int begin j1;int end nums.size()-1;while(beginend){if((long) nums[i]nums[j]nums[begin]nums[end]target){// 找到符合要求的数组记录result.push_back({nums[i],nums[j],nums[begin],nums[end]});while(beginendnums[begin]nums[begin1]){begin;}while(beginendnums[end]nums[end-1]){end--;}begin;end--;}else if((long)nums[i]nums[j]nums[begin]nums[end]target){end--;}else{begin;}}}}return result;}
};
