/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:int self_distance(ListNode *self){int distance = 1;ListNode *temp = self->next;while(temp != self){distance++;temp = temp->next;}if(temp == self){return distance;}return -1; // No loop}bool hasCycle(ListNode *head) { // O(1) 内存ListNode *temp = head;while(temp){if(self_distance(temp) != -1){return true;}temp = temp->next;}return false;}};
思路是把每一个节点检验一下有没有首尾都是自己的环，但是time exceed，不确定有bug还是算法太差

dd

class Solution {public:bool hasCycle(ListNode *head) { // O(1) 内存if(!head){return false;}ListNode *tempA = head, *tempB = head->next;while(tempA && tempB){while(tempB->next){if(tempA != tempB){tempB = tempB->next;}else{return true;}}tempA = tempA->next;tempB = tempA->next->next;}return false;}};
换了点写法，一样的算法，仍然time exceed，说明算法问题

看了答案，哈希表肯定最快啦，但不满足进阶要求的O(1)空间。
我的解法时间复杂度是O(N^2)，算是最暴力的方法，不是很行。
题解进阶方法是“快慢指针”。
慢指针一下移一位，快指针以下移两位。假如没有环，快指针将先到nullptr。假设有环，会在O(N)的时间之后追及。

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:bool hasCycle(ListNode *head) { // O(1) 内存ListNode *slow = head;if(!head){return false;}ListNode *fast = head->next;while(fast != slow){if(!fast){return false;}else{fast = fast->next;if(!fast){return false;}fast = fast->next;slow = slow->next;}}return true;}};
按照正确算法写的正确答案

数据结构75 颜色分类
一共就三种，可以手动桶来统计数据
class Solution {public:void sortColors(vector<int>& nums) {int n = nums.size();int numzero = 0, numone = 0, numtwo = 0;for(int i = 0; i < n; i++){if(nums[i] == 0){numzero++;}else if(nums[i] == 1){numone++;}else{numtwo++;}}for(int i = 0; i < numzero; i++){nums[i] = 0;}for(int i = numzero; i < numzero + numone; i++){nums[i] = 1;}for(int i = numzero + numone; i < n; i++){nums[i] = 2;}}};

数据结构119杨辉三角
class Solution {public:vector<int> getRow(int rowIndex) { /* vector<int> ans; for(int i = 0; i < rowIndex + 1; i++){ ans.push_back(1); int temp; for(int j = 1; j < i; j++){ temp = ans[j - 1]; ans[j] = ans[j] + temp; } } return ans; */ // 空间可以再省一倍，但是我没脑子思考了vector<int> buffer;vector<int> ans;for(int i = 0; i < rowIndex + 1; i++){ans.push_back(1);for(int j = 1; j < i; j++){ans[j] = buffer[j - 1] + buffer[j];}buffer = ans;}return ans;}};