给定一个有 n 个节点的有向无环图，节点编号从 1 到 n。请编写一个程序，找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示
输入描述 > 第一行包含两个整数 N，M，表示图中拥有 N 个节点，M 条边 > 后续 M 行，每行包含两个整数 s 和 t，表示图中的 s 节点与 t 节点中有一条路径
输出描述 >
输出所有的可达路径，路径中所有节点之间空格隔开，每条路径独占一行，存在多条路径，路径输出的顺序可任意。如果不存在任何一条路径，则输出
-1。 > 注意输出的序列中，最后一个节点后面没有空格！ 例如正确的答案是
1 3 5,而不是 1 3 5， 5后面没有空格！
1 | #include<iostream> |
求雨水高度，需要弹出当前池底值，再求两边最小：min(凹槽左边高度,
凹槽右边高度) - 凹槽底部高度 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public:
int trap(vector<int>& height) {
int water = 0;
stack<int> st;
st.push(0);
for(int i = 1; i < height.size(); i++){
while(!st.empty() && height[i] > height[st.top()]){
int mid = st.top();
st.pop();
if(!st.empty()){
int h = min(height[i], height[st.top()]) - height[mid];
int w = i - st.top()-1;
water += h * w;
}
}
st.push(i);
}
return water;
}
};
这题我初步想法是对于每个柱，求以它为高度的最大矩形。但是具体怎么用类似前后缀表的方法优化查询，我有点没思路。
看了题解反应过来还是要用单调栈求区间的宽和高，同时因为我们要弹出一个元素来获取左边元素的下标，为了头尾元素能顺利出栈，需要在前后都加入0
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
26class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> st;
int max_h = 0;
heights.insert(heights.begin(), 0);
heights.push_back(0);
st.push(0);
for(int i = 1; i < heights.size(); i++){
if(heights[i] >= heights[st.top()]){
st.push(i);
}else{
while(!st.empty() && heights[i] < heights[st.top()]){
int mid_i = st.top();
st.pop();
int left_i = st.top();
int w = i - left_i - 1;
int h = heights[mid_i];
max_h = max(max_h, w * h);
}
st.push(i);
}
}
return max_h;
}
};
维护一个栈来记录未更新的数组值
using xx = xxxx仅可用于为现有变量创建别名，如果数组变量名太长请创建引用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
stack<int> st;
vector<int> out_v(temperatures.size(), 0);
st.push(0);
for(int i = 1; i < temperatures.size(); i++){
if(temperatures[i] <= temperatures[st.top()]){
st.push(i);
}else{
while(!st.empty() && temperatures[i] > temperatures[st.top()]){
out_v[st.top()] = i - st.top();
st.pop();
}
st.push(i);
}
}
return out_v;
}
};
和上一题很像的思路，但是需要借助两个数组都没有重复数字的假设构造map，使答案不超时
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#include<unordered_map>
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int>mp;
for(int i = 0; i < nums1.size(); i++){
mp[nums1[i]] = i;
}
vector<int> ng(nums1.size(), -1);
stack<int> st;
st.push(0);
for(int i = 1; i < nums2.size(); i++){
while(!st.empty() && nums2[i] > nums2[st.top()]){
int ntop = nums2[st.top()];
if(mp.find(ntop) != mp.end()){
ng[mp[ntop]] = nums2[i];
}
// cout<<endl;
st.pop();
}
st.push(i);
}
return ng;
}
};
我想的是找到最大的元素，从下一个数开始遍历一遍，不过看题解直接遍历两遍数组即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> res(nums.size(), -1);
// int max_n = nums[0];
// int max_i = 0;
// for(int i = 0; i < nums.size(); i++){
// if(nums[i] > max_n){
// max_n = nums[i];
// max_i = i;
// }
// }
stack<int> st;
st.push(0);
for(int j = 1; j < nums.size()*2; j++){
int n_i = j % nums.size();
while(!st.empty() && nums[n_i] > nums[st.top()]){
res[st.top()] = nums[n_i];
st.pop();
}
st.push(n_i);
}
return res;
}
};
首先是找到递推关系，对于字符串中下标i-j的字串，如果s[i] == s[j]则可以由dp[i+1][j-1]推出dp[i][j]
然后是遍历顺序，因为要先知道dp[i+1][j-1]，所以要从下往上，从左至右遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
int countSubstrings(string s) {
vector<vector<bool>> dp(s.size(),vector<bool>(s.size(), false));
int cnt = 0;
for(int i = s.size()-1; i >= 0; i--){
for(int j = i; j < s.size(); j++){
if(s[i] != s[j]){
dp[i][j] = false;
}else{
if(j - i <= 1){
dp[i][j] = true;
cnt++;
}else{
dp[i][j] = dp[i+1][j-1];
if(dp[i][j] == true)cnt++;
}
}
}
}
return cnt;
}
};
和上一题思路类似 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public:
int longestPalindromeSubseq(string s) {
vector<vector<int>>dp(s.size(), vector<int>(s.size(),0));
for(int i = s.size()-1; i >= 0; i--){
for(int j = i; j < s.size(); j++){
if(s[i] != s[j]){
dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
}else{
if(i == j){
dp[i][j] = 1;
}else if(i - j == 1){
dp[i][j] = 2;
}else{
dp[i][j] = dp[i+1][j-1]+2;
}
}
}
}
return dp[0][s.size()-1];
}
};
DNS 用来将主机名和域名转换为IP地址, 其查询过程一般通过以下步骤：
本地DNS缓存检查：首先查询本地DNS缓存，如果缓存中有对应的IP地址，则直接返回结果。 如果本地缓存中没有，则会向本地的DNS服务器（通常由你的互联网服务提供商（ISP）提供， 比如中国移动）发送一个DNS查询请求。 如果本地DNS解析器有该域名的ip地址，就会直接返回，如果没有缓存该域名的解析记录，它会向根DNS服务器发出查询请求。根DNS服务器并不负责解析域名，但它能告诉本地DNS解析器应该向哪个顶级域（.com/.net/.org）的DNS服务器继续查询。 本地DNS解析器接着向指定的顶级域名DNS服务器发出查询请求。顶级域DNS服务器也不负责具体的域名解析，但它能告诉本地DNS解析器应该前往哪个权威DNS服务器查询下一步的信息。 本地DNS解析器最后向权威DNS服务器发送查询请求。 权威DNS服务器是负责存储特定域名和IP地址映射的服务器。当权威DNS服务器收到查询请求时，它会查找"example.com"域名对应的IP地址，并将结果返回给本地DNS解析器。 本地DNS解析器将收到的IP地址返回给浏览器，并且还会将域名解析结果缓存在本地，以便下次访问时更快地响应。 浏览器发起连接： 本地DNS解析器已经将IP地址返回给您的计算机，您的浏览器可以使用该IP地址与目标服务器建立连接，开始获取网页内容。
CDN是一种分布式网络服务，通过将内容存储在分布式的服务器上，使用户可以从距离较近的服务器获取所需的内容，从而加速互联网上的内容传输。
就近访问：CDN 在全球范围内部署了多个服务器节点，用户的请求会被路由到距离最近的 CDN 节点，提供快速的内容访问。 内容缓存：CDN 节点会缓存静态资源，如图片、样式表、脚本等。当用户请求访问这些资源时，CDN 会首先检查是否已经缓存了该资源。如果有缓存，CDN 节点会直接返回缓存的资源，如果没有缓存所需资源，它会从源服务器（原始服务器）回源获取资源，并将资源缓存到节点中，以便以后的请求。通过缓存内容，减少了对原始服务器的请求，减轻了源站的负载。 可用性：即使某些节点出现问题，用户请求可以被重定向到其他健康的节点。
题目描述：
输入一串存储的数据，用N表示数据个数，用K表示数据块的大小，设计一个方法判断当前数据块是否和前面的数据块有重复，两个数据块内容完全一样则表示重复，如果重复则将这个数据块删除，并且在第一个出现数据块的后面增加重复数据的计数，输出经过重删之后的数据内容。
输入示例： 输出示例： 1
2
38
3
3 4 5 3 4 5 5 41
3 4 5 2 5 4 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
47
48
49
50
51
52#include <map>
#include <vector>
#include <iostream>
using namespace std;
int main(){
int total;
int len;
int c;
vector<int> data;
cin>>total>>len;
while(cin>>c){
data.push_back(c);
}
map<vector<int>, int> mp;
vector<vector<int>> uniqueBlock;
vector<bool> isUnique;
for(int i = 0; i < data.size(); i+=len){
int cnt = 0;
vector<int> block;
while(cnt < len && (i+cnt) < data.size()){
block.push_back(data[i+cnt]);
// cout<<"pushed in block: "<<data[i+cnt]<<endl;
cnt++;
}
// cout<<endl;
mp[block]++;
if(mp[block] == 1){
isUnique.push_back(true);
}else{
isUnique.push_back(false);
}
uniqueBlock.push_back(block);
}
for(int i = 0; i < uniqueBlock.size(); i++){
if(isUnique[i] == true){
for(int n: uniqueBlock[i]){
cout<<n<<' ';
}
cout<<mp[uniqueBlock[i]]<<' ';
}
}
// cout<<endl;
// cout<<"total data: "<<total<<endl;
// cout<<"len of blocks: "<<len<<endl;
// for(int i: data){
// cout<<i<<' ';
// }
// cout<<endl;
}
这回笔试，我选择寄得比算法多（好久没刷八股题了=_=||），某境外电商的算法还是相对简单的
REPEATABLE READ
sort库函数怎么传递比较参数（比如我不需要默认的从小到大，而是从大到小该怎么办） 怎么构造并使用大/小顶堆
打包员有m个相同重量上限k的袋子，需要打包weights数组个物品，这些物品一定是从前向后依次打包的，已知物品个数n, 每个物品重量的数组weights,求k的最小值
这个我本来以为需要背包算法，后来发现二分查找就可以了
这题我想到要对于t的每个字符，一在s里匹配到，就从两串的下一个字符开始往后匹配。这么一看感觉开始递归了，不太动态规划。
题解的递推公式如下： 这一类问题，基本是要分析两种情况 -
s[i - 1] 与 t[j - 1]相等 -
s[i - 1] 与 t[j - 1] 不相等
当s[i - 1] 与
t[j - 1]相等时，dp[i][j]可以有两部分组成。 -
一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母，所以只需要
dp[i-1][j-1]。 -
一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。
当s[i - 1] 与
t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素），即：dp[i - 1][j]
注意上限长度且所有字符一样的s和t，会使得dp超long long的限制，此时使用uint64_t
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
27class Solution {
public:
int numDistinct(string s, string t) {
vector<vector<uint64_t>> dp(t.size()+1, vector<uint64_t>(s.size()+1,0));
// dp[0][0] = 1;
for(int i=0; i<s.size();i++){
if(s[i] == t[0])dp[0][i] = 1;
}
for(int i=1; i<=t.size(); i++){
for(int j=1; j<=s.size(); j++){
if(s[j-1] == t[i-1]){
dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
// if(i == 1)dp[i][j] = max(dp[i][j], 1);
}else{
dp[i][j] = dp[i][j-1];
}
}
}
// for(auto c:dp){
// for(int c_i : c){
// cout<<c_i<<' ';
// }
// cout<<endl;
// }
return dp[t.size()][s.size()];
}
};
和上一题有些类似的思路 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1,0));
for(int i = 1; i <= word1.size(); i++)dp[i][0] = i;
for(int j = 1; j <= word2.size(); j++)dp[0][j] = j;
for(int i = 1; i <= word1.size(); i++){
for(int j = 1; j <= word2.size(); j++){
if(word1[i-1] == word2[j-1]){
dp[i][j] = dp[i-1][j-1];
}else{
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1;
dp[i][j] = min(dp[i][j], dp[i-1][j-1]+2);
}
}
}
// for(auto line : dp){
// for(auto i : line){
// cout<<i<<' ';
// }
// cout<<endl;
// }
return dp[word1.size()][word2.size()];
}
};
跟上两题差不多的思路，差点就写对了 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
27class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));
for(int i = 0; i < word1.size(); i++)dp[i+1][0] = (i+1);
for(int i = 0; i < word2.size(); i++)dp[0][i+1] = (i+1);
// dp[0][0] = 1;
for(int i = 1; i <= word1.size(); i++){
for(int j = 1; j <= word2.size(); j++){
if(word1[i-1] != word2[j-1]){
dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1);
dp[i][j] = min(dp[i][j], dp[i-1][j-1]+1);
}else{
dp[i][j] = dp[i-1][j-1];
}
}
}
// for(auto line : dp){
// for(int i : line){
// cout << i << ' ';
// }
// cout << endl;
// }
return dp[word1.size()][word2.size()];
}
};
按照动态规划，每次比较成功就加一，取所有值最大的思路是错的，这种会把乱序但是相同的字符也算进去。
于是我想了半天怎么先循环以i,j为右下角的正方形，本来想的是记忆化将i,j赋值为比较后相等的值，看了题解发现得在递推公式上作更改
因为字符中间可能会插入别的字符，所以ac,ace的比较结果和ac,aced的比较结果是一样的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
vector<vector<int>> dp(text1.size()+1, vector<int> (text2.size()+1, 0));
for(int i = 1; i <= text1.size();i++){
for(int j = 1; j <= text2.size(); j++){
if(text1[i-1] == text2[j-1]){
dp[i][j] = dp[i-1][j-1]+1;
}else{
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[text1.size()][text2.size()];
}
};
既然一个数只能连一根线，那么其实和上一题是一个意思了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp(nums1.size()+1, vector<int> (nums2.size()+1, 0));
for(int i = 1; i <= nums1.size(); i++){
for(int j = 1; j <= nums2.size(); j++){
if(nums1[i-1] == nums2[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}else{
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[nums1.size()][nums2.size()];
}
};
我想的是，dp[i]由dp[i-1],dp[i-1]+nums[i],nums[i]中的最大值决定，但是这样解会算出不连续的最大值
题解的推算法是这样的： dp[i]只有两个方向可以推出来： -
dp[i-1] + nums[i]，即：nums[i]加入当前连续子序列和
- nums[i]，即：从头开始计算当前连续子序列和
再找每个的dp[i]最大值 1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public:
int maxSubArray(vector<int>& nums) {
vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
int res = nums[0];
for(int i = 1; i < nums.size(); i++){
dp[i] = max(dp[i-1]+nums[i], nums[i]);
if(dp[i] > res)res = dp[i];
}
return res;
}
};
常规做的话双指针法即可，按照动态规划来做是和第一题是差不多的思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
bool isSubsequence(string s, string t) {
vector<vector<int>> dp(s.size()+1, vector<int>(t.size()+1, 0));
for(int i = 1; i <= s.size(); i++){
for(int j = 1; j <= t.size(); j++){
if(s[i-1] == t[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}else{
dp[i][j] = dp[i][j-1];
}
}
}
return dp[s.size()][t.size()] == s.size() ? true : false;
}
};
第一次握手：客户端向服务器发送一个SYN （同步序列编号）报文，请求建立连接，客户端进入SYN_SENT 状态。 第二次握手：服务器收到SYN 报文后，如果同意建立连接，则会发送一个SYN-ACK （同步确认）报文作为响应，同时进入SYN_RCVD 状态。 第三次握手：客户端收到服务器的SYN-ACK 报文后，会发送一个ACK （确认）报文作为最终响应，之后客户端和服务器都进入ESTABLISHED 状态，连接建立成功。
(2)为什么需要三次握手 因为TCP需要简历双向的数据连接。通过三次握手，客户端和服务器都能够确认对方的接收和发送能力。第一次握手确认了客户端到服务器的通道是开放的；第二次握手确认了服务器到客户端的通道是开放的；第三次握手则确认了客户端接收到服务器的确认，从而确保了双方的通道都是可用的。
而如果仅使用两次握手，服务器可能无法确定客户端的接收能力是否正常，比如客户端可能已经关闭了连接，但之前发送的连接请求报文在网络上延迟到达了服务器，服务器就会主动去建立一个连接，但是客户端接收不到，导致资源的浪费。而四次握手可以优化为三次。
（1）四次挥手的过程
第一次挥手：客户端发送一个FIN报文给服务端，表示自己要断开数据传送，报文中会指定一个序列号 (seq=x)。然后,客户端进入FIN-WAIT-1 状态。 第二次挥手：服务端收到FIN报文后，回复ACK报文给客户端，且把客户端的序列号值+1，作为ACK报文的序列号(seq=x+1)。然后，服务端进入CLOSE-WAIT(seq=x+1)状态，客户端进入FIN-WAIT-2状态。 第三次挥手：服务端也要断开连接时，发送FIN报文给客户端，且指定一个序列号(seq=y+1)，随后服务端进入LAST-ACK状态。 第四次挥手：客户端收到FIN报文后，发出ACK报文进行应答，并把服务端的序列号值+1作为ACK报文序列号(seq=y+2)。此时客户端进入TIME-WAIT状态。服务端在收到客户端的ACK 报文后进入CLOSE 状态。如果客户端等待2MSL没有收到回复，才关闭连接。
（2）为什么需要四次挥手
TCP是全双工通信，可以双向传输数据。任何一方都可以在数据传送结束后发出连接释放的通知，待对方确认后进入半关闭状态。 当另一方也没有数据再发送的时候，则发出连接释放通知，对方确认后才会完全关闭 TCP 连接。因此两次挥手可以释放一端到另一端的TCP连接，完全释放连接一共需要四次挥手。
只有通过四次挥手，才可以确保双方都能接收到对方的最后一个数据段的确认，主动关闭方在发送完最后一个ACK后进入TIME-WAIT 状态，这是为了确保被动关闭方接收到最终的ACK ，如果被动关闭方没有接收到，它可以重发FIN 报文，主动关闭方可以再次发送ACK 。
而如果使用三次挥手，被动关闭方可能在发送最后一个数据段后立即关闭连接，而主动关闭方可能还没有接收到这个数据段的确认。
HTTP 的 Keep-Alive，是由应用层实现的，称为 HTTP 长连接 每次请求都要经历这样的过程：建立 TCP连接 -> HTTP请求资源 -> 响应资源 -> 释放连接，这就是HTTP短连接，但是这样每次建立连接都只能请求一次资源，所以HTTP 的 Keep-Alive实现了使用同一个 TCP 连接来发送和接收多个 HTTP 请求/应答，避免了连接建立和释放的开销，就就是 HTTP 长连接。通过设置HTTP头Connection: keep-alive来实现。
TCP 的 Keepalive，是由TCP 层（内核态）实现的，称为 TCP 保活机制，是一种用于在 TCP 连接上检测空闲连接状态的机制 当TCP连接建立后，如果一段时间内没有任何数据传输，TCP Keepalive会发送探测包来检查连接是否仍然有效。
补充说明：
其实这里tcp的keepalive，不只是支持http，还可以支持ftp和smtp的，他是一个能力，类似于gc。
http的这个keepalive感觉更是一种策略吧，比如你有一个http用了keepalive，然后过了一会，你不传输数据了，这个时候没有通知对方close，这个时候tcp的keepalive就会起到用处去关闭这次链接。