Maxw的小站

刷了有快一周leetcode题目了，感觉算法这块进度偏慢，一天可能刷一两道题就是极限了。

刷的是leetcode学习栏里的初级算法选题。有时候感觉自己的记忆力真是差到一定程度了，有好两道题刷完后才发现自己在算法竞赛入门里看过，就是记不起来，结果还是用了最笨的方法…

可以预感到自己学了有些方法，例如双指针，之后还需要适应…太难了！一步一步来吧

(以下所有题目来源力扣cn官网)

2/25-3/1

LC26. 删除有序数组中的重复项

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int a=0;
        int b=nums.size();
        if(b<=1) return b;
        for(int i=0;i<(b-1);i++){
            if(nums[i]!=nums[i+1]){
                nums[a]=nums[i];
                a++;
            }
        }
        nums[a]=nums[b-1];
        return a+1;
    }
};

这里（重新）学到了双指针的思想，熟悉了下许久未见的cpp。选cpp语言来学其实只是因为自己以前选的好几本（算法跟opencv）教程都是cpp的，虽然听说cpp面试在语言特性上挺严格的，但是感觉比起另一个我学过一点的python，这个更能展现一些语言内部的设定吧，python总感觉隐去了不少细节，对我之后代码风格不是太有利。

这道题其实还好，后面有在原值上修改的题，就一定要用vector<int>& nums这种传引用的方式。

在写这道题的时候发现自己各种函数都快忘完了，.size()/memset()/.length() 都不记得了，哎。

122. 买卖股票的最佳时机 II

给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。

在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。
返回 你能获得的 最大 利润 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int day=0;
        int count=0;
        bool st=false;
        if(prices.size()==1)return 0;
        for(int i=0;i<prices.size()-1;i++){
            if(prices[i]<prices[i+1]&&i+1!=prices.size()-1&&st==false){
                day=i;
                st=true;
            }
            if(prices[i]>prices[i+1]&&st==true){
                count+=prices[i]-prices[day];
                st=false;
            }
            if(prices[i]<=prices[i+1]&&i+1==prices.size()-1){
                if(st==true)count+=prices[i+1]-prices[day];
                if(st==false)count+=prices[i+1]-prices[i];
            }
        }
        return count;
    }
};

做这道题的时候我想到了要在下降的最低日买，上升的最高日卖，然后就捅了if窝……不过这几个条件想合并确实有点难吧。

然后我一想到这个解决方法就乐起来了，完全没想到自己之前在教程里看过一个更简单的解法，就是求每一个前后两日差，然后求其中正数的和。其实我思考题目的时候想到了是不是可以利用每一段买入到卖出可以拆解成这段时间每天都买入卖出，但是没想到啥好的利用方法。

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        for(int i=0;i<prices.size()-1;i++){
            prices[i]=prices[i+1]-prices[i];
        }
        int pf=0;
        for(int j=0;j<prices.size()-1;j++){
            if(prices[j]>0)pf+=prices[j];
        }
        return pf;
    }
};

哦对，还可以代码复用一下

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int pf=0;
        for(int i=0;i<prices.size()-1;i++){
            prices[i]=prices[i+1]-prices[i];
            if(prices[i]>0)pf+=prices[i];
        }
        return pf;
    }
};

这样看起来就简洁多了！需要注意的是最后一天没有别的天数来减（买了不卖也是亏），在第二个循环中不用加上。

48.旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

1
2

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

这题显然是有一定的规律可以利用的，否则一边一边写旋转，代码有点太多了。看到题目强调矩阵这个概念，我就想到了可以把矩阵操作一下，比如转置之类的。

第一次做这题时，我想到可以先转置，再看看怎么调整。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int tri = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0+tri; j < n; j++) {
                int tr=matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tr;
            }
            tri++;
        }
        for (int i = 0; i < n; i++) {
            reverse(matrix[i].begin(),matrix[i].end());
        }
    }
};

果然，转置过后，每一行reverse一下就行了。不过需要注意的是转置时遍历一个三角即可，不然是转置两次。

后来重做了一遍，我是倒过来想的，先reverse列，再转置。

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
	void rotate(vector<vector<int>>& matrix) {
		reverse(matrix.begin(), matrix.end());
		for (int i = 0; i < matrix.size(); i++) {
			for (int j = i; j < matrix[i].size(); j++) {
				int ori = matrix[i][j];
				matrix[i][j] = matrix[j][i];
				matrix[j][i] = ori;
			}
		}
	}
};

这次我学聪明了，知道遍历三角可以j = i，少几行代码。不过这样写使用内存居然比第一次多！我把这个想法也改成用j = 0+tri的形式（其他没变），内存使用变成和第一次一样了。这是为什么呢？

我想去stackoverflow上问问，就去了leetcode英文站看看英文题目描述，顺手再提交了两次题目，发现内存占用又一样了…但是我用最开始的写法时间更快。好吧，看来这或许不是我现阶段能了解的问题。

虽然遇到了一些问题，不过都很快找到方法解决了。看来之前安装VS和openCV的坑不是白踩的。

Maxw终于有了自己的博客啦！有点激动，也有点犹豫跟纠结，虽然理由已经充分到说服自己无数遍，但我仍无法预测自己毅然走出专业的圈走进写代码的坑是不是更加正确的选择…

2/23-2/24

git初试

follow 枫叶的教程
problem occur:
can’ t clone existing repostory with git bash reports timeout
or OpenSSL SSL_read: Connection was reset, errno 10054

从GitHub上clone仓库的时候，试了几次，有时git bash报错10054，有时timeout。

我先是按网上教程改了git的global config，还是报错

想到自己上GitHub都要科学方法，就觉得应该是代理的问题。git应该并非使用系统代理设置，而是需要自行设置，果不其然。

solve:
setup proxy for git, following git设置代理

博客搭建

follow 枫叶的教程合集

感谢枫叶大佬的教程，有时间一定上知乎评论区里发个反馈。

安装node.js与插件的过程中报错属于node.js本地的文件夹无法访问。一开始觉得很奇怪，明明特意从c盘卸载了安别的盘，后来我想起来那个盘是我从c盘分出去的了，草（感叹词）。所以应该是因为也需要管理员权限（也可能是我把git安到c盘了？）。果然管理员启动bash之后，安装就顺畅了。

枫叶的教程里面设置npm的环境变量那里可能有点问题，设置好之后应该是不需要像网上一些教程说的那样安装两遍npm的。npm所在目录需要保留而不是更改，再按教程添加node的目录。在系统变量里添加node的路径后，path里需要添加对应的%NODE_PATH%，这也是教程里未提及的。

其他问题应该就只是跟版本有关了，比如GitHub把主分支从master改成main，创建个人网页的setting单独分页了等等。以及博客更新后无需删除.git重新上传，hexo的操作估计是有延迟的。

我跳过了教程里设置自己的域名的部分。（以后博客里内容多了再为它花钱吧）

在菜单中增加新页面需要同时hexo new page以及在主题的config文件中设置（参考枫叶的教程）

一些感叹

虽然我对于文件系统和权限的理解仅限一鳞半爪，但在配置网站的过程中，这些知识还是帮了我不少忙。不愧是程序员的基本功。

一些bug

git报错the remote end hung up unexpectedly：照此教程解决了：
https://jingyan.baidu.com/article/afd8f4de38d87174e386e967.html

一些bug 2.0

。。。又给git的proxy摆了一道没办法deploy博客，不想用的时候一定要记得git config --global --unset http.proxy 重置啊！设置回来则是git config --global http.proxy proxyaddress:port

最近总感觉自己记性有点差，这是写完博客后如何deploy:
在博客的根文件夹（那个有.deploy_git的文件夹）打开git bash，输入：

1
2
3

hexo clean
hexo generate
hexo deploy