网站建设信息,上海建溧建设集团有限公司网站,网站开发filter,排名前十的招聘app 141. Linked List Cycle
题意#xff1a;给你一个链表#xff0c;判断链表有没有环
我的思路
两个指针#xff0c;一个每次走两步#xff0c;一个每次走一步#xff0c;如果走两步的那个走到了NULL#xff0c;那说明没有环#xff0c;如果两个指针指向相等给你一个链表判断链表有没有环
我的思路
两个指针一个每次走两步一个每次走一步如果走两步的那个走到了NULL那说明没有环如果两个指针指向相等说明有环
代码 Runtime7 ms Beats 91.63% Memory 8 MB Beats 67.57%
class Solution {
public:bool hasCycle(ListNode *head) {ListNode *phead;ListNode *qhead;if(headNULL||head-nextNULL)return 0;pp-next;qq-next-next;while(q!NULLq!p){pp-next;if(q-next!NULL)qq-next-next;else qq-next;}if(qNULL)return 0;return 1;}
};
标答 简洁
原理是一样的 就是代码更简洁了
class Solution {
public:bool hasCycle(ListNode *head) {ListNode* slowhead;ListNode* fasthead;while(fast fast-next){slowslow-next;fastfast-next-next;if(fastslow)return true;}return false;}
}; 142. Linked List Cycle II
题意给一个链表有环返回环的开始没环返回NULL
我的思路
虽然想用快慢指针但是不一定能返回环的开始位置所以想了想还是用map把第一个相同的map就是环的位置
代码 Runtime14 ms Beats 12.81% Memory 10.1 MB Beats 5.29%
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(headNULL)return NULL;unordered_mapListNode *,intmp;ListNode *qhead;while(q-next!NULL){if(mp[q])return q;mp[q];qq-next;} return NULL;}
};
标答 快慢指针
如果头指针为空的话返回空定义慢指针和快指针
如果快指针和快指针的next不为空否则跳出循环那么慢指针走一步步快指针走走两步如果快指针等于慢指针跳出循环
跳出循环后如果快指针为空或者快指针的next为空返回NULL
这时的环的大小是慢指针走过的路程数slow指向head时slow和head的距离是环的长度的倍数
详见下方公式 代码 Runtime 4 ms Beats 93.5% Memory 7.6 MB Beats 51.24%
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(!head) return NULL;auto slow head, fast head;while(fast fast-next) {slow slow-next;fast fast-next-next;if(slow fast) break;}if(!fast || !fast-next) return NULL;slow head;while(slow ! fast) {slow slow-next;fast fast-next;}return slow;}
}; 146. LRU Cache
题意cache容量为size如果不停地向cache中put(key,value)如果超出容量了就会把最长时间问访问的删除get函数是返回key的value同时刷新最近访问
我的思路
我记得之前牛客做过但是忘记了
put的时候需要有list来控制先后最近的刷新在链表的最前所以超过容量的时候list的表尾删掉put加上的时候在最前面加上本身就有的话刷新因为答案里输入的是一对所以list的数据类型是pair
get的时候要找到key对应的结点这个时候要用mapmap和listint::iterator
代码 Runtime 409 ms Beats 87.32% Memory 174 MB Beats 53.92%
class LRUCache {
public:int size;unordered_mapint, listpairint, int ::iteratormp;list pairint,int li;LRUCache(int capacity) {sizecapacity;}int get(int key) {if(mp.count(key)0){pairint,inttmp*mp[key];li.erase(mp[key]);//get一次刷新一次li.push_front(tmp);mp[key]li.begin();return tmp.second;}return -1;}void put(int key, int value) {pairint,int tmp{key,value};if(mp.count(key) 0){//以前就有把以前的删掉li.erase(mp[key]);}else if(li.size()size){//以前没有但是满了把最前面的删掉auto litli.end();lit--;pairint,int del*lit;//值li.pop_back();mp.erase(del.first);//现在没了}li.push_front(tmp);//新加入的放在最前面mp[key]li.begin();}
};
标答 没仔细看
代码 vector Runtime346 ms Beats 98.88% Memory163.8 MB Beats 97.1%
class LRUCache {
public:queueint LRU;vectorint usages vectorint(10001, 0);vectorint kvp vectorint(10001, -1);int size 0;int cap 0;LRUCache(int capacity) {cap capacity;}int get(int key) {if(kvp[key] ! -1){LRU.push(key);usages[key];}return kvp[key];}void put(int key, int value) {if(size cap || kvp[key] ! -1){if(kvp[key] -1) size;LRU.push(key);usages[key];kvp[key] value;return;}while(usages[LRU.front()] ! 1){usages[LRU.front()]--;LRU.pop();}kvp[LRU.front()] -1;usages[LRU.front()]--;LRU.pop();LRU.push(key);usages[key];kvp[key] value;}
}; 148. Sort List
题意链表升序排序
我的思路
说要nlogn想到的有快排和归并翻了翻标答居然超时了看了看数据原来是降序排序好吧那就按照归并做吧
【后来想了想快排还要倒着走确实不太适合单向链表】
归并就是先递归左边之后递归右边最后归并
数组我会但是链表怎么做呢
标答
首先定义prev指针快指针和慢指针之后让慢指针到链表二分之一的位置快指针在NULL之前prev在slow指针的前面之后prev-nextNULL使他彻底变成两条指针
递归第一条链表和第二条链表直到headNULL或者head-nextNULL 返回head指针
最后把这两个head指针的链表合起来合并也是用递归合并如果l1的值小于l2的值合并(l1-nextl2)【因为要从小到大排序所以要留下小的值让后面的值去比较
代码 Runtime 127 ms Beats 99.16% Memory 53.2 MB Beats 79.49%
class Solution {
public:ListNode* sortList(ListNode* head) {if(headNULL||head-nextNULL)return head;ListNode* prevNULL;ListNode* slowhead;ListNode* fasthead;while(fast!NULLfast-next!NULL){prevslow;slowslow-next;fastfast-next-next;}prev-nextNULL;ListNode* l1sortList(head);ListNode* l2sortList(slow);return merge(l1,l2);}ListNode* merge(ListNode* l1,ListNode* l2){//合并递归if(l1NULL)return l2;if(l2NULL)return l1;if(l1-vall2-val){l1-nextmerge(l1-next,l2);return l1;}else {l2-nextmerge(l1,l2-next);return l2;}}
}; 152. Maximum Product Subarray
题意最大子段积
我的思路
动态规划但是有负数欸看提示是前缀积先来个O(n^2)
但是普通的前缀积不太行因为有0算了现在个最暴力的O(n^2)-----TLE了
class Solution {
public:int maxProduct(vectorint nums) {ios::sync_with_stdio(false);cin.tie(0);int nnums.size(),maxxnums[0];if(n1)return nums[0];for(int i0;in;i){int pro1;for(int ji;jn;j){propro*nums[j];maxxmax(maxx,pro);}}return maxx;}
};
标答 动态规划
首先定义了min和max如果这个数是负数就把max和min交换一下之后更新max和min和ans
代码 Runtime3 ms Beats 92.63% Memory13.8 MB Beats 23.8%
class Solution {
public:int maxProduct(vectorint nums) {int nnums.size();int maxxnums[0],minnnums[0],ansnums[0];for(int i1;in;i){if(nums[0]0)swap(maxx,minn);minnmin(minn*nums[i],nums[i]);//和nums[i]作比较maxxmax(maxx*nums[i],nums[i]);//表示的是以i为右端点的最大or最小值ansmax(ans,maxx);}return ans;}
}; 153. Find Minimum in Rotated Sorted Array
题意数组被rotate了1到n次以logn的时间复杂度返回最小的数字
我的思路
其实循环On也能 Runtime0 ms Beats 100% Memory10.1 MB Beat 93.66%
class Solution {
public:int findMin(vectorint nums) {int minn5001;for(int i0;inums.size();i)minnmin(minn,nums[i]);return minn;}
};
但是logn的话那就二分如果用归并的想法都切成2个2个的最后返回最小的
但是这没有用到rotate的部分也不知道是不是logn
好像不是【因为a2b2f(n)1所以复杂度为n】 Runtime0 ms Beats 100% Memory 10.1 MB Beats 93.66%
class Solution {
public:int fi(vectorint nums,int l,int r){if(lr)return nums[l];int midl(r-l)/2;return min(fi(nums,l,mid),fi(nums,mid1,r));}int findMin(vectorint nums) {int nnums.size();return fi(nums,0,n-1);}
};
标答
因为题中的rotate是把数组分成两个部分这两个部分交换的意思
例如 0 1 2 3 4 5 7---3 4 5 7 0 1 2这样的纯交换所以虽然看上去递归两次其实只要递归一边 为什么这个是logn At each level, at least one side could be done in O(1).T(N) O(1) T(N/2) O(\log{N}) 代码 Runtime0 ms Beats 100% Memory10.1 MB Beats 51.34%
class Solution {
public:int fi(vectorint nums,int l,int r){if(lr)return nums[l];if(nums[l]nums[r])return nums[l];int midl(r-l)/2;return min(fi(nums,l,mid),fi(nums,mid1,r));}int findMin(vectorint nums) {int nnums.size();return fi(nums,0,n-1);}
}; 155. Min Stack 题意建立一个栈它有正常的栈都有的功能就是多了一个getmin的函数求当前剩下的数字中最小的那个
我的思路
如果是普通的栈的话stack和vector都可以但是如何getmin
先On试试
代码 Runtime 200 ms Beats 5.2% Memory 16.4 MB Beats 25.58%
class MinStack {
public:vectorlong longv;MinStack() {}void push(int val) {v.push_back(val);}void pop() {v.pop_back();}int top() {return v[v.size()-1];}int getMin() {long long minn-9999999999999999999;for(int i0;iv.size();i)minnmin(minn,v[i]);return minn;}
};标答 单调栈
创建两个栈一个是正常的栈一个是专门存放最小值的栈 为什么不会存在pop正常栈的值第二小的值再pop正常栈的值第一小的值再getmin为什么不会出现第二小的值 因为存放最小值的栈是单调栈只会存放当前数的右边比它更小的值 代码 Runtime17 ms Beats 85.63% Memory16.1 MB Beats 92.4%
class MinStack {
public:stackint st;stackint mi;void push(int val) {st.push(val);if(mi.empty()||mi.top()val)mi.push(val);//注意这里是等于}void pop() {if(mi.top()st.top())mi.pop();st.pop();}int top() {return st.top();}int getMin() {return mi.top();}
};
160. Intersection of Two Linked Lists 题意返回两条链表的交点如果没有交点返回NULL
我的思路
用map做
代码 Runtime 67 ms Beats 15.53% Memory 21.2 MB Beats 5.5%
class Solution {
public:mapListNode *,boolmp;ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(headANULL||headBNULL)return NULL;ListNode *pheadA;ListNode *qheadB;while(p!NULLq!NULL){if(mp[p])return p;else mp[p]1;if(mp[q])return q;else mp[q]1;pp-next;qq-next;}while(p!NULL){if(mp[p])return p;else mp[p]1;pp-next;}while(q!NULL){if(mp[q])return q;else mp[q]1;qq-next;}return NULL;}
};
标答
设p是headAq是headB两个指针p和q一起向前走当有一个指针假设是p指向空的时候这个指针p来到q的起始位置当q指向空的时候q来到p的起始位置这时两者的起始到空的位置都是一样的了
一般来说位置交换只要双方来一次就可以完成了
代码 Runtime 32 ms Beats 93.83% Memory14.6 MB Beats 33.15%
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *pheadA;ListNode *qheadB;while(p!q){if(pNULL)pheadB;else pp-next;if(qNULL)qheadA;else qq-next;}return p;}
}; 169. Majority Element 题意给定一个数组返回众数
我的思路
用map
好吧看了标答才注意到这样只要大于n/2就可以return了
The majority element is the element that appears more than ⌊n / 2⌋ times.
代码 Runtime12 ms Beats 81.64% Memory19.8 MB Beats 6.3%
class Solution {
public:int majorityElement(vectorint nums) {ios::sync_with_stdio(false);cin.tie(0);pairint,intmaxx{0,0}; mapint,intmp;for(int i0;inums.size();i){mp[nums[i]];if(mp[nums[i]]maxx.second)maxx{nums[i],mp[nums[i]]};}return maxx.first;}
};
标答 摩尔投票法
因为要求的是绝对众数所以可以用摩尔投票法简而言之就是初始化can为第一个被提名人cnt为票数当有一个人被提名且不是can那么cnt--因为绝对众数所以绝对众数的票全部给其他人抵消了还会剩下多的
代码 Runtime 5 ms Beats 98.86% Memory19.9 MB Beats 6.3%
class Solution {
public:int majorityElement(vectorint nums) {ios::sync_with_stdio(0);int can0,cnt0;int nnums.size();for(int i0;in;i){if(cnt0) cannums[i];if(cannums[i])cnt;else cnt--;}return can;}
};
拓展摩尔投票
算法学习笔记(78): 摩尔投票 - 知乎 (zhihu.com) 189. Rotate Array
题意 Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.Could you do it in-place with O(1) extra space?
我的思路
重新开一个空间
代码 Runtime19 ms Beats 90.37% Memory26.4 MB Beats 5.92%
class Solution {
public:void rotate(vectorint nums, int k) {vectorint v;int nnums.size();kk%n;for(int i0;ik;i)v.push_back(nums[n-ki]);for(int i0;in-k;i)v.push_back(nums[i]);numsv;}
};
标答
只能说其实如此 eg 1 3 4 5 6 8 9k5 第一次reverse3 1 4 5 6 8 9 第二次reverse3 1 9 8 6 5 4 第三次reverse4 5 6 8 9 1 3 代码 Runtime18 ms Beats 92.46% Memory 25 MB Beats 65.31%
class Solution {
public:void rotate(vectorint nums, int k) {int nnums.size(); kk%n;reverse(nums.begin(),nums.end()-k);reverse(nums.begin()n-k,nums.end());reverse(nums.begin(),nums.end());}
};
