classSolution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2){ int hash1[1000] = {0}; int hash2[1000] = {0};
// 统计两个数组nums1和nums2中每个数值出现的频次 for (int i = 0; i < nums1.size(); i ++ ) hash1[nums1[i]] ++ ; for (int i = 0; i < nums2.size(); i ++ ) hash2[nums2[i]] ++ ;
vector<int> res;
// 若一个数同时在nums1和nums2数组中出现的频次>=1，则该数是两数组的重叠，放入结果数组res中 for (int i = 0; i < 1000; i ++ ) { if (hash1[i] && hash2[i]) res.push_back(i); } return res; } };
// nums1中出现过的数，则将其在哈希数组中的值标记为1 for (int num: nums1) hash[num] = 1;
// 若nums2中的数在nums1中出现过，则将其插入res中 for (int num: nums2) if (hash[num] == 1) res.insert(num); // unordered_set->vector returnvector<int>(res.begin(), res.end()); } };
202. 快乐数
题目中说：Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.本题本来是一个数学问题，可以得到严格的数学证明，但我们不需要懂数学，可以用编程的思维去解决它。
classSolution { public: ListNode* removeElements(ListNode* head, int val){ // 删除头节点 while (head != NULL && head -> val == val) { ListNode* tmp = head; head = head -> next; delete tmp; }
// 删除非头节点 ListNode* cur = head; // cur存储要删去的节点的前一个节点 // 要删的节点cur->next不可为空, cur != NULL是考虑空链表的情况 while (cur != NULL && cur -> next != NULL) { if (cur -> next -> val == val) { ListNode* tmp = cur -> next; cur -> next = cur -> next -> next; delete tmp; } else cur = cur -> next; // 后移一位 } return head; } };
classSolution { public: ListNode* removeElements(ListNode* head, int val){ // 创建虚拟头节点 ListNode* dummyHead = newListNode(0); dummyHead -> next = head; // 上面的两行代码：创建虚拟头节点可以简写为： // ListNode* dummyHead = new ListNode(0, head); // 或者ListNode* dummyHead = new ListNode(); // dummyHead -> next = head;
// 统一方法删去值为val的节点 // 从虚拟头节点开始遍历, cur为目标节点的前一个节点 // 此时因为加入了虚拟头节点，因此链表不可能为空，因此不再需要考虑链表为空的判断条件：cur != NULL ListNode* cur = dummyHead; while (cur -> next != NULL) { if (cur -> next -> val == val) { ListNode* tmp = cur -> next; cur -> next = cur -> next -> next; delete tmp; } else cur = cur -> next; }
return cur -> val; } voidaddAtHead(int val){ LinkedList* head = newLinkedList(val); head -> next = _dummyHead -> next; _dummyHead -> next = head; _size ++ ; } voidaddAtTail(int val){ LinkedList* tail = newLinkedList(val);
LinkedList* cur = _dummyHead; // while循环中的条件不能是_size -- ，不然会破坏链表长度的准确性 while(cur -> next != NULL) cur = cur -> next; cur -> next = tail; _size ++ ; } voidaddAtIndex(int index, int val){ if (index > _size || index < 0) return;
LinkedList* cur = _dummyHead; LinkedList* node = newLinkedList(val);
while(index -- ) cur = cur -> next;
node -> next = cur -> next; cur -> next = node; _size ++ ; } voiddeleteAtIndex(int index){ if (index < 0 || index >= _size) return; LinkedList* cur = _dummyHead; while (index -- ) cur = cur -> next; LinkedList* tmp = cur -> next; cur -> next = cur -> next -> next; delete tmp; _size -- ; }
classSolution { public: intminSubArrayLen(int target, vector<int>& nums){ int len = INT32_MAX; int sub = 0; for (int i = 0; i < nums.size(); i ++ ) { int s = 0; for (int j = i; j < nums.size(); j ++ ) { s += nums[j]; if (s >= target) { sub = j - i + 1; len = len < sub ? len: sub; break; } } }
classSolution { public: intminSubArrayLen(int target, vector<int>& nums){ int len = INT32_MAX; // result int i = 0; // i是滑动窗口的起始位置 int sub = 0; // 窗口长度 int sum = 0; // 窗口之和
// j是滑动窗口的终止位置 for (int j = 0; j < nums.size(); j ++ ) { sum += nums[j]; // 将新的终止位置放到窗口的和中去
// 更新滑动窗口 while(sum >= target) { sub = j - i + 1; len = len < sub ? len: sub; sum -= nums[i]; i ++ ; } } return len == INT32_MAX ? 0: len; } };
