{"id":481,"date":"2022-08-31T19:41:50","date_gmt":"2022-08-31T19:41:50","guid":{"rendered":"http:\/\/www.gislxz.top\/?p=481"},"modified":"2023-03-26T12:36:37","modified_gmt":"2023-03-26T12:36:37","slug":"leetcode%e5%88%9d%e7%ba%a7%e7%ae%97%e6%b3%95%e6%95%b4%e7%90%86","status":"publish","type":"post","link":"https:\/\/www.gislxz.com\/index.php\/2022\/08\/31\/leetcode%e5%88%9d%e7%ba%a7%e7%ae%97%e6%b3%95%e6%95%b4%e7%90%86\/","title":{"rendered":"Leetcode\u521d\u7ea7\u7b97\u6cd5\u6574\u7406"},"content":{"rendered":"\n

\u6570\u7ec4<\/h2>\n\n\n\n

1\u5220\u9664\u6392\u5e8f\u6570\u7ec4\u4e2d\u7684\u91cd\u590d\u9879 \u5feb\u6162\u6307\u9488<\/p>\n\n\n\n

2\u4e70\u5356\u80a1\u7968\u7684\u6700\u4f73\u65f6\u673a II \u6700\u7b80\u5355\u7684\u8d2a\u5fc3\u7b97\u6cd5<\/p>\n\n\n\n

3\u65cb\u8f6c\u6570\u7ec4 \u5206\u591a\u6b21\u65cb\u8f6c<\/p>\n\n\n\n

\u65cb\u8f6c\u6570\u7ec4<\/p>\n\n\n\n

class Solution {\npublic:\n    void rotate(vector<int>& nums, int k) {\n        k=k%nums.size();\n        reverse(nums,0,nums.size()-1);\n        reverse(nums,0,k-1);\n        reverse(nums,k,nums.size()-1);\n    }\n    void reverse(vector<int>& nums,int begin,int end){\n        for(int i=0;i<(end-begin+1)\/2;i++){\n            int a=nums[begin+i];\n            nums[begin+i]=nums[end-i];\n            nums[end-i]=a;\n        }\n    }\n};<\/code><\/pre>\n\n\n\n
4\u5b58\u5728\u91cd\u590d\u5143\u7d20  \u5e38\u89c4\uff1a\u54c8\u5e0c\u8868 \uff0cset<\/p>\n\n\n\n
5\u53ea\u51fa\u73b0\u4e00\u6b21\u7684\u6570\u5b57 \u5f02\u6216\u8fd0\u7b97<\/p>\n\n\n\n
class Solution {\npublic:\n    int singleNumber(vector<int>& nums) {\n        int result=0;\n        for(int i=0;i<nums.size();i++){\n            result ^= nums[i];\n        }\n        return result;\n    }\n};<\/code><\/pre>\n\n\n\n
6\u4e24\u4e2a\u6570\u7ec4\u7684\u4ea4\u96c6 II  \u6392\u5e8f\u540e\u53cc\u6307\u9488\/map<\/p>\n\n\n\n
7\u52a0\u4e00 \u5faa\u73af\uff0c\u632a\u4f4d<\/p>\n\n\n\n
8\u79fb\u52a8\u96f6 \u5feb\u6162\u6307\u9488<\/p>\n\n\n\n
9\u4e24\u6570\u4e4b\u548c \u54c8\u5e0c\u8868<\/p>\n\n\n\n
10\u6709\u6548\u7684\u6570\u72ec \u5faa\u73af<\/p>\n\n\n\n
11\u65cb\u8f6c\u56fe\u50cf \u5faa\u73af<\/p>\n\n\n\n
\u5b57\u7b26\u4e32<\/h2>\n\n\n\n
1\u53cd\u8f6c\u5b57\u7b26\u4e32  \u540c\u6570\u7ec4\u53cd\u8f6c<\/p>\n\n\n\n
2\u6574\u6570\u53cd\u8f6c \u6ce8\u610f\u6ea2\u51fa\u68c0\u6d4b\u65b9\u6cd5<\/p>\n\n\n\n
    public int reverse(int x) {\n        int res = 0;\n        while (x != 0) {\n            int t = x % 10;\n            int newRes = res * 10 + t;\n            \/\/\u5982\u679c\u6570\u5b57\u6ea2\u51fa\uff0c\u76f4\u63a5\u8fd4\u56de0\n            if ((newRes - t) \/ 10 != res)\n                return 0;\n            res = newRes;\n            x = x \/ 10;\n        }\n        return res;\n    }<\/code><\/pre>\n\n\n\n
3\u5b57\u7b26\u4e32\u4e2d\u7684\u7b2c\u4e00\u4e2a\u552f\u4e00\u5b57\u7b26 hashmap\uff0c\u4e5f\u8bb8\u6570\u7ec4\u6548\u7387\u66f4\u9ad8<\/p>\n\n\n\n
4\u6709\u6548\u7684\u5b57\u6bcd\u5f02\u4f4d\u8bcd hashmap\u6216\u6570\u7ec4<\/p>\n\n\n\n
5\u9a8c\u8bc1\u56de\u6587\u4e32 \u53cc\u6307\u9488<\/p>\n\n\n\n
6\u5b57\u7b26\u4e32\u8f6c\u6574\u6570
7strStr() \u9010\u4e2a\u5224\u65ad\/KMP\u7b97\u6cd5<\/p>\n\n\n\n
8\u5916\u89c2\u6570\u52179\u6700\u957f\u516c\u5171\u524d\u7f00 \u6ca1\u5565\u8bf4\u7684<\/p>\n\n\n\n
\u94fe\u8868<\/h2>\n\n\n\n
1\u5220\u9664\u94fe\u8868\u4e2d\u7684\u8282\u70b9<\/p>\n\n\n\n
class Solution {\r\npublic:\r\n    void deleteNode(ListNode* node) {\r\n        ListNode *next1 = node->next;\r\n        node->val = next1->val;\r\n        node->next = next1->next;\r\n        delete next1;\r\n        next1=nullptr;        \r\n    }\r\n};<\/code><\/pre>\n\n\n\n
2\u5220\u9664\u94fe\u8868\u5012\u6570\u7b2cN\u4e2a<\/p>\n\n\n\n
class Solution {\r\npublic:\r\n    ListNode* removeNthFromEnd(ListNode* head, int n) {\r\n        if(head->next==nullptr)\r\n            return nullptr;\r\n        int *time = new int;\r\n        *time = n;\r\n        remove(head,time);\r\n        if(*time==0)\r\n            return head->next;\r\n        else\r\n            return head;\r\n    }\r\n    void remove(ListNode* head, int* times){\r\n        if(head->next!=nullptr)\r\n            remove(head->next,times);\r\n        if(*times!=0)\r\n            *times = *times - 1;\r\n        else{\r\n            ListNode *temp = head->next;\r\n            head->next=temp->next;\r\n            delete temp;\r\n            *times = *times - 1;\r\n        }\r\n    }\r\n};<\/code><\/pre>\n\n\n\n
3\u53cd\u8f6c\u94fe\u8868<\/p>\n\n\n\n
class Solution {\r\npublic:\r\n    ListNode* reverseList(ListNode* head) {\r\n        if(head==nullptr || head->next==nullptr)\r\n            return head;\r\n        ListNode* head1 = reverseList(head->next);\r\n        head->next->next=head;\r\n        head->next = nullptr;\r\n        return head1;\r\n    }\r\n};<\/code><\/pre>\n\n\n\n
4\u5408\u5e76\u4e24\u4e2a\u6709\u5e8f\u94fe\u8868<\/p>\n\n\n\n
class Solution {\r\npublic:\r\n    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {\r\n        if(list1==nullptr)\r\n            return list2;\r\n        if(list2==nullptr)\r\n            return list1;\r\n        ListNode *l1;ListNode *l2;\r\n        if(list1->val<=list2->val){\r\n            l1=list1;l2=list2;\r\n        }\r\n        else{\r\n            l1=list2;l2=list1;\r\n        }\r\n        digui(l1,l1->next,l2);\r\n        return l1;\r\n    }\r\n    void digui(ListNode* begin,ListNode* l1,ListNode* l2){\r\n        if(l1==nullptr){\r\n            begin->next=l2;\r\n            return;\r\n        }\r\n        if(l2==nullptr){\r\n            begin->next=l1;\r\n            return;\r\n        }\r\n        if(l1->val<=l2->val){\r\n            begin->next=l1;\r\n            digui(l1,l1->next,l2);\r\n        }\r\n        else{\r\n            begin->next=l2;\r\n            digui(l2,l1,l2->next);\r\n        }\r\n    }\r\n};<\/code><\/pre>\n\n\n\n
5\u56de\u6587\u94fe\u8868 \u5feb\u6162\u6307\u9488\u4e0e\u53cd\u8f6c\u94fe\u8868<\/p>\n\n\n\n
class Solution {\r\npublic:\r\n    bool isPalindrome(ListNode* head) {\r\n        ListNode *slow,*fast;\r\n        slow=fast=head;\r\n        while(fast->next!=nullptr && fast->next->next!=nullptr){\r\n            slow=slow->next;\r\n            fast=fast->next->next;\r\n        }\r\n        if(slow->next==nullptr)\r\n            return true;\r\n        slow->next=reverse(slow->next);\r\n        slow=slow->next;\r\n        while(slow!=nullptr){\r\n            if(head->val!=slow->val)\r\n                return false;\r\n            slow=slow->next;\r\n            head=head->next;\r\n        }\r\n        return true;\r\n    }\r\n    ListNode* reverse(ListNode *head){\r\n        ListNode* prev = nullptr;\r\n        ListNode* next = nullptr;\r\n        while(head!=nullptr){\r\n            next=head->next;\r\n            head->next=prev;\r\n            prev=head;\r\n            head=next;\r\n        }\r\n        return prev;\r\n    }\r\n};<\/code><\/pre>\n\n\n\n
6\u73af\u5f62\u94fe\u8868 \u5feb\u6162\u6307\u9488<\/p>\n\n\n\n
class Solution {\r\npublic:\r\n    bool hasCycle(ListNode *head) {\r\n        if(head==nullptr)\r\n            return false;\r\n        ListNode *slow, *fast;\r\n        slow=fast=head;\r\n        while(slow!=nullptr){\r\n            if(fast->next==nullptr || fast->next->next==nullptr)\r\n                return false;\r\n            slow=slow->next;\r\n            fast=fast->next->next;\r\n            if(slow==fast)\r\n                return true;\r\n        }\r\n        return false;\r\n    }\r\n};<\/code><\/pre>\n\n\n\n
\u6811<\/h2>\n\n\n\n
1\u4e8c\u53c9\u6811\u7684\u6700\u5927\u6df1\u5ea6 \u9012\u5f52<\/p>\n\n\n\n
class Solution {\r\npublic:\r\n    int maxDepth(TreeNode* root) {\r\n        if(root==nullptr)\r\n            return 0;\r\n        return max(maxDepth(root->left),maxDepth(root->right))+1;\r\n    }\r\n};<\/code><\/pre>\n\n\n\n
2\u9a8c\u8bc1\u4e8c\u53c9\u641c\u7d22\u6811 \u9012\u5f52<\/p>\n\n\n\n
class Solution {\r\npublic:\r\n    bool isValidBST(TreeNode* root) {\r\n        return fanwei(root,LONG_MIN,LONG_MAX);\r\n    }\r\n    bool fanwei(TreeNode* root,long left,long right){\r\n        if(root==nullptr)\r\n            return true;\r\n        long val = long(root->val);\r\n        if(val<=left||val>=right)\r\n            return false;\r\n        return (fanwei(root->left,left,min(right,val)) && fanwei(root->right,max(left,val),right));\r\n    }\r\n};<\/code><\/pre>\n\n\n\n
3\u5bf9\u79f0\u4e8c\u53c9\u6811<\/p>\n\n\n\n
class Solution {\r\npublic:\r\n    bool isSymmetric(TreeNode* root) {\r\n        if(root==nullptr)\r\n            return true;\r\n        return duicheng(root->left,root->right);\r\n    }\r\n    bool duicheng(TreeNode* left,TreeNode* right){\r\n        if(left==nullptr&&right==nullptr)\r\n            return true;\r\n        if(left==nullptr||right==nullptr)\r\n            return false;\r\n        if(left->val!=right->val)\r\n            return false;\r\n        return duicheng(left->left,right->right)&&duicheng(left->right,right->left);\r\n    }\r\n};<\/code><\/pre>\n\n\n\n
4\u4e8c\u53c9\u6811\u7684\u5c42\u5e8f\u904d\u5386 \u4f7f\u7528\u961f\u5217\u8bb0\u5f55node<\/p>\n\n\n\n
class Solution {\r\npublic:\r\n    vector<vector<int>> levelOrder(TreeNode* root) {\r\n        vector<vector<int>> answer;\r\n        if(root==nullptr)\r\n            return answer;\r\n        queue<TreeNode*> nodequeue;\r\n        int num=1;\r\n        nodequeue.push(root);\r\n        while(num!=0){\r\n            vector<int> temp;\r\n            for(int i=0;i<num;i++){\r\n                TreeNode* current = nodequeue.front();\r\n                temp.push_back(current->val);\r\n                nodequeue.pop();\r\n                if(current->left!=nullptr)\r\n                    nodequeue.push(current->left);\r\n                if(current->right!=nullptr)\r\n                    nodequeue.push(current->right);\r\n            }\r\n            answer.push_back(temp);\r\n            num=nodequeue.size();\r\n        }        \r\n    return answer;\r\n    }\r\n};<\/code><\/pre>\n\n\n\n
5\u5c06\u6709\u5e8f\u6570\u7ec4\u8f6c\u5316\u6210\u4e3a\u4e8c\u53c9\u641c\u7d22\u6811<\/p>\n\n\n\n
class Solution {\r\npublic:\r\n    TreeNode* sortedArrayToBST(vector<int>& nums) {\r\n        int size = nums.size();\r\n        TreeNode *top = new TreeNode(nums[size\/2]);\r\n        top->left = digui(nums,0,size\/2 - 1);\r\n        top->right = digui(nums,size\/2 + 1,size - 1);\r\n        return top;\r\n    }\r\n    TreeNode* digui(vector<int>& nums,int left,int right){\r\n        if(left>right)\r\n            return nullptr;\r\n        int size = right-left+1;\r\n        TreeNode *top = new TreeNode(nums[left+size\/2]);\r\n        if(size>=2)\r\n            top->left = digui(nums,left,left + size\/2-1);\r\n        if(size>=3)\r\n            top->right = digui(nums,left + size\/2+1,right);\r\n        return top;\r\n    }\r\n};<\/code><\/pre>\n\n\n\n
\u6392\u5e8f\u548c\u641c\u7d22<\/h2>\n\n\n\n
1\u5408\u5e76\u4e24\u4e2a\u6709\u5e8f\u6570\u7ec4 \u4ece\u540e\u5411\u524d\u6392<\/p>\n\n\n\n
2\u7b2c\u4e00\u4e2a\u9519\u8bef\u7248\u672c \u4e8c\u5206\u67e5\u627e<\/p>\n\n\n\n
class Solution {\r\npublic:\r\n    int firstBadVersion(int n) {\r\n        int left=1;int right=n;\r\n        while(left<right){\r\n            int mid=left\/2+right\/2;\r\n            if(isBadVersion(mid)==true){\r\n                left = left;right=mid;\r\n            }\r\n            else{\r\n                left=mid + 1;right=right;\r\n            }\r\n        }\r\n        return left;\r\n    }\r\n};<\/code><\/pre>\n\n\n\n
\u52a8\u6001\u89c4\u5212<\/h2>\n\n\n\n
1\u722c\u697c\u68af<\/p>\n\n\n\n
class Solution {\r\npublic:\r\n    int climbStairs(int n) {\r\n        if(n==1)\r\n            return 1;\r\n        if(n==2)\r\n            return 2;\r\n        int a=1;int b=2;\r\n        for(int i=2;i<n;i++){\r\n            if(i%2==0){\r\n                a=a+b;\r\n            }\r\n            else{\r\n                b=a+b;\r\n            }\r\n        }\r\n        return a>b?a:b;\r\n    }\r\n};<\/code><\/pre>\n\n\n\n
2\u4e70\u5356\u80a1\u7968\u7684\u6700\u4f73\u65f6\u673a \u52a8\u6001\u89c4\u5212\/\u5feb\u6162\u6307\u9488\/\u5355\u8c03\u6808<\/p>\n\n\n\n
3\u6700\u5927\u5b50\u5e8f\u548c \u52a8\u6001\u89c4\u5212<\/p>\n\n\n\n
4\u6253\u5bb6\u52ab\u820d \u52a8\u6001\u89c4\u5212\uff0c\u30102\uff0clength\u3011\u8bb0\u5f55\u662f\u5426\u6253\u52ab\u60c5\u51b5\u4e0b\u7684\u6700\u5927\u5229\u6da6<\/p>\n\n\n\n
<\/p>\n\n\n\n
<\/p>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
\u6570\u7ec4 1\u5220\u9664\u6392\u5e8f\u6570\u7ec4\u4e2d\u7684\u91cd\u590d\u9879 \u5feb\u6162\u6307\u9488 2\u4e70\u5356\u80a1\u7968\u7684\u6700\u4f73\u65f6\u673a II \u6700\u7b80\u5355\u7684\u8d2a\u5fc3\u7b97\u6cd5 3\u65cb\u8f6c\u6570\u7ec4 \u5206\u591a\u6b21\u65cb\u8f6c \u65cb\u8f6c\u6570\u7ec4 4\u5b58\u5728\u91cd …<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[12,6,5,11],"tags":[],"class_list":["post-481","post","type-post","status-publish","format-standard","hentry","category-leetcode","category-6","category-5","category-11"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/posts\/481","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/comments?post=481"}],"version-history":[{"count":1,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/posts\/481\/revisions"}],"predecessor-version":[{"id":484,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/posts\/481\/revisions\/484"}],"wp:attachment":[{"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/media?parent=481"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/categories?post=481"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.gislxz.com\/index.php\/wp-json\/wp\/v2\/tags?post=481"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}