改变眼泪的理由 - 个人主页动态 - 牛客网

发布(48) 刷题

改变眼泪的理由

2023-07-30 21:08

电子科技大学计算机类

题解 | #左旋转字符串#

//这题比较简单的做法是用额外的空间来做。但用原地空间进行操作才更有挑战。 //同样，只要把需要左移的部分字符串，和不需要左移的部分字符串，分别反转后，再反转整个字符串，即可完成。 class Solution { public: void reversestr(string &str,int begin,int end) { int j = 0; for (int i = begin; i < (begin+end)/2; i++) { swap(str[i], str[end - j - 1]); ...

0 点赞评论收藏

转发

改变眼泪的理由

2023-07-30 20:40

电子科技大学计算机类

题解 | #翻转单词序列#

//先把每个单词内部局部反转，然后再整体反转即可。 class Solution { public: string ReverseSentence(string str) { int begin,end=0; while(end<str.size()) { while(str.at(end)!=char{' '}) { end++;//抵达该单词的终点。 if(end>=str.size())break; ...

0 点赞评论收藏

转发

改变眼泪的理由

2023-07-30 15:59

电子科技大学计算机类

题解 | #替换空格#

//看到这题第一时间能想到一些思路。比如从前往后进行原地替换——这样每次替换后都要向后移动大量元素，时间复杂度是n^2（准确来说是n*k，取决于空格的数量）。 //另一个思路是开辟一个新字符串，每次遇到空格后都写入%20，其他时候则正常写入。这样做的缺点是要额外花On的空间。 //代码随想录提供了一个原地操作的On办法。先统计空格的数量，然后为字符串开辟额外的空间，用双指针法，一个指向新空间末，一个指向原字符串末。两个一起往左移动。没遇到空格时，将原字符串的内容拷到新空间中。遇到空格时，则让指向原字符串的指针暂停一下，让指向新空间的连动3步把%20打出来。 class Solution { p...

0 点赞评论收藏

转发

改变眼泪的理由

2023-07-20 21:23

电子科技大学计算机类

题解 | #兑换零钱(二)#

#include <vector> class Solution { public: //完全背包-种数-组合数 //dp[j]：总金额为j，在nums存储的硬币面额中，有dp[j]种 组合 方式。 //递推公式：求种数的问题，递推公式为dp[j]=dp[j] + dp[j-num[i] ]。原因详见代码随想录的“目标和”章节。 //遍历顺序：外层物品，内层容量。如果内层是物品的话，会导致变成排列。由于是完全背包，物品可以重复使用，因此内层容量为正遍历。 //初始化：dp[0]=1，目的是点燃“原初之火”，而其他都初始化为0，否则在递推的过程...

0 点赞评论收藏

转发

改变眼泪的理由

2023-07-19 01:22

电子科技大学计算机类

题解 | #分割等和子集#

#include <vector> class Solution { public: //dp[j]：容量为j的背包中能装下的物品的最大价值为dp[j]，在本题中j的最大值是数组和的一半，当dp[j]=j，也就是正好有一种情况，能满足让某些数字构成数组和的一半时，剩下的数字自然也能构成另一半，因此就能满足题意了。 //递推公式：由于使用的是滚动背包，以将空间复杂度从nxv降低到v，所以每一次遍历时都是用j的值从后往前覆盖掉j-1的值。 //在二维背包里，dp[i][j]=max(dp[i-1][j] 即不放物品i, dp[i][j-weight(i)]+va...

0 点赞评论收藏

转发

改变眼泪的理由

2023-07-16 21:53

电子科技大学计算机类

题解 | #跳台阶#

class Solution { public: //dp[i]：i代表爬几层楼梯，dp[i]代表爬i层楼梯一共有几种方法 //递推公式：dp[i]可由dp[i-1]爬一步，dp[i-2]跨两步这两种得到，因此和斐波那契的公式一样。 //初始化：dp[0]不作讨论，dp[1]=1，dp[2]=2，从i=3开始递推 //遍历顺序：从前往后 int climbStairs(int n) { vector<int>dp = {1, 2}; if (n == 1) return 1; ...

0 点赞评论收藏

转发

改变眼泪的理由

2023-07-16 21:33

电子科技大学计算机类

题解 | #不同路径的数目(一)#

#include <vector> class Solution { public: //dp[i][j]：从[0,0]走到[i,j]一共有多少种路径 //递推公式：dp[i][j]=dp[i-1][j] + dp[i][j-1] （i和j都要大于0） //初始化：dp[i][0]=1，dp[0][j]=1 //遍历顺序，正向双层遍历 int uniquePaths(int m, int n) { vector<vector<int> >dp(m,vector<int>(n,1));//初始...

0 点赞评论收藏

转发

改变眼泪的理由

2023-07-16 18:42

电子科技大学计算机类

题解 | #最小花费爬楼梯#

#include <algorithm> #include <vector> class Solution { public: //dp[i]：到达第i层台阶所需的最小cost总和。而cost[i]指的是从第i层楼梯起步所需要的cost，支付cost后能爬1~2步。 //递推公式：dp[i]=min(dp[i-1]+cost[i-1] , dp[i-2]+cost[i-2]) //初始化：dp[0]=0,dp[1]=0。 //遍历顺序：从前往后 //细节：到达台阶顶部是要比cost数组的size多1的。比如[2,5,20]，20并不是台阶顶部，而是到达顶部前的最后一级...

0 点赞评论收藏

转发

改变眼泪的理由

2023-07-15 18:37

电子科技大学计算机类

题解 | #两个链表的第一个公共结点#

#include <cstdlib> //两种解法，比较常规的就是快慢指针，先算出两条链表的长度，然后让快指针指向长的那一条，让它先走delta步，接着再快慢指针一起走，这样就能正好走到入口处了。 class Solution { public: ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { return FindFirstCommonNode_2(pHead1,pHead2); } ListNode* FindFirstCommonNode_2( ListNode* pH...

0 点赞评论收藏

转发

改变眼泪的理由

2023-07-15 18:23

电子科技大学计算机类

题解 | #反转链表#

//将链表节点摘下来挂在链表头部的解法。 class Solution { public: ListNode* ReverseList(ListNode* head) { ListNode* p=new ListNode(-1); if(head==nullptr || head->next==nullptr) return head;//如果只有一个节点或没有节点 p->next=head; ListNode* current=head->next; ListNode*next=current->next; whil...

0 点赞评论收藏

转发

改变眼泪的理由

2023-07-15 17:52

电子科技大学计算机类

题解 | #最小的K个数#

//使用了堆排序的思路。不是构建一个最小堆，把所有数据排完序后取前K个，而是构建一个最大堆，只保存k个数，这个最小堆我们视它为当前暂时筛选出来的k个最小数。如果有哪个数比这k个最小数中的最大的那个小，就相当于拥有了进入这个最小堆的权力。堆中的最大的这个数我们可以看成是“门槛”。它进来后可以把原本的门槛取而代之。 //如果要求你写的是“最大的K个数”，也没多少要改的，只需要把priority_queue中的第三个模板参数设置为greater（默认用的是less构建大根堆），以构建最小堆来保存最大的k个数。 //找最大的k个数用最小堆，找最小的k个数用最大堆，看起来很矛盾，但实际上这是因为我们并不...

0 点赞评论收藏

转发

改变眼泪的理由

2023-07-04 01:39

已编辑

电子科技大学计算机类

题解 | #三数之和#

//参考了代码随想录15.三数之和的写法 //本题的思路是“三指针”，先对数组进行排序，排序后用遍历数组，指针i指向的就是数字a，指针i的下一个位置记为left，即数字b，然后再拿一个指针指向数组中的最后一个数字，即数字c。 //通过不断判断a+b+c与0的关系，比0大就让right左移，比0小就让left右移。通过这种方式不断收缩left与right，直到找到a+b+c=0为止，将其添加进列表里。当然，一个i中可能有多解，在这种情况下依然需要继续收缩left与right。也有可能没解，这样收缩到left==right时，就步进i。 //这题的一大难点在于“去重”。对a的去重时应该使用num[...

0 点赞评论收藏

转发

改变眼泪的理由

2023-07-02 16:12

电子科技大学计算机类

题解 | #两数之和#

//根据代码随想录中的思路：这题我们需要不断地去判断与num对应的target-num是否曾经在数组里出现过。这种需要去“判断一个元素是否曾经出现过”的情况非常需要用哈希表来做。 //而且，由于本题还希望你知道每个曾经出现过的元素的下标，因此只用set不够，还得用map。 #include <unordered_map> #include <vector> class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { unor...

0 点赞评论收藏

转发

改变眼泪的理由

2023-07-02 15:20

电子科技大学计算机类

题解 | #快乐数#

//******************************************************************* //代码随想录中提到的快乐数。通过使用哈希表来检查中途的计算结果是否曾经出现过。如果出现过则代表进入无限循环了。 #include <unordered_set> #include <vector> class Solution { private: unordered_set<int>TempSum; public: bool happynum(int n) { // write...

0 点赞评论收藏

转发

改变眼泪的理由

2023-07-02 14:31

电子科技大学计算机类

题解 | #两个数组的交集#

//这一题使用了哈希表的思路来找到重复元素。 #include <unordered_set> #include <vector> class Solution { private: unordered_set<int>s1; unordered_set<int>s2; public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { s1.clear(); s2...

0 点赞评论收藏

转发

工具箱

TA的圈子

TA的笔记

牛客网
牛客企业服务