Personal Blog
该板块为个人写过的 Timus 题目
该板块都为原创代码，搬运请注明出处，谢谢。
Github上别人写的代码您也可以作为 参考1 参考2。
共性问题说明：
cin读取速度慢，但所有题目时间都考虑到cin时间，如果超时，建议换算法，实在不行可以加入：std::ios::sync_with_stdio(false);std::cin.tie(nullptr); 加快cin速度或者改成scanf或scanf_s（最快）。当scanf或scanf_s读入string后不要轻易改变该string赋值否则可能会有很大bug，建议用scanf输入时储存为char。并且建议不要混用cin和scanf。如果你追求极致时间，请用scanf和printf输入和输出。
如果想联系我也可以加QQ：2114496089
来自杭州电子科技大学自动化专业的大二理工男一枚。
一只整个暑假都在学校学习的学生。
准备更新资料：无
b站同性交友帐号搜索：承包户
steam好友代码：241282993
喜欢的游戏：明日方舟、csgo、彩虹六号……
如果想联系我也可以加QQ：2114496089，请备注来意。
服务器主要功能为个人博客，于2021.7.1开始正式运营，为wordpress模板。
该博客会不定期更新个人学习到的知识进行分享，你也可以通过我的博客了解我。
请不要在此网站泄露任何个人信息，评论姓名等个人信息请匿名填写，个人不能保证此网站不被攻击，如果出问题请自行负责！请爱护服务器，大佬请不要无故攻击谢谢！请不要对服务器运行爬虫或各种压力测试软件，谢谢，服务器设置每秒访问上限，可能你会被封ip。服务器运行速度及网速可能稍慢，望见谅（有钱了买个好的）。
迭代。eg: 65 / 8 = (65 – 8) / 8 + 1 = (57 – 16) / 8 + 2 + 1 = (41 – 32) / 8 + 4 + 2 + 1 = 9 / 8 + 7 = (9 – 8) / 8 + 1 + 7 = 1 / 8 + 8 = 8
因为有 INT_MAX 和 INT_MIN 的干扰，还得排除一下特殊情况
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
class Solution { public: int divide(int dividend, int divisor) { if (divisor == INT_MIN) { if (dividend == INT_MIN)return 1; else return 0; } int flag = 1, fix = 0; if (dividend == INT_MIN) { if (divisor == 1)return INT_MIN; else if (divisor == -1)return INT_MAX; dividend = INT_MAX; divisor = -divisor; fix = 1; } if (dividend > 0 && divisor < 0) { divisor = -divisor; flag = -1; } else if (dividend < 0 && divisor > 0) { dividend = -dividend; flag = -1; } else if (dividend < 0 && divisor < 0) { dividend = -dividend; divisor = -divisor; } if (divisor > dividend)return 0; int result = 1 + iteration(dividend - divisor + fix, 1, divisor, divisor); return result * flag; } int iteration(int divide, int result, int now, int base) { if (divide < base) return 0; else if (now > divide) return iteration(divide, 1, base, base); else if (now <= divide) return result + iteration(divide - now, result << 1, now << 1, base); return 0; } }; |
无算法遍历。高级算法：Knuth-Morris-Pratt 算法，前后缀法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { public: int strStr(string haystack, string needle) { int n1 = haystack.size(), now = 0, n2 = needle.size(); while (1) { if (now + n2 > n1) return -1; int i = 0, begin = now; for (; i < n2; i++) { if (needle[i] == haystack[now++]) continue; else break; } if (i == n2)return now - i; now = begin + 1; } return -1; } }; |
更简单，刚开始我以为要把整个vector都变掉，结果只需要变前几个，返回长度就行，运行时间差的就很多。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public: int removeDuplicates(vector<int>& nums) { for(auto ptr = nums.begin() + 1; ptr != nums.end();){ if(*ptr == *(ptr - 1)) { ptr = nums.erase(ptr); continue; } ptr++; } return nums.size(); } }; |
|
1 2 3 4 5 6 7 8 9 10 11 |
class Solution { public: int removeDuplicates(vector<int>& nums) { int now = 0; for(auto ptr = nums.begin() + 1; ptr != nums.end(); ptr++){ if(*ptr == *(ptr - 1)) continue; else nums[++now] = *ptr; } return now + 1; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 |
class Solution { public: int removeElement(vector<int>& nums, int val) { int now = 0; for(auto ptr = nums.begin(); ptr != nums.end(); ptr++){ if(*ptr == val) continue; else nums[now++] = *ptr; } return now; } }; |
迭代
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution: def generateParenthesis(self, n: int) -> list[str]: self.result = [] self.interation("", n, n) return self.result def interation(self, word, left, right): if left == 0 and right == 0: self.result.append(word) return 0 if left == right: self.interation(word + '(', left - 1, right) else: if left != 0: self.interation(word + '(', left - 1, right) if right != 0: self.interation(word + ')', left, right - 1) |
指针交换操作
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* temp; if(list1 == nullptr && list2 == nullptr)return nullptr; else if(list1 == nullptr) return list2; else if(list2 == nullptr) return list1; if(list1->val > list2->val){ temp = list1; list1 = list2; list2 = temp; } ListNode* pre; ListNode* result = list1; while(1){ if(list1->val <= list2->val) { pre = list1; list1 = list1->next; } else if(list1->val > list2->val){ temp = list2->next; pre->next = list2; pre = list2; list2->next = list1; list2 = temp; } if(list1 == nullptr){ pre->next = list2; return result; } else if(list2 == nullptr){ return result; } } return result; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode* result = nullptr; if(lists.empty()) return result; else if(lists.size() == 1)return lists[0]; result = mergeTwoLists(lists[0], lists[1]); for(int i = 2;i < lists.size();i++){ result = mergeTwoLists(result, lists[i]); } return result; } ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* temp; if(list1 == nullptr && list2 == nullptr)return nullptr; else if(list1 == nullptr) return list2; else if(list2 == nullptr) return list1; if(list1->val > list2->val){ temp = list1; list1 = list2; list2 = temp; } ListNode* pre; ListNode* result = list1; while(1){ if(list1->val <= list2->val) { pre = list1; list1 = list1->next; } else if(list1->val > list2->val){ temp = list2->next; pre->next = list2; pre = list2; list2->next = list1; list2 = temp; } if(list1 == nullptr){ pre->next = list2; return result; } else if(list2 == nullptr){ return result; } } return result; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode* result = new ListNode(0, head); if(head == nullptr) return nullptr; ListNode* pre = result; ListNode* temp; while(1){ if(head == nullptr || head->next == nullptr) return result->next; pre->next = head->next; temp = head->next->next; head->next->next = head; head->next = temp; pre = head; head = temp; } return result->next; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { ListNode* result = new ListNode(0, head); if (head == nullptr) return nullptr; ListNode* pre = result; ListNode* last; ListNode* temp; while (1) { temp = head; last = head; for (int i = 1; i < k + 1; i++) { if (temp == nullptr) return result->next; temp = temp->next; } ListNode* now_pre = pre; for (int i = 0; i < k - 1; i++) { head = now_pre->next; pre = now_pre; for (int j = 0; j < k - i - 1; j++) { pre->next = head->next; pre = pre->next; temp = head->next->next; head->next->next = head; head->next = temp; } } pre = last; head = last->next; } return result->next; } }; |
浙ICP备2021019730-1 
浙公网安备 33010902002953号
Copyright © 2022 PanCake