解题思路

KMP

class Solution {
public:
    int strStr(string s, string p) {
        int n = s.size(), m = p.size();
        s = ' ' + s, p = ' ' + p;

        vector<int> next(m + 1);

        for(int i = 2, j = 0; i <= m; i ++ ) {
            while(j && p[i] != p[j + 1]) j = next[j];
            if(p[i] == p[j + 1]) j ++;
            next[i] = j;
        }

        for (int i = 1, j = 0; i <= n; i ++) {
            while(j && s[i] != p[j + 1]) j = next[j];
            if(s[i] == p[j + 1]) j ++;
            if(j == m) return i - m;
        }
        return -1;
    }
};

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0;
        for(int fast = 0; fast < nums.size(); fast ++){
            if(nums[fast] != val) nums[slow ++] = nums[fast];
        }
        return slow;
    }
};

时间复杂度 $O(n)$

连标题一定画图！！！！

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        auto dummy = new ListNode(-1);
        dummy->next = head;

        for(auto p = dummy;;){
            auto q = p;
            for(int i = 0; i < k && q; i ++) q = q->next;
            if(!q) break;

            auto a = p->next, b = a->next;
            for(int i = 0; i < k - 1; i ++) {
                auto c = b->next;
                b->next = a;
                a = b, b = c;
            }
            auto c = p->next;
            p->next = a, c->next = b;
            p = c;
        }
        return dummy->next;
    }
};

解题思路

只是把每个链表的头结点的地址push进去了，而不是把整个链表push进去。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:

    struct Cmp{
        bool operator() (ListNode* a, ListNode* b){
            return a->val > b->val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, Cmp>  heap;
        auto dummy = new ListNode(-1), tail = dummy;
        for(auto l : lists) if(l) heap.push(l);

        while(heap.size()){
            auto t = heap.top();
            heap.pop();

            tail->next = t;
            tail = tail->next;

            if(t->next) heap.push(t->next);
        }
        return dummy->next;
    }
};

解题思路

最好的做法

class Solution {
public:
    string leftRotateString(string str, int n) {
        int len = str.size();
        reverse(str.begin(), str.end());
        reverse(str.begin(), str.end() - n);
        reverse(str.begin() + len - n, str.end());
        return str;
    }
};

我的思路就是把两个str连起来，然后截串 n,length

class Solution {
public:
    string leftRotateString(string str, int n) {
        int len = str.size();
        string s = str + str;
        return s.substr(n,len);
    }
};

解题思路

hash表

遍历数组每个元素 x，判断是否存在 target - x
若有，返回 target - x 和 x
若没有，将x插入hash表

class Solution {
public:
    vector<int> findNumbersWithSum(vector<int>& nums, int target) {
        unordered_set<int> hash;
        for(auto x : nums){
            if(hash.count(target - x)) return vector<int>{target - x, x};
            hash.insert(x);
        }
        return vector<int>();
    }
};

解题思路

由于题目要求时间复杂度为O(n),空间复杂度为O(1)，所以不能用hash表

不符合题意的hash表做法(很傻)

class Solution {
public:
    int findNumberAppearingOnce(vector<int>& nums) {
        unordered_map<int, int> hash;
        for(auto num : nums){
            hash[num] ++;
        }
        for(auto num : nums){
            if(hash[num] == 1)
                return num;
        }
        return -1;
    }
};

解题思路

位运算

异或运算：两个相同的数异或为0
1. 所有数异或一遍，剩下的就是两个不相同的数的异或值 x ^ y
2. x 和 y 肯定在某一位(第k位)上一个为0，一个为1
3. 找出所有第k位为1的数，剩下的就是所有第k位为0的数
4. 分别对这两个集合做异或运算，集合一就剩下x，集合二就剩y。
5. 返回x和y

class Solution {
public:
    vector<int> findNumsAppearOnce(vector<int>& nums) {
        int sum = 0;
        for(auto x : nums) sum ^= x; // 将所有数都异或一遍 sum = x ^ y。想同的数异或为0

        int k = 0;
        while(!(sum >> k & 1)) k ++; // 找出 x 和 y 在第 k 位不同（此处是求第k位为1的）

        int first = 0;
        for(auto x : nums)
            if(x >> k & 1) // 求出所有第k位为1的数
                first ^= x; // 运算完后first就是两个不同的数之一

        return vector<int>({first, sum ^ first});
    }
};

hash表

时间复杂度 O(n)

hash表的存取是O(1)，遍历了两遍数组为2n，所以时间复杂度为O(n);

class Solution {
public:
    vector<int> findNumsAppearOnce(vector<int>& nums) {
        vector<int> ans;
        unordered_map<int, int> hash;
        for(int i = 0; i < nums.size(); i ++){
            hash[nums[i]]++;
        }
        for(auto x : nums){
            if(hash[x] == 1) ans.push_back(x);
        }
        return ans;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool ans = true;
    bool isBalanced(TreeNode* root) {
        dfs(root);
        return ans;
    }
    int dfs(TreeNode* root){
        if(!root) return 0;
        int left = dfs(root->left), right = dfs(root->right);
        if(abs(left - right) > 1) ans = false;
        return max(left, right) + 1;
    }

};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int treeDepth(TreeNode* root) {
        if (!root) return 0;
        return max(treeDepth(root->left),treeDepth(root->right)) + 1;
    }
};