Posted on | Edited on | In |

最近阅读Mastering Node.js一书，看到第六章，觉得书中的几个例子都特别有代表性，所以自己也事项一遍，顺便做点笔记，以备以后参阅。

AJAX

第一节讲的是AJAX，可能之前比较熟悉吧，或者说，我这一代人可能从来没有接触过那种一个URL，获取HTML文件，里边并不能做什么其它事情的WEB时代。

AJAX主要就是这个A，异步，可以让浏览器在自己想向server获取数据的时候发出请求，并在服务器返回之后做相应的处理，而不用请求整个文档，我目前的理解大致就是这样，不做过多叙述了。

WebSocket

socket的确之前接触的不多，感觉的确很神奇，如何做到实时的通信呢？很是好奇。

不过看过之后，发现其并不是走HTTP协议，所以不是什么黑科技了，而是底层的浏览器所提供的功能，与server之间建立持久的TCP连接，然后相互通信。

书上配套的例子，一个协同画画的东西，很好的展示了websocket的功能，下边就是写的一些说明，备以后查阅。

co-draw

代码：https://github.com/brickmaker/node-real-time-demo/tree/master/co-draw

server

server端的代码非常简单，直接复制过来，因为基本没有特别的与socket.io无关的内容：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const Koa = require('koa');
const app = new Koa();
const serve = require('koa-static');
const server = require('http').createServer(app.callback());
const io = require('socket.io')(server);
app.use(serve(__dirname + '/public'));
io.on('connection', (socket) => {
  console.log(`client ${socket.id} connected`)
  socket.on('draw', data => {
    socket.broadcast.emit('draw', data)
  });
});
server.listen(8102);

用了Koa，用koa-static来serve前端文件，Koa和socket.io的接入可能需要记一下，好像并不是那么想当然。

服务端监听客户端的连接，并可以得到客户端的socket，进行后续操作：

1
io.on('connection', socket => {...})

在回调里就可以写一些逻辑了。

client

客户端初始化socket.io很简单：

在index.html中加入：

1
<script src="/socket.io/socket.io.js"></script>

然后在scripts中加一条：

1
const socket = io.connect('/');

就OK了，觉得很神奇。

至于操作，这里只用到了两个：

  1. 在自己绘制的时候，向server发消息：“我在绘制…”，并附上绘制的数据
  2. 监听服务器传来别人绘制的消息，然后把别人画的也加上来

OK，基本就是这样。

SSE(Server Sent Events)

顾名思义，就是server向客户端发送消息，不过其实这一点websocket也可以做，这可能也是之前自己从来没有听过这个名词的原因吧。

它的好处可能就是用的是HTTP协议，然后比较简单吧，具体的看Stack Overflow上的两者对比：https://stackoverflow.com/questions/5195452/websockets-vs-server-sent-events-eventsource

Real-time Q&A

唔，写到后边都不太想写了，真的，参考价值不大，其实关于SSE的很少，不过还是要学习一下这种方式。

代码：https://github.com/brickmaker/node-real-time-demo/tree/master/real-time-QA

说白了，就这个例子来看，其实就相当于，建立了一个持久的HTTP连接，然后有数据就写数据，没有什么特别的，只不过都通过那个HTTP发，然后断了之后能重新连上。

server

服务端，拿到客户端请求Event Source时候的socket，存下来，想给谁发数据的时候，直接socket.write()就OK了。

client

客户端的连接也比较简单：

1
const eventSource = new EventSource('/event-source');

然后就是各种addEventListener(...)来监听消息。

值得注意的是，可以设定不同的事件，是通过字符串的方式设定的，比如这样：

1
2
clientSocket.write(`event: ${event}\n`);
clientSocket.write(`data: ${JSON.stringify(data)}\n\n`);

客户端监听对应的事件类别就可以了~

Posted on | In |

曾经觉得D3超级难用，API反人类，好多东西跟现代的JS不符，上手不容易…
后来，当开始用D3之后，发现，自己误会了D3.js的定位，D3的丰富与灵活超乎了自己的想象，于是决定认真地学习下这个古老而又有极强生命力的库！

Overview

阅读D3的Overview：https://d3js.org/

虽然篇幅很短，但是介绍了D3的核心特性，个人总结两点：

  1. 强大的DOM操作功能
  2. Data->DOM 的 transformation

感觉D3的核心功能就这么两个，它的API也是为这两个而服务的，习惯了之后特别的简洁和自然。

DOM操作功能不必说，跟JQuery类似，对DOM的获取、属性修改等操作非常容易，不过D3强大的地方在于，由于是Data Driven的，对于DOM操作的动态性以及与数据的贴合性非常的好，使其在用DOM显示数据上有很大的优势！

第二项，非常的优秀！

Transformation, not Representation

这是D3的一个特性，其所有的显示，都是普普通通的DOM元素，图形是SVG之类的，没有自己的一套表现，D3的重点不在于此，而是在于转化上，将普通的数据，能够很便利的映射到DOM上，通过丰富的SVG的表现力，来呈现可视化图形。

加上许多D3的插件或者辅助功能，D3的能力被大幅的提升，比如d3-force，运用力引导图的算法布局图，然后运用d3来呈现出来，其实算法本身跟显示关系并不大，只需要将每个点的位置算出来即可，但是由于D3生态的丰富以及表现的方便，于是就与其结合了起来。现在去找一个力引导布局的算法，首选还是d3-force。

学习

没有找到官方的Tutorial，这很难过，D3的所有官方文档，都在GitHub Repo的wiki里：https://github.com/d3/d3/wiki 而其中的tutorial部分，其实就是一个awesome-list，虽然很多，但没有系统完整的，非常的不友好！

不过有几个东西还是很值得参考的：

  1. API Reference，不管什么，reference都是必须的，写的还算明白，不过不能拿来学习：https://github.com/d3/d3/blob/master/API.md
  2. Gallery：https://github.com/d3/d3/wiki/Gallery 现在应该所有的例子，都放在了Observable上，这是个类似于notebook的新玩意，似乎还挺好玩的
  3. Observable上的visualization collection：https://beta.observablehq.com/collection/@observablehq/visualization

目前打算是稍微看下Observable这个东西，然后挑感兴趣的例子去看如何实现，然后尝试自己写一些！

Posted on | Edited on | In |

一直对ES6都是知识了解其大致的feature，却从来没有用过，也不知道怎么用…
一直对前端的组织、打包不了解，类似Babel、Webpack、Browsify这些看着都是避而远之…
一直对React、Vue这些框架的使用都是套scaffold，根本不知道其中是怎样运作的，脱离了脚手架完全不会写…

可是，这样终归是不行的，终于下定决心去了解，去使用这些东西，真正接触现代的JavaScript！

浏览器script标签

好吧，我以前只知道script标签是把src中指的文件复制过来，现在发现自己已经火星了，去年chrome就支持了引入module，好吧，这样看来，如果就自己用新版的Chrome的话，一切变得简单起来~

写一个最简单的demo，虽然很直白，但毕竟纪念一下自己第一次使用module:

index.html:

1
2
3
4
5
6
7
8
9
10
11
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>test</title>
</head>
<body>
  hello world
  <script type="module" src="./index.js"></script>
</body>
</html>

index.js:

1
2
import * as a from './a.js'
console.log(a.aaa)

a.js:

1
export const aaa = 3

console:

1
3

可以看出，如果浏览器支持的话，只要加个type='module'就可以，不用什么编译工具呀，打包工具呀之类的。

Module怎么用？？？

其实目前自己对module的理解就是很不具体，可能就是能分成好多个文件写，避免一个文件写的太长；把一些公用的东西提出来，比如config、常数之类的供复用；隔离作用域之类的…

这些应该都是没有错的，可是真正让自己用的时候，就觉得，没那么简单，它到底是干什么用的？什么时候该用？什么时候不该用？有什么范式嘛？有什么best practice吗？

这些可能需要长期使用后才有体会吧，目前自己可以先学习一点..

这里，我觉得讲了一点比较具体的东西，感觉应该值得一看，这本书好像都挺不错的样子：
http://exploringjs.com/es6/ch_modules.html#sec_modules-in-javascript
http://exploringjs.com/es6/ch_modules.html#sec_design-goals-es6-modules

具体的，就不再说了，毕竟没有什么使用经验，以后可以补上…

编译与打包

前边提到的是直接浏览器标签type='module'来让js引入module。

  1. 如果要给用户用呢？用户的浏览器可是无法预知的..
  2. 标签引入是不是不怎么好呀，如果不是http/2的话，是不是还是打包下比较好？

自己虽然不懂第二点，但是目前这前端形势，第一条就决定了你除非是自己写着玩玩，否则必须使用编译到ES5以及打包的工具..

于是，自己要接触自己之前恐惧的名词了：Babel，Browsify，Rollup，Webpack…

这里自己看了一篇文风非常impressive的文章..感觉对新手来说还是很友好的：
https://blessing.studio/how-could-i-use-es6-modules-in-production/

其中这张图片比较好的说明了问题：

Babel转译工具

如果单纯的来说的话，Babel就是一个转译工具，把原来用ES6+的语法变成ES5的或者其它的，可是自己不解的地方在于，ES6支持的module，Babel是怎么变的？转译之后，又该如何使用呢？？

了解了一下，发现它好像是把module转换成CommonJS的规范，所以也不能直接script标签引入完事，而是要用一定的库，比如RequireJS，这个自己之后有时间再看吧，毕竟有了现成的打包工具把它变成一个bundle.js，我为何还要煞费苦心的处理这心转译之后的文件呢？还是看看一些打包工具吧。

Webpack打包工具

如果用一句话解释，就是官网上的slogan：

bundle your scripts
bundle your styles
bundle your assets
bundle your images

或者官网这张图：

-w1131

把有依赖的各种资源编程静态的assets，让我们不用考虑依赖之类的。

具体的如何整理依赖，tree-shaking什么的就先不管了，反正，最后给我一个bundle.js直接script引入就很合适~

具体的使用之后再补充吧。

TypeScript+Webpack

其实，我一直以为TypeScript和Babel是两个完全不相干的东西，也以为两者一般要同时使用，但后来经过了解发现，反着这俩都能够转换到ES5，所以用TS也不一定要用Babel~

那么就来入坑TS吧，配一个TypeScript+Webpack的前端项目环境吧，这样就可以优雅的支持Module了~~~

最简单的TS+Webpack配置Demo

文件结构：

1
2
3
4
5
6
7
8
9
10
11
.
├── dist
│   ├── bundle.js
│   └── index.html
├── package-lock.json
├── package.json
├── src
│   ├── bar.ts
│   └── index.ts
├── tsconfig.json
└── webpack.config.js

安装依赖包：

1
2
3
4
5
6
7
8
9
{
  ...
  "devDependencies": {
    "ts-loader": "^5.2.2",
    "typescript": "^3.1.3",
    "webpack": "^4.22.0",
    "webpack-cli": "^3.1.2"
  }
}

tsconfig.json

1
2
3
4
5
6
7
8
9
10
11
{
  "compilerOptions": {
    "outDir": "./dist/",
    "sourceMap": true,
    "noImplicitAny": true,
    "module": "es6",
    "target": "es5",
    "jsx": "react",
    "allowJs": true
  }
}

webpack.config.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const path = require('path');
module.exports = {
  entry: './src/index.ts',
  mode: 'production',
  devtool: 'inline-source-map',
  module: {
    rules: [
      {
        test: /\.tsx?$/,
        use: 'ts-loader',
        exclude: /node_modules/
      }
    ]
  },
  resolve: {
    extensions: ['.tsx', '.ts', '.js']
  },
  output: {
    filename: 'bundle.js',
    path: path.resolve(__dirname, 'dist')
  }
};

src/index.ts

1
2
3
import { greet } from './bar'
greet("world")

src/bar.ts

1
2
3
4
5
const greet = (a: String) => {
  console.log(`Hello ${a}`)
}
export { greet }

dist/index.html

1
2
3
4
5
6
7
8
9
10
11
12
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>test</title>
</head>
<body>
  Hello World
  <script src="bundle.js"></script>
</body>
</html>

执行：

1
npx webpack

bundle.js就生成了~

这个demo反正实现了webpack打包成一个单独的bundle.js文件，且是ES5的，这样一来就可以用高端的TypeScript了，感觉牛的不行，这已经达到了原来的功能。

如果用webpack来管理的话，思路和原来的是很不一样的，自己也需要重新学习webpack的思路与组织方式，这就放在之后的博客来说吧哈哈哈

Posted on | In , |

很经典的题目，以LeetCode上的4-Sum为例说明。

题目

https://leetcode.com/problems/4sum/description/

-w949

想法

递归的进行，把 k Sum 分解成 K-1 Sum，直到 2 Sum！！！

可能效率不是最高的，但代码应该是最清楚的

复杂度还是很高的，O( N^k-1 )

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
private:
    vector<vector<int>> kSum(vector<int>& nums, int target, int k, int start) {
        vector<vector<int>> res;
        if (nums.size() - start < k)
            return res;
        if (k == 2) {
            int l = start, r = nums.size() - 1;
            while (l < r) {
                if (nums[l] + nums[r] == target) {
                    res.push_back({nums[l], nums[r]});
                    l++;
                    while (l < r && nums[l] == nums[l - 1])
                        l++;
                    r--;
                    while (l < r && nums[r] == nums[r + 1])
                        r--;
                } else if (nums[l] + nums[r] < target) {
                    l++;
                } else {
                    r--;
                }
            }
        } else {
            int i = start;
            while (i < nums.size() - k + 1) {
                vector<vector<int>> subRes = kSum(nums, target - nums[i], k - 1, i + 1);
                if (!subRes.empty()) {
                    for (auto r : subRes) {
                        r.insert(r.begin(), nums[i]);
                        res.push_back(r);
                    }
                }
                i++;
                while (i < nums.size() && nums[i] == nums[i - 1])
                    i++;
            }
        }
        return res;
    }
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        return kSum(nums, target, 4, 0);
    }
};

Posted on | Edited on | In , |

数相关

1. 判断素数

2. GCD

线性结构相关

1. 二分查找

注意满足条件跳出的下标

low <= high
return low
…
视情况而定

树相关

1. AVL tree

记录height，记得更新height，四种旋转的方式

2. 并查集

findroot，union

初始化为-1，根中存的值为-size

图相关

1. Dijkstra

Posted on | Edited on | In , |

特殊格式

时间

通常转化为分钟数或秒数，也可以直接用字符串格式来比较，都是可以的

如果时间需要进行相互之间的运算，可以考虑用同一时间的偏移来表示，比如MM:DD:HH:MM:SS - 01:01:00:00:00，比如不同时间有不同权值，这样计算时会方便很多

多项式

数组表示，下标表示次幂，值表示系数，没有的值按0算

线性结构

链表

多用id - key - next的三元组表示，存储的时候直接开两个大数组，key和next，这样操作就跟普通链表没有什么区别了。

树

二叉树

根据前中、后中建树，递归实现：

1
Node *build(int posL, int posR, int inL, int inR);

根据 parent-left-right 建树

先开数组存所有节点，再根据关系，确定指针关系

多叉树

二维数组，a[i]表示根节点为i的子节点数组

图

二维数组

矩阵表示，如果没有权，那么用bool，有权值为权

Posted on | Edited on | In , |

iterator

1
2
3
4
prev(v.end())
next(it)
rbegin(v)
...

algorithm

sort

从大到小排序：

1
sort(a.begin(), a.end(), greater<int>());

vector

删除特定元素

1
v.erase(remove_if(v.begin(), v.end(), pred), v.end());

string

删除特定字符

1
s.erase(remove_if(s.begin(), s.end(), pred), s.end());

find

1
2
size_type pos = s.find(ch);
pos == string::npos ?

queue

priority_queue

1
2
3
4
5
6
struct X;
priority_queue<X, vector<X>, decltype(cmp)> pq(cmp);
priority_queue<X, vector<X>, greater<X>> pq;
pq.push();
pq.top();
pq.pop();

set

合并set

1
s1.insert(s2.begin(), s2.end());

numeric

accumulate

1
2
3
vector<string> vs;
string a;
string res = accumulate(vs.begin(), vs.end(), a);

Posted on | Edited on | In , |

1001 A+B Format

数计算，修改字符串，没什么好说的

emm，自己当年还是用JAVA写的，想想也是3年前了吧，唉，恍惚三年

1002 A+B for Polynomials

多项式存储，遍历即可

1003 Emergency

最短路径，同时有一些其它的权重，不过这里的people num局部最优就是全局最优，所以不用保存多条路径，还是比较常规的，标准的Dijkstra算法。

1004 Counting Leaves

数叶子节点，树的表示和遍历，BFS，DFS之类的
需要遍历的时候记录层数

1005 Spell It Right

数字每位处理，字符串映射，没什么特别的地方
（前边的题好简单啊发现）

1006 Sign In and Sign Out

时间格式的处理，找最大值最小值

1007 Maximum Subsequence Sum

很经典的一道题，计算最大子序列的和

可以用DP做，dp[i] = max(num[i], dp[i - 1] + num[i])

其实不用dp数组也没有问题，从左到右，如果加上之后比原来的大，就加上，否则继续看，需要累加变负的之后，置零，这本质上和DP是一样的，只不过更加trick罢了

1008 Elevator

模拟过程，挨个按照条件模拟就好了，没什么

1009 Product of Polynomials

字符串处理

1010 Radix

进制转换

这里要注意的是，需要使用二分查找，不然会超时

1011 World Cup Betting

阅读理解题

1012 The Best Rank

花式排序题

注意，有greater<int>()，省去了写lambda的麻烦

1013 Battle Over Cities

连通分量，DFS即可

注意计算的时候，需要记录visited，防止循环

cin超时我也是醉了。。。

1014 Waiting in Line

排队模拟题，最讨厌的题了，很烦很烦！

排队一般用queue，有优先级的注意可以使用priority_queue。

对问题的抽象在解决这类问题中很关键，不过自己的抽象能力并不强。

1015 Reversible Primes

进制转换，数的处理

判断素数（判断素数需要闭着眼睛写出来，还有GCD这些）

1016 Phone Bills

花式排序整理题，只不过这道题有点烦罢了，遇到这种题不要怕，通常都是阅读理解+时间处理之类的，题目理解对了就不会有什么坑了

这里算时间的时候，需要注意，可以用统一基准，这样方便比较和相互之间的运算

1017 Queueing at Bank

排队题，烦

priority_queue真好用

1018 Public Bike Management

最短路径问题，不过这里不能直接得出最优的一条路径，而是要得到所有最短路径，然后DFS找到最优的

注意理解题意吖！！！

1019 General Palindromic Number

进制转换，没什么

1020 Tree Traversals

后中建树，需要熟练使用

1021 Deepest Root

这道题用到了知识性的东西，一开始自己并不知道。

最深的路径，从任意一个点遍历，找到最深的节点，然后从这些节点中任意一个开始遍历，找到最深的节点集合就是了

1022 Digital Library

花式IO、排序、查询题

没想到暴力就能解决，本来还担心超时

1023 Have Fun with Numbers

数的处理，遇到这种题真的开心的要死！

1024 Palindromic Number

数处理，字符串处理，这种题，最好循规蹈矩的来，相对还是比较简单的

1025 PAT Ranking

花式排序题，阅读理解题，不说了，注意看清题意

1026 Table Tennis

唯一一道，没有自己做的题目！！！

花式排队题！！！真的是很烦！

还是自己对问题的抽象能力不够，不过不想看它了，这应该是模拟排序题里的极品了吧，碰到像这样的我认栽。

1027 Colors in Mars

数字转换，开心hhh，基本也没有什么坑

1028 List Sorting

花式排序题，没什么，这个很常规，就是写个lambda就好了。

1029 Median

毕竟LeetCode上hard级别的题目

自己做的时候确实没有做出来

很经典很经典！！！

根据中位数的定义，是中间的那个数
由于有内存限制，所以只能存1个，另一个需要在线处理，也就是边读，边判断是不是合适，如果arr1里的大，选arr1里的，对应cnt1++，如果此数大，选此数，对应cnt2++。

实现起来也是很精妙的！！！

1030 Travel Plan

标准的Dijkstra，不说了，做了这么多，也背过了，包括处理cost，记录路径等等。

1031 Hello World for U

数数，字符串处理，格式输出，没什么，送分题吧，注意特殊条件的考虑，哪怕列举呢，反正没多少

1032 Sharing

链表格式需要注意一下，剩下的就很常规了

1033 To Fill or Not to Fill

还是比较有技巧的一道题，贪心地一段一段往上加

虽然很暴力，但是也可以AC，聪明点的做法是从起点开始，找可以到达范围内的加油站，遇到比自己低的，就用低的走接下来的路，直到走不下去或者结束

1034 Head of a Gang

DFS，连通分量

不过这道题还是挺烦的吧，需要求最大的节点，遍历的过程中求就是了，只是有点烦，不至于不知道如何下手

1035 Password

字符串处理，送分题

1036 Boys vs Girls

花式排序，花式格式题

注意特殊情况的考虑就好

1037 Magic Coupon

唉，就，小trick而已，问题转换，求乘积最大值

1038 Recover the Smallest Number

很经典的一道题

自己刚开始想的很多，不过，后来发现，用贪心的策略就可以解决了，局部最优就是全局最优！排序就对了！

1039 Course List for Student

map的使用，计数，注意可能出现的超时问题

这里有个技巧，如果名字是string不好处理的话，可以考虑hash到对应的整数

1040 Longest Symmetric String

没想到，分奇数长度和偶数长度暴力判断就可以AC哈哈

1041 Be Unique

set或者map的使用，没有什么好说的，遇到这种题估计会开心的要死

1042 Shuffling Machine

字符串转换

这个题需要厘清，到底是从什么转换到什么，很容易搞混

1043 Is It a Binary Search Tree

前序转后序，一开始的时候不熟练，后来遇到的时候也就知道了，递归的进行左子树和右子树

BST性质不担心，按照这样的规则，不符合BST自然不会被加入到tree中

1044 Shopping in Mars

哈哈，碰到“Mars”就要小开心了，多半有时字符串处理啊，进制转换类的题目，至少不会很难。

没想到，这个竟然不是！！！

两个指针，左右，扫一遍就可以了。

1045 Favorite Color Stripe

非常经典的一道题！！！

考虑输入的时候就筛掉不符合要求的数据。

DP之中的经典，当前最长，是对之前所有的j, max(len[i], len[j] + 1)

DP还是难想啊！！！

1046 Shortest Distance

两指针问题

先正遍历一遍求与左边距离，再逆遍历一遍求与右边距离，两者的距离就是中间那段或者距左右两端的和

1047 Student List for Course

跟前边一道题正好相反，也是map的使用，不过，不知道为什么，map会超时，直接开个大数组来的直接红红火火恍恍惚惚

1048 Find Coins

超经典问题，2SUM

左右指针，往中间靠就好，总会找到的

相关的升级版3Sum也是超级经典的问题

1049 Counting Ones

可以说是很经典了，但同时也可以说是很无聊了

这种题感觉背过就可以了，也不会变出什么花样，思想是非常好的，需要好好借鉴

数每一位出现1的次数

1050 String Subtraction

set使用，这里需要记住删除字符串中的字符的使用方式

1051 Pop Sequence

按照题目的要求模拟就好了

我当时做的时候真的是想多了，想的进展序列是前序，出栈序列是中序，还写了个check前中hhh

1052 Linked List Sorting

hhh，直接无视list，排序就好，反正根据排序序列就知道下一个是啥

不过要注意的是，还是要先根据list把在list中的数据放到新数组中，输入中可能有无效数据

1053 Path of Equal Weight

树的遍历，DFS，计算weight，比较常规

1054 The Dominant Color

数数就好了，遇到这种题，肯定开心的要死

1055 The World’s Richest

花式排序题，本来还担心超时，但后来发现，其实还好

1056 Mice and Rice

模拟题，这道题还是很烦的，需要使用到queue来模拟一层一层的操作，不过也没有什么好注意的，认真读题，想最恰当的方式模拟就好了。

1057 Stack

这道题还是值得关注的！

有多种解法吧。

自己采用的是两个set平分栈中的元素，其实有些trick吧，就是利用了set的有序性，这样取中间数，只需要找set1的尾元素或set2的头元素即可。

由于可能有相同的元素，需要用到multiset。

1058 A+B in Hogwarts

进制转换 送分题

1059 Prime Factors

素数，分解因式，没什么

1060 Are They Equal

字符串浮点数处理，贼烦，注意考虑的点很多，比如leading zero，小数点，有效位数等等，耐心的一种情况一种情况考虑，题目本身没什么难度

1061 Dating

阅读理解题，不予评述

1062 Talent and Virtue

花式分类排序题，理解清题意，大致就没有问题了

1063 Set Similarity

set的使用，还好，挨个check就好，不会超时

1064 Complete Binary Search Tree

还是值得注意的一道题，用到了完全二叉树的性质

中序为从大到小的序列，可以递归的进行
层次遍历，就是数组的顺序，所以没什么，只要根据中序把对应的值放对就可以了

1065 A+B and C (64bit)

溢出的判断，仔细考虑溢出的情况

1066 Root of AVL Tree

AVL操作，应该已经可以背过了，闭着眼睛要能写出来

1067 Sort with Swap(0, i)

分两种情况，分开模拟就是了

1068 Find More Coins

经典！经典！经典！

背包问题，DP解决

这道题需要自己再次回味！！！

1069 The Black Hole of Numbers

模拟运算，没什么好说的

1070 Mooncake

理解清题意哇！！！

仔细注意题中的条件，不能只看输入输出！！！

1071 Speech Patterns

map操作，字符串处理，计数

按照题意来就好了，没什么

1072 Gas Station

比较有趣的一道题

标准的Dijkstra，再加上特定条件的判断，还好

1073 Scientific Notation

字符串处理，需要注意，负号，小数点，0等特殊情况

1074 Reversing Linked List

链表处理，还好，就是有点烦，不过对于头尾特殊情况处理好，想清楚就没什么了

1075 PAT Judge

花式排序题，不做评价

1076 Forwards on Weibo

BFS

对于marker的使用需要注意，应该是，遇到marker出队列，而队列仍然不为空的时候放入新的marker

1077 Kuchiguse

字符串处理，共同后缀，遍历判断就好了，也没什么

1078 Hashing

没什么吧，hash的概念，注意加增量是在原来的hash值上加，不是累加

1079 Total Sales of Supply Chain

树DFS遍历求最值，没啥

1080 Graduate Admission

花式排序题，不做评述

1081 Rational Sum

唉，这类题也挺烦的

首先求gcd必须闭着眼睛也能写得出来

其次，按个数输出要考虑到，比如，有整数没分数，有分数没整数，为零的情况等等！！

1082 Read Number in Chinese

按照汉语的4位一个单位进行就可以了，每四位是一致的~

这种题估计不会考第二次了吧，可能考一个反的？？那应该会更简单吧

还是要注意，0的情况，直接输出0

1083 List Grades

花式排序判断题，没有什么

1084 Broken Keyboard

直接查找都可以，用set可能会更快些，送分题

1085 Perfect Sequence

这道题还是有点意思的

因为线性搜索会超时，需要用到二分查找，注意二分查找符合条件的下标，最后是取low还是high

1086 Tree Traversals Again

标准的栈操作和树遍历的结合，也就是前中转后，固定写法一定要熟练的写出

1087 All Roads Lead to Rome

Dijkstra+一堆奇奇怪怪的优先级

比较烦，而且输入是字符，还需要转换一下

注意如果遇到特定条件之后，更新对应的值，比如路径的数组啦，最大值啦，最小值啦，该清空，还是该加入等

1088 Rational Arithmetic

这道题是一道极烦的字符串数字运算题目，需要考虑的很多，没有办法，如果考试遇到这个我认栽

没有什么特别要注意的，注意考虑除数为0的情况，以及，能化简先化简，否则有可能中间运算溢出

1089 Insert or Merge

唉，这道题，本来没有那么麻烦，只不过自己遇到的bug特别难发现罢了。

注意考虑数相等的情况！！！！

1090 Highest Price in Supply Chain

树的表示与DFS，还是比较常规的

1091 Acute Stroke

DFS题目，用BFS超内存了，不知道为什么，看来还是DFS比较靠谱

1092 To Buy or Not to Buy

没什么，遍历计数即可

1093 Count PAT’s

挨个计数就可以了，需要想一下，不过还算好想

1094 The Largest Generation

树最大深度，DFS、BFS均可，想想当年还青涩，BFS还用两个queue，来回倒hhh

1095 Cars on Campus

花式排序题，就是有点烦，其它还好

1096 Consecutive Factors

没什么，遍历，符合的话，就继续找就是了，应该有更巧的方法，不过AC了，也就没有管了

1097 Deduplication on a Linked List

本身的处理很常规，但是找bug花了很长时间

唉，bug也很无语，是自己一个没注意，没有办法，智能自己注意咯

1098 Insertion or Heap Sort

这俩排序特征还是比较好找的

边界条件注意，< 和 <= 经常自己被坑在等号上

1099 Build A Binary Search Tree

按照给定的结构建树，然后，中序遍历一遍，得到节点的指针，再按顺序赋值就OK啦

中序遍历什么的，用递归方式就好啦，省的自己用栈操作有问题

1100 Mars Numbers

字符串处理转换，没什么，string操作有点烦，需要考虑空格

1101 Quick Sort

左右扫两遍，还是很经典的一道题，不过知道了之后，就觉得还好啦

当时遇到了一个格式错误的测试点，后来多输出一个空行就好了，唉，算了，这OJ

1102 Invert a Binary Tree

树的遍历，真的是非常常规的题目了

1103 Integer Factorization

这道题坑了自己很久，死活有个点过不去

后来发现，是自己在维护maxSum的时候，没有更新

唉，只有一个点过不去，以为是边界条件，没想到是这样的bug，防不胜防啊，只能自己细心点喽

1104 Sum of Number Segments

数学题，找规律也可以，不是很难找

1105 Spiral Matrix

维护方向，模拟向前走就可以了

1106 Lowest Price in Supply Chain

也是树的遍历，就不多说什么了，这一系列的题都还好

1107 Social Clusters

并查集的经典考法，唉，PAT之前都没有考过并查集，从这道题开始，考了有两三道

因为要输出最后的结果，所以用set存了，注意set的合并操作

1108 Finding Average

字符串处理题，唉，就是有点烦，其它还好

1109 Group Photo

按照题目中给的要求划分求解就好，注意要细心，不然找bug需要很久！！

1110 Complete Binary Tree

BFS判断即可，没有什么

1111 Online Map

两遍Dijkstra即可，没有什么特别的地方，除了打字多一点之外

1112 Stucked Keyboard

字符串处理

有一些情况还是很难分清楚的，注意处理每一步都自习一点

1113 Integer Set Partition

emm，排序一遍就好，反正就两种情况，送分题

1114 Family Property

又是一道并查集，跟之前的那个基本一样，根节点维护相关的信息即可，union的时候也更新信息

1115 Counting Nodes in a BST

BFS即可，比较简单

1116 Come on! Let’s C

花式排序判断题

1117 Eddington Number

计数，最大值，没有什么特别的地方

1118 Birds in Forest

又是一道并查集 不过这个比较简单，不需要维护什么，只需要检测是不是一个根就可以了

1119 Pre- and Post-order Traversals

前后转中，同时判断是不是unique

还是蛮经典的一道题，主语判断非唯一的条件，就是没有右子树，想放到左边或右边都可以

1120 Friend Numbers

数字处理，送分题，开心

1121 Damn Single

map，集合使用，没有什么特别的地方

1122 Hamiltonian Cycle

图，判断，没有什么特别

1123 Is It a Complete AVL Tree

AVL tree的操作

判断完全二叉树

就是写的有点多，其实还好

1124 Raffle for Weibo Followers

花式计数题

1125 Chain the Ropes

贪心，priority_queue真好用

1126 Eulerian Path

数度数就好了

注意还要判断是不是联通图，如果不是，那自然没有欧拉路径了

1127 ZigZagging on a Tree

中后建树
BFS

都比较常规，需要熟练掌握

1128 N Queens Puzzle

数学题吧，反正，很水就是了

1129 Recommendation System

每次更新信息，重新sort，可以说是相当暴力了，不过没超时，那就可以了，OJ，本来就是面向AC得嘛

1130 Infix Expression

树的中序遍历，没啥

注意单个值的考虑

1131 Subway Map

相当之烦的一道关于图的题，可以说是这类题中的极品了，坑也肯多，调bug调了好久

需要注意的是，不能随便选择一条最短的，还要找换乘少的，换乘也是可以从不同路线中选的，所以，唉，坑啊

1132 Cut Integer

字符串数字处理，没啥

1133 Splitting A Linked List

链表处理

本来没啥，可是自己写的时候遇到了bug，后来发现是自己智障了，为null的判断需要时判断是否为-1而不是0

1134 Vertex Cover

需要注意，不是所有的图都用邻接矩阵存，用二维数组，存相邻节点也就OK了

1135 Is It A Red-Black Tree

树，遍历判断，没啥

1136 A Delayed Palindrome

字符串、数字处理，这些基本上都不会有什么大坑

1137 Final Grading

花式排序题，不想说些什么了

1138 Postorder Traversal

前中转后，还更省事，只用输出第一个元素，开心

1139 First Contact

图的题目，阅读理解题，还是比较常规的

注意考虑自身情况，唉，可能还是理解题意的问题

1140 Look-and-say Sequence

阅读理解题，唉，只有好好读题了

1141 PAT Ranking of Institutions

花式排序统计题，没啥的

1142 Maximal Clique

这道题，还是有些意思的！！

求强连通分量！

合并集合太浪费时间了，还是循环比较来的比较直接，应该有更好的算法，需要学习一个

1143 Lowest Common Ancestor

先要根据前序建树，烦

然后要查找，烦

然后要判断LCA，烦

就是烦，其它的都还好

唉，其实有更直接的解法，不过自己没想到，就老老实实一步一步做喽，反正也是很机械的事

1144 The Missing Number

数数，没啥

1145 Hashing - Average Search Time

这道题还是挺烦的，考到了hash的一些概念

虽然试也能试出结果

平方探测，增量是从 0^2 到 size^2 size+1次

1146 Topological Order

暴力的，visit之后，就把相关的所有边去掉，竟然AC了hhh

其实，只要记录入度就可以了，没必要记录整个信息

1147 Heaps

DFS或BFS判断就是了，没啥

然后后序遍历也没啥

Posted on | In , |

题目

https://leetcode.com/problems/longest-increasing-subsequence/description/

-w948

想法

LIS

1
2
3
4
5
dp[N] = {1,}
for i 0..N:
    for j 0..i:
        if num[j] < num[i]:
            dp[i] = max(dp[i], dp[j] + 1)

很经典的DP，唉，DP就是这样，没想到的时候，怎么也觉得不顺，想到了，好优雅的设计
这是O( N^2 )的解法，还有O( NlogN )的解法，有时间再看

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty())
            return 0;
        vector<int> dp(nums.size(), 1);
        int res = 0;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};

Posted on | In , |

题目

https://leetcode.com/problems/number-of-digit-one/description/

-w956

想法

这道题的解法有多种，看discussion就会知道花样百出。

一开始想的是，9，99，999…之间的递推关系，但是，这并不好表示一个不整的数，discussion中也有类似的解答，但是一下子也没有看明白。

换了思路之后，参考了 https://leetcode.com/problems/number-of-digit-one/discuss/64382/JavaPython-one-pass-solution-easy-to-understand 这个解法。

计算在某一位1出现的次数，累加起来

而某一位出现1的次数分为3中情况：

对于数AxB，其中A表示x之前的数，B表示x之后的数，例如123456，x为4的话，A = 123，B = 56.
以下假设B有2位：

三种情况

  1. x == 0: A 100
    先看前半部分：Ax，如果递减此数，那么，A每减1，x都会出现0-9中的数，那么也就是说，A减到0，减了A次，x处就出现了A次1.
    然后看后半部分，因为高位减下来的，低位肯定会有00-99，也就是100个，组合以下，就是A    100了
  2. x > 1: A * 100 + 100
    按照上边的情况，还多了不用减A部分，直接减x到1，又有100
  3. x == 1: A * 100 + B + 1
    这种情况比较复杂，除了第一种情况之外，还有当Ax不变的时候，可能的情况。此时，低位可以从0数到B，总共B+1次，所以加上B+1

边界条件

如果x是最低位：
对应的乘的系数是1，B为0，符合条件

如果x为最高位：
A为0，三种情况都符合

实现

实现的代码还是很精巧的，如何计算A和B，都有很好的处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int countDigitOne(int n) {
        if (n == 0)
            return 0;
        int res = 0;
        int x = 1;
        int origin = n;
        do {
            int r = n % 10;
            n /= 10;
            res += n * x;
            if (r == 1) {
                res += origin % x + 1;
            } else if (r > 1) {
                res += x;
            }
            x *= 10;
        } while (n > 0);
        return res;
    }
};