无重复字符的最长子串思考我记得是左右指针做的之后用vector记录比unordered_map要快代码执行用时分布11ms击败66.62%消耗内存分布20.78MB击败9.77%class Solution { public: int lengthOfLongestSubstring(string s) { s#s; int l0; vectorint vis(300,0); int ans0; for(int i1;is.size();i){ if (!vis[s[i]] || vis[s[i]]l){//如果是s[i]不在这个字符串里面 ansmax(ans,i-l); vis[s[i]]i; } else{//如果在的 lvis[s[i]]; vis[s[i]]i; } } return ans; } };206. 反转链表要求用递归和迭代思路 头插法直接头插法新建一个链表L的头然后L-next指向新的节点新的节点的next指向L-next的节点就这样循环代码 头插法0ms击败100.00%消耗内存分布13.04MB击败90.17%class Solution { public: ListNode* reverseList(ListNode* head) { if(head nullptr) return nullptr; ListNode fir(0,nullptr); ListNode* prehead; ListNode* lashead-next; while(pre!nullptr){ pre-nextfir.next; fir.nextpre; prelas; if(pre ! nullptr)las pre-next; } return fir.next; } };代码 三指针方法就不创建节点了直接用三个指针反转class Solution { public: ListNode* reverseList(ListNode* head) { if(head nullptr) return nullptr; ListNode* curhead; ListNode* prehead-next; ListNode* lasnullptr; while(cur!nullptr){ cur-nextlas; lascur; curpre; if(cur!nullptr)precur-next; } return las; } };代码 递归递归三要素函数定义返回的是什么终止条件递推关系这个函数返回的是反转的链表终止条件是返回的内容是空递推关系是现在的节点入参指向 函数返回的这个链表 返回指向现在节点的指针例如3-2-1-null递归函数是RR(3)的时候返回的是1-2-3所以应该R(head-next)head3的时候R的内容是1-2这时3的next还是2所以3的next【也就是2】的next指向33的next指向空因此设cur是R的内容head的next的next指向headhead的next指向空返回curclass Solution { public: ListNode* reverseList(ListNode* head) { if(headnullptr||head-next nullptr) return head; ListNode* curreverseList(head-next); head-next-nexthead; head-nextnullptr; return cur; } };53. 最大子数组和思路 O(n)首先肯定要是正的不然所有的都舍弃之后贪心就好了题目里写了子数组最少包含一个元素所以有可能是负的那如果当前的内容是负的同时之前的内容是负的那cursum就是当前的内容后面就分情况讨论就可以了代码 O(n)执行用时分布4ms击败24.46%消耗内存分布70.03MB击败92.69%class Solution { public: int maxSubArray(vectorint nums) { int ans-999999;int cursum-99999; for (int i0;inums.size();i){ if(nums[i]0 cursum0){cursumnums[i];ansmax(cursum,ans);} else if(nums[i]0 cursum0){ cursumcursumnums[i]; ansmax(cursum,ans); } else if(nums[i]0){ cursummax(cursum,0); cursumcursumnums[i]; ansmax(cursum,ans); } } return ans; } };优化后的内容没必要区分正的还是负的 如果cursum是负的那么变成现在的就好了所以只需要cursum max(nums[i], cursum nums[i]);执行用时分布0ms击败100.00%消耗内存分布70.19MB击败57.24%class Solution { public: int maxSubArray(vectorint nums) { int ansnums[0];int cursumnums[0]; for (int i1;inums.size();i){ cursummax(nums[i],cursumnums[i]); ansmax(ans,cursum); } return ans; } };思路 分治 O(nlogn)分治的思想在于最大的可能在[l,m]可能在[m1,r]也可能在[l,r]最后最大值在三个里面产生前两个是没说一定经过哪一个点所以只要求最大就可以[l,r]的区间一定要经过m点所以从m点向两侧的最大值相加可以用climits库中的最小值class Solution { public: int cs(vectorint nums,int l,int m,int r){ int lans-999999,lsum0; for(int im;il;i--){ lsumlsumnums[i]; lansmax(lans,lsum); } int rans-999999,rsum0; for(int im1;ir;i){ rsumrsumnums[i]; ransmax(rans,lsum); } return lansrans; } int divi(vectorint nums,int l,int r){ if(lr)return nums[l]; int mil(r-l)/2; return max(max(divi(nums,l,mi),divi(nums,mi1,r)),cs(nums,l,mi,r)); } int maxSubArray(vectorint nums) { int ansnums[0];int cursumnums[0]; for (int i1;inums.size();i){ cursummax(nums[i],cursumnums[i]); ansmax(ans,cursum); } return ans; } };19. 删除链表的倒数第 N 个结点思路一不小心看到答案了 那就复述一遍答案吧。首先前指针先跑n次之后快慢指针详细的内容还是要多画图对照一下代码执行用时分布0ms击败100.00%消耗内存分布14.82MB击败16.93%class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* prehead; for(int i0;in;i){ prepre-next; } if (prenullptr){//这个代表的是删除头节点 ListNode* nodehead-next; delete head; return node; } ListNode* curhead; while(pre-next!nullptr){ prepre-next; curcur-next; } ListNode* nodecur-next; cur-nextcur-next-next; delete node; return head; } };215. 数组中的第K个最大元素简单的哈希不过考的应该是快速选择下个帖子学习快速排序的时候学习一下吧代码执行用时分布3ms击败94.30%消耗内存分布71.89MB击败10.99%class Solution { public: int findKthLargest(vectorint nums, int k) { vectorint ha(20004,0); for(int i0;inums.size();i){ ha[10000nums[i]]; } for(int i20001;i0;i--){ if(k-ha[i]0)return i-10000; kk-ha[i]; } return 10000; } };
)
