week24

231 - 2的幂

是2的幂次 就证明 这个数的二进制位只能有一个1;

lowbit运算: 返回保留最后一个1的二进制数 e.g. lowbit(1010) -> 10

其实就是 x & (-x) == x

class Solution {
public:
    bool isPowerOfTwo(int n) {
        // 这题 2的幂次 证明 二进制只能有一个1
        if(n <= 0) return false;
        return (n & (-n)) == n;
    }
};

232 - 用栈实现队列

怎么在栈中找到最早插入的元素？ -> 辅助栈 每次插入新元素都插入stk头部

感谢jp人提供的思路

class MyQueue {
public:
    stack<int> stk, helper;
public:
    /** Initialize your data structure here. */
    MyQueue() = default;
    
    /** Push element x to the back of queue. */
    void push(int x) {
        // 每次插入 都插入到头部
        while(stk.size())
        {
            helper.push(stk.top());
            stk.pop();
        }
        stk.push(x);
        while(helper.size())
        {
            stk.push(helper.top());
            helper.pop();
        }
    }
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int res = stk.top();
        stk.pop();
        return res;
    }
    
    /** Get the front element. */
    int peek() {
        return stk.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return stk.empty();
    }
};

233 - 数字1的个数

+ 数位DP

经典的数位DP了 快来复习一下数位DP

avatar

这一题 我们枚举的是每一位中1的出现次数

class Solution {
public:
    int countDigitOne(int n) {
        if(n <= 0) return 0;
        // * 1. 把n的每一位扣出来
        int num = n;
        vector<int> nums;
        while(num)
        {
            nums.push_back(num % 10);
            num /= 10;
        }
        reverse(nums.begin(), nums.end());
        int left = 0, p = pow(10, nums.size() - 1), right = n % p, res = 0;
        // * 2. 计算每一位的1出现情况
        // 这里的left就是上面的abc right 就是efg 
        for(int i = 0; i < nums.size(); i++)
        {
            int d = nums[i];
            if(d == 0)  res += left * p;
            else if (d == 1) res += left * p + right + 1;
            else res += (left + 1) * p;
            // 处理
            left = left * 10 + nums[i];
            p /= 10;
            if(p) right = n % p;
        }
        return res;
    }
};

234 - 回文链表

进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

这题把链表的好多操作都用上了：

• 找中点：快慢指针

• 反转链表

整体思路就是找到中点 -> 反转后半链表，得到两个子链表 -> 对比元素 不一致就不满足回文要求

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // * 太经典了 找中点 后半部分反转链表 然后再遍历
        if(!head || !head->next) return true;
        ListNode* slow = head, *fast = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        // * 此时 slow 是中点前面的那个节点
        ListNode* a = slow, *b = slow->next;
        a->next = nullptr;
        while(b)
        {
            ListNode* tmp = b->next;
            b->next = a;
            a = b, b = tmp;
        }
        // * 此时 两个链表 一个头结点是head 一个头结点是a
        while(a && head)
        {
            if(a->val != head->val) return false;
            a = a->next;
            head = head->next;
        }
        return true;
    }
};

235 - 二叉搜索树的最近公共祖先

+ 最近公共祖先（LCA)

肯定是递归搜索了 和root比 一大一小就是当前的root为答案, 不然就往两边走 相等直接返回即可（根据定义）

那个bool判断异或 if((rootval < pval) ^ (rootval < qval)) 是两个之中保证一个成立的意思 简化if的判断条件

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 肯定是递归搜索了 和root比 一大一小就是当前的root为答案
        // 最近公共祖先节点可以为节点本身。
        int pval = p->val, qval = q->val;
        while(root)
        {
            int rootval = root->val;
            if(rootval == pval || rootval == qval) return root;
            if((rootval < pval) ^ (rootval < qval)) return root;
            if(pval < rootval) root = root->left;
            else root = root->right;
        }
        return nullptr;   
    }
};

236 - 二叉树的最近公共祖先

+ 最近公共祖先(LCA)问题

这里指路图论总结专题 有两个算法 在线：倍增法 和 离线：Tarjan

这里因为就查询一次，所以直接标记法就好了，分别记录从root到p和q的路径 重合的就是公共祖先 找到最后一个就是最近公共祖先了

总的来说还是不太正经 正经的LCA问题上面的两个算法还是要背好

class Solution {
public:
    bool dfs(TreeNode* root, vector<TreeNode*>& path, TreeNode* target)
    {
        path.push_back(root);
        if(root->val == target->val) return true;
        if(root->left && dfs(root->left, path, target)) return true;
        if(root->right && dfs(root->right, path, target)) return true;
        path.pop_back();
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 这里只用查询一次 就标记法？
        vector<TreeNode*> pathp, pathq;
        dfs(root, pathp, p);
        dfs(root, pathq, q);
        TreeNode* res = nullptr;
        for(int i = 0; i < min(pathp.size(), pathq.size()); i++)
        {
            if(pathp[i]->val == pathq[i]->val)
                res = pathp[i];
            else break;
        }
        return res;
    }
};

237 - 删除链表中的节点

这题没有给任何前驱节点 怎么删呢？ 假扮后继

先把node后面的点删了 再把node改成后面删除点的val

class Solution {
public:
    void deleteNode(ListNode* node) {
        // 前驱结点呢？？
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

238 - 除自身以外数组的乘积

请不要使用除法，且在 O(n) 时间复杂度内完成此题

你可以在常数空间复杂度内完成这个题目吗 （出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

前后缀分解 前后缀分解是一个非常重要的技巧，将数组按照i 分为前半段前缀和后半段后缀 而前缀和后缀都可通过递推来实现；

这里题目要求常数空间复杂度（输出数组不算） 相当于只能开一个数组，这里我们把前缀成绩直接存储在输出数组res中， 在求后缀的过程直接用一个变量sub代替

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, 0);
        // * 前缀乘积 -> res
        for(int i = 0; i < n; i++)
        {
            if(i == 0) res[i] = nums[0];
            else res[i] = nums[i] * res[i - 1];
        }
        // * 后缀乘积 由于也不会用到 直接就用一个变量sub替代
        int sub = 1;
        for(int i = n - 1; ~i; i--)
        {
            if(i) res[i] = sub * res[i - 1];
            else res[i] = sub;
            sub *= nums[i];
        }
        return res;
    }
};

239 - 滑动窗口最大值

+ 单调队列

单调队列就是拿来求滑动窗口最值问题的， 直接默写8

注意队列是双端队列 用数组模拟就好

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        int n = nums.size();
        vector<int> q(n + 2, 0);
        int hh = 0, tt = -1;
        for(int i = 0; i < n; i++)
        {
            if(hh <= tt && q[hh] < i - k + 1) hh++;
            while(hh <= tt && nums[q[tt]] <= nums[i]) tt--;
            q[++tt] = i;
            if(i >= k - 1) res.push_back(nums[q[hh]]);
        }
        return res;
    }
};

240 - 搜索二维矩阵II

有单调性搜索肯定考虑二分 但本题没有一个合适的全局单调性来处理 -> 很巧妙的一个做法

avatar

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix[0].empty()) return false;
        int n = matrix.size(), m = matrix[0].size();
        int i = 0, j = m - 1;
        while(i < n && j >= 0)
        {
            int t = matrix[i][j];
            if(t == target) return true;
            else if (t > target) j--;
            else i++;
        }
        return false;
    }
};