Posts

LeetCode 链表（2） 题目 4. 双指针 19 删除链表的倒数第N个节点 删除链表的倒数第 n 个节点。 在链表中不易直接取到倒数第 n 个位置，所以用两个指针 prev 和 tail，tail 先往前走 n 步，然后两个指针一起往前走直到 tail 没有后继指针，此时 prev 的后继指针就是倒数第 n 个位置，删除其即可。注意如果要删除的指针是头指针的话要单独处理。 class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *prev = head, *tail = head; for (int i = 0; i < n; ++i) tail = tail->next; if (!tail) { head = head->next; delete prev; return head; } while (tail->next) tail = tail->next, prev = prev->next; ListNode *next = prev->next; prev->next = next->next; delete next; return head; } }; 61 旋转链表 给一个链表，将其每个节点向右移动 k 个位置。 ...

LeetCode 链表（1） 题目 1. 常规题 2 两数相加 给两个链表分别代表两个正数的逆序表示，计算两个链表之和。 依次按位进行相加。 class Solution { public: ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) { int acc = 0, val = 0; auto head = l1, tail = l1; while (l1 && l2) { val = l1->val + l2->val + acc; acc = val / 10; l1->val = val % 10; if (!l1->next) l1->next = l2->next, l2->next = nullptr; tail = l1; l1 = l1->next, l2 = l2->next; } while (l1) { val = l1->val + acc; acc = val / 10; l1->val = val % 10; tail = l1; l1 = l1->next; } if (acc) tail->next = new ListNode(1); return head; } }; 21 合并两个有序链表 合并两个有序链表。 ...

LeetCode 动态规划 题目 6. 字符串相关 712 两个字符串的最小ASCII删除和 给定两个字符串，计算使两个字符串相同所需要删除的字符的ASCII值的和的最小值。 对于两个字符串中的字符 s1[i] 和 s2[j]，如果s1[i] == s2[j]，那么这两个字符都不需要被删除，所以 dp[i][j] = dp[i - 1][j - 1]，否则至少有一个应该被删除，取两个中的最小值，状态转移方程是dp[i][j] = min(dp[i - 1][j] + s1[i], dp[i][j - 1] + s2[j])。时间复杂度是 O(m * n)，空间复杂度是 O(m * n)。 class Solution { public: int minimumDeleteSum(string s1, string s2) { int n1 = s1.size(), n2 = s2.size(); vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0)); for (int i = 1; i <= n1; ++i) dp[i][0] = dp[i - 1][0] + s1[i - 1]; for (int j = 1; j <= n2; ++j) dp[0][j] = dp[0][j - 1] + s2[j - 1]; for (int i = 0; i < n1; ++i) for (int j = 0; j < n2; ++j) if (s1[i] == s2[j]) dp[i + 1][j + 1] = dp[i][j]; else dp[i + 1][j + 1] = min(dp[i][j] + s1[i] + s2[j], min(dp[i][j + 1] + s1[i], dp[i + 1][j] + s2[j])); return dp[n1][n2]; } }; 5 最长回文子串 找到一个字符串中的最长回文子串。 ...

LeetCode 动态规划 题目 3. 数组相关 300 最长上升子序列 在无序数组中找到最长上升子序列的长度。 用一个数组 dp[i] 表示到第 i 个数字为止的最长上升子序列，每次遍历 i 之前的每个数字 j，如果 nums[i] > nums[j]，那么 j 和 i 可以形成一个上升子序列，让 dp[i] = max(dp[i], dp[j] + 1) 就能得到最长的上升子序列了。 class Solution { public: int lengthOfLIS(vector<int>& nums) { int n = nums.size(), res = 2; if (n <= 1) return n; vector<int> dp(n, 1); for (int i = 1; i < n; ++i) for (int j = 0; j < i; ++j) if (nums[i] > nums[j]) { dp[i] = max(dp[i], dp[j] + 1); res = max(res, dp[i]); } return res; } }; 53 最大子序和 找一个数组中具有最大和的连续子数组的和。 ...

LeetCode 动态规划 题目 1. 数字相关 263 丑数 判断一个数 num 是否是丑数。 通用的方法是自底向上求出大于等于 num 的第一个数来判断 num 是否是丑数。但这道题已经给出了数 num，直接通过模运算就能得到结果了。 class Solution { public: bool isUgly(int num) { if (num < 1) return false; while (num % 2 == 0) num /= 2; while (num % 3 == 0) num /= 3; while (num % 5 == 0) num /= 5; return num == 1; } }; 264 丑数 II 求第 n 个丑数。 用一个数组 ugly 来保存前 m 个丑数，用三个质因数 2，3，5 乘以其当前系数对应的丑数，得到新的丑数，最小的一个就是第 m + 1 个丑数。时间复杂度是 O(m * n)，其中 m 是质因数的个数，n 是要找的第 n 个丑数。 class Solution { public: int nthUglyNumber(int n) { vector<int> ugly(n, 1); int base_2 = 0, base_3 = 0, base_5 = 0; int m = INT_MAX; for (int i = 1; i < n; ++i) { ugly[i] = min({2 * ugly[base_2], 3 * ugly[base_3], 5 * ugly[base_5]}); if (2 * ugly[base_2] == ugly[i]) ++base_2; if (3 * ugly[base_3] == ugly[i]) ++base_3; if (5 * ugly[base_5] == ugly[i]) ++base_5; cout << ugly[i] << endl; } return ugly[n - 1]; } }; 313 超级丑数 给定质因数数组 primes，求第 n 个丑数。 ...