day06打卡

142. 环形链表 II

时间复杂度：O(N)，空间复杂度：O(1)

第一想法：快慢指针追逐问题，当相遇时，再让一个指针从head处开始找，直到和环内的节点相遇，这个位置就是环的入口。

证明：忘记了，这几天补上

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast = head, * slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;if(fast == slow){//记录相遇点ListNode* meet = fast;while(head != meet){head = head->next;meet = meet->next;}return meet;}}return NULL;}
};

242. 有效的字母异位词

时间复杂度：O(N)，空间复杂度：O(N)

第一想法：创建哈希表，遍历一遍字符串t，再遍历一遍s，看看哈希表中有没有不为0的映射值。

class Solution {
public:bool isAnagram(string s, string t) {int hash[26] = {0};for(auto& e : t){hash[e - 'a']++;}for(auto& e : s){hash[e - 'a']--;}for(auto& e : hash){if(e != 0)return false;}return true;}
};

349. 两个数组的交集

时间复杂度：O(N)，空间复杂度：O(N)

第一想法：创建哈希表，把nums1中的数，插入哈希表中，并全部置为1，再遍历nums2，从哈希表中查找相同的元素即可。

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_map<int, int> hash;vector<int> ret;for(auto& e : nums1){hash[e] = 1;}for(auto& e : nums2){if(hash[e] > 0){hash[e] = 0;ret.push_back(e);}}return ret;}
};

202. 快乐数

时间复杂度：O(logN)，空间复杂度：O(1)

第一想法：有点没有头绪，忘记之前怎么写的了

看了题解：模仿环形链表即可，快慢指针找出相交的点，看是不是变成1造成的循环即可。

class Solution {
public:int getVal(int n){int val = 0;while(n){int tmp = n % 10;val += tmp * tmp;n /= 10;}return val;}bool isHappy(int n) {int fast = getVal(n), slow = n;while(fast != slow){slow = getVal(slow);fast = getVal(getVal(fast));}return slow == 1;}
};

1. 两数之和

时间复杂度：O(N)，空间复杂度：O(N)

第一想法：暴力解，O(N^2)太慢了

看了题解：创建一个哈希表，遍历这个nums，用当前的数找出新的newTarget：target - nums[0]，从哈希表中找这个newTarget是否存在即可，最后将这个nums[i]插入哈希表。（向哈希表前查找）

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hash;for(int i = 0; i < nums.size(); i++){int newTarget = target - nums[i];if(hash.count(newTarget)) return {hash[newTarget], i};hash[nums[i]] = i;}return {};}
};