\u9012\u5f52 \u94fe\u8868<\/p>\n
\u8fed\u4ee3<\/p>\n
class Solution {
\npublic:
\n ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
\n ListNode head;
\n ListNode *cur = &head, *cur1 = list1, *cur2 = list2;
\n while (cur1 && cur2) {
\n if (cur1->val < cur2->val) {
\n cur->next = cur1;
\n cur1 = cur1->next;
\n } else {
\n cur->next = cur2;
\n cur2 = cur2->next;
\n }
\n cur = cur->next;
\n }
\n if (cur1) {
\n cur->next = cur1;
\n } else {
\n cur->next = cur2;
\n }
\n return head.next;
\n }
\n};<\/p>\n
\u9012\u5f52<\/p>\n
class Solution {
\npublic:
\n ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
\n if (list1 == nullptr) {
\n return list2;
\n } else if (list2 == nullptr) {
\n return list1;
\n } else if (list1->val < list2->val) {
\n list1->next = mergeTwoLists(list1->next, list2);
\n return list1;
\n } else {
\n list2->next = mergeTwoLists(list1, list2->next);
\n return list2;
\n }
\n }
\n};<\/p>\n
\u5b57\u7b26\u4e32 \u56de\u6eaf<\/p>\n
class Solution {
\npublic:
\n vector<string> generateParenthesis(int n) {
\n vector<string> ret;
\n string path;
\n int left = 0, right = 0;
\n dfs(ret, path, left, right, n);
\n return ret;
\n }<\/p>\n
void dfs(vector<string>& ret, string& path, int left, int right, int n) {
\n if (right == n) {
\n ret.push_back(path);
\n return;
\n }
\n if (left < n) {
\n path.push_back('(');
\n dfs(ret, path, left + 1, right, n);
\n path.pop_back();
\n }
\n if (right < left) {
\n path.push_back(')');
\n dfs(ret, path, left, right + 1, n);
\n path.pop_back();
\n }
\n }
\n};<\/p>\n
\u94fe\u8868 \u5206\u6cbb<\/p>\n
\u987a\u5e8f\u5408\u5e76<\/p>\n
class Solution {
\npublic:
\n ListNode* mergeKLists(vector<ListNode*>& lists) {
\n ListNode* ret = nullptr;
\n for (size_t i = 0; i < lists.size(); i++) {
\n ret = mergeTwoLists(ret, lists[i]);
\n }
\n return ret;
\n }<\/p>\n
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
\n if (!l1 || !l2) {
\n return l1 ? l1 : l2;
\n }<\/p>\n
ListNode head, *cur = &head, *cur1 = l1, *cur2 = l2;
\n while (cur1 && cur2) {
\n if (cur1->val < cur2->val) {
\n cur->next = cur1;
\n cur1 = cur1->next;
\n } else {
\n cur->next = cur2;
\n cur2 = cur2->next;
\n }
\n cur = cur->next;
\n }<\/p>\n
cur->next = cur1 ? cur1 : cur2;
\n return head.next;
\n }
\n};<\/p>\n
\u5408\u5e76\u5206\u6cbb<\/p>\n
class Solution {
\npublic:
\n ListNode* mergeKLists(vector<ListNode*>& lists) {
\n return merge(lists, 0, lists.size() – 1);
\n }<\/p>\n
ListNode* merge(vector<ListNode*>& lists, int left, int right) {
\n if (left > right) {
\n return nullptr;
\n }
\n if (left == right) {
\n return lists[left];
\n }
\n int mid = (left + right) >> 1;
\n return mergeTwoLists(merge(lists, left, mid), merge(lists, mid + 1, right));
\n }<\/p>\n
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
\n if (!l1 || !l2) {
\n return l1 ? l1 : l2;
\n }<\/p>\n
ListNode head, *cur = &head, *cur1 = l1, *cur2 = l2;
\n while (cur1 && cur2) {
\n if (cur1->val < cur2->val) {
\n cur->next = cur1;
\n cur1 = cur1->next;
\n } else {
\n cur->next = cur2;
\n cur2 = cur2->next;
\n }
\n cur = cur->next;
\n }<\/p>\n
cur->next = cur1 ? cur1 : cur2;
\n return head.next;
\n }
\n};<\/p>\n
\u4f18\u5148\u7ea7\u961f\u5217<\/p>\n
struct Status {
\n int val;
\n ListNode* ptr;<\/p>\n
bool operator<(const Status& rhs) const { return val > rhs.val; }<\/p>\n
Status(int x, ListNode* node) : val(x), ptr(node) {}
\n};<\/p>\n
class Solution {
\npublic:
\n ListNode* mergeKLists(vector<ListNode*>& lists) {
\n priority_queue<Status> q;
\n for (const auto& node : lists) {
\n if (node) {
\n q.push({node->val, node});
\n }
\n }
\n ListNode head, *cur = &head;
\n while (!q.empty()) {
\n auto front = q.top();
\n q.pop();
\n cur->next = front.ptr;
\n cur = cur->next;
\n if (front.ptr->next) {
\n q.push({front.ptr->next->val, front.ptr->next});
\n }
\n }
\n return head.next;
\n }
\n};<\/p>\n
\u94fe\u8868<\/p>\n
\u9012\u5f52<\/p>\n
class Solution {
\npublic:
\n ListNode* swapPairs(ListNode* head) {
\n if (head == nullptr || head->next == nullptr) {
\n return head;
\n }<\/p>\n
ListNode* newhead = head->next;
\n head->next = swapPairs(newhead->next);
\n newhead->next = head;<\/p>\n
return newhead;
\n }
\n};<\/p>\n
\u8fed\u4ee3<\/p>\n
class Solution {
\npublic:
\n ListNode* swapPairs(ListNode* head) {
\n ListNode newhead;
\n newhead.next = head;
\n ListNode* cur = &newhead;
\n while (cur->next && cur->next->next) {
\n ListNode* node1 = cur->next;
\n ListNode* node2 = cur->next->next;
\n cur->next = node2;
\n node1->next = node2->next;
\n node2->next = node1;
\n cur = node1;
\n }
\n return newhead.next;
\n }
\n};<\/p>\n
class Solution {
\npublic:
\n ListNode* swapPairs(ListNode* head) {
\n if (head == nullptr || head->next == nullptr) {
\n return head;
\n }<\/p>\n
ListNode newhead;
\n newhead.next = head;
\n ListNode* prev = &newhead;
\n ListNode* cur = prev->next;
\n ListNode* next = cur->next;<\/p>\n
while (cur && next) {
\n prev->next = next;
\n cur->next = next->next;
\n next->next = cur;<\/p>\n
prev = cur;
\n cur = cur->next;
\n if (cur) {
\n next = cur->next;
\n }
\n }<\/p>\n
return newhead.next;
\n }
\n};<\/p>\n
\u94fe\u8868<\/p>\n
class Solution {
\npublic:
\n ListNode* reverseKGroup(ListNode* head, int k) {
\n \/\/ 1. \u5148\u6c42\u51fa\u9700\u8981\u9006\u5e8f\u591a\u5c11\u7ec4
\n int n = 0;
\n ListNode* cur = head;
\n while (cur) {
\n cur = cur->next;
\n n++;
\n }
\n n \/= k;<\/p>\n
\/\/ 2. \u91cd\u590d n \u6b21：\u957f\u5ea6\u4e3a k \u7684\u94fe\u8868\u7684\u9006\u5e8f\u5373\u53ef
\n ListNode newhead;
\n ListNode* pre = &newhead;
\n cur = head;
\n for (int i = 0; i < n; i++) {
\n ListNode* tmp = cur;
\n for (int j = 0; j < k; j++) {
\n ListNode* next = cur->next;
\n cur->next = pre->next;
\n pre->next = cur;
\n cur = next;
\n }
\n pre = tmp;
\n }<\/p>\n
\/\/ 3. \u628a\u4e0d\u9700\u8981\u7ffb\u8f6c\u7684\u63a5\u4e0a
\n pre->next = cur;
\n return newhead.next;
\n }
\n};<\/p>\n
\u6570\u7ec4 \u53cc\u6307\u9488<\/p>\n
\u53cc\u6307\u9488<\/p>\n
class Solution {
\npublic:
\n int removeDuplicates(vector<int>& nums) {
\n int n = nums.size();
\n if (n == 0)
\n return 0;<\/p>\n
int i = 0, j = 1;
\n int dst = 0;
\n while (j < n) {
\n if (nums[i] == nums[j]) {
\n j++;
\n } else {
\n nums[dst++] = nums[i];
\n i = j;
\n j++;
\n }
\n }
\n nums[dst++] = nums[i];<\/p>\n
return dst;
\n }
\n};<\/p>\n
class Solution {
\npublic:
\n int removeDuplicates(vector<int>& nums) {
\n int n = nums.size();
\n if (n == 0)
\n return 0;<\/p>\n
int fast = 1, slow = 1;
\n while (fast < n) {
\n if (nums[fast] != nums[fast – 1]) {
\n nums[slow++] = nums[fast];
\n }
\n ++fast;
\n }<\/p>\n
return slow;
\n }
\n};<\/p>\n
\u6570\u7ec4 \u53cc\u6307\u9488<\/p>\n
\u53cc\u6307\u9488<\/p>\n
class Solution {
\npublic:
\n int removeElement(vector<int>& nums, int val) {
\n int n = nums.size();
\n int src = 0, dst = 0;
\n while (src < n) {
\n if (nums[src] != val)
\n nums[dst++] = nums[src++];
\n else
\n ++src;
\n }
\n return dst;
\n }
\n};<\/p>\n
\u53cc\u6307\u9488\u4f18\u5316<\/p>\n
class Solution {
\npublic:
\n int removeElement(vector<int>& nums, int val) {
\n int left = 0, right = nums.size();
\n while (left < right) {
\n if (nums[left] == val) {
\n nums[left] = nums[–right];
\n } else {
\n left++;
\n }
\n }
\n return left;
\n }
\n};<\/p>\n
\u53cc\u6307\u9488 \u5b57\u7b26\u4e32 \u5b57\u7b26\u4e32\u5339\u914d<\/p>\n
class Solution {
\npublic:
\n int strStr(string haystack, string needle) {
\n int n = haystack.size();
\n for (int i = 0; i < n; i++) {
\n if (haystack[i] == needle[0]) {
\n int start = 0;
\n while (i + start < n && start < needle.size()) {
\n if (haystack[i + start] == needle[start]) {
\n start++;
\n } else {
\n break;
\n }
\n }
\n if (start == needle.size()) {
\n return i;
\n }
\n }
\n }
\n return -1;
\n }
\n};<\/p>\n
class Solution {
\npublic:
\n int strStr(string haystack, string needle) {
\n int n = haystack.size();
\n int m = needle.size();
\n for (int i = 0; i <= n – m; i++) {
\n int j = i, k = 0;
\n while (k < m && haystack[j] == needle[k]) {
\n j++;
\n k++;
\n }
\n if (k == m) {
\n return i;
\n }
\n }
\n return -1;
\n }
\n};<\/p>\n
KMP<\/p>\n
class Solution {
\npublic:
\n int strStr(string haystack, string needle) {
\n int n = haystack.size(), m = needle.size();
\n if (m == 0) {
\n return 0;
\n }
\n \/\/ \u8bbe\u7f6e\u54e8\u5175
\n haystack.insert(haystack.begin(), ' ');
\n needle.insert(needle.begin(), ' ');
\n vector<int> next(m + 1);
\n \/\/ \u9884\u5904\u7406next\u6570\u7ec4
\n for (int i = 2, j = 0; i <= m; i++) {
\n while (j && needle[i] != needle[j + 1]) {
\n j = next[j];
\n }
\n if (needle[i] == needle[j + 1]) {
\n j++;
\n }
\n next[i] = j;
\n }
\n \/\/ \u5339\u914d\u8fc7\u7a0b
\n for (int i = 1, j = 0; i <= n; i++) {
\n while (j && haystack[i] != needle[j + 1]) {
\n j = next[j];
\n }
\n if (haystack[i] == needle[j + 1]) {
\n j++;
\n }
\n if (j == m) {
\n return i – m;
\n }
\n }
\n return -1;
\n }
\n};<\/p>\n
\u6570\u5b66 \u4e8c\u5206\u67e5\u627e<\/p>\n
\u4e8c\u5206\u67e5\u627e<\/p>\n
class Solution {
\npublic:
\n int divide(int dividend, int divisor) {
\n \/\/ \u8003\u8651\u88ab\u9664\u6570\u4e3a\u6700\u5c0f\u503c\u7684\u60c5\u51b5
\n if (dividend == INT_MIN) {
\n if (divisor == 1) {
\n return INT_MIN;
\n }
\n if (divisor == -1) {
\n return INT_MAX;
\n }
\n }
\n \/\/ \u8003\u8651\u9664\u6570\u4e3a\u6700\u5c0f\u503c\u7684\u60c5\u51b5
\n if (divisor == INT_MIN) {
\n return dividend == INT_MIN ? 1 : 0;
\n }
\n \/\/ \u8003\u8651\u88ab\u9664\u6570\u4e3a 0 \u7684\u60c5\u51b5
\n if (dividend == 0) {
\n return 0;
\n }<\/p>\n
\/\/ \u4e00\u822c\u60c5\u51b5，\u4f7f\u7528\u4e8c\u5206\u67e5\u627e
\n \/\/ \u5c06\u6240\u6709\u7684\u6b63\u6570\u53d6\u76f8\u53cd\u6570，\u8fd9\u6837\u5c31\u53ea\u9700\u8981\u8003\u8651\u4e00\u79cd\u60c5\u51b5
\n bool rev = false;
\n if (dividend > 0) {
\n dividend = -dividend;
\n rev = !rev;
\n }
\n if (divisor > 0) {
\n divisor = -divisor;
\n rev = !rev;
\n }<\/p>\n
\/\/ \u5feb\u901f\u4e58
\n auto quickAdd = [](int y, int z, int x) {
\n \/\/ x \u548c y \u662f\u8d1f\u6570，z \u662f\u6b63\u6570
\n \/\/ \u9700\u8981\u5224\u65ad z * y >= x \u662f\u5426\u6210\u7acb
\n int result = 0, add = y;
\n while (z) {
\n if (z & 1) {
\n \/\/ \u9700\u8981\u4fdd\u8bc1 result + add >= x
\n if (result < x – add) {
\n return false;
\n }
\n result += add;
\n }
\n if (z != 1) {
\n \/\/ \u9700\u8981\u4fdd\u8bc1 add + add >= x
\n if (add < x – add) {
\n return false;
\n }
\n add += add;
\n }
\n \/\/ \u4e0d\u80fd\u4f7f\u7528\u9664\u6cd5
\n z >>= 1;
\n }
\n return true;
\n };<\/p>\n
int left = 1, right = INT_MAX, ret = 0;
\n while (left <= right) {
\n \/\/ \u6ce8\u610f\u6ea2\u51fa，\u5e76\u4e14\u4e0d\u80fd\u4f7f\u7528\u9664\u6cd5
\n int mid = left + ((right – left) >> 1);
\n bool check = quickAdd(divisor, mid, dividend);
\n if (check) {
\n ret = mid;
\n \/\/ \u6ce8\u610f\u6ea2\u51fa
\n if (mid == INT_MAX) {
\n break;
\n }
\n left = mid + 1;
\n } else {
\n right = mid – 1;
\n }
\n }<\/p>\n
return rev ? -ret : ret;
\n }
\n};<\/p>\n
\u7c7b\u4e8c\u5206\u67e5\u627e<\/p>\n
class Solution {
\npublic:
\n int divide(int dividend, int divisor) {
\n \/\/ \u8003\u8651\u88ab\u9664\u6570\u4e3a\u6700\u5c0f\u503c\u7684\u60c5\u51b5
\n if (dividend == INT_MIN) {
\n if (divisor == 1) {
\n return INT_MIN;
\n }
\n if (divisor == -1) {
\n return INT_MAX;
\n }
\n }
\n \/\/ \u8003\u8651\u9664\u6570\u4e3a\u6700\u5c0f\u503c\u7684\u60c5\u51b5
\n if (divisor == INT_MIN) {
\n return dividend == INT_MIN ? 1 : 0;
\n }
\n \/\/ \u8003\u8651\u88ab\u9664\u6570\u4e3a 0 \u7684\u60c5\u51b5
\n if (dividend == 0) {
\n return 0;
\n }<\/p>\n
\/\/ \u4e00\u822c\u60c5\u51b5，\u4f7f\u7528\u7c7b\u4e8c\u5206\u67e5\u627e
\n \/\/ \u5c06\u6240\u6709\u7684\u6b63\u6570\u53d6\u76f8\u53cd\u6570，\u8fd9\u6837\u5c31\u53ea\u9700\u8981\u8003\u8651\u4e00\u79cd\u60c5\u51b5
\n bool rev = false;
\n if (dividend > 0) {
\n dividend = -dividend;
\n rev = !rev;
\n }
\n if (divisor > 0) {
\n divisor = -divisor;
\n rev = !rev;
\n }<\/p>\n
vector<int> candidates = {divisor};
\n \/\/ \u6ce8\u610f\u6ea2\u51fa
\n while (candidates.back() >= dividend – candidates.back()) {
\n candidates.push_back(candidates.back() + candidates.back());
\n }
\n int ans = 0;
\n for (int i = candidates.size() – 1; i >= 0; –i) {
\n if (candidates[i] >= dividend) {
\n ans += (1 << i);
\n dividend -= candidates[i];
\n }
\n }<\/p>\n
return rev ? -ans : ans;
\n }
\n};<\/p>\n
\u54c8\u5e0c\u8868 \u5b57\u7b26\u4e32 \u6ed1\u52a8\u7a97\u53e3<\/p>\n
class Solution {
\npublic:
\n vector<int> findSubstring(string s, vector<string>& words) {
\n unordered_map<string, int> hash1; \/\/ \u4fdd\u5b58 words \u91cc\u9762\u6240\u6709\u5355\u8bcd\u7684\u9891\u6b21
\n for (const auto& s : words) {
\n hash1[s]++;
\n }
\n vector<int> ret;<\/p>\n
int len = words[0].size(), m = words.size();
\n for (int i = 0; i < len; i++) {
\n unordered_map<string, int> hash2; \/\/ \u7ef4\u62a4\u7a97\u53e3\u5185\u5355\u8bcd\u7684\u9891\u6b21
\n for (int left = i, right = i, count = 0; right + len <= s.size();
\n right += len) {
\n \/\/ \u8fdb\u7a97\u53e3 + \u7ef4\u62a4 count
\n string in = s.substr(right, len);
\n hash2[in]++;
\n if (hash1.count(in) && hash2[in] <= hash1[in]) {
\n count++;
\n }<\/p>\n
\/\/ \u5224\u65ad
\n if (right – left + 1 > len * m) {
\n \/\/ \u51fa\u7a97\u53e3 + \u7ef4\u62a4 count
\n string out = s.substr(left, len);
\n if (hash1.count(out) && hash2[out] <= hash1[out]) {
\n count–;
\n }
\n hash2[out]–;
\n left += len;
\n }<\/p>\n
\/\/ \u66f4\u65b0\u7ed3\u679c
\n if (count == m) {
\n ret.push_back(left);
\n }
\n }
\n }<\/p>\n
return ret;
\n }
\n};<\/p>\n","protected":false},"excerpt":{"rendered":"
21\u3001[\u7b80\u5355] \u5408\u5e76\u4e24\u4e2a\u6709\u5e8f\u94fe\u8868
\n\u9012\u5f52 \u94fe\u8868 \u8fed\u4ee3 class Solution {
\npublic:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode head;ListNode *cur &head, *cur1 list1, *cur2 list2;while (cur1 && cur2) {if (cur1->val val) {cur->next cur1;c<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[8185,55,99,2692,81,1983,427],"topic":[],"class_list":["post-79377","post","type-post","status-publish","format-standard","hentry","category-server","tag-lenyiin","tag-c","tag-java","tag-leetcode","tag-python","tag-1983","tag-427"],"yoast_head":"\n