zhanghanwen96 / interview Goto Github PK
View Code? Open in Web Editor NEWinterview questions
interview questions
1000瓶药水,1瓶有毒药,服用后一小时毒发,毒药可以无限稀释,那么一小时内用几只小白鼠能够找出毒药?
这道题考察的是对2进制的理解,具体实现与3老鼠确定8瓶子原理一样。
000=0
001=1
010=2
011=3
100=4
101=5
110=6
111=7
2进制每一位表示一个老鼠,表示的十进制表示第几个瓶子,假设老鼠1,3死了,老鼠2没死,那么对应的毒药是101 = 5, 对于1000瓶药水可以用10只老鼠(<2^10测出。
如果可以测两轮,那么可以测多少瓶水中的一瓶毒药?
如果1000瓶里有2瓶毒药,需要多少只小鼠?
1000瓶里1瓶毒药有1000种可能性,而1000瓶2瓶毒药则有C(1000,2),即499500种可能性,那么log2(499500) 为18.93,即需要19只小鼠。具体实现方式为以两两混合法将1000瓶拆成499500滴,并用题目1中的方法测得。
那么对1000瓶中的N瓶毒药,则需要log2(C(1000,N))只小鼠,若N>=500,则取C(1000,1000-N)。
https://www.zhihu.com/question/30218438
DNS 是一个网络服务器,我们的域名解析简单来说就是在 DNS 上记录一条信息记录。
例如 baidu.com 220.114.23.56(服务器外网IP地址)80(服务器端口号)
根域名 》顶级域名com 》权威域名google.com
在 IP 协议里面需要有源地址 IP 和 目标地址 IP:
*源地址IP,即是客户端输出的 IP 地址;
生成了 IP 头部之后,接下来网络包还需要在 IP 头部的前面加上 MAC 头部。
ARP 协议会在以太网中以广播的形式,对以太网所有的设备喊出:“这个 IP 地址是谁的?请把你的
MAC 地址告诉我”。
MAC 报文生成
IP 生成的网络包只是存放在内存中的一串二进制数字信息,没有办法直接发送给对方。因此,我们需要将数字信息转换为电信号,才能在网线上传输,也就是说,这才是真正的数据发送过程。
下面来看一下包是如何通过交换机的。交换机的设计是将网络包原样转发到目的地。交换机工作在
MAC 层,也称为二层网络设备。
首先,电信号到达网线接口,交换机里的模块进行接收,接下来交换机里的模块将电信号转换为数字信号。
然后通过包末尾的 FCS 校验错误,如果没问题则放到缓冲区。这部分操作基本和计算机的网卡相
同,但交换机的工作方式和网卡不同。
计算机的网卡本身具有 MAC 地址,并通过核对收到的包的接收方 MAC 地址判断是不是发给自己的,
如果不是发给自己的则丢弃;相对地,交换机的端口不核对接收方 MAC 地址,而是直接接收所有的包并存放到缓冲区中。因此,和网卡不同,交换机的端口不具有 MAC 地址。
将包存入缓冲区后,接下来需要查询一下这个包的接收方 MAC 地址是否已经在 MAC 地址表中有记录
了。
交换机的 MAC 地址表主要包含两个信息:
所以,交换机根据 MAC 地址表查找 MAC 地址,然后将信号发送到相应的端口。
地址表中找不到指定的 MAC 地址。这可能是因为具有该地址的设备还没有向交换机发送过包,或者这个设备一段时间没有工作导致地址被从地址表中删除了。
这种情况下,交换机无法判断应该把包转发到哪个端口,只能将包转发到除了源端口之外的所有端口
上,无论该设备连接在哪个端口上都能收到这个包。
这样做不会产生什么问题,因为以太网的设计本来就是将包发送到整个网络的,然后只有相应的接收者才接收包,而其他设备则会忽略这个包。
路由器的端口具有 MAC 地址,因此它就能够成为以太网的发送方和接收方;同时还具有 IP 地址,从这个意义上来说,它和计算机的网卡是一样的。
TCP 三次握手结束后,开始发送 HTTP 请求报文。
请求报文由请求行(request line)、请求头(header)、请求体3个部分组成,如下图所示:
是具有一定独立功能的程序,是系统进行资源分配的最小单位,可以独立运行。
是进程的一个实体, 是cpu调度的最小单位,不拥有系统资源,所有线程共享进程的内存数据。
1、调度:线程作为调度和分配的基本单位,进程作为拥有资源的基本单位。
2、并发性:不仅进程之间可以并发执行,同一个进程的多个线程之间也可以并发执行。
3、拥有资源:进程是拥有资源的一个独立单位,线程不拥有系统资源,但可以访问隶属于进程的资源。
类似“进程是资源分配的最小单位,线程是CPU调度的最小单位”这样的回答感觉太抽象,都不太容易让人理解。
做个简单的比喻:进程=火车,线程=车厢
作者:biaodianfu
链接:https://www.zhihu.com/question/21535820/answer/411196449
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
var foo = {
value: 1
};
function bar() {
console.log(this.value);
}
bar.call(foo); // 1
// lets break it down
// what we try to achieve is to call the bar function as it is inside foo instance
var foo = {
value: 1,
bar: function() {
console.log(this.value)
}
};
foo.bar(); // 1
Function.prototype.myCall = function(context, ...args) {
var context = context || window;
context.fn = this;
var result = context.fn(...args);
delete context.fn;
return result;
}
// 实现apply
Function.prototype.myApply = function(context, args) {
var context = context || window;
context.fn = this;
var result;
if(!arr || arr.length === 0) {
result = context.fn();
} else {
result = context.fn(...args);
}
delete context.fn;
return result;
}
Function.prototype.bind = function (context, ...args) {
if (typeof this !== "function") {
throw new Error("Function.prototype.bind - what is trying to be bound is not callable");
}
var _this = this;
return function(...args2) {
return _this.apply(context, args.concat(args2))
}
}
function objectFactory() {
var obj = new Object();
// this is kinda like super()
Constructor = [].shift.call(arguments);
obj.__proto__ = Constructor.prototype
// this is to check whether if the constructor returns something.
var ret = Constructor.apply(obj, arguments);
return typeof ret === 'object' ? ret : obj;
}
Number String Null Undefined Boolean Object
// (es6新引入了一种数据类型,Symbol)
对象放在heap(堆)里,常见的基础类型和函数放在stack(栈)里,函数执行的时候在栈里执行。栈里函数执行的时候可能会调一些Dom操作,ajax操作和setTimeout定时器,这时候要等stack(栈)里面的所有程序先走**(注意:栈里的代码是先进后出)**,走完后再走WebAPIs,WebAPIs执行后的结果放在callback queue(回调的队列里,注意:队列里的代码先放进去的先执行),也就是当栈里面的程序走完之后,再从任务队列中读取事件,将队列中的事件放到执行栈中依次执行,这个过程是循环不断的。
1.所有同步任务都在主线程上执行,形成一个执行栈
2.主线程之外,还存在一个任务队列。只要异步任务有了运行结果,就在任务队列之中放置一个事件。
3.一旦执行栈中的所有同步任务执行完毕,系统就会读取任务队列,将队列中的事件放到执行栈中依次执行
4.主线程从任务队列中读取事件,这个过程是循环不断的
本地函数的局部变量和参数
当前嵌套调用链上的其他函数的变量和参数
全局变量
什么是垃圾:
一般来说没有被引用的对象就是垃圾,就是要被清除, 有个例外如果几个对象引用形成一个环,互相引用,但根访问不到它们,这几个对象也是垃圾,也要被清除。
// 订阅发布模式
var events = (function(){
var topics = {};
return {
subscribe: function(topic, handler) {
if(!topics.hasOwnProperty(topic)) {
topics[topic] = [];
}
topics[topic].push(handler);
},
public: function(topic, info) {
if(topics.hasOwnProperty(topic)) {
topics[topic].forEach(handler => handler(info));
}
},
unsubscribe: function(topic, handler) {
if(!topics.hasOwnProperty(topic)) return;
topics[topic] = topics[topic].filter(item => item !== handler);
},
removeAll: function(topic) {
if(topics.hasOwnProperty(topic)) {
topics[topic] = [];
}
}
}
})()
class Observer {
constructor(name) {
this.name = name
}
update(value) {
console.log(`${this.name} has recived message from subject + ${value}`)
}
}
class ObserverList {
constructor() {
this.observerList = []
}
add(ob) {
return this.observerList.push(ob);
}
remove(ob) {
this.observerList.filter(observer => ob != observer);
}
getList() {
return this.observerList;
}
}
class Subject {
constructor() {
this.observers = new ObserverList();
}
addObserver(ob) {
this.observers.add(ob);
}
removeObserver(ob) {
this.observers.remove(ob);
}
notify(...args) {
for(let ob of this.observers.getList()) {
ob.update(...args)
}
}
}
var obj = { a: {a: "hello", b: 21} };
var initalObj = Object.assign({}, obj);
initalObj.a.a = "changed";
console.log(obj.a.a); // "changed"
需要注意的是:
Object.assign()可以处理一层的深度拷贝,如下:
var obj1 = { a: 10, b: 20, c: 30 };
var obj2 = Object.assign({}, obj1);
obj2.b = 100;
console.log(obj1);
// { a: 10, b: 20, c: 30 } <-- 沒被改到
console.log(obj2);
// { a: 10, b: 100, c: 30 }
var obj1 = { body: { a: 10 } };
var obj2 = JSON.parse(JSON.stringify(obj1));
obj2.body.a = 20;
console.log(obj1);
// { body: { a: 10 } } <-- 沒被改到
console.log(obj2);
// { body: { a: 20 } }
console.log(obj1 === obj2);
// false
console.log(obj1.body === obj2.body);
// false
但是这种方法也有不少坏处,譬如它会抛弃对象的constructor。也就是深拷贝之后,不管这个对象原来的构造函数是什么,在深拷贝之后都会变成Object。
这种方法能正确处理的对象只有 Number, String, Boolean, Array, 扁平对象,即那些能够被 json 直接表示的数据结构。RegExp对象是无法通过这种方式深拷贝。
function deepClone(obj) {
if (obj === null) return null; //null 的情况
if (obj instanceof RegExp) return new RegExp(obj); //正则表达式的情况
if (obj instanceof Date) return new Date(obj); //日期对象的情况
if (typeof obj == 'Function') return new function(obj){}; //函数的情况
if (typeof obj != "object") {
//非复杂类型,直接返回 也是结束递归的条件
return obj
}
//[].__proto__.constructor=Array()
//{}.__proto__.constructor=Object()
var newObj = new obj.__proto__.constructor;
for(let key in obj) {
if(Object.hasOwnProperty(key)) {
newObj[key] = deepClone(obj[key])
}
}
return newObj
}
03/07
03/08
03/10
03/11
03.12
3.13
3.15
- 236 二叉树的最近公共祖先
- 22 括号生成
- 104 二叉树最大深度
3.17
3.19
public static Node process1(int[] postArr, int L, int R) {
if(L > R) {
return null;
}
Node head = new Node(postArr[R]);
if(L == R) return head;
int M = L - 1;
for(int i = 0; i < R; i ++) {
if(postArr[i] < postArr[R]) {
M = i;
}
}
head.left = process1(postArr, L, M);
head.right = process1(postArr, M+1, R-1);
return head
}
// 更容易理解的分类判断
public static Node process3(int[] postArr, int L, int R) {
if(L > R) {
return null;
}
Node head = new Node(postArr[R]);
if(L == R) return head;
int M = -1;
for(int i = 0; i < R; i ++) {
if(postArr[i] < postArr[R]) {
M = i;
}
}
if(M == -1) {
head.right = process3(postArr, L, R-1);
} else if(M == R - 1) {
head.left = process3(postArr, L, R - 1);
} else {
head.left = process3(postArr, L, M);
head.right = process3(postArr, M+1, R-1);
}
return head
}
// 利用二分法寻找M
public static Node process2(int[] postArr, int L, int R) {
if(L > R) {
return null;
}
Node head = new Node(postArr[R]);
if(L == R) return head;
int M = L - 1;
//二分
int left = L;
int right = R - 1;
while(left <= right) {
int mid = left + ((right - left) >> 1);
if(postArr[mid] < postArr[R]) {
M = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
head.left = process1(postArr, L, M);
head.right = process1(postArr, M+1, R-1);
return head
}
For test only, generate random BST
public static Node generateRandomBST(int min, int max, int N) {
if(min > max) return null;
return createTree(min, max, level, N);
}
public static Node createTree(int min, int max, int level, int N) {
if(min > max || level > N) {
return null;
}
Node head = new Node(random(min, max));
head.left = createTree(min, head.value - 1, level +1, N);
head.right = createTree(head.value + 1, max, level +1, N);
return head;
}
public static int random(int min, int max) {
return min + (int) (Math.random() * (max - min + 1));
}
'acdbsgee' 里包含 'adcb' 顺序不重要
// 暴力循环方法
public static int contain(String s, String a) {
if(s == null || a == null || s.length() < a.length()) {
return -1;
}
char[] str = s.toCharArray();
char[] aim = a.toCharArray();
for(int i = 0; i <= str.length - aim.length; i ++) {
if(isCountEqual(str, aim, i)) {
return i;
}
}
}
public static Boolean isCountEqual(char[] str, char[] aim, int L) {
int[] count = new int[256];
for(char c : aim) {
count[c]++;
}
for(int i = 0; i < aim.length; i++) {
if(-- count[str[i+L]] < 0) {
return false;
}
}
return true;
}
public static int contain2(String s, String a) {
char[] aim = a.toCharArray();
char[] str = s.toCharArray();
int[] count = new int[256];
for(char c : aim) {
count[c]++;
}
int M = aim.length;
int inValidtimes = 0;
int R = 0;
for(; R < M; R ++) {
if(-- count[R] < 0) {
inValidtimes ++;
}
}
for(; R < str.length; R++) {
if(inValidtimes == 0) {
return R - M;
}
if(--count[R] < 0 ) {
inValidtimes ++;
}
if(count[R-M]++ < 0) {
inValidtimes --;
}
}
return inValidtimes == 0 ? R - M : -1;
}
public static String LCS(String s1, String s2) {
int len1 = s1.length();
int len2 = s2.length();
int[][] dp = new int[len1][len2]
int lastI = 0;
int maxLen = 0;
for(int i = 0; i <= len1; i++) {
for(int j = 0; j <= len2; j++) {
if((i==0 || j==0)) dp[i][j] = 0;
else if(s1.charAt(i-1) == s2.charAt(j-1)) {
dp[i][j] = d[i-1][j-1] +1;
if(dp[i][j] > maxLen) {
maxLen = dp[i][j];
lastI = i;
}
}
}
}
if(maxLen == 0) return "-1";
return s1.substring(lastI - maxLen, lastI + 1);
}
public static int LCS2(String s1, String s2) {
int len1 = s1.length();
int len2 = s2.length();
int[][] dp = new int[len1+1][len2+1];
for(int i = 0; i <= len1; i++) {
for(int j = 0; j <= len2; j++) {
if((i==0 || j==0)) dp[i][j] = 0;
else if(s1.charAt(i-1) == s2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] +1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[len1][len2];
}
public String LP(String s) {
if(s == null || s.length() == 0) {
return "";
}
int len = s.length();
int start = 0, end = 0, max = 0;
boolean[][] dp = new boolean[len][len];
for(int i = 0; i < len; i++) {
for(int j = 0; j <=i; j++) {
if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j-1][i-1])) {
dp[j][i] = true;
}
if(dp[j][i] && max < i - j + 1) {
max = i - j + 1;
start = j;
end = i;
}
}
}
return s.substring(start, end + 1);
}
public int lengthOfLIS(int[] nums) {
if(nums.length==1){
return nums.length;
}
int[] a = new int[nums.length];
int ans = 0;
for(int i = 0; i < a.length; ++i){
a[i] = 1;
}
for(int i = 1; i < a.length; ++i){
for(int j = 0; j < i; ++j){
if(nums[j] < nums[i]){
a[i] = Math.max(a[j]+1, a[i]);
}
}
ans = Math.max(ans, a[i]);
}
return ans;
}
// 用双指针,因为装水的瓶颈在height最低的那个木板,所以每次按最低的算
public int maxArea(int[] height) {
int ans = 0;
int i = 0, j = height.length-1;
while(i < j) {
ans = Math.max(ans, Math.min(height[i], height[j]) * (j - i));
if(height[i] <= height[j]) {
i ++;
} else {
j --;
}
}
return ans;
}
public boolean exist(char[][] board, String word) {
if (board == null || board[0] == null || board.length == 0 || board[0].length == 0 || word == null || word.equals("")) {
return false;
}
boolean[][] visited = new boolean[board.length][board[0].length];
char[] wordArr = word.toCharArray();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == word.charAt(0)) {
if (dfs(board, wordArr, i, j, 1, visited)) return true;
}
}
}
return false;
}
public boolean dfs(char[][] board, char[] wordArr, int i, int j, int len, boolean[][] visited) {
if(i < 0 || j < 0 || i == board.length || j == board[0].length || wordArr[len-1] != board[i][j] || visited[i][j]) {
return false;
}
if(len == wordArr.length) {
return true;
}
visited[i][j] = true;
boolean ans = dfs(board, wordArr, i+1, j, len + 1, visited) || dfs(board, wordArr, i-1, j, len + 1, visited) || dfs(board, wordArr, i, j+1, len + 1, visited)|| dfs(board, wordArr, i, j-1, len + 1, visited);
visited[i][j] = false;
return ans;
}
for(int i = 0; i < m; i ++) {
dp[i][0] = 1;
}
for(int i = 0; i < n; i ++) {
dp[0][i] = 1;
}
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}
int[][] dp = new int[rows][cols];
for(int i = 0; i < rows && obstacleGrid[i][0] != 1; ++ i) {
dp[i][0] = 1;
}
for(int i = 0; i < cols && obstacleGrid[0][i] != 1; ++ i) {
dp[0][i] = 1;
}
for(int i = 1; i < rows; ++ i) {
for(int j = 1; j < cols; ++ j) {
if(obstacleGrid[i][j] != 1) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[rows - 1][cols - 1];
}
}
## 不同路径III
<a name='不同路径III'>
```java
class Solution {
public int uniquePathsIII(int[][] grid) {
int count = 0, x = 0, y = 0;
for(int i = 0; i <grid.length; i++ ) {
for(int j = 0; j < grid[0].length; j++) {
if(grid[i][j]==1) {
x=i;
y=j;
}
if(grid[i][j] == 0) count ++;
}
}
return dfs(grid, x, y, grid.length, grid[0].length, count+1, 0);
}
public int dfs(int[][] grid, int x, int y, int rows, int cols, int total, int current) {
if(x < 0 || y < 0 || x >= rows || y >= cols || grid[x][y] == -1) return 0;
if(grid[x][y] == 2) {
return current == total ? 1 : 0;
}
grid[x][y] = -1;
int ans = 0;
ans += dfs(grid, x-1, y, rows, cols, total, current +1);
ans +=dfs(grid, x+1, y, rows, cols, total, current +1);
ans +=dfs(grid, x, y-1, rows, cols, total, current +1);
ans +=dfs(grid, x, y+1, rows, cols, total, current +1);
grid[x][y] = 0;
return ans;
}
}
class Solution {
public boolean validPalindrome(String s) {
int len = s.length();
if(len < 2) return true;
int i = 0, j = len - 1;
while(i < j) {
if(s.charAt(i) != s.charAt(j)) {
return isValid(s, i+1, j) || isValid(s, i, j - 1);
}
i++;
j--;
}
return true;
}
public boolean isValid(String s, int start, int end) {
while(start < end) {
if(s.charAt(start++) != s.charAt(end--)){
return false;
}
}
return true;
}
}
class Solution {
public int lengthOfLongestSubstring(String s) {
HashSet<Character> set = new HashSet<>();
int i =0, j = 0, max = 0;
while(j < s.length()){
if(!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
max = Math.max(max, set.size());
}else{
set.remove(s.charAt(i++));
}
}
return max;
}
}
public int lengthOfLongestSubstring(String s) {
if (s.length()==0) return 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int max=0;
for (int i=0, j=0; i<s.length(); ++i){
if (map.containsKey(s.charAt(i))){
j = Math.max(j,map.get(s.charAt(i))+1);
}
map.put(s.charAt(i),i);
max = Math.max(max,i-j+1);
}
return max;
}
public class Solution {
public int lengthOfLongestSubstring(String s) {
int result = 0;
int[] cache = new int[256];
for (int i = 0, j = 0; i < s.length(); i++) {
j = (cache[s.charAt(i)] > 0) ? Math.max(j, cache[s.charAt(i)]) : j;
cache[s.charAt(i)] = i + 1;
result = Math.max(result, i - j + 1);
}
return result;
}
}
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while(cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
else if(l2 == null) return l1;
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = (l1 == null) ? l2 : l1;
return dummy.next;
}
}
// 先进行优化,创建两个array
class Solution {
public int trap(int[] arr) {
if(arr == null || arr.length < 2) {
return 0;
}
int N = arr.length;
int[] leftMax = new int[N];
int[] rightMax = new int[N];
leftMax[0] = arr[0];
rightMax[N-1] = arr[N-1];
for(int i = 1; i < N; i++) {
leftMax[i] = Math.max(leftMax[i-1], arr[i]);
}
for(int i = N-2; i >= 0; i--) {
rightMax[i] = Math.max(leftMax[i+1], arr[i]);
}
int water = 0;
for(int i = 1; i < N -1; i ++) {
water += Math.max(Math.min(rightMax[i+ 1], leftMax[i-1]) - arr[i], 0);
}
return water;
}
}
// 双指针
int left = 0, right = arr.length - 1;
int ans = 0;
int leftMax = 0, rightMax = 0;
while(left < right) {
if(arr[left] < arr[right]){
arr[left] >= leftMax ? leftMax = arr[left] : ans += (leftMax - arr[left]);
++ left;
} else {
arr[right] >= rightMax ? rightMax = arr[right]: ans += (rightMax - arr[right]);
-- right;
}
}
return ans;
public class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> largeK = new PriorityQueue<Integer>(k + 1);
for(int el : nums) {
largeK.add(el);
if (largeK.size() > k) {
largeK.poll();
}
}
return largeK.poll();
}
}
public class Solution {
public int findKth(int[] a, int n, int K) {
// write code here
return findKth(a, 0, n-1, K);
}
public int findKth(int[] a, int low, int high, int k) {
int part = partition(a, low, high);
if(k == part - low + 1) return a[part];
else if(k > part - low + 1) return findKth(a, part + 1, high, k - part + low -1);
else return findKth(a, low, part -1, k);
}
public int partition(int[] a, int left, int right) {
int pivot = a[right];
int low = left, high = right;
while(low < high) {
while(low<high && a[low] >= pivot) {
low ++;
}
while(low<high && a[high] <= pivot) {
high --;
}
int temp = a[low];
a[low] = a[high];
a[high] = temp;
}
int temp = a[low];
a[low] = pivot;
a[right] = temp;
return low;
}
}
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
if (n <= 1) return new ArrayList<>();
Arrays.sort(nums);
List<List<Integer>> res = new LinkedList<>();
for (int i = 0; i < n - 2; i++) {
//为了保证不加入重复的 list,因为是有序的,所以如果和前一个元素相同,只需要继续后移就可以
if (i==0 || (i > 0 && nums[i] != nums[i-1])) {
int low = i + 1, high = n - 1, sum = 0 - nums[i];
while (low < high) {
if (nums[low] + nums[high] == sum) {
res.add(Arrays.asList(nums[i], nums[low], nums[high]));
while (low < high && nums[low] == nums[low+1]) low++;
while (low < high && nums[high] == nums[high-1]) high --;
low ++;
high --;
} else if (nums[low] + nums[high] < sum) {
low ++;
} else {
high --;
}
}
}
}
return res;
}
}
for(int i=1; i < prices.length; ++i){
maxcur = Math.max(0, maxcur += prices[i] - prices[i-1]);
maxsofar = Math.max(maxsofar, maxcur);
}
return maxsofar;
}
}
```java
public int maxProfit(int[] prices) {
int min = Integer.MAX_VALUE, max = 0;
for (int price: prices) {
min = Math.min(min, price);
max = Math.max(price - min, max);
}
return max;
}
class Solution {
public int maxProfit(int[] prices) {
int maxprofit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1])
maxprofit += prices[i] - prices[i - 1];
}
return maxprofit;
}
}
class Solution {
List<List<Integer>> edges;
int[] visited;
boolean valid = true;
public boolean canFinish(int numCourses, int[][] prerequisites) {
edges = new ArrayList<>();
for (int i = 0; i < numCourses; ++i) {
edges.add(new ArrayList<Integer>());
}
visited = new int[edges.size()];
for(int[] p : prerequisites) {
edges.get(p[1]).add(p[0]);
}
for(int i = 0; i < edges.size() & valid; i++) {
if(visited[i] == 0) {
dfs(i);
}
}
return valid;
}
public void dfs(int u) {
visited[u] = 1;
for(int v : edges.get(u)) {
if(visited[v] == 0) {
dfs(v);
if(!valid) {
return;
}
} else if(visited[v] == 1) {
valid = false;
return;
}
}
visited[u] = 2;
}
}
// to do
class MyQueue {
private Stack<Integer> a;// 输入栈
private Stack<Integer> b;// 输出栈
/** Initialize your data structure here. */
public MyQueue() {
a = new Stack<>();
b = new Stack<>();
}
/** Push element x to the back of queue. */
public void push(int x) {
a.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
if(b.isEmpty()) {
while(!a.isEmpty()) {
b.push(a.pop());
}
}
return b.pop();
}
/** Get the front element. */
public int peek() {
if(b.isEmpty()) {
while(!a.isEmpty()) {
b.push(a.pop());
}
}
return b.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return a.isEmpty() && b.isEmpty();
}
}
class Solution {
public TreeNode invertTree(TreeNode root) {
// if (root == null)
// return null;
// TreeNode right = invertTree(root.right);
// TreeNode left = invertTree(root.left);
// root.left = right;
// root.right = left;
// return root;
if (root == null) return null;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
TreeNode temp = current.left;
current.left = current.right;
current.right = temp;
if (current.left != null) queue.add(current.left);
if (current.right != null) queue.add(current.right);
}
return root;
}
}
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
int[] visited = new int[nums.length];
backtrack(res, nums, visited, new ArrayList<>());
return res;
}
public void backtrack(List<List<Integer>> res, int[] nums, int[] visited, ArrayList<Integer> temp) {
if(temp.size() == nums.length) {
res.add(new ArrayList<>(temp));
return;
}
for(int i = 0; i < nums.length; i++) {
if(visited[i] == 1) continue;
visited[i] = 1;
temp.add(nums[i]);
backtrack(res, nums, visited, temp);
temp.remove(temp.size() - 1);
visited[i] = 0;
}
}
}
class Solution {
public List<List<Integer>> res=new ArrayList<>();
// public List<List<Integer>> subsets(int[] nums) {
// List<Integer> temp = new ArrayList<>();
// dfs(nums, temp, 0);
// res.add(new ArrayList<>());
// return res;
// }
// public void dfs(int[] nums, List<Integer> temp, int len) {
// for(int i = len; i < nums.length; i++) {
// temp.add(nums[i]);
// res.add(new ArrayList<>(temp));
// dfs(nums, temp, i + 1);
// temp.remove(temp.size() - 1);
// }
// }
public List<List<Integer>> subsets(int[] nums) {
res.add(new ArrayList<>());
for(int num : nums) {
for(int i = 0, j=res.size(); i < j; i ++) {
List<Integer> list = new ArrayList(res.get(i));
list.add(num);
res.add(list);
}
}
return res;
}
}
class Solution {
public ListNode sortList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode mid = findMid(head);
ListNode rightNode = mid.next;
mid.next = null;
ListNode left = sortList(head);
ListNode right = sortList(rightNode);
return merge(left, right);
}
public ListNode findMid(ListNode head) {
if(head == null || head.next == null) return head;
ListNode fast = head.next, slow = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast= fast.next.next;
}
return slow;
}
public ListNode merge(ListNode left, ListNode right) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while(left != null && right != null) {
if(left.val < right.val) {
cur.next = left;
left = left.next;
} else {
cur.next = right;
right = right.next;
}
cur = cur.next;
}
cur.next = left != null ? left : right;
return dummy.next;
}
}
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0) {
return null;
}
return mergeKLists(lists, 0, lists.length - 1);
}
public ListNode mergeKLists(ListNode[] lists, int low, int high) {
if(low >= high) return lists[low];
int mid = low + ((high - low) >> 1);
ListNode left = mergeKLists(lists, low, mid);
ListNode right = mergeKLists(lists, mid + 1, high);
return merge(left ,right);
}
public ListNode merge(ListNode left, ListNode right) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while(left != null && right != null) {
if(left.val < right.val) {
cur.next = left;
left = left.next;
} else {
cur.next = right;
right = right.next;
}
cur = cur.next;
}
cur.next = left != null ? left : right;
return dummy.next;
}
}
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int max = 0;
for(int i = 0; i < grid.length; ++ i) {
for(int j = 0; j < grid[0].length; ++ j) {
if(grid[i][j] == 1) {
max = Math.max(dfs(grid, i, j), max);
}
}
}
return max;
}
public int dfs(int[][] grid, int i, int j) {
if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) return 0;
int count = 1;
grid[i][j] = 0;
count += dfs(grid, i + 1, j);
count += dfs(grid, i -1, j);
count += dfs(grid, i, j + 1);
count += dfs(grid, i, j - 1);
return count;
}
}
class Solution {
public int[] searchRange(int[] nums, int target) {
int right = search(nums, target, true);
int left = search(nums, target, false);
return new int[] {left, right};
}
// find the rightmost index of the target if <right> is true
public int search(int[] nums, int target, boolean right) {
int low = 0;
int high = nums.length - 1;
int mid;
int index = -1;
while(low <= high) {
mid = low + ((high - low) >> 1);
if(nums[mid] < target || (right && nums[mid] == target)) {
low = mid + 1;
} else {
high = mid - 1;
}
if(nums[mid] == target) {
index = mid;
}
}
return index;
}
}
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == q || root == p) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left != null && right != null) {
return root;
} else if(left != null) {
return left;
} else {
return right;
}
}
}
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
return count(root, 0);
}
public int count(TreeNode root, int level) {
if(root != null) {
return Math.max(count(root.left, level + 1), count(root.right, level +1));
} else {
return level;
}
}
}
public int maxDepth(TreeNode root) {
if(root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
dfs(res, "", 0, 0, n);
return res;
}
public void dfs(List<String> res, String str, int left, int right, int n) {
if(left < right || left > n) return;
if(left + right == 2*n) {
res.add(str);
}
dfs(res, str + "(", left + 1, right, n);
dfs(res, str + ")", left, right + 1, n);
}
}
class Solution {
List<Integer> res = new ArrayList<>();
public List<Integer> rightSideView(TreeNode root) {
if(root == null) return res;
// for bfs search
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
int size = queue.size();
for(int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
if(i == size - 1) {
res.add(node.val);
}
}
}
return res;
}
}
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int x = matrix[0].length, y = matrix.length;
List<Integer> res = new ArrayList<>();
int top = 0, left = 0, bottom = y - 1, right = x - 1;
int total = 0;
int index = 0;
while(total < x*y) {
for(int i = left; i <= right; i++) {
res.add(matrix[top][i]);
total ++;
}
top ++;
for(int i = top; i <= bottom; i++) {
res.add(matrix[i][right]);
total ++;
}
right --;
for(int i = right ; i >= left ;i --) {
res.add(matrix[bottom][i]);
total ++;
}
bottom --;
for(int i = bottom; i >= top ; i --) {
res.add(matrix[i][left]);
total ++;
}
left ++;
}
return res;
}
}
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return root;
TreeNode left = mirrorTree(root.left);
TreeNode right = mirrorTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) return null;
ListNode a = headA;
ListNode b = headB;
while(a != b) {
a = a == null ? headB : a.next;
b = b == null ? headA: b.next;
}
return a;
}
}
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
dfs(res, root, 0);
return res;
}
public void dfs(List<List<Integer>> res, TreeNode root, int level) {
if(root == null) return;
if(res.size() == level) {
res.add(new ArrayList<>());
}
if(level % 2 == 0) {
res.get(level).add(root.val);
} else {
res.get(level).add(0, root.val);
}
dfs(res, root.left, level +1);
dfs(res, root.right, level +1);
}
}
public int solution(int[][] intervals) {
TreeMap<Integer, Integer> map = new TreeMap<>();
int max = 0, total = 0;
for(int[] interval : intervals) {
int count = map.getOrDefault(interval[0], 0);
map.put(interval[0], count + 1);
count = map.getOrDefault(interval[1], 0);
map.put(interval[1], count - 1);
}
for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
total += entry.getValue();
max = Math.max(total, max);
}
return max;
}
public int solution2(int[][] intervals) {
if(intervals.length == 0) return 0;
int max = 1;
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
PriorityQueue<Integer> q = new PriorityQueue<>();
for(int[] interval : intervals) {
while(interval[0] >= q.peek()) {
q.poll();
}
q.offer(interval[1]);
max = Math.max(q.size(), max);
}
return max;
}
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
ArrayList<int[]> lists = new ArrayList<>();
// lists.add(new int[] {intervals[0][0], intervals[0][1]});
// for(int i = 1; i < intervals.length; ++ i) {
// if(intervals[i][0] > lists.get(lists.size() - 1)[1]) {
// lists.add(new int[] {intervals[i][0], intervals[i][1]});
// } else {
// lists.get(lists.size() - 1)[1] = Math.max(lists.get(lists.size() - 1)[1], intervals[i][1]);
// }
// }
int max;
for(int i = 0; i < intervals.length;) {
int j = i + 1;
int t = intervals[i][1];
while(j< intervals.length && t >= intervals[j][0]) {
t = Math.max(t, intervals[j][1]);
j ++;
}
lists.add(new int[] {intervals[i][0], t});
i = j;
}
return lists.toArray(new int[lists.size()][2]);
}
}
import Link from 'next/link'
<Link href="/home"><a>Home</a></Link>
import Image from 'next/image'
import Head from 'next/head'
export const getStaticProps = async () => {
const res = await fetch("https://jsonplaceholder.typicode.com/users")
const data = await res.json()
return {
props: { ninjas: data }
}
}
The data will be attached to the component as props
/ninjas/:id
getStaticPath
npm run build, all pages are generated
https://segmentfault.com/a/1190000016708006
function Parent () {
this.name = 'kevin';
}
Parent.prototype.getName = function () {
console.log(this.name);
}
function Child () {}
Child.prototype = new Parent();
function Parent () {
this.names = ['kevin', 'daisy'];
}
function Child () {
Parent.call(this);
}
var child1 = new Child();
child1.names.push('yayu');
console.log(child1.names); // ["kevin", "daisy", "yayu"]
var child2 = new Child();
console.log(child2.names); // ["kevin", "daisy"]
// 重写构造函数
function Child(name, age) {
Parent.call(this, name);
this.age = age;
}
https://segmentfault.com/a/1190000016708006
原型链继承和经典继承双剑合璧。
function Parent (name) {
this.name = name;
this.colors = ['red', 'blue', 'green'];
}
Parent.prototype.getName = function () {
console.log(this.name)
}
function Child (name, age) {
Parent.call(this, name);
this.age = age;
}
Child.prototype = new Parent();
Child.prototype.constructor = Child;
var child1 = new Child('kevin', '18');
child1.colors.push('black');
console.log(child1.name); // kevin
console.log(child1.age); // 18
console.log(child1.colors); // ["red", "blue", "green", "black"]
var child2 = new Child('daisy', '20');
console.log(child2.name); // daisy
console.log(child2.age); // 20
console.log(child2.colors); // ["red", "blue", "green"]
function debounce(fn, delay) {
var timer;
return function(){
var _args = arguments;
var _this = this;
if(timer) {
clearTimeout(timer);
}
setTimeout(() => fn.apply(__this, _args), delay);
}
}
function print(e, content) {
console.log(e, content);
}
var testDebounceFn = debounce(testDebounce, 1000);
document.onmousemove = function (e) {
testDebounceFn(e, 'debounce'); // 给防抖函数传参
}
function throttle(fn, delay) {
var timer;
return function(){
var _this = this;
var args = arguments;
if(timer) return
timer = setTimeout(function () {
fn.apply(_this, args);
timer = null; // 在delay后执行完fn之后清空timer,此时timer为假,throttle触发可以进入计时器
}, delay)
}
}
//test
function testThrottle(e, content) {
console.log(e, content);
}
var testThrottleFn = throttle(testThrottle, 1000); // 节流函数
document.onmousemove = function (e) {
testThrottleFn(e, 'throttle'); // 给节流函数传参
}
function trueCurrying(fn, ...args) {
var _this = this;
return function(...args2) {
// 应该是args2 + args如果提前传入args参数的话
if(args.concat(args2).length >= fn.length) {
fn.apply(_this, args.concat(args2))
} else {
return trueCurrying.apply(_this, fn, args.concat(args2))
}
}
}
function Foo()
let f1 = new Foo()
let f2 = new Foo()
f1.__proto__ == Foo.prototype;
f2.__proto__ == Foo.prototype;
Foo.__proto__ == Function.prototype // 本质是函数对象
Foo.prototype.__proto__ == Object.prototype // prototype也是普通对象
Object.prototype.__proto__ == null // 原型链在这里终止
Foo.prototype.constructor == Foo // 原型对象的constructor指向构造函数本身
// 从中间 Function Object()开始分析这一张经典之图
Function Object()
let o1 = new Object();
let o2 = new Object();
o1.__proto__ = Object.prototype; //
o2.__proto__ = Object.prototype; //
Object.prototype.__proto__ = null; // 原型链到此停止
Object.prototype.constructor = Object; //
Object.__proto__ = Function.prototype // (Object本质也是函数);
// 此处有点绕,Object本质是函数,Function本质是对象
Function.prototype.__proto__ = Object.prototype; // (Function.prototype本质也是普通对象)
Object.prototype.__proto__ = null; // 原型链到此停止
// 从下方 Function Function()开始分析这一张经典之图
Function Function()
Function.__proto__ = Function.prototype //
Function.prototype.constructor = Function; //
反射型 XSS 只是简单地把用户输入的数据 “反射” 给浏览器,这种攻击方式往往需要攻击者诱使用户点击一个恶意链接,或者提交一个表单,或者进入一个恶意网站时,注入脚本进入被攻击者的网站。
恶意链接的地址指向了 localhost:8001/?q=111&p=222。然后,我再启一个简单的 Node 服务处理恶意链接的请求:
const http = require('http');
function handleReequest(req, res) {
res.setHeader('Access-Control-Allow-Origin', '*');
res.writeHead(200, {'Content-Type': 'text/html; charset=UTF-8'});
res.write('<script>alert("反射型 XSS 攻击")</script>');
res.end();
}
const server = new http.Server();
server.listen(8001, '127.0.0.1');
server.on('request', handleReequest);
这样就产生了反射型 XSS 攻击。攻击者可以注入任意的恶意脚本进行攻击,可能注入恶作剧脚本,或者注入能获取用户隐私数据(如cookie)的脚本,这取决于攻击者的目的。
存储型 XSS 会把用户输入的数据 "存储" 在服务器端,当浏览器请求数据时,脚本从服务器上传回并执行。这种 XSS 攻击具有很强的稳定性。
比较常见的一个场景是攻击者在社区或论坛上写下一篇包含恶意 JavaScript 代码的文章或评论,文章或评论发表后,所有访问该文章或评论的用户,都会在他们的浏览器中执行这段恶意的 JavaScript 代码。
<input type="text" id="input">
<button id="btn">Submit</button>
<script>
const input = document.getElementById('input');
const btn = document.getElementById('btn');
let val;
input.addEventListener('change', (e) => {
val = e.target.value;
}, false);
btn.addEventListener('click', (e) => {
fetch('http://localhost:8001/save', {
method: 'POST',
body: val
});
}, false);
</script>
启动一个 Node 服务监听 save 请求。为了简化,用一个变量来保存用户的输入:
const http = require('http');
let userInput = '';
function handleReequest(req, res) {
const method = req.method;
res.setHeader('Access-Control-Allow-Origin', '*');
res.setHeader('Access-Control-Allow-Headers', 'Content-Type')
if (method === 'POST' && req.url === '/save') {
let body = '';
req.on('data', chunk => {
body += chunk;
});
req.on('end', () => {
if (body) {
userInput = body;
}
res.end();
});
} else {
res.writeHead(200, {'Content-Type': 'text/html; charset=UTF-8'});
res.write(userInput);
res.end();
}
}
const server = new http.Server();
server.listen(8001, '127.0.0.1');
server.on('request', handleReequest);
当用户点击提交按钮将输入信息提交到服务端时,服务端通过 userInput 变量保存了输入内容。当用户通过 http://localhost:8001/${id} 访问时,服务端会返回与 id 对应的内容(本示例简化了处理)。如果用户输入了恶意脚本内容,则其他用户访问该内容时,恶意脚本就会在浏览器端执行:
基于 DOM 的 XSS 攻击是指通过恶意脚本修改页面的 DOM 结构,是纯粹发生在客户端的攻击。
<h2>XSS: </h2>
<input type="text" id="input">
<button id="btn">Submit</button>
<div id="div"></div>
<script>
const input = document.getElementById('input');
const btn = document.getElementById('btn');
const div = document.getElementById('div');
let val;
input.addEventListener('change', (e) => {
val = e.target.value;
}, false);
btn.addEventListener('click', () => {
div.innerHTML = `<a href=${val}>testLink</a>`
}, false);
</script>
点击 Submit 按钮后,会在当前页面插入一个链接,其地址为用户的输入内容。如果用户在输入时构造了如下内容
'' onclick=alert(/xss/)
用户提交之后,页面代码就变成了:
<a href onlick="alert(/xss/)">testLink</a>
HttpOnly 最早由微软提出,至今已经成为一个标准。浏览器将禁止页面的Javascript 访问带有 HttpOnly 属性的Cookie。
上文有说到,攻击者可以通过注入恶意脚本获取用户的 Cookie 信息。通常 Cookie 中都包含了用户的登录凭证信息,攻击者在获取到 Cookie 之后,则可以发起 Cookie 劫持攻击。所以,严格来说,HttpOnly 并非阻止 XSS 攻击,而是能阻止 XSS 攻击后的 Cookie 劫持攻击。
不要相信用户的任何输入。 对于用户的任何输入要进行检查、过滤和转义。建立可信任的字符和 HTML 标签白名单,对于不在白名单之列的字符或者标签进行过滤或编码。
在 XSS 防御中,输入检查一般是检查用户输入的数据中是否包含 <,> 等特殊字符,如果存在,则对特殊字符进行过滤或编码,这种方式也称为 XSS Filter。
而在一些前端框架中,都会有一份 decodingMap, 用于对用户输入所包含的特殊字符或标签进行编码或过滤,如 <,>,script,防止 XSS 攻击:
// vuejs 中的 decodingMap
// 在 vuejs 中,如果输入带 script 标签的内容,会直接过滤掉
const decodingMap = {
'<': '<',
'>': '>',
'"': '"',
'&': '&',
' ': '\n'
}
用户的输入会存在问题,服务端的输出也会存在问题。一般来说,除富文本的输出外,在变量输出到 HTML 页面时,可以使用编码或转义的方式来防御 XSS 攻击。例如利用 sanitize-html 对输出内容进行有规则的过滤之后再输出到页面中。
CSRF,即 Cross Site Request Forgery,中译是跨站请求伪造,是一种劫持受信任用户向服务器发送非预期请求的攻击方式。
通常情况下,CSRF 攻击是攻击者借助受害者的 Cookie 骗取服务器的信任,可以在受害者毫不知情的情况下以受害者名义伪造请求发送给受攻击服务器,从而在并未授权的情况下执行在权限保护之下的操作
HTTP是一个基于TCP/IP通信协议来传递数据的协议,传输的数据类型为HTML 文件,、图片文件, 查询结果等。
HTTP协议一般用于B/S架构()。浏览器作为HTTP客户端通过URL向HTTP服务端即WEB服务器发送所有请求。
实际使用中,绝大说的网站现在都采用的是https协议,这也是未来互联网发展的趋势。下面是通过wireshark抓取的一个博客网站的登录请求过程。
可以看到访问的账号密码都是明文传输, 这样客户端发出的请求很容易被不法分子截取利用,因此,HTTP协议不适合传输一些敏感信息,比如:各种账号、密码等信息,使用http协议传输隐私信息非常不安全。
为了解决上述HTTP存在的问题,就用到了HTTPS。
HTTPS 协议(HyperText Transfer Protocol over Secure Socket Layer):一般理解为HTTP+SSL/TLS,通过 SSL证书来验证服务器的身份,并为浏览器和服务器之间的通信进行加密。
用混合加密可以保证 数据安全 ==》中间人攻击,偷换了服务器的公钥,获取对称秘钥 =》
如何证明浏览器收到的公钥一定是该网站的公钥? =》 **数字证书,**身份证由权威CA机构颁发 =》
证书本身的传输过程中,如何防止被篡改? =》数字签名,摘要算法 =》 中间人有可能篡改该证书吗?=》
由于他没有CA机构的私钥,所以无法得到此时加密后签名,无法相应地篡改签名 =》 中间人有可能把证书掉包吗? =》 因为证书里包含了网站A的信息,包括域名,浏览器把证书里的域名与自己请求的域名比对一下就知道有没有被掉包了。 =》怎么证明CA机构的公钥是可信的?=》浏览器本身会预装一些它们信任的根证书,如果其中有该CA机构的根证书,那就可以拿到它对应的可信公钥了。
网站在使用HTTPS前,需要向“CA机构”申请颁发一份数字证书,数字证书里有证书持有者、证书持有者的公钥等信息,服务器把证书传输给浏览器,浏览器从证书里取公钥就行了,证书就如身份证一样,可以证明“该公钥对应该网站”。然而这里又有一个显而易见的问题了,**证书本身的传输过程中,如何防止被篡改?**即如何证明证书本身的真实性?身份证有一些防伪技术,数字证书怎么防伪呢?解决这个问题我们就基本接近胜利了!
数字签名的制作过程:
浏览器验证过程:
HTTPS 采用的是对称加密和非对称加密结合的「混合加密」方式:
客户端在发送明文之前会通过摘要算法算出明文的「指纹」,发送的时候把「指纹 + 明文」一同加密成密文后,发送给服务器,服务器解密后,用相同的摘要算法算出发送过来的明文,通过比较客户端携带的「指纹」和当前算出的「指纹」做比较,若「指纹」相同,说明数据是完整的。
客户端先向服务器端索要公钥,然后用公钥加密信息,服务器收到密文后,用自己的私钥解密。
这就存在些问题,如何保证公钥不被篡改和信任度?
所以这里就需要借助第三方权威机构 CA (数字证书认证机构),将服务器公钥放在数字证书(由数
字证书认证机构颁发)中,只要证书是可信的,公钥就是可信的。
SSL(Secure Socket Layer,安全套接字层):1994年为 Netscape 所研发,SSL 协议位于 TCP/IP 协议与各种应用层协议之间,为数据通讯提供安全支持。
TLS(Transport Layer Security,传输层安全):其前身是 SSL,它最初的几个版本(SSL 1.0、SSL 2.0、SSL 3.0)由网景公司开发,1999年从 3.1 开始被 IETF 标准化并改名,发展至今已经有 TLS 1.0、TLS 1.1、TLS 1.2 三个版本。SSL3.0和TLS1.0由于存在安全漏洞,已经很少被使用到。TLS 1.3 改动会比较大,目前还在草案阶段,目前使用最广泛的是TLS 1.1、TLS 1.2。
持久连接的特点是,只要任意一端没有明确提出断开连接,则保持 TCP 连接状态。
即可在同一个 TCP 连接里面,客户端可以发起多个请求,只要第一个请求发出去了,不必等其回来,就可以发第二个请求出去,可以减少整体的响应时间。
但是服务器还是按照顺序,先回应 A 请求,完成后再回应 B 请求。要是前面的回应特别慢,后面就会
有许多请求排队等着。这称为「队头堵塞」。
UDP协议全称是用户数据报协议,在网络中它与TCP协议一样用于处理数据包,是一种无连接的协议。在OSI模型中,在第四层——传输层,处于IP协议的上一层。UDP有不提供数据包分组、组装和不能对数据包进行排序的缺点,也就是说,当报文发送之后,是无法得知其是否安全完整到达的。
首先 UDP 是不需要和 TCP一样在发送数据前进行三次握手建立连接的,想发数据就可以开始发送了。并且也只是数据报文的搬运工,不会对数据报文进行任何拆分和拼接操作。
UDP 不止支持一对一的传输方式,同样支持一对多,多对多,多对一的方式,也就是说 UDP 提供了单播,多播,广播的功能。
发送方的UDP对应用程序交下来的报文,在添加首部后就向下交付IP层。UDP对应用层交下来的报文,既不合并,也不拆分,而是保留这些报文的边界。因此,应用程序必须选择合适大小的报文
首先不可靠性体现在无连接上,通信都不需要建立连接,想发就发,这样的情况肯定不可靠。
并且收到什么数据就传递什么数据,并且也不会备份数据,发送数据也不会关心对方是否已经正确接收到数据了。
再者网络环境时好时坏,但是 UDP 因为没有拥塞控制,一直会以恒定的速度发送数据。即使网络条件不好,也不会对发送速率进行调整。这样实现的弊端就是在网络条件不好的情况下可能会导致丢包,但是优点也很明显,在某些实时性要求高的场景(比如电话会议)就需要使用 UDP 而不是 TCP。
因此 UDP 的头部开销小,只有八字节,相比 TCP 的至少二十字节要少得多,在传输数据报文时是很高效的
当一台计算机想要与另一台计算机通讯时,两台计算机之间的通信需要畅通且可靠,这样才能保证正确收发数据。例如,当你想查看网页或查看电子邮件时,希望完整且按顺序查看网页,而不丢失任何内容。当你下载文件时,希望获得的是完整的文件,而不仅仅是文件的一部分,因为如果数据丢失或乱序,都不是你希望得到的结果,于是就用到了TCP。
TCP协议全称是传输控制协议是一种面向连接的、可靠的、基于字节流的传输层通信协议,由 IETF 的RFC 793定义。TCP 是面向连接的、可靠的流协议。流就是指不间断的数据结构,你可以把它想象成排水管中的水流。
三次握手
四次挥手
面向连接
面向连接,是指发送数据之前必须在两端建立连接。建立连接的方法是“三次握手”,这样能建立可靠的连接。建立连接,是为数据的可靠传输打下了基础。
仅支持单播传输
每条TCP传输连接只能有两个端点,只能进行点对点的数据传输,不支持多播和广播传输方式。
面向字节流
TCP不像UDP一样那样一个个报文独立地传输,而是在不保留报文边界的情况下以字节流方式进行传输。
可靠传输
对于可靠传输,判断丢包,误码靠的是TCP的段编号以及确认号。TCP为了保证报文传输的可靠,就给每个包一个序号,同时序号也保证了传送到接收端实体的包的按序接收。然后接收端实体对已成功收到的字节发回一个相应的确认(ACK);如果发送端实体在合理的往返时延(RTT)内未收到确认,那么对应的数据(假设丢失了)将会被重传。
提供拥塞控制
当网络出现拥塞的时候,TCP能够减小向网络注入数据的速率和数量,缓解拥塞
TCP提供全双工通信
TCP允许通信双方的应用程序在任何时候都能发送数据,因为TCP连接的两端都设有缓存,用来临时存放双向通信的数据。当然,TCP可以立即发送一个数据段,也可以缓存一段时间以便一次发送更多的数据段(最大的数据段大小取决于MSS)
TCP与UDP区别总结:
1、TCP面向连接(如打电话要先拨号建立连接);UDP是无连接的,即发送数据之前不需要建立连接
2、TCP提供可靠的服务。也就是说,通过TCP连接传送的数据,无差错,不丢失,不重复,且按序到达;UDP尽最大努力交付,即不保 证可靠交付
3、TCP面向字节流,实际上是TCP把数据看成一连串无结构的字节流;UDP是面向报文的
UDP没有拥塞控制,因此网络出现拥塞不会使源主机的发送速率降低(对实时应用很有用,如IP电话,实时视频会议等)
4、每一条TCP连接只能是点到点的;UDP支持一对一,一对多,多对一和多对多的交互通信
5、TCP首部开销20字节;UDP的首部开销小,只有8个字节
6、TCP的逻辑通信信道是全双工的可靠信道,UDP则是不可靠信道
————————————————
版权声明:本文为CSDN博主「Li_Ning_」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/Li_Ning_/article/details/52117463
UDP | TCP | |
---|---|---|
是否连接 | 无连接 | 面向连接 |
是否可靠 | 不可靠传输,不使用流量控制和拥塞控制 | 可靠传输,使用流量控制和拥塞控制 |
连接对象个数 | 支持一对一,一对多,多对一和多对多交互通信 | 只能是一对一通信 |
传输方式 | 面向报文 | 面向字节流 |
首部开销 | 首部开销小,仅8字节 | 首部最小20字节,最大60字节 |
应用场景 | 适用于实时应用(IP电话、视频会议、直播等 | 适用于要求可靠传输的应用,例如文件传输 |
https://cloud.tencent.com/developer/article/1405940
流量控制拥堵机制
滑动窗口
js内部的 new
的实现:
const new = (constructor) => {
const obj = {};
obj.__proto__ = constructor.prototype; // $1
// ......... 省略
return obj;
}
通过 const book = new Book()
,我们通常只会调用book的方法和属性,但实际上 book 的属性是挂载在 book自己身上的,但是 私有方法都挂载在 class Book
上,而实际上是挂载在 Book.prototype
上. 所以 $1
都作用其实是 让 book
根据prototype原型链访问到 Book
类的属性,方法。
通过以上的分析,我们其实可以分解。现有 class Child, class Parent, instance c
,我们最终需要得到 c
,c
的 __proto__
指向 Child.prototype,拥有自己的属性, Child.prototype.__proto__
指向 Parent.prototype
。
得到一个没有任何私有属性的Child.prototype (换言之,就是不执行constructor函数,或者constructor函数为空),且Child.prototype.__proto__指向Parent.prototype
得到一个Parent的instance,但是不执行它的constructor函数,没有任何私有属性
执行 Parent和Child的constructor,挂载上私有属性,即
function Child() {
// 挂载Parent私有属性
Parent.call(this);
// 挂载Child私有属性
this.age = 1;
}
接受一个组件,返回一个组件
我们有一个这样的 List 组件,如果我们想给这个 List 组件加一个 loading 功能,我们可以这么做:
const List = ({ data, isLoading }) => (
isLoading ?
<div>我正在加载...</div> :
<ul>
{data.map(item => <li key={item.name}>{item.name}</li>)}
</ul>
)
我们修改一下 List 组件的代码,让它根据 isLoading 的状态来判断是否出现加载动画。这样做不是不可以,但是不够优雅。第一,这么做需要修改原来组件的代码;第二,如果我们有其它组件,比如 Table也需要 loading 功能,我们又需要重复写相同的判断逻辑。我们用高阶组件/函数就可以完美的解决上面两个问题。
const withLoading = BaseComponent => ({ isLoading, ...otherProps }) => (
isLoading ?
<div>我正在加载...</div> :
<BaseComponent {...otherProps} />
)
const LoadingList = withLoading(List)
https://segmentfault.com/a/1190000018891454#%E8%99%9A%E6%8B%9FDOM%E5%8E%9F%E7%90%86
虚拟 DOM 就是一个用于描述真实 DOM 结构的普通 JS 对象。
使用JavaScript,我们在编写应用程序时的关注点在于如何更新DOM。
使用React,你只需要告诉React你想让视图处于什么状态,React则通过VitrualDom确保DOM与该状态相匹配。你不必自己去完成属性操作、事件处理、DOM更新,React会替你完成这一切。
这让我们更关注我们的业务逻辑而非DOM操作,这一点即可大大提升我们的开发效率。
直接操作DOM是非常耗费性能的,这一点毋庸置疑。但是React使用VitrualDom也是无法避免操作DOM的。
如果是首次渲染,VitrualDom不具有任何优势,甚至它要进行更多的计算,消耗更多的内存。
VitrualDom的优势在于React的Diff算法和批处理策略,React在页面更新之前,提前计算好了如何进行更新和渲染DOM。实际上,这个计算过程我们在直接操作DOM时,也是可以自己判断和实现的,但是一定会耗费非常多的精力和时间,而且往往我们自己做的是不如React好的。所以,在这个过程中React帮助我们"提升了性能"。
虚拟dom ---> patch更新真实dom(通过diff算法)
setState有时候有异步的假象,由执行机制看,setState本身并不是异步的,而是如果在调用setState时,如果react正处于更新过程,当前更新会被暂存,等上一次更新执行后在执行,这个过程给人一种异步的假象。
setState =》 存储要更新的partialState到queue里 =》 是否处于batch upadte状态 =》
-no =》设置batch update flag为true
=》更新然后执行生命周期函数
基于以上三个前提策略,React 分别对 tree diff、component diff 以及 element diff 进行算法优化,事实也证明这三个前提策略是合理且准确的,它保证了整体界面构建的性能。
基于策略一,React 对树的算法进行了简洁明了的优化,即对树进行分层比较,两棵树只会对同一层次的节点进行比较。
https://zhuanlan.zhihu.com/p/20346379
当节点处于同一层级时,React diff 提供了三种节点操作,分别为:INSERT_MARKUP(插入)、MOVE_EXISTING(移动)和 REMOVE_NODE(删除)。
memo
包裹functional component达到pureComponent
效果useMemo
可以帮我们将变量缓存起来,useCallback
可以缓存回调函数useRef
, ref 对象在组件的整个生命周期内保持不变import { useEffect, useRef } from 'react'
const useDebounce = (fn, ms=30, deps=[]) => {
let timeout = useRef();
useEffect(() => {
if(timeout.current) clearTimeout(timeout.current)
timeout.current = setTimeout(() => {
fn()
}, ms)
}, deps)
const cancel = () => {
clearTimeout(timeout.current)
timeout = null
}
return [cancel]
}
import { useDebounce } from 'hooks'
const Home = (props) => {
const [a, setA] = useState(0)
const [b, setB] = useState(0)
const [cancel] = useDebounce(() => {
setB(a)
}, 2000, [a])
const changeIpt = (e) => {
setA(e.target.value)
}
return <div>
<input type="text" onChange={changeIpt} />
{ b } { a }
</div>
}
const useThrottle = (fn, ms=30, deps=[]) => {
let timeout = useRef();
useEffect(() => {
if(timeout.current) return
timeout.current = setTimeout(() => {
fn()
timeout.current = null
}, ms)
}, deps)
const cancel = () => {
clearTimeout(timeout.current)
timeout = null
}
return [cancel]
}
我们都知道如果想让组件重新渲染,我们不得不更新state,但是有时候业务需要的state是没必要更新的,我们不能仅仅为了让组件会重新渲染而强制让一个state做无意义的更新,所以这个时候我们就可以自定义一个更新的hooks来优雅的实现组件的强制更新,实现代码如下:
import { useState } from 'react'
const useUpdate = () => {
const [, setFlag] = useState()
const update = () => {
setFlag(Date.now())
}
return update
}
export default useUpdate
const Home = (props) => {
// ...
const update = useUpdate()
return <div>
{Date.now()}
<div><button onClick={update}>update</button></div>
</div>
}
const useScroll = (scrollRef) => {
const [pos, setPos] = useState([0, 0]);
useEffect(() => {
function handleScroll(e) {
setPos([scrollRef.current.scrollLeft, scrollRef.current.scrollTop]);
}
scrollRef.current.addEventListener("scroll", handleScroll, false);
return () => {
scrollRef.current.removeEventListener(
"scroll",
handleScroll,
false
);
};
}, []);
return pos;
};
export default useScroll;
由以上代码可知,我们在钩子函数里需要传入一个元素的引用,这个我们可以在函数组件中采用ref和useRef来获取到,钩子返回了滚动的x,y值,即滚动的左位移和顶部位移,具体使用如下:
import React, { useRef } from "react";
import { useScroll } from "hooks";
const Home = (props) => {
const scrollRef = useRef(null);
const [x, y] = useScroll(scrollRef);
return (
<div>
<div ref={scrollRef}>
<div className='innerBox'></div>
</div>
<div>
{x}, {y}
</div>
</div>
);
};
我们都知道如果想让组件重新渲染,我们不得不更新state,但是有时候业务需要的state是没必要更新的,我们不能仅仅为了让组件会重新渲染而强制让一个state做无意义的更新,所以这个时候我们就可以自定义一个更新的hooks来优雅的实现组件的强制更新,实现代码如下:
import { useState } from 'react'
const useUpdate = () => {
const [, setFlag] = useState()
const update = () => {
setFlag(Date.now())
}
return update
}
const Home = (props) => {
// ...
const update = useUpdate()
return <div>
{Date.now()}
<div><button onClick={update}>update</button></div>
</div>
}
https://developer.mozilla.org/zh-CN/docs/Web/Performance/How_browsers_work
当浏览器接收到服务器响应来的HTML文档后,会遍历文档节点,生成DOM树。
需要注意的是,DOM树的生成过程中可能会被CSS和JS的加载执行阻塞。渲染阻塞问题下文会讲。
浏览器解析CSS文件并生成CSS规则树,每个CSS文件都被分析成一个StyleSheet对象,每个对象都包含CSS规则。CSS规则对象包含对应于CSS语法的选择器和声明对象以及其他对象
渲染阻塞 😄
当浏览器遇到一个 script 标记时,DOM 构建将暂停,直至脚本完成执行,然后继续构建DOM。每次去执行JavaScript脚本都会严重地阻塞DOM树的构建,如果JavaScript脚本还操作了CSSOM,而正好这个CSSOM还没有下载和构建,浏览器甚至会延迟脚本执行和构建DOM,直至完成其CSSOM的下载和构建。所以,script 标签的位置很重要。实际使用时,可以遵循下面两个原则:CSS 优先:引入顺序上,CSS 资源先于 JavaScript 资源。JS置后:我们通常把JS代码放到页面底部,且JavaScript 应尽量少影响 DOM 的构建。当解析html的时候,会把新来的元素插入dom树里面,同时去查找css,然后把对应的样式规则应用到元素上,查找样式表是按照从右到左的顺序去匹配的。例如: div p {font-size: 16px},会先寻找所有p标签并判断它的父标签是否为div之后才会决定要不要采用这个样式进行渲染)。所以,我们平时写CSS时,尽量用id和class,千万不要过渡层叠。
通过DOM树和CSS规则树我们便可以构建渲染树。浏览器会先从DOM树的根节点开始遍历每个可见节点。对每个可见节点,找到其适配的CSS样式规则并应用。渲染树构建完成后,每个节点都是可见节点并且都含有其内容和对应规则的样式。这也是渲染树与DOM树的最大区别所在。渲染树是用于显示,那些不可见的元素当然就不会在这棵树中出现了,譬如。除此之外,display等于none的也不会被显示在这棵树里头,但是visibility等于hidden的元素是会显示在这棵树里头的。
第四步是在渲染树上运行布局以计算每个节点的几何体。布局是确定呈现树中所有节点的宽度、高度和位置,以及确定页面上每个对象的大小和位置的过程。回流是对页面的任何部分或整个文档的任何后续大小和位置的确定。
构建渲染树后,开始布局。渲染树标识显示哪些节点(即使不可见)及其计算样式,但不标识每个节点的尺寸或位置。为了确定每个对象的确切大小和位置,浏览器从渲染树的根开始遍历它。
在网页上,大多数东西都是一个盒子。不同的设备和不同的桌面意味着无限数量的不同的视区大小。在此阶段,考虑到视区大小,浏览器将确定屏幕上所有不同框的尺寸。以视区的大小为基础,布局通常从body开始,用每个元素的框模型属性排列所有body的子孙元素的尺寸,为不知道其尺寸的替换元素(例如图像)提供占位符空间。
第一次确定节点的大小和位置称为布局。随后对节点大小和位置的重新计算称为回流。在我们的示例中,假设初始布局发生在返回图像之前。由于我们没有声明图像的大小,因此一旦知道图像大小,就会有回流。
一般意味着元素的内容、结构、位置或尺寸发生了变化,需要重新计算样式和渲染树。
即重绘。意味着元素发生的改变只是影响了元素的一些外观之类的时候(例如,背景色,边框颜色,文字颜色等),此时只需要应用新样式绘制这个元素就可以了。
当遇到上述的外链时,会单独开启一个下载线程去下载资源(http1.1 中是每一个资源的下载都要开启一个 http 请求,对应一个 tcp/ip 链接)
css 下载时异步的,不会阻塞浏览器构建 DOM 树;
但是会阻塞渲染,也就是在构建 render 树时,等到 css 下载解析后才进行(与浏览器优化有关,防止 css 规则不断变化,避免重复的构建)
遇到图片等资源时,直接就是异步下载,不会阻塞解析,下载完毕后直接用图片替换原有src的地方
实现下拉更新分三步
touchstart
事件,记录开始的位置,e.touches[0].pageY
/touchmove
事件,记录transitionHeight,也就是当前位置和初始位置的差值,大于0表示向下拉,并借助transitionY
属性使元素与手势同步变化,同时也该设置一个最大滑动值;touchend
事件, 若此时下拉达到刷新临界点,则出发callback,同时恢复元素的位置<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<main>
<p class="refreshText"></p>
<ul id="refreshContainer">
<li>111</li>
<li>222</li>
<li>333</li>
<li>444</li>
<li>555</li>
</ul>
</main>
<script>
// 1 记录touchstart的位置
var element = document.getElementById('refreshContainer');
var refreshText = document.querySelector('.refreshText');
var startPos = 0;
var transitionHeight = 0;
element.addEventListener('touchstart', function(e) {
console.log('初始位置', e.touches[0].pageY)
startPos = e.touches[0].pageY;
// element.style.position = 'relative';
element.style.transition = 'transform 0s';
}, false)
element.addEventListener('touchmove', function(e) {
console.log('当前位置:', e.touches[0].pageY);
transitionHeight = e.touches[0].pageY - startPos;
if (transitionHeight > 0 && transitionHeight < 60) {
refreshText.innerText = '下拉刷新';
element.style.transform = 'translateY('+transitionHeight+'px)';
}
}, false);
element.addEventListener('touchend', function(e) {
element.style.transition = 'transform 0.5s ease 1s';
element.style.transform = 'translateY(0px)';
if (transitionHeight > 55) {
refreshText.innerText = '释放更新';
}
refreshText.innerText = '更新中...';
//用delay模拟ajax请求
setTimeout(() => {
for(let i = 0; i < 5; i++) {
let tag = document.createElement('li');
tag.append(i);
element.appendChild(tag);
}
refreshText.innerText = '更新完毕...';
refreshText.innerText = '';
}, 300)
// todo...
}, false);
</script>
</body>
</html>
scrollTop + clientHeight >= scrollHeight
let clientHeight = document.documentElement.clientHeight; //浏览器高度
let scrollHeight = document.body.scrollHeight;
let scrollTop = document.documentElement.scrollTop;
let distance = 50; //距离视窗还用50的时候,开始触发;
if ((scrollTop + clientHeight) >= (scrollHeight - distance)) {
console.log("到底了,开始加载数据");
}
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.