快排

平均时间复杂度

nT(n)=[T(0)+T(n1)+cn+T(1)+T(n2)+cn++T(n1)+T(0)+cn]=[T(0)+T(1)++T(n1)]+[T(n1)+T(n2)++T(0)]+cn2=2[T(0)+T(1)++T(n1)]合并+cn2=2j=0n1T(j)+cn2 \begin{aligned} nT(n) &= \begin{bmatrix} T(0) + T(n - 1) + cn \\ + \\ T(1) + T(n - 2) + cn \\ + \\ \vdots \\ + \\ T(n - 1) + T(0) + cn \end{bmatrix} \\ \\ &= [T(0) + T(1) + \dots + T(n-1)] + [T(n-1) + T(n-2) + \dots + T(0)] + cn^2\\ \\ &= 2\underbrace{[T(0) + T(1) + \dots + T(n-1)]}_{\text{合并}} + cn^2 \\ \\ &= 2 \sum_{j=0}^{n-1} T(j) + cn^2 \end{aligned}

Cookie

HTTP 协议是"无状态的",但需要通过某些标记来判断用户身份,Cookie 为此而生.
Cookie 是保存在浏览器上的一段数据,常用来识别用户身份.当浏览器向服务器发出 HTTP 请求时,会自动携带 Cookie.
修改 Cookie 的方法有两种, 在服务器发送响应数据时设置 response headers,或在浏览器中执行 Js.
浏览器 Cookie 可以储存的数据有条数和大小限制.一般限制为50条以下 , 大小不超过4096bytes.

Cookie 有大小限制,且浏览器会自动发送 Cookie,最好不要把 Cookie 当作 LocalStore 使用.

5 Longest Palindromic Substring

题目

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

Example 1:

1
2
3
4
5
6
7
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

解题思路

从左向右依次遍历字符串.
以当前字符(假设回文数为基数长度)或当前字符和下一个字符(假设回文数为偶数长度)为回文数中心, 向左右两侧搜索.

时间复杂度 O(n2)O(n^2)

Mocha

Mocha 是一个功能丰富的 JavaScript 串行测试框架.支持多种运行环境,可以在 Node.js 和 浏览器 中运行.
通过 Mocha, 可以便捷的测试异步函数, 捕获错误, 生成测试报告.

官网文档

下面是针对 sum 函数创建的一个测试案例:

1
2
3
4
5
6
7
8
9
10
const sum = (a, b) => {
const num = a + b;
return parseFloat(num.toPrecision(15));
}

describe('sum 函数', () => { // 测试套件
it('0.1 + 0.2 = 0.3', () => { // 测试用例
expect(sum(0.1, 0.2)).to.equal(0.3); // 断言
})
});

HTTP 响应状态码

HTTP 响应状态码(HTTP Response Status Code) 用于表示服务器对此次 HTTP 请求的响应结果(服务器是否正常, 是否返回了数据).
其由是一个3位整数的状态码(status-code)及一个原因短语(reason-phrase)组成,状态码和原因短语间用空格隔开(例如最常见的表示请求成功的 200 OK).
1234.PNG

通常可以用 XMLHttpRequest.status 属性来获取返回的状态码.

1
2
3
4
5
6
7
8
var xml = new XMLHttpRequest();
xml.open('GET', 'https://httpstat.us/200');
xml.onreadystatechange = () => {
if (xml.readyState === 4) {
console.log(xml.status) // 200
}
}
xml.send();

fetch 的话也一样

1
fetch('https://httpstat.us/200').then(response => console.log(response.status))  // 200

status-code 的第一个数字用于区分响应的类别,一共可分为 5 大类.

  • 1xx (Informational responses) 信息提示
  • 2xx (Successful responses) 请求成功
  • 3xx (Redirects) 重定向
  • 4xx (Client errors) 客户端错误
  • 5xx (Server errors) 服务端错误

常用 POST 数据类型

Content-Type 接受 MIME类型 作为参数值.
传送数据时, 浏览器通过 Content-Type 来告诉服务器发送的数据格式是什么. 发送POST数据时, 常用的 MIME类型 有以下几种:

application/json

Content-Type: application/json 中的 application 表示 POST 数据为 "应用程序特有的格式", json 表示子类为 "JSON".

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var url = 'http://jsonplaceholder.typicode.com/posts';
var xml = new XMLHttpRequest();
xml.open('POST', url);
xml.withCredentials = true;
xml.setRequestHeader('content-type', 'application/json');
xml.onreadystatechange = () => {
if (xml.readyState === 4) {
if (xml.status >= 200 && xml.status < 300) {
console.log(xml.responseText);
}
}
};
var data = { foo: 'bar' };
xml.send(JSON.stringify(data));

3 Longest Substring Without Repeating Characters

题目

Given a string, find the length of the longest substring without repeating characters.

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

2 Add Two Numbers

题目

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

1. Two Sum

题目

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].