141. Linked List Cycle
题意：给你一个链表，判断链表有没有环
我的思路
两个指针，一个每次走两步，一个每次走一步，如果走两步的那个走到了NULL，那说明没有环，如果两个指针指向相等，说明有环
代码 Runtime7 ms Beats 91.63% Memory 8 MB Beats 67.57%
class Solution {
public:bool hasCycle(ListNode *head) {ListNode *p=head;ListNode *q=head;if(head==NULL||head->next==NULL)return 0;p=p->next;q=q->next->next;while(q!=NULL&&q!=p){p=p->next;if(q->next!=NULL)q=q->next->next;else q=q->next;}if(q==NULL)return 0;return 1;}
};标答 简洁
原理是一样的 就是代码更简洁了
class Solution {
public:bool hasCycle(ListNode *head) {ListNode* slow=head;ListNode* fast=head;while(fast && fast->next){slow=slow->next;fast=fast->next->next;if(fast==slow)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(head==NULL)return NULL;unordered_map<ListNode *,int>mp;ListNode *q=head;while(q->next!=NULL){if(mp[q])return q;mp[q]++;q=q->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对应的结点，这个时候要用map，map和list<int>::iterator
代码 Runtime 409 ms Beats 87.32% Memory 174 MB Beats 53.92%
class LRUCache {
public:int size;unordered_map<int, list<pair<int, int> >::iterator>mp;list< pair<int,int > > li;LRUCache(int capacity) {size=capacity;}int get(int key) {if(mp.count(key)>0){pair<int,int>tmp=*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) {pair<int,int> tmp={key,value};if(mp.count(key) > 0){//以前就有，把以前的删掉li.erase(mp[key]);}else if(li.size()==size){//以前没有，但是满了，把最前面的删掉auto lit=li.end();lit--;pair<int,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:queue<int> LRU;vector<int> usages = vector<int>(10001, 0);vector<int> kvp = vector<int>(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->next=NULL，使他彻底变成两条指针
递归第一条链表和第二条链表，直到head==NULL或者head->next==NULL 返回head指针；
最后把这两个head指针的链表合起来，合并也是用递归合并；如果l1的值小于l2的值，合并(l1->next，l2)【因为要从小到大排序，所以要留下小的值，让后面的值去比较
代码 Runtime 127 ms Beats 99.16% Memory 53.2 MB Beats 79.49%
class Solution {
public:ListNode* sortList(ListNode* head) {if(head==NULL||head->next==NULL)return head;ListNode* prev=NULL;ListNode* slow=head;ListNode* fast=head;while(fast!=NULL&&fast->next!=NULL){prev=slow;slow=slow->next;fast=fast->next->next;}prev->next=NULL;ListNode* l1=sortList(head);ListNode* l2=sortList(slow);return merge(l1,l2);}ListNode* merge(ListNode* l1,ListNode* l2){//合并递归if(l1==NULL)return l2;if(l2==NULL)return l1;if(l1->val<l2->val){l1->next=merge(l1->next,l2);return l1;}else {l2->next=merge(l1,l2->next);return l2;}}
};152. Maximum Product Subarray
题意：最大子段积
我的思路
动态规划？但是有负数欸；看提示，是前缀积？先来个O(n^2)
但是普通的前缀积不太行，因为有0；算了，现在个最暴力的O(n^2)----->TLE了
class Solution {
public:int maxProduct(vector<int>& nums) {ios::sync_with_stdio(false);cin.tie(0);int n=nums.size(),maxx=nums[0];if(n==1)return nums[0];for(int i=0;i<n;i++){int pro=1;for(int j=i;j<n;j++){pro=pro*nums[j];maxx=max(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(vector<int>& nums) {int n=nums.size();int maxx=nums[0],minn=nums[0],ans=nums[0];for(int i=1;i<n;i++){if(nums[0]<0)swap(maxx,minn);minn=min(minn*nums[i],nums[i]);//和nums[i]作比较maxx=max(maxx*nums[i],nums[i]);//表示的是以i为右端点的最大or最小值ans=max(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(vector<int>& nums) {int minn=5001;for(int i=0;i<nums.size();i++)minn=min(minn,nums[i]);return minn;}
};但是logn的话，那就二分，如果用归并的想法，都切成2个2个的，最后返回最小的
但是这没有用到rotate的部分，也不知道是不是logn
好像不是【因为a=2，b=2，f(n)=1，所以复杂度为n】
Runtime0 ms Beats 100% Memory 10.1 MB Beats 93.66%
class Solution {
public:int fi(vector<int>& nums,int l,int r){if(l>=r)return nums[l];int mid=l+(r-l)/2;return min(fi(nums,l,mid),fi(nums,mid+1,r));}int findMin(vector<int>& nums) {int n=nums.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(vector<int>& nums,int l,int r){if(l>=r)return nums[l];if(nums[l]<nums[r])return nums[l];int mid=l+(r-l)/2;return min(fi(nums,l,mid),fi(nums,mid+1,r));}int findMin(vector<int>& nums) {int n=nums.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:vector<long long>v;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 i=0;i<v.size();i++)minn=min(minn,v[i]);return minn;}
};
标答 单调栈
创建两个栈，一个是正常的栈，一个是专门存放最小值的栈
为什么不会存在pop正常栈的值（第二小的值），再pop正常栈的值（第一小的值），再getmin为什么不会出现第二小的值？
因为存放最小值的栈是单调栈，只会存放当前数的右边比它更小的值
代码 Runtime17 ms Beats 85.63% Memory16.1 MB Beats 92.4%
class MinStack {
public:stack<int> st;stack<int> 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:map<ListNode *,bool>mp;ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(headA==NULL||headB==NULL)return NULL;ListNode *p=headA;ListNode *q=headB;while(p!=NULL&&q!=NULL){if(mp[p])return p;else mp[p]=1;if(mp[q])return q;else mp[q]=1;p=p->next;q=q->next;}while(p!=NULL){if(mp[p])return p;else mp[p]=1;p=p->next;}while(q!=NULL){if(mp[q])return q;else mp[q]=1;q=q->next;}return NULL;}
};标答
设p是headA，q是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 *p=headA;ListNode *q=headB;while(p!=q){if(p==NULL)p=headB;else p=p->next;if(q==NULL)q=headA;else q=q->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(vector<int>& nums) {ios::sync_with_stdio(false);cin.tie(0);pair<int,int>maxx={0,0}; map<int,int>mp;for(int i=0;i<nums.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(vector<int>& nums) {ios::sync_with_stdio(0);int can=0,cnt=0;int n=nums.size();for(int i=0;i<n;i++){if(cnt==0) can=nums[i];if(can==nums[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(vector<int>& nums, int k) {vector<int> v;int n=nums.size();k=k%n;for(int i=0;i<k;i++)v.push_back(nums[n-k+i]);for(int i=0;i<n-k;i++)v.push_back(nums[i]);nums=v;}
};标答
只能说其实如此
eg 1 3 4 5 6 8 9，k=5
第一次reverse：3 1 4 5 6 8 9
第二次reverse：3 1 9 8 6 5 4
第三次reverse：4 5 6 8 9 1 3
代码 Runtime18 ms Beats 92.46% Memory 25 MB Beats 65.31%
class Solution {
public:void rotate(vector<int>& nums, int k) {int n=nums.size(); k=k%n;reverse(nums.begin(),nums.end()-k);reverse(nums.begin()+n-k,nums.end());reverse(nums.begin(),nums.end());}
};
