头像

初静




离线:29分钟前


最近来访(38)
用户头像
Bluuush
用户头像
MinYoun
用户头像
注意负对数
用户头像
yxc
用户头像
rach
用户头像
诺亚方舟.
用户头像
我要出去乱说
用户头像
FredericNiu
用户头像
Once.
用户头像
七酱
用户头像
lixiaoqian
用户头像
DeAnfield
用户头像
填海难....填心更难
用户头像
jcxioo
用户头像
WenWawa
用户头像
AE86丶
用户头像
div
用户头像
Hygen
用户头像
麦麦片片片
用户头像
切切狸


初静
2天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

比较好的单调队列的考察题目,用到了deque


和 AcWing 41. 包含min函数的栈 对应的一道题 如下 (使用单调队列求出的)

下面代码是 剑指 Offer 59 - II. 队列的最大值

59.png

最优做法(LC官方题解)

class MaxQueue {
public:
    queue<int> que;
    deque<int> deq;

    MaxQueue() {

    }

    int max_value() {
        if (deq.empty()) return -1;
        return deq.front();
    }

    void push_back(int value) {
        que.push(value);
        while (!deq.empty() && deq.back() < value) deq.pop_back(); //这里用的单调对了的思想,只是用双端队列实现的

        deq.push_back(value);
    }

    int pop_front() { //这里返回的就是普通的队列的队头元素,不是队列的最大元素,不要搞混了, 队列中的最大值是用max_value()函数返回的
        if (que.empty()) return -1;
        if (deq.front() == que.front()) deq.pop_front();

        int ans = que.front();
        que.pop();
        return ans;
    }
};

不是最优的做法

class MaxQueue {
public:
    vector<int> q; //也可以用成员变量的方式做(LC官方题解)

    MaxQueue() {

    }

    int max_value() {
        int res = -1;
        for (int i = 0; i < q.size(); i ++) res = max(res, q[i]);
        return res;
    }

    void push_back(int value) {
        q.push_back(value);
    }

    int pop_front() {
        if (q.empty()) return -1;
        int x = q[0];
        reverse(q.begin(), q.end());
        q.pop_back();
        reverse(q.begin(), q.end()); //这里是想将vector<int> 中的第一个元素删掉
        return x;
    }
};

LC官方题解 (不是最优做法)

class MaxQueue {
public:
    int q[20000];
    int begin = 0, end = 0;

    MaxQueue() {

    }

    int max_value() {
        int ans = -1;
        for (int i = begin; i != end; i ++) ans = max(ans, q[i]);
        return ans;
    }

    void push_back(int value) {
        q[end ++] = value;
    }

    int pop_front() {
        if (begin == end) return -1;
        return q[begin ++];
    }
};




初静
2天前

暂时没做,如果后面面试会考这个题 看题解:AcWing 31. 表示数值的字符串——神奇的指针移动解法

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



初静
2天前

43.png

可以用数位统计DP 来做, 但是本题不是典型的数位DP,所以这里用数学方法做 (代码写的很有巧妙性)

写代码的技巧 left right p

问题:给定一个整数 n,计算所有小于等于 n 的非负整数中数字 1 出现的个数。

S8.png


S5.png

时间复杂度是:$O(N^2)$ N不是数的大小,而是数的位数

class Solution {
public:
    int countDigitOne(int n) {
        if (n <= 0) return 0; //考虑到n是负数或0的情况
        vector<int> nums;
        while (n) {
            nums.push_back(n % 10);
            n /= 10;
        }
        reverse(nums.begin(), nums.end());

        int res = 0;
        for (int i = 0; i < nums.size(); i ++) {
            int d = nums[i];
            int left = 0, right = 0, p = 1;
            for (int j = 0; j < i; j ++) left = left * 10 + nums[j];
            for (int j = i + 1; j < nums.size(); j ++) { // 这里是j=i+1,不是j=i;因为第i位是 d,是我们当前枚举的第几位, d = nums[i]
                right = right * 10 + nums[j];
                p = p * 10;
            }

            if (d == 0) res += left * p;
            else if (d == 1) res += left * p + right + 1;
            else res += (left + 1) * p;
        } 
        return res;
    }
};

233-1.png

class Solution {
public:
    int countDigitOne(int n) {
        if (n <= 0) return 0;
        vector<int> nums;
        while (n) {
            nums.push_back(n % 10);
            n /= 10;
        }

        reverse(nums.begin(), nums.end());

        int res = 0;

        for (int i = 0; i < nums.size(); i ++) {
            int d = nums[i];
            int left = 0, right = 0, p = 1;
            for (int j = 0; j < i; j ++) {
                left = left * 10 + nums[j];         
            }
            for (int j = i + 1; j < nums.size(); j ++) {
                right = right * 10 + nums[j];
                p *= 10;
            }

            if (d == 0) res += left * p;
            else if (d == 1) res += (left * p) + right + 1;
            else res += (left + 1) * p;
        } //这里才是外层for循环的结尾
        return res;
    }
};


活动打卡代码 AcWing 86. 构建乘积数组

初静
3天前

66.png

不满足题目空间要求的写法 能不能只使用常数空间?(除了输出的数组之外)
(LC上没有空间要求)

class Solution {
public:
    vector<int> constructArr(vector<int>& A) {
        if (A.empty()) return vector<int> ();
        vector<int> left (A.size(), 1);
        vector<int> right (A.size(), 1);

        for (int i = 1; i < A.size(); i ++) //这里从1开始,因为left[0]已经初始化过了,是1
            left[i] = A[i - 1] * left[i - 1];

        for (int i = A.size() - 2; ~i; i --) //这里从A.size() - 2开始,因为right[A.size() - 1] 已经初始化了,是1
            right[i] = A[i + 1] * right[i + 1];

        vector<int> B (A.size(), 0); //这里初始化成0,因为要求的是B[]的所有值
        for (int i = 0; i < A.size(); i ++)
            B[i] = left[i] * right[i];

        return B;
    }
};

满足空间要求的写法:
能不能只使用常数空间?(除了输出的数组之外)

class Solution {
public:
    vector<int> constructArr(vector<int>& A) {
        if (A.empty()) return vector<int> ();
        int n = A.size();
        vector<int> B (n);

        for (int i = 0, p = 1; i < n; i ++) { //先让B[i]等于i左半边的乘积
            B[i] = p;
            p *= A[i];
        }

        for (int i = n - 1, p = 1; ~i; i --) { //再用B[i]乘以i右半边的乘积
            B[i] *= p;
            p *= A[i];
        }

        return B;
    }
};


活动打卡代码 AcWing 50. 序列化二叉树

初静
4天前

50.png

class Codec {
public:

    string serialize(TreeNode* root) {
        string res;
        dfs1(root, res);
        return res;  
    }

    void dfs1(TreeNode* root, string &res) {
        if (!root) {
            res += "#,";
            return ;
        }

        res += to_string(root->val) + ','; //这里千万别忘记 将root->val转成to_string()字符串类型,否则会爆int
        dfs1(root->left, res);
        dfs1(root->right, res);
    }


    TreeNode* deserialize(string data) {
        int u = 0;
        return dfs2(data, u);        
    }

    TreeNode* dfs2(string& data, int &u) {
        if (data[u] == '#') {
            u += 2;
            return NULL;
        }

        bool minus = false;
        int t = 0;

        if (data[u] == '-') {
            minus = true;
            u ++;
        }

        while (data[u] != ',' && data[u] != '-') {
            t = t * 10 + data[u] - '0';
            u ++;
        }

        u ++; //这里的u ++很容易忘记,因为data中每个数都是用,隔开的,所以进行下一轮判断时要u++
        if (minus) t = -t;

        auto root = new TreeNode(t);
        root->left = dfs2(data, u);
        root->right = dfs2(data, u);
        return root;
    }
};
class Codec {
public:
    string serialize(TreeNode* root) {
       string res;
       dfs1(root, res);
       return res; 
    }

    void dfs1(TreeNode* root, string& res) {
        if (!root) {
            res += "#,";
            return ;
        }
        res += to_string(root->val) + ',';
        dfs1(root->left, res);
        dfs1(root->right, res);
    }

    TreeNode* deserialize(string data) {
        int u = 0;
        return dfs2(data, u); 
    }

    TreeNode* dfs2(string& data, int& u) {      //这里的int &不可少
        if (data[u] == '#') {
            u += 2; //这里是 #, 两个字符过滤掉
            return NULL;
        }

        int t = 0;
        bool is_minus = false;
        while (data[u] != ',') {
            if (data[u] == '-') is_minus = true;
            else t = t * 10 + data[u] - '0';
            u ++;
        } 

        u ++; //!!!!
        if (is_minus) t = -t;
        auto root = new TreeNode(t);
        root->left = dfs2(data, u);
        root->right = dfs2(data, u);
        return root;
    }
};



初静
4天前

AcWing 88. 树中两个结点的最低公共祖先

AC上是LC剑指offer上面的这道题——剑指 Offer 68 - II. 二叉树的最近公共祖先 (在最下面)

下面是 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

68-2.png


68.png

68-1.png

下面是 —— 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

代码:

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return NULL;
        if (p->val > q->val) swap(p, q);
        if (p->val <= root->val && q->val >= root->val) return root;
        if (q->val < root->val) return lowestCommonAncestor(root->left, p, q);
        return lowestCommonAncestor(root->right, p, q); 
    }
};

另一种写法: 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

68-3.png

AcWing 88. 树中两个结点的最低公共祖先

剑指 Offer 68 - II. 二叉树的最近公共祖先

69-1.png
69.png

Sn.png

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
       if (!root) return NULL;
       if (p == root || q == root) return root;
       auto left = lowestCommonAncestor(root->left, p, q);
       auto right = lowestCommonAncestor(root->right, p, q);

       if (left == NULL) return right;
       if (right == NULL) return left;
       return root;
    }
};

LC官方题解 (很好)

236.png

这段代码有难度,但是很好,面试要是写出来绝对加分

class Solution {
public:
    unordered_map<int, TreeNode*> fa;
    unordered_map<int, bool> vis;

    void dfs(TreeNode* root) { //哈希表fa存储所有节点的父节点
        if (root->left != NULL) {
            fa[root->left->val] = root;
            dfs(root->left);
        }
        if (root->right != NULL) {
            fa[root->right->val] = root;
            dfs(root->right);
        }
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        fa[root->val] = NULL; 
        dfs(root);
        while (p != NULL) { //从p节点开始不断往上跳,并记录已经访问过的节点
            vis[p->val] = true;
            p = fa[p->val];
        }
        while (q != NULL) { //q节点开始不断往上跳,如果碰到已经访问过的节点,说明该节点就是要找的p和q的LCA
            if (vis[q->val]) return q; //这里进行判断,是否是同一个祖父
            q = fa[q->val];
        }
        return NULL;
    }
};


活动打卡代码 AcWing 5.3. homework_3

初静
4天前

要注意的一点是: 在git add .的时候,一定要在homework 文件夹下,也就是只能在项目根目录下将工作区的内容加到暂存区和版本库

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 Linux 5.9. homework_9

初静
4天前

要现在myserver上配置git环境
先生成密钥ssh-keygen 一路回车
然后将公钥复制到ACgit里面

接下来就是在myserver上的homework文件夹下创建lesson_5文件夹,再git clone git@git.acwing.com:chujing/homework.git

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 4.0. homework_0

初静
9天前

homework 4 getinfo得到你的服务器账号信息
1. 进入自己的~./.ssh文件夹里,如果没有就自己创建一个就行
2. vim config 这个文件名不能错
3.

Host myserver
   HostName 123.57.47.211
   User acs_293

保存就行了,再配置免密登录

配置免密登录
1. 首先创建密钥 ssh-keygen 一路回车就可以
2. 在.ssh/文件夹下会发现多了两个文件 私钥id_rsa 和 公钥 id_rsa.pub
3. 再用命令一键添加公钥到myserver服务器的账户里 ssh-copy-id myserver
4. 输入你通过homework 4 getinfo 获得的服务器登录密码

完成免密登录,登录服务器ssh myservere即可登录服务器

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 75. 颜色分类

初静
12天前

小米笔试 (红白蓝彩条排序)

头条二面

75-题目.png


75-3.png

参考题解1

class Solution {
public:
    void sortColors(vector<int>& nums) {
        for (int i = 0, j = 0, k = nums.size() - 1; i <= k;) {
            if (nums[i] == 0) swap(nums[i ++], nums[j ++]);
            else if (nums[i] == 2) swap(nums[i], nums[k --]);
            else i ++;
        }
    }
};

另一种写法:
1. 用三个变量a b c分别记录0 1 2 的个数
2. 先扫描统计三个数分别有多少个,然后再从前往后先写a个0 b个1 c个2

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int count[3] = {0};

        for(int i = 0; i < nums.size(); ++i)
            ++count[nums[i]];

        for(int i = 0, t = 0;i < 3; ++i)
            for(int j = 0; j < count[i]; ++j)
                nums[t++] = i;

    }
};