22.02.20

392. 判断子序列

https://www.cnblogs.com/arknights/articles/13387155.html

//dp解法
    bool isSubsequence(string s, string t){
        int n = s.length(),m = t.length();
        //dp数组dp[i][j]表示字符串t以i位置开始第一次出现字符j的位置
        vector<vector<int>> dp(m + 1,vector<int> (26,0));
        //初始化边界条件，dp[i][j] = m表示t中不存在字符j
        for(int i=0;i<26;i++){
            dp[m][i] = m;
        }
        //从后往前递推初始化dp数组
        for(int i = m - 1;i>=0;i--) {
            for(int j=0;j<26;j++){
                if(t[i] == 'a' + j){
                    dp[i][j] = i;
                }else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        int add = 0;
        for(int i = 0;i<n;i++){
            //t中没有s[i] 返回false
            if(dp[add][s[i] - 'a'] == m){
                return false;
            }
            //否则直接跳到t中s[i]第一次出现的位置之后一位
            add = dp[add][s[i] - 'a'] + 1;
        }
        return true;
    }

1646. 获取生成数组中的最大值

class Solution {
public:
    int getMaximumGenerated(int n) {
        if(n == 0) return 0;
        vector<int> nums(n + 1);
        nums[1] = 1; //初始化，已经有默认的nums[0] = 0

        for (int i = 2; i <= n; i ++){
            nums[i] = nums[i /2] + i % 2* nums[i/2 + 1]; // 通过取余再相乘合并奇偶公式 
        }

        return *max_element(nums.begin(), nums.end());//直接用max_element返回
    }
};

剑指 Offer 10- I. 斐波那契数列

//不要忘记取模

class Solution {
public:
    int fib(int n) {
        int mod = 1e9 + 7;

        if(n < 2) return n;

        int p = 0, q= 0, r = 1;
        for (int i = 2; i <= n; i ++){
            p = q;
            q = r;
            r = (p + q ) % mod;
        }

        return r;
    }
};

剑指 Offer 10- II. 青蛙跳台阶问题

class Solution {
public:
    int numWays(int n) {
        vector<int> dp(n +2);

        //需要单独处理下初始n的情况，不然数组会出现越界
        if(n == 0) return 1;
        else if(n == 1) return 1;
        else if(n ==2) return 2;
        dp[1] = 1;
        dp[2] = 2;
        dp[0] = 1;
        for (int i = 3; i <= n; i ++){
            dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
        }
        return dp[n];
    }
};

24. 两两交换链表中的节点

递归

/**
 * 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* swapPairs(ListNode* head) {
        if(head == nullptr || head -> next == nullptr) return head;

        ListNode* newHead = head -> next;
        head -> next = swapPairs(newHead -> next);
        newHead -> next  head;
        return newHead;
    }
};

迭代

主要操作：

temp.next = node2
node1.next = node2.next
node2.next = node1

代码实现：

/**
 * 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* swapPairs(ListNode* head) {
        //创建dummy节点
        ListNode* dummyHead = new ListNode(0);
        dummyHead -> next = head;
        ListNode* temp = dummyHead;
        while (temp -> next != nullptr && temp -> next -> next != nullptr){
            //初始化node1和node2
            ListNode* node1 = temp -> next;
            ListNode* node2 = temp -> next -> next;

            //进行swap操作
            temp -> next = node2;
            node1 -> next = node2 -> next;
            node2 -> next = node1;

            //temp重新到node位置，为下一次swap做准备
            temp = node1;
        }

        return dummyHead -> next;
    }
};

61. 旋转链表

/**
 * 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* rotateRight(ListNode* head, int k) {
        // head == nullptr 和 head -> next == nullptr 不能调换顺序，否则head == nullptr时候找不到head -> next 会报错
        if(k == 0 ||  head == nullptr  ||head -> next == nullptr) return head;
        ListNode* iter = head;
        int n = 1;

        //遍历链表，求节点总数n
        while(iter -> next != nullptr){
            iter = iter -> next;
            n ++;
        }

        int add = n -k%n;

        if(add == n) return head;
        iter -> next = head;//形成环

        //iter 到链表徐娅停止的位置
        while (add--){
            iter = iter -> next;
        }

        ListNode* ret = iter -> next;
        iter -> next = nullptr;//iter后面断掉

        return ret;
    }
};

28. 实现 strStr() (KMP)

比较难， yet to review

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if(m == 0) return 0;
        vector<int> pi(m);

        for (int i = 1, j = 0; i < m; i ++){
            while (j > 0 && needle[i] != needle[j]){
                j = pi[j -1];
            }

            if(needle[i] == needle[j]) j ++;
            pi[i] = j;
        }

        for (int i = 0, j = 0; i < n; i ++){
            while(j > 0 && haystack[i] != needle[j]) j = pi[j -1];
            if(haystack[i] == needle[j]) j ++;
            if (j == m) return i - m + 1;
        }


        return -1;

    }
};

22.02.21

838. 推多米诺

class Solution {
public:
    string pushDominoes(string dominoes) {
        int n = dominoes.size(), i = 0;
        char left = 'L';
        while(i < n){
            int j = i;
            while(j < n && dominoes[j] == '.' ) j ++;
            char right = j < n ? dominoes[j] : 'R';

            if(left == right){
                while (i < j){
                    dominoes[i++] = right;
                } 
            }else if(left == 'R' && right == 'L'){
                int k = j -1;
                while(i < k){
                    dominoes[i ++] = 'R';
                    dominoes[k--] = 'L';
                }
            }

            left = right;
            i = j + 1;
        }
        return dominoes;
    }
};

86. 分隔链表

/**
 * 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* partition(ListNode* head, int x) {
        ListNode* small = new ListNode(0);
        ListNode* smallHead = small;
        ListNode* large = new ListNode(0);
        ListNode* largeHead = large;

        while (head!= nullptr){
            if (head -> val < x){
                small -> next = head;
                small = small -> next;
            }else{
                large -> next = head;
                large = large -> next;
            }
            head = head -> next;
        }

        large -> next = nullptr;
        small -> next = largeHead -> next;
        return smallHead -> next;

    }
};

92. 反转链表 II

两种解法

/**
 * 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 {
private:
    void reverseLinkedList(ListNode *head){
        ListNode *pre = nullptr;
        ListNode *cur = head;
        while(cur != nullptr){
            ListNode *next = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = next;
        }
    }
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode *dummyNode = new ListNode(-1);
        dummyNode ->next = head;

        ListNode *pre = dummyNode;

        for (int i = 0; i < left -1; i ++){
            pre = pre -> next;
        }

        ListNode *rightNode = pre;
        for (int i = 0; i < right -left + 1;i ++){
            rightNode = rightNode -> next;
        }

        ListNode *leftNode = pre -> next;
        ListNode *curr = rightNode -> next;


        //需要截断链表
        pre -> next = nullptr;
        rightNode -> next = nullptr;

        reverseLinkedList(leftNode);
        pre -> next = rightNode;
        leftNode -> next = curr;
        return dummyNode -> next;
    }
};

1994. 好子集的数目

leetcode 每日打卡题

class Solution {
private:
    static constexpr array<int,10> primes = {2,3,5,7,11,13,17,19,23,29};
    static constexpr int num_max = 30;
    static constexpr int mod = 1000000007;
public:
    int numberOfGoodSubsets(vector<int>& nums) {
        vector<int> freq(num_max + 1);
        for (int num : nums){
            ++freq[num];
        }

        vector<int> f(1 << primes.size());
        f[0] = 1;

        for (int _ = 0; _ < freq[1]; ++_){
            f[0] = f[0] * 2 % mod;
        }

        for (int i = 2; i <= num_max; ++i){
            if(!freq[i]) continue;

            int subset = 0, x = i;
            bool check = true;
            for (int j = 0; j < primes.size(); ++j){
                int prime = primes[j];
                if(x % (prime *prime) == 0){
                    check = false;
                    break;
                }

                if(x % prime == 0)subset |= (1 << j);

            }

            if(!check) continue;

            for (int mask = (1 <<primes.size()) -1; mask > 0; --mask){
                if((mask & subset) == subset){
                    f[mask] = (f[mask] + static_cast<long long>(f[mask ^ subset]) * freq[i] )% mod;
                }
            }
        }

        int ans = 0;
        for (int mask = 1, mask_max = (1 << primes.size()); mask < mask_max; ++ mask){
            ans = (ans +f[mask]) % mod;
        }

        return ans;
    }
};

22.02.22

109. 有序链表转换二叉搜索树

/**
 * 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) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    ListNode* getMedian(ListNode* left, ListNode* right) {
        ListNode* fast = left;
        ListNode* slow = left;
        while(fast!=right && fast -> next != right){
            fast = fast -> next;
            fast = fast -> next;
            slow = slow -> next;
        }
        return slow;
    }

    TreeNode* buildTree(ListNode* left, ListNode* right){
        if(left == right) return nullptr;
        ListNode* mid = getMedian(left, right);
        TreeNode* root = new TreeNode(mid -> val);
        root -> left = buildTree(left, mid);
        root -> right = buildTree(mid -> next, right);
        return root;    
    }

    TreeNode* sortedListToBST(ListNode* head){
        return buildTree(head, nullptr);
    }
};

116. 填充每个节点的下一个右侧节点指针

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if(root == nullptr){
            return root;
        }

        Node* leftmost = root;
        while(leftmost -> left != nullptr){
            Node* head = leftmost;
            while(head != nullptr){
                head -> left -> next = head -> right;

                if (head -> next != nullptr){
                    head -> right -> next = head -> next -> left;
                }

                head = head -> next;
            }

            leftmost = leftmost -> left;
        }

        return root;
    }


};