刷题记录 · C++技术

# 指针三剑客之一：链表 ## 13.1 数据结构介绍（单）链表是有节点和指针构成的数据结构，每个节点存在一个值，和一个指向下一个节点的指针，因此很多链表问题可以用递归来处理。不同于数组，链表并不能直接获取任意节点的值，必须要通过指针找到该节点后才能获取其值。同理，在未遍历到链表结尾时，我们也无法知道链表的长度，除非依赖其他数据结构来存储长度。LeetCode默认的链表表示方法如下 ~~~ Struct ListNode { int val; ListNode* next; ListNOde(int x) : val(x), next(nullptr) {} } ~~~ 由于在进行链表操作时，尤其是删除节点时，经常会因为对当前节点进行操作而导致内存或指针出现问题。有两个小技巧可以解决这个问题：一是尽量处理当前节点的下一个节点而非当前节点本身，二是建立一个虚拟节点（dummy node）,使其指向当前链表的头结点，这样即使原链表所有节点全部被删除，也会有一个dummy存在，返回dummy->next即可。一般来说，算法题不需要删除内存。在刷LeetCode的时候，如果想要删除一个节点，可以直接进行指针操作而无需回收内存。实际做软件工程时，必须要显式回收或利用智能指针。 ## 13.2 链表的基本操作 #### [206\. 反转链表](https://leetcode-cn.com/problems/reverse-linked-list/) 题目描述翻转一个链表递归解法： ~~~ ListNode* reverseList(ListNode* head, ListNode* prev = nullptr) { if (!head) return prev; ListNode* next = head->next; head->next = prev; return reverseList(next, head); } ~~~ 非递归解法： ~~~ ListNode* reverseList(ListNode* head) { ListNode* reverse = nullptr; while (head) { ListNode* next = head->next; head->next = reverse; reverse = head; head = next; } return reverse; } ~~~ #### [21\. 合并两个有序链表](https://leetcode-cn.com/problems/merge-two-sorted-lists/) 题目描述给定两个递增的链表，试将其合并成一个增序的链表 ~~~ ListNode* mergeTwoList(ListNode* l1, ListNode* l2) { if (!l1) return l2; if (!l2) return l1; ListNode dummy(0); ListNode* p = &dummy; while (l1 && l2) { if (l1->val < l2->val) { p->next = l1; l1 = l1->next; } else { p->next = l2; l2 = l2->next; } p = p->next; } p->next = l1 ? l1 : l2; return dummy.next; } ~~~ #### [24\. 两两交换链表中的节点](https://leetcode-cn.com/problems/swap-nodes-in-pairs/) 题目描述给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 ~~~ ListNode* swapPairs(ListNode* head) { ListNode dummy(0); dummy.next = head; ListNode* p = &dummy; while (p->next && p->next->next) { ListNode* tmp = p->next->next; p->next->next = tmp->next; tmp->next = p->next; p->next = tmp; p = tmp->next; } return dummy.next; } ~~~ ## 13.3 其他链表技巧 #### [160\. 相交链表](https://leetcode-cn.com/problems/intersection-of-two-linked-lists/) 给定两个链表，判断他们是否相较于一点，并求这个相交节点 ~~~ l1: 2->3->6->7 | v 9->10->23 ^ | l2: 4->5->8 ~~~ 法1：长的链表先走 ~~~ int listLen(ListNode* head) { int len = 0; while (head) { len++; head = head->next; } return len; } ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { int lenA = listLen(headA); int lenB = listLen(headB); if (lenA < lenB) { ListNode* tmp = headA; headA = headB; headB = tmp; int len = lenA; lenA = lenB; lenB = len; } for (int i = 0; i < lenA - lenB; i++) { if (!headA) return nullptr; headA = headA->next; } while (headA && headB) { if (headA == headB) return headA; headA = headA->next; headB = headB->next; } return nullptr; } ~~~ 法2：使用两个指针，分别指向两个链表的头结点，并以相同的速度前进，若到达链表结尾，则移动到另一条链表的头结点继续前进。按照这种前进方式，两个节点会同时到达相交节点。若无节点，也刚好走完两条链表的距离，两节点都为NULL，不会出现死循环。 ~~~ ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { ListNode* l1 = headA; ListNode* l2 = headB; while (l1 != l2) { l1 = l1 ? l1->next : headB; l2 = l2 ? l2->next : headA; } return l1; } ~~~ #### [234\. 回文链表](https://leetcode-cn.com/problems/palindrome-linked-list/) 题目描述以O(1)的空间复杂度，判断链表是否回文 1->2->3->2->1 思路：先使用快慢指针找到链表中点，再把链表切成两半；然后把后半段翻转；最后比较两半是否相等。 ~~~ bool isPalindrome(ListNode* head) { if (!head || !head->next) return true; ListNode* slow = head; ListNode* fast = head; while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; } slow->next = reverseList(slow->next); slow = slow->next; while (slow) { if (head->val != slow->val) return false; head = head->next; slow = slow->next; } return true; } ListNode* reverseList(ListNode* head) { ListNode* reverse = nullptr; while (head) { ListNode* next = head->next; head->next = reverse; reverse = head; head = next; } return reverse; } ~~~ # 指针三剑客之二：树 ## 14.1 数据结构介绍作为（单）链表的升级，我们通常接触的树都是二叉树（binary tree），即每个节点最多有两个子节点；且除非题目说明，默认树中不存在环形结构。LeetCode默认的树的表示方法如下： ~~~ struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} } ~~~ 可以看出，其与链表的主要差别就是多了一个子节点的指针。 ## 14.2 树的递归 #### [104\. 二叉树的最大深度](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/) 题目描述求一个二叉树的最大深度 ~~~ int maxDepth(TreeNode* root) { if (!root) return 0; int left = maxDepth(root->left); int right = maxDepth(root->right); return max(left, right) + 1; } ~~~ #### [110\. 平衡二叉树](https://leetcode-cn.com/problems/balanced-binary-tree/) 题目描述判断一个二叉树是否平衡 ~~~ bool isBalanced(TreeNode* root) { return helper(root) != -1; } int helper(TreeNode* root) { if (!root) return 0; int left = helper(root->left); int right = helper(root->right); if (left == -1 || right == -1 || abs(left - right) > 1) { return -1; } return max(left, right) + 1; } ~~~ #### [543\. 二叉树的直径](https://leetcode-cn.com/problems/diameter-of-binary-tree/) 题目描述求一个二叉树的最长直径。 ~~~ int diameterOfBinaryTree(TreeNode* root) { int result = 0; helper(root, result); return result; } int helper(TreeNode* root, int &result) { if (!root) return 0; int left = helper(root->left, result); int right = helper(root->right, result); result = max(result, left + right); return max(left, right) + 1; } ~~~ # 令人头大的字符串 ## 引言字符串可以看成是字符组成的数组。由于字符串时程序了经常需要处理的数据类型，因此很多针对字符串处理的题目，以下是一些常见的类型。 ## 字符串比较 #### [242\. 有效的字母异位词](https://leetcode-cn.com/problems/valid-anagram/) 题目描述判断两个字符串包含的字符是否完全相同 ~~~ bool isAnagram(string s, string t) { if (s.size() != t.size()) return false; vector<int> count(26, 0); for (int i = 0; i < s.size(); i++) { count[s[i] - 'a']++; count[t[i] - 'a']--; } for (int i = 0; i < 26; i++) { if (count[i]) { return false; } } return true; } ~~~ #### [205\. 同构字符串](https://leetcode-cn.com/problems/isomorphic-strings/) 题目描述判断两个字符串是否同构。同构的定义是，可以通过把一个字符串的某些相同的字符转换成另一些相同的字符，使得两个字符串相同，且两种不同的字符不能够被转换成同一种字符。题解我们可以将问题转化一下：记录两个字符串每个位置的字符第一次出现的位置，如果两个字符串中相同位置的字符与它们第一次出现的位置一样，那么这两个字符串同构。举例来说，对于“paper”和“title”，假设我们现在遍历到第三个字符“p”和“t”，发现它们第一次出现的位置都在第一个字符，则说明目前位置满足同构。 ~~~ bool isIsomorphic(string s, string t) { if (s.size() != t.size()) return false; vector<int> s_first_index(256, -1); vector<int> t_first_index(256, -1); for (int i = 0; i < s.size(); i++) { if (s_first_index[s[i]] != t_first_index[t[i]]) { return false; } s_first_index[s[i]] = i; t_first_index[t[i]] = i; } return true; } ~~~ #### [647\. 回文子串](https://leetcode-cn.com/problems/palindromic-substrings/) 题目描述给定一个字符串，求其有多少个回文子字符串，回文的定义是左右对称。 ~~~ int countSubstrings(string s) { int count = 0; for (int i = 0; i < s.size(); i++) { count += helper(s, i, i); // 奇数长度 count += helper(s, i, i + 1); // 偶数长度 } return count; } int helper(string s, int l, int r) { int count = 0; while (l >= 0 && r < s.size() && s[l] == s[r]) { count++; l--; r++; } return count; } ~~~ 题目描述给定一个0-1字符串，求有多少非空子字符串的0和1数量相同 #### [28\. 实现 strStr()](https://leetcode-cn.com/problems/implement-strstr/) 字符串匹配 ~~~ int strStr(string haystack, string needle) { if (needle.size() == 0) return 0; int Base = 1000000; int power = 1; int targetCode = 0; int len = needle.size(); for (auto x : needle) { targetCode = (targetCode * 31 + x) % Base; power = (power * 31) % Base; } int code = 0; for (int i = 0; i < haystack.size(); i++) { code = (code * 31 + haystack[i]) % Base; if (i < len - 1) { continue; } if (i >= len) { code = code - haystack[i - len] * power; while (code < 0) { code += Base; } } if (code == targetCode) { if (needle.compare(haystack.substr(i - len + 1, len)) == 0) { return i - len + 1; } } } return -1; } ~~~ 字符串理解 LeetCode最后一个用例超出时间限制 ```cpp int calculate(string s) { return parseExpression(s, 0); } int parseExpression(string s, int i) { char op = '+'; long left = 0; long right = 0; while (i < s.size()) { if (s[i] != ' ') { if (isdigit(s[i])) { int n = parseNumber(s, i); switch (op) { case '+': left += right; right = n; break; case '-': left += right, right = -n; break; case '*': right *= n; break; case '/': right /= n; break; } } op = s[i]; } i++; } return left + right; } long parseNumber(string s, int i) { long result = 0; while (i < s.size() && isdigit(s[i])) { result = result * 10 + s[i] - '0'; i++; } return result; } ```