难度3

回文链表 原题链接：https://leetcode.cn/problems/aMhZSa/ 给定一个链表的 头节点 head ，请判断其是否为回文链表。 如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。 1.试解栈123456789101112131415161718192021class Solution {public: bool isPalindrome(ListNode* head) { if (head->next == nullptr) return true; //1.stk push stack<ListNode*> stk; ListNode* p = head; while (p) { stk.push(p); p = p->next; } //2.traverse linklist p = head; while (p) { if (stk.top()->val != p->val) return false; stk.pop(); p = p->next; } return true; }}; 2.数组+双指针1 3.递归1 4.快慢指针1

两个链表的第一个重合节点 原题链接：https://leetcode.cn/problems/3u1WK4/ 给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。 图示两个链表在节点 c1 开始相交： 题目数据 保证 整个链式结构中不存在环。 函数返回结果后，链表必须 保持其原始结构 。 1.哈希表主要思路： 遍历listA将其中的结点全部标记存入unset中（哈希表） 遍历listB直到其中出现相同的next域的值 直接返回其值即为结果 若遍历listB都完都没有出现符合要求的结果则返回nullptr 1234567891011121314151617181920//注：将unordered_set放到成员方法内部可以提高时间效率class Solution {public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_set<ListNode*> unset; //1.initialize unset ListNode* tmp = headA; while (tmp) { unset.insert(tmp); tmp = tmp->next; } //2.find the first node tmp = headB; while (tmp) { if (unset.count(tmp)) return tmp; tmp = tmp->next; } return nullptr; }}; 时间：48ms 内存：16.24mb 时间复杂度：$O(N)$ 空间复杂度：$O(N)$ 2.双指针主要思路： 首先判断链表是否为空，如果其中有一个链表为空则两个链表一定不相交返回nullptr 当链表都不为空时 创建两个指 ...

链表中环的入口节点 原题链接：https://leetcode.cn/problems/c32eOV/ 给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 注意 pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。 说明：不允许修改给定的链表。 1.哈希表思路： 利用哈希表建立一个标记数组 用于标记已经出现的next指针域 while循环遍历链表 直到出现重复的next指针域 表示链表环开始出现 返回此时的链表结点指针 即为环入口结点 unordered_map1234567891011121314class Solution {public: unordered_map<ListNode*, int> mark; ListNode *detectCycle(ListNode *head) { if (head == nullptr) return nullptr; ListNode* p = head; while (p) { if (mark[p]) return p; mark[p] = 1; p = p->next; } return nullptr; }}; 时间：12ms 内存：9.8mb unordered_set12345678910111213public: unordered_set<ListNode*> mark; ListNode *detectCycle(ListNode *head) { if (head == nullptr) return nullptr; ListNode* p = head; while (p) { if (mark. ...

数组中和为0的三个数 原题链接：https://leetcode.cn/problems/1fGaJU/ 1.暴力法暴力法虽然测试用例能正确输出，但是程序时间复杂度太高直接超时， 123456789101112131415161718192021222324252627class Solution {public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ans; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); ++i) { if (i > 0 && nums[i] == nums[i - 1]) continue; //使用双指针解决剩余两个数字 for (int j = i + 1; j < nums.size(); ++j) { for (int k = j + 1; k < nums.size(); ++k) { if (nums[i] + nums[j] + nums[k] == 0) { //判定符合要求的答案是否重复 //ans.push_back({nums[i], nums[j], nums[k]}); if (ans.size() == 0) ans.push_back({nums[i], nums[j], nums[k]}); else { int flag = 1; for (in ...

前n个数字二进制中1的个数 原题链接：https://leetcode.cn/problems/w3tCBm/ 给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。 1.一般思路12345678910111213141516class Solution {public: vector<int> countBits(int n) { vector<int> ans; for (int i = 0; i <= n; ++i) { int x = i; int count = 0; while (x) { if (x % 2 == 1) count++; x /= 2; } ans.push_back(count); } return ans; }}; 2.位运算12345678910111213141516class Solution {public: vector<int> countBits(int n) { vector<int> ans; for (int i = 0; i <= n; ++i) { int count = 0; int x = i; while (x != 0) { count++; x = x & (x - 1); } ans.push_back(count); } return ans; }}; 3.动态规划对于所有的数字，只有奇数和偶数两种： 奇数：二进制表示中，奇数一定比前面那个偶数多一 ...

二进制加法 原题链接：https://leetcode.cn/problems/JFETK5/ 位运算是将数字用二进制形式表示之后，对每位上0或1的运算，二进制及其位运算是现代计算机科学的基石， 位运算种类：非~、与&、或|、异或^、左移<<、右移>> 按位与&：对应二进制位上，a与b必须同时为真 按位或|：对应二进制进位上，a与b有一边为真即可 异或运算^：对应二进制位上，相同则为0，不同则为1（逆运算首先满足交换律） 关于异或运算的补充： 异或运算是逆运算：由 a ^ b = c 可得 c ^ a = b； c ^ b = a； 相同的数异或运算为0：n ^ n = 0 ; 任何数与0异或运算值不变：0 ^ n = n； 问：在文件中有一堆整数，每一次数都出现了两次，其中有一个值只出现了一次，如何快速找到只出现一次的这个数的值？ 答：利用异或运算解决，将所有整数互相异或，最后得到的值即为只出现一次的值 左移 m << n ：二进制数整 m 左移n 位 右移 m >> n：二进制数整 m 右移 n 位 运算 按位与& 0 & 0 = 0 1 & 0 = 0 0 & 1 = 0 1 & 1 = 1 按位或| 0 | 0 = 0 1 | 0 = 1 0 | 1 = 1 1 | 1 = 1 按位异或^ 0 ^ 0 = 0 1 ^ 0 = 1 0 ^ 1 = 1 1 ^ 1 = 0 1.数制转换主要思路：将输入的二进制转换为10进制，使用10进制进行运算，将得到的结果转化回二进制即可。 存在问题：outside the range of representable values of type ‘int’，将int类型改为long long 无法存储， 1234567891011121314151617181920212223242526272829303132333435class Solution {public: string _ ...

移除指定元素 原题链接：https://leetcode.cn/problems/remove-element/ 1.巧妙的移动元素1234567891011121314class Solution {public: int removeElement(vector<int>& nums, int val) { int count = 0; for (int i = 0; i < nums.size(); ++i) { if (nums[i] == val) { count++; } else { nums[i - count] = nums[i]; } } return nums.size() - count; }}; 2.重复项删除类似12345678910111213class Solution {public: int removeElement(vector<int>& nums, int val) { int black = 0; for (int red = 0; red < nums.size(); ++red) { if (nums[red] != val) { nums[black] = nums[red]; black++; } } return black; }};

删除有序数组中的重复项 原题链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/ 不要使用额外的空间，你必须在 原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。 1.双指针1234567891011121314class Solution {public: int removeDuplicates(vector<int>& nums) { if (nums.size() == 0) return 0; int black = 0; for (int red = 1; red < nums.size(); ++red) { if (nums[red] != nums[black]) { black++; nums[black] = nums[red]; } } return black + 1; }};

最长公共前缀 原题链接：https://leetcode.cn/problems/longest-common-prefix/ 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串。 1.substr解法1：暴力循环 + substr字符串截取 runtime beats 73.15 % of cpp submissions memory usage beats 27.86 % of cpp submissions (9 MB) 12345678910111213class Solution {public: string longestCommonPrefix(vector<string>& strs) { if (strs.size() == 0) return ""; string ans = strs[0]; for (int i = 1; i < strs.size(); ++i) { int index = 0; for (;index < max(strs[i].length(), ans.length()) && ans[index] == strs[i][index]; ++index); ans = strs[i].substr(0, index); } return ans; }}; 2.+=操作解法2：暴力循环 + 字符串的+=操作（取消了对substr的引用，性能更优） runtime beats 73.15 % of cpp submissions memory usage beats 92.63 % of cpp submissions (8.8 MB) 1234567891011121314151617181920class Solution {public: string longestCommonPrefix(vector<string>& strs) { ...

罗马数字转整数 原题链接：https://leetcode.cn/problems/roman-to-integer/ 罗马数字包含以下七种字符：I， V， X， L，C，D 和 M。 12345678字符 数值I 1V 5X 10L 50C 100D 500M 1000 例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII 而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值。同样地数字9表示为 IX。 这个特殊的规则只适用于以下六种情况： I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。 X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。 给定一个罗马数字，将其转换成整数。 1234567891011121314151617181920212223242526272829303132333435363738394041424344class Solution {public: int romanToInt(string s) { int ans = 0; for (int i = 0; i < s.length(); ++i) { if (s[i] == 'I') { //特殊判断 if (s[i + 1] == 'V' || s[i + 1] == 'X') { ans += (s[i + 1] == 'V' ...