leetcode

2021-08-31

4 median of two sorted arrays

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // merge
        vector<int> nums(nums1.size()+nums2.size());
        int i=0,j=0,index=0;
        while(i<nums1.size() && j<nums2.size()){
            if(nums1[i]<=nums2[j]){
                nums[index++] = nums1[i++];
            }else{
                nums[index++] = nums2[j++];
            }
        }
        while(i<nums1.size()){
            nums[index++] = nums1[i++];
        }
        while(j<nums2.size()){
            nums[index++] = nums2[j++];
        }
        // middle
        if(nums.size()%2==0){
            return (double(nums[nums.size()/2])+nums[nums.size()/2-1])/2;
        }else{
            return double(nums[nums.size()/2]);
        }
    }
};

68 左右文本对齐

class Solution {
public:
    /*
     * 1. 先采用贪心算法取出一行能够容纳的单词范围，设为bg, end
     * 2. 一行中，单词与单词之间有至少一个空格，称为spaceSuffix;
     *    除去spaceSuffix, 单词，剩下的空间就是spaceCount,它要合理分配在wordCount-1个单词间隙中。  
     * 3. spaceCount/(wordCount-1)块空间可以分配在每个单词间隙中，
     *    spaceCount%(wordCount-1)块空间从左到右一个一个分配在单词间隙中
     * 4. 特殊判断：
     *    如果一行只有一个单词，那么单词左对齐，然后右侧填满空格
     *    如果是在考虑最后一行，那么就要所有单词左对齐，中间只有一个空格，最后一个单词右侧填满空格
     */
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        int bg = 0, space=0;
        vector<string> ans;
        for(int i=0;i<words.size();i++){
            space += (words[i].size()+1);
            if(i==words.size()-1 || space+words[i+1].size()+1>maxWidth+1){
                ans.push_back(fillWords(words,bg,i,maxWidth,i==words.size()-1));
                bg = i+1;
                space = 0;
            }
        }
        return ans;
    }
private:
    string fillWords(vector<string>& words, int bg, int end, int maxWidth, bool lastLine){
        string ans;
        int wordCount = end-bg+1;
        if(wordCount==1){
            ans += words[bg];
            fill_n(back_inserter(ans),maxWidth-words[bg].size(),' ');
            return ans;
        }
        int spaceCount = maxWidth+1;
        for(int i=bg;i<=end;i++) spaceCount-=(words[i].size()+1);
        if(lastLine){
            for(int i=bg;i<=end;i++){
                ans+=words[i];
                if(i != end)
                	ans+=" ";
            }
            fill_n(back_inserter(ans), spaceCount,' ');
            return ans;
        }
        int spaceAvg = spaceCount/(wordCount-1);
        int spaceExtra = spaceCount%(wordCount-1);
        int spaceSuffix = 1;
        for(int i=bg;i<=end;i++){
            ans += words[i];
            if(i==end) break;
            fill_n(back_inserter(ans), spaceSuffix+spaceAvg+((i-bg)<spaceExtra), ' ');
        }
        return ans;
    }
};

95 Unique Binary Search Trees II(moderate)

https://leetcode.com/explore/challenge/card/september-leetcoding-challenge-2021/636/week-1-september-1st-september-7th/3961/

#include<bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
	/*
	 * 计算n=1的情况下，所有可能的BST保存在trees[1]中
	 * 计算n=2的情况下，所有可能的BST保存在trees[2]中
	 * ...
	 * 计算n=i的情况下，所有可能的BST保存在trees[i]中，若去j为根结点(1<=j<=i),那么左右子树可以在
	 *   trees[k](k<i)中找。但是会遇到一个问题,假如i=5,j=3,那么要计算右子树,右子树的结点应该是
	 *   [4,5]区间内，但是保存的trees[2]中树的结点是[1,2]区间的，因此要把复制trees[2]中的树，并且
	 *   更改对应的结点,比如1变成4,2变成5. 
	 */
    vector<TreeNode*> generateTrees(int n) {
    	trees[0].push_back(nullptr);
    	trees[1].push_back(new TreeNode(1));
    	for(int i=2;i<=n;i++){
    		for(int j=1;j<=i;j++){
    			// 考虑左子树,左子树的结点在[1,j-1]区间内
    			for(int k=0;k<trees[j-1].size();k++){
    				// 考虑右子树,右子树的结点在[j+1,i]区间内
					for(int k2=0;k2<trees[i-j].size();k2++){
						TreeNode* root = new TreeNode(j);
						root->left = (j-1==0?nullptr:copyTree(trees[j-1][k],0));
						root->right = (i-j==0?nullptr:copyTree(trees[i-j][k2],j));
						trees[i].push_back(root);
					}
				}
			}
		}
		return trees[n];
    }
    //test
    void print(int n){
    	for(int i=0;i<trees[n].size();i++){
    		print2(trees[n][i]);
    		cout<<endl;
		}
	}
	void print2(TreeNode* root){
		if(root){
			cout<<root->val<<" ";
			print2(root->left);
			print2(root->right);
		}else{
			cout<<"#"<<" ";
		}
	}
private:
	vector<TreeNode*> trees[10];
	TreeNode* copyTree(TreeNode* original, int add){
		TreeNode* root = nullptr;
		if(original == nullptr){
			return root;
		}
		root = new TreeNode();
		root->val = (original->val)+add;
		root->left = copyTree(original->left,add);
		root->right = copyTree(original->right,add);
		return root;
	}
};

int main(){
	Solution sol = Solution();
	sol.generateTrees(3);
	sol.print(3);
}

146. LRU Cache(moderate)

网址：https://leetcode.com/problems/lru-cache/

/* 
 * 本题采用链表形式表示LRU，链表头总是放最近访问过的结点，链表尾在空间不足时被驱逐掉
 */

#include<bits/stdc++.h>
using namespace std;

const int MAXCAPACITY = 3005;

/*
 * Node结点存储每个键值对的结点
 * next指向LRU结点方向，pre指向最近访问结点的访问
 * 如果此Node结点不存储兼职对，那么nextFree指向下一个空闲Node结点
 * 空闲Node结点的next=pre=0
 */
typedef struct Node{
    int key, value, next, pre, nextFree;
}Node;

class LRUCache {
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        head = tail = 0; // head和tail为0表示cache中还没有kv, kv从cache[1]开始放
        // 初始化空闲链表
        free = 1;
        for(int i=1;i<MAXCAPACITY-1;i++) cache[i].nextFree = i+1;
        cache[MAXCAPACITY-1].nextFree = 0;
    }
    
    /*
     * 若访问的key存在，则分为三种情况来考虑：
     *   1. head==index。直接返回key对应的值
     *   2. head!=index && index==tail: 将tail所指向的结点移动到head前面,更新tail和head
     *   3. head!=index && index!=tail: 将tail所指向的结点移动到head前面，更新head
     * 最后返回key对应的value
     */
    int get(int key) {
        unordered_map<int,int>::iterator it = mp.find(key);
        if(it==mp.end()) {
            return -1;
        }else{
            int index = it->second;
            if(head != index){
                if(index == tail){ // 2
                    // 更新tail
                    tail = cache[index].pre;
                    cache[tail].next = 0;
                    // index结点移动到head结点前面
                    cache[index].pre = 0;
                    cache[index].next = head;
                    cache[head].pre = index;
                    // 更新head
                    head = index;
                    // 返回值
                    return cache[index].value;
				}else{ // 3
					int pre = cache[index].pre, next = cache[index].next;
                    // 将index结点移动到head前面
                	cache[pre].next = next;
					cache[next].pre = pre;
                	cache[index].next = head;
                	cache[index].pre = 0;
                	cache[head].pre = index;
                    // 更新head
                	head = index;
                    // 返回key对应的value
                	return cache[index].value;
				}
            }else{ // 1
                return cache[index].value;
            }
        }
    }
    
    void put(int key, int value) {
    	// 当插入的key在cache中时，就更新这个key-value对，然后再访问一下key: get(key)
		if(mp.find(key) != mp.end()){
			int index = mp[key];
			cache[index].value = value;
			get(key);
			return;
		} 
        if(mp.size() >= this->capacity){
            // 从mp中删除tail指向的kv
            mp.erase(cache[tail].key);
            
            if(head == tail){
                // 将head结点移动到空闲链头部
            	cache[head].nextFree = free;
            	free = head;
                // 清空head结点中的pre和next
            	cache[head].pre = cache[head].next = 0;
                
            	head = tail = 0;
			}else{
				// 把tail指向的kv结点移动到空闲链头部
            	cache[tail].nextFree = free;
            	free = tail;
				// tail指向它的pre 
				int temp = tail;
				tail = cache[tail].pre;
				// 清空被删除结点中的pre和next
				cache[temp].pre = cache[temp].next = 0;
			}
        }
        // 从空闲链表中取出空块，放入kv，mp中加入kv, 加入到head前面, 更新空闲链表，
        cache[free].key = key;
        cache[free].value = value;
        mp[key] = free;
        cache[free].next = head==0?0:head; // 第一个kv插入进来时 
        if(head != 0)
            cache[head].pre = free;
        head = free;
        if(tail==0) tail=free; // 第一个kv插入进来时 
        free = cache[free].nextFree;
    }
private:
    int capacity;
    int head, tail, free; // tail指向LRU结点, head指向最近访问结点, free指向空闲链表的第一个结点
    Node cache[MAXCAPACITY]; // 键值对的池
    unordered_map<int,int> mp;  // 存储key到cache索引的映射
};

上述解法的速度只超过了6%的用户，为什么这么慢？

166 分数到小数

class Solution {
public:
    string fractionToDecimal(int numerator2, int denominator2) {
        long long numerator = numerator2, denominator = denominator2;
        // 预处理,将分子和分母都转换为正数，并判断结果是否为正数，如果是正数，则pos=true
        bool pos = true;
        if(numerator>0&&denominator<0){
            pos = false;
            denominator = -denominator;
        }else if(numerator<0 && denominator>0){
            pos = false;
            numerator = -numerator;
        }else if(numerator<0 && denominator<0){
            numerator = -numerator;
            denominator = -denominator;
        }

        // a[0]存储整数部分
        // a[1]及以后是小数部分,a[1]是十分位,a[2]是百分位...
        vector<long long> a;
        // 先计算整数部分
        a.push_back(numerator/denominator);
        numerator = numerator%denominator;
        // 如果numerator是0，则说明最终结果也是整数
        if(numerator == 0){
            return (pos?numToStr(a[0]):("-"+numToStr(a[0])));
        }else{
            bool loop = true; // 表示是否是循环小数
            unordered_map<int,int> mp;
            int beg, end;
            for(end=1;;end++){
                if(numerator == 0){
                    loop = false;
                    break;
                }else if(mp.find(numerator) != mp.end()){
                    beg = mp[numerator];
                    break;
                }else{
                    mp[numerator] = end;
                    numerator *= 10;
                    a.push_back(numerator/denominator);
                    numerator = numerator%denominator;
                }
            }
            end--;
            if(!loop){
                string ans;
                ans += numToStr(a[0]);
                ans += ".";
                for(int i=1;i<=end;i++){
                    ans += numToStr(a[i]);
                }
                return (pos?ans:("-"+ans));
            }else{
                string ans;
                ans += numToStr(a[0]);
                ans += ".";
                for(int i=1;i<beg;i++){
                    ans += numToStr(a[i]);
                }
                ans += "(";
                for(int i=beg;i<=end;i++){
                    ans += numToStr(a[i]);
                }
                ans += ")";
                return (pos?ans:("-"+ans));
            }
        }
    }
private:
    // i是一个正数
    // 将i转换为字符串
    string numToStr(long long i){
        char tmp[100];
        sprintf(tmp,"%lld",i);
        return string(tmp);
    }
};

187 重复的DNA序列

class Solution {
public:
    // 1. 遍历每个子串s2
    // 2. 看s2的id有没有出现过，若没有出现过，则加进去
    // 3. 若出现过，则看该id下的所有子串有没有和s2一样的，若没有，则加进去
    // 4. 否则，说明s2以前出现过，则把s2进到结果中
    vector<string> findRepeatedDnaSequences(string s) {
        if(s.size()<11){
            return vector<string>(0);
        }
        map<int,set<string>> mp;
        int prea=0, prec=0, preg=0, pret=0;
        for(int i=0;i<10;i++){
            if(s[i]=='A') prea++;
            else if(s[i]=='C') prec++;
            else if(s[i]=='G') preg++;
            else pret++;
        }
        mp[getId(prea,prec,preg,pret)].emplace(s.substr(0,10));

        set<string> ans;
        vector<string> ans2;
        for(int i=10;i<s.size();i++){
            if(s[i]=='A') prea++;
            else if(s[i]=='C') prec++;
            else if(s[i]=='G') preg++;
            else pret++;
            if(s[i-10]=='A') prea--;
            else if(s[i-10]=='C') prec--;
            else if(s[i-10]=='G') preg--;
            else pret--;
            
            int id = getId(prea,prec,preg,pret);
            string s2 = s.substr(i-9,10);
            if(mp.find(id) != mp.end()){
                if(mp[id].find(s2) != mp[id].end()){
                    ans.emplace(s2);
                }else{
                    mp[id].emplace(s2);
                }
            }else{
                mp[id].emplace(s2);
            }
        }
        for(string str:ans){
            ans2.emplace_back(str);
        }
        return ans2;
    }
private:
    // 计算一个长度为10的子串的Id，由A,C,G,T的个数算出来
    int getId(int prea,int prec,int preg,int pret){
        return prea*11*11*11 + prec*11*11 + preg*11 + pret;
    }
};

212 单词搜索2

解法1

class Solution {
public:
    /*
     * 1. 从board的任意一个单元格出发做dfs，如果能够找到一条路径使其组成这个单词，则把这个单词加到vec中
     */
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        vector<string> ans;
        for(string& w:words){
            vector<vector<bool>> vis(board.size(), vector<bool>(board[0].size(), false));
            bool flag = false;
            for(int i=0;i<board.size();i++){
                for(int j=0;j<board[0].size();j++){
                    if(dfs(board, w, 0, vis, {i,j})){
                        flag = true;
                        break;
                    }
                }
                if(flag) break;
            }
            if(flag) ans.push_back(w);
        }
        return ans;
    }
private:
    bool dfs(vector<vector<char>>& board, string& word, int beg, vector<vector<bool>>& vis, pair<int,int> p){
        if(beg >= word.size()) return true;
        char c = board[p.first][p.second];
        if(word[beg] != c) return false;
        vis[p.first][p.second] = true;
        if(beg+1 >= word.size()){
            vis[p.first][p.second] = false;
            return true;
        } 

        vector<int> dx = {0,0,1,-1};
        vector<int> dy = {1,-1,0,0};
        for(int i=0;i<4;i++){
            int x2=p.first+dx[i], y2=p.second+dy[i];
            if(x2<0 || x2>=board.size() || y2<0 || y2>=board[0].size()) continue;
            if(vis[x2][y2]) continue;
            if(dfs(board, word, beg+1, vis, {x2,y2})){
                vis[p.first][p.second] = false;
                return true;
            }
        }

        vis[p.first][p.second] = false;
        return false;
    }
};

解法2

前缀树解法，将words中的所有单词组织在一个前缀树中，然后从board的所有点开始遍历。

struct TrieNode{
    string word;
    unordered_map<char,TrieNode*> children;
    TrieNode(){
        this->word = "";
    }
};
class Solution{
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words){
        TrieNode* root = new TrieNode();
        set<string> res;
        vector<string> ans;
        
        for(string& word:words){
            insertTrie(root, word);
        }
        for(int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                dfs(board,i,j,root,res);
            }
        }
        for(string word:res){
            ans.emplace_back(word);
        }
        return ans;
    }
private:
    int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    static void insertTrie(TrieNode* root, const string& word){
        TrieNode* node = root;
        for(char c:word){
            if(!node->children.count(c)){
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->word = word;
    }
    void dfs(vector<vector<char>>& board, int x, int y, TrieNode* root, set<string>& res){
        char ch = board[x][y];
        if(!root->children.count(ch)){
            return;
        }
        root = root->children[ch];
        if(root->word.size() > 0){
            res.insert(root->word);
        }
        
        board[x][y] = '#';
        for(int i=0;i<4;i++){
            int nx = x+dirs[i][0];
            int ny = y+dirs[i][1];
            if(nx>=0 && nx<board.size() && ny>=0 && ny<board[0].size()){
                if(board[nx][ny] != '#'){
                    dfs(board, nx, ny, root, res);
                }
            }
        }
        board[x][y] = ch;
        
        return;
    }
};

223 矩形面积

class Solution {
public:
    int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        int x = min(ax2,bx2) - max(ax1,bx1);
        x = (x>=0?x:0);
        int y = min(ay2,by2) - max(ay1,by1);
        y = (y>=0?y:0);
        return (ax2-ax1)*(ay2-ay1) + (bx2-bx1)*(by2-by1) - x*y;
    }
};

273 整数转换英文表示

class Solution {
public:
    string numberToWords(int num) {
        if(num == 0) return "Zero";
        int thousand=1000,million=1000000,billion=1000000000;
        string ans;
        // 比如：在输出百万位前，看前面有没有更高的位输出，如果没有，则不用输出空格
        bool pre = false;
        // 十亿位
        if(num / billion != 0){
            ans += smallNumberToWords(num/billion);
            ans += " Billion";
            num %= billion;
            pre = true;
        }
        // 百万位
        if(num / million != 0){
            if(pre) ans += " ";
            ans += smallNumberToWords(num/million);
            ans += " Million";
            num %= million;
            pre = true;
        }
        // 千位
        if(num / thousand != 0){
            if(pre) ans += " ";
            ans += smallNumberToWords(num/thousand);
            ans += " Thousand";
            num %= thousand;
            pre = true;
        }
        if(num != 0){
            if(pre) ans += " ";
            ans += smallNumberToWords(num);
        }
        return ans;
    }
private:
    // 小于一千的数字的读法
    string smallNumberToWords(int num){
        static string bit[20] = {"Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
        static string bit2[10] = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};

        string ans;
        bool pre = false;
        // 百位
        if(num / 100 != 0){
            ans += bit[num/100] + " Hundred";
            num %= 100;
            pre = true;
        }
        // 如果num是0，则可以直接返回
        if(num == 0) return ans;
        // 这个时候，还有十位或个位
        if(pre) ans += " ";
        // 如果num<20，可以直接输出，然后返回
        if(num < 20){
            ans += bit[num];
            return ans;
        }
        // 如果num>=20，先输出twenty之类的，在输出个位
        ans += bit2[num/10];
        num %= 10;
        if(num != 0){
            ans += " ";
            ans += bit[num];
        }
        return ans;
    }
};

352 将数据流变为多个不相交区间

class SummaryRanges {
    class Node{
        public:
           int head, tail;
           bool exist; 
    };
public:
    SummaryRanges() {
        for(int i=0;i<MAXN;i++) {
            nodes[i].head = nodes[i].tail = -1;
            nodes[i].exist = false;
        }
    }
    
    void addNum(int val) {
        if(nodes[val].exist){
            return;
        }
        nodes[val].exist = true;
        nodes[val].head = nodes[val].tail = val;
        st.emplace(nodes[val].head);
        leftJoin(val);
        rightJoin(val);
    }
    
    vector<vector<int>> getIntervals() {
        vector<vector<int>> ans;
        for(auto i:st){
            ans.emplace_back(vector<int>{i, nodes[i].tail});
        }
        return ans;
    }
private:
    const static int MAXN = 10005;
    Node nodes[MAXN];
    set<int> st;
    // 以s开头的区间和以s-1结尾的区间合并, 如果s-1存在的话
    // 合并后改变相应的链表结构和st
    void leftJoin(int s){
        if(s==0 || !nodes[s-1].exist){
            return;
        }
        int tail = nodes[s].tail;
        nodes[tail].head = nodes[s-1].head;
        nodes[nodes[tail].head].tail = tail;
        st.erase(s);
    }
    void rightJoin(int s){
        if(!nodes[s+1].exist){
            return;
        }
        leftJoin(s+1);
        st.erase(s+1);
    }
};

/**
 * Your SummaryRanges object will be instantiated and called as such:
 * SummaryRanges* obj = new SummaryRanges();
 * obj->addNum(val);
 * vector<vector<int>> param_2 = obj->getIntervals();
 */

371 两整数之和

class Solution {
public:
    int getSum(int a, int b) {
        int ans = 0;
        int t = 0;
        for(int i=0;i<32;i++){
            int c = (a&1) + (b&1) + t; // 这里的括号不能省
            ans = ans | ((c%2)<<i);

            t = c/2;
            a = a>>1;
            b = b>>1;
        }
        return ans;
    }
};

405 数字转换为十六进制数

class Solution {
public:
    /*
     * 将num转换为unsigned int类型的n, 这里有个坑：-1右移之后还是-1,原因是左边补1而不是0
     * 考虑n的低4位，转换为10进制数，然后转换为对应的1-9,a-f字符，然后累加到ans前面
     * n右移4位
     * 重复上述操作，直到n为0
     */
    string toHex(int num) {
        unsigned int n = (unsigned int)num;
        if(n == 0) return "0";
        string ans;
        while(n !=0){
            int a = n & (15);
            char temp[2];
            temp[0] = (a>=10?(a-10+'a'):('0'+a));
            temp[1] = '\0';
            ans = string(temp) + ans;
            n >>= 4;
        }
        return ans;
    }
};

414 第三大的数

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        priority_queue<int> q;
        for(int i:nums){
            q.push(i);
        }
        int maxnum = q.top(); 
        q.pop();
        while(!q.empty() && q.top()==maxnum) {
            q.pop();
        }
        int temp;
        if(!q.empty()){
            temp = q.top();
            q.pop();
        }else{
            return maxnum;
        }
        while(!q.empty() && q.top()==temp) {
            q.pop();
        }
        return (q.empty()?maxnum:q.top());
    }
};

430 扁平化多级双向链表

思路：当p指针移动到3号点时，会做下述事情：

递归将p->child扁平化，并返回子链表扁平化后的头结点和尾结点ht, 保存p->next到next中
更改相关指针：p与ht.first之间的，ht.second与next之间的

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
*/

class Solution {
public:
    /*
     * 递归做法:
     *   写一个递归程序，功能是将一个链表扁平化，返回扁平化后的头结点，尾结点
     *   遍历链表的每个结点，如果遇到含有子链表的结点，则递归调用来扁平化子链表
     */
    Node* flatten(Node* head) {
        pair<Node*, Node*> p = flat(head);

        return p.first;
    }
private:
    pair<Node*, Node*> flat(Node* head){
        Node* p = head, *pre;
        pair<Node*, Node*> ans;
        while(p){
            if(!p->child){
                pre = p;
                p = p->next;
            }else{
                Node* next = p->next;
                pair<Node*, Node*> ht = flat(p->child);
                p->next = ht.first;
                ht.first->prev = p;
                p->child = nullptr;
                ht.second->next = next;
                if(next) next->prev = ht.second;
                pre = ht.second;
                p = next;
            }
        }
        return {head, pre};
    }
};

437 路径总和3

思路：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        map<int,int> mp;
        return getPathNum(root, targetSum, mp);
    }
private:
    // 1. 得到从root开始的所有路径中路径长度等于path的路径个数
    // 2. 递归分析root->left, root->right的所有路径中长度等于path的路径个数
    // 顺便得到root->left的所有可能路径长度，保存在leftPathNum中，root->right也同理
    // 3. 合并的意思: {(1,2),{3,1}}, {(1,1), (2,1),{3,2}}，两个map合并，则有{{1,3},{2,1},{3,3}}
    // 若root->val=10，则变为{(10,1),(11,3),(12,1),(13,3)}
    // 合并算法可以采用双指针法
    int getPathNum(TreeNode* root, int path, map<int,int>& res){
        if(!root){
            return 0;
        }
        map<int,int> leftPathNum;
        map<int,int> rightPathNum;
        int num1 = getPathNum(root->left, path, leftPathNum);
        int num2 = getPathNum(root->right, path, rightPathNum);
        // 合并
        auto it1 = leftPathNum.begin();
        auto it2 = rightPathNum.begin();
        while(it1!=leftPathNum.end() && it2!=rightPathNum.end()){
            if(it1->first == it2->first){
                res[it1->first+root->val] = it1->second+it2->second;
                it1++;
                it2++;
            }else if(it1->first < it2->first){
                res[it1->first+root->val] = it1->second;
                it1++;
            }else{
                res[it2->first+root->val] = it2->second;
                it2++;
            }
        }
        while(it1 != leftPathNum.end()){
            res[it1->first+root->val] = it1->second;
            it1++;
        }
        while(it2 != rightPathNum.end()){
            res[it2->first+root->val] = it2->second;
            it2++;
        }
        if(res.find(root->val) != res.end()){
            res[root->val] += 1;
        }else{
            res[root->val] = 1;
        }
        
        int ans;
        if(res.find(path) != res.end()){
            ans = res[path] + num1 + num2;
        }else{
            ans = num1 + num2;
        }

        return ans;
    }
};

441 排列硬币

解法1

class Solution {
public:
    int arrangeCoins(int n) {
        vector<long long> dp(100000,0);
        int i;
        for(i=1;dp[i-1]<n;i++){
            dp[i] = dp[i-1] + i;
        }
        return (dp[i-1]==n?(i-1):(i-2));
    }
};

解法2

class Solution {
public:
    int arrangeCoins(int n) {
        long long cnt = 0;
        int i;
        for(i=1;cnt<n;i++){
            cnt += i;
        }
        return (cnt==n?(i-1):(i-2));
    }
};

解法3

class Solution {
public:
    int arrangeCoins(int n) {
        long long left = 1, right = 1e5;
        long long mid;
        long long res;
        while(left < right){
            mid = (left + right) / 2;
            res = mid*(mid+1)/2;
            if(res < n){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        res = left*(left+1)/2;
        return (res==n?left:(left-1));
    }
};

447 回旋镖的数量

解法1

使用组合算法，从size个点中找出3个点的所有组合，然后计算这三个点的6个排列中有哪些是符合飞镖的。

但是这个算法超时了。

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int m=3, size=points.size(),ans=0;
        zuhe(points, size, m, ans);
        return ans;
    }
private:
    /*
     * group最后是三个点的集合，这三个点是从所有点中取出来的一个组合
     * 然后计算这三个点的6个排列中有哪些是符合飞镖的
     */ 
    vector<pair<int,int>> group;
    void zuhe(vector<vector<int>>& points, int size, int m, int& ans){
        if(m==0){
            ans += cal();
            return;
        }
        for(int i=size-1; i>=m-1; i--){
            group.push_back({points[i][0], points[i][1]});
            zuhe(points, i, m-1, ans);
            group.pop_back();
        }
    }
    /*
     * 此时，group有三个点了，可以分析这三个点的6个排列中有哪些是符合飞镖的
     * 返回结果
     */
    int cal(){
        int ans = 0;
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                for(int k=0;k<3;k++){
                    if(i==j || i==k || j==k) continue;
                    int x1=group[i].first, y1=group[i].second;
                    int x2=group[j].first, y2=group[j].second;
                    int x3=group[k].first, y3=group[k].second;
                    if(pow(x2-x1,2)+pow(y2-y1,2) == pow(x3-x1,2)+pow(y3-y1,2)){
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
};

解法2

class Solution {
public:
    /*
     * 我们先固定住三个点中的第一个点p，然后从剩下的点中找
     * 所有与p距离相等的点的集合，这个集合有多个
     * 比如, set1表示距离为dist1的点的集合，有n1个
     *       set2表示距离为dist2的点的集合，有n2个...
     * 最后由p点开头的飞镖的个数为n1*(n1-1)+n2*(n2-1)+...
     * 因为n1个点中找两个点排列数为n1*(n1-1)
     */
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int ans = 0;
        unordered_map<int,int> cnt;
        for(int i=0;i<points.size();i++){
            cnt.clear();
            for(int j=0;j<points.size();j++){
                if(i==j) continue;
                int x = pow(points[i][0]-points[j][0],2);
                int y = pow(points[i][1]-points[j][1],2);
                cnt[x+y]++;
            }
            for(auto& p:cnt){
                ans += p.second*(p.second-1);
            }
        }
        return ans;
    }
};

470 Implement Rand10() Using Rand7()

https://leetcode.com/problems/implement-rand10-using-rand7/

// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7

class Solution {
public:
    int rand10() {
        int a,b;
        do{
            a = rand7();
        }while(a==7);
        do{
            b = rand7();
        }while(b>5);
        return (a%2==0?b:b+5);
    }
};

502 IPO

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
    	int size = profits.size();
    	using pii = pair<int,int>;
        vector<pii> projs(size);
        for(int i=0;i<size;i++){
        	projs[i] = {profits[i],capital[i]};
		}
        sort(projs.begin(),projs.end(),[](pii a,pii b){
        	return a.second<b.second;
		});
        
        priority_queue<int> q; // 存利润 
        int i=0;
		int maxCapital = w;
		while(k--){
			for(;i<size;i++){
				if(projs[i].second <= maxCapital) q.push(projs[i].first);
				else break;
			}
			if(q.empty()) break;
			int profit = q.top();
			q.pop();
			maxCapital += profit;
		}
        return maxCapital;
    }
};

517

class Solution {
public:
    int findMinMoves(vector<int>& machines) {
        int n = machines.size();
        int sum = 0;
        for(int i:machines) sum+=i;
        int target = sum/n;
        if(sum%n != 0) return -1;
        
        vector<int> move(n,0);
        int res = 0;
        for(int i=0;i<n-1;i++){
            if(machines[i]>target){
                move[i] += machines[i]-target;
                machines[i+1] += machines[i]-target;
                machines[i] = target;
                res = max(res, move[i]);
            }else{
                move[i+1] = target-machines[i];
                machines[i+1] -= target-machines[i];
                machines[i] = target;
                res = max(res, move[i+1]);
            }
        }
        
        return res;
    }
};

524 通过删除字母匹配到字典里的最长单词(middle)

解法1

采用双指针法来找到一个串是否含有给定子串

class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        sort(dictionary.begin(), dictionary.end(), [](string& a, string& b)->bool{
            if(a.size() == b.size()){
                return a<b;
            }
            return a.size()>b.size();
        });
        for(string& s2:dictionary){
            if(findSubStr(s, s2)){
                return s2;
            }
        }
        return "";
    }
private:
    // a中有子串b吗
    bool findSubStr(string& a, string& b){
        int i=0, j=0;
        while(i<a.size() && j<b.size()){
            if(a[i]==b[j]){
                i++;
                j++;
            }else{
                i++;
            }
        }
        if(j<b.size()){
            return false;
        }
        return true;
    }
};

解法2

我们可以优化一下解法1的代码，解法1的代码可以发现指向源字符串的指针i是一点一点移动的，如果这个指针能够一下子移动到目标串的指针j所指向的字符，就高效了。

源：abcdefg
目：be
j=1
i应该指向'e'出现的第一个位置，也就是4

我们可以计算源串的每个字符从该位置开始往后每一个字符第一次出现的位置。

f[i][j]表示i位置的字符对应j号字符第一次出现的位置（j=0表示’a’）

class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        sort(dictionary.begin(), dictionary.end(), [](string& a, string& b)->bool{
            if(a.size() == b.size()){
                return a<b;
            }
            return a.size()>b.size();
        });
        // 计算源串的每个字符从该位置开始往后每一个字符第一次出现的位置。
        vector<vector<int>> dp(s.size(), vector<int>(26, -1));
        for(int i=s.size()-2; i>=0; i--){
            for(int j=0; j<26; j++){
                if('a'+j == s[i+1]){
                    dp[i][j] = i+1;
                }else{
                    dp[i][j] = dp[i+1][j];
                }
            }
        }

        for(string& s2:dictionary){
            if(findSubStr(s, dp, s2)){
                return s2;
            }
        }
        return "";
    }
private:
    // a中有子串b吗
    bool findSubStr(string& a, vector<vector<int>>& dp, string& b){
        int i = 0;
        for(int j=0;j<b.size();j++){
            if(i>=a.size() || i==-1){
                return false;
            }else if(b[j] == a[i]){
                i++;
            }else if(dp[i][b[j]-'a'] != -1){
                i = dp[i][b[j]-'a'] + 1;
            }else{
                return false;
            }
        }
        return true;
    }
};

565 Array Nesting(moderate)

使用unordered_map记录加入s数组的数字。

#include<bits/stdc++.h>
using namespace std;
#define DEBUG1 1
#define DEBUG2 2

class Solution{
public:
    int arrayNesting(vector<int>& nums){
    	int maxCount = 1;
    	for(int i=0;i<nums.size();i++){
    		int head = i;
        	int p = head;
        	unordered_map<int,int> mp;
        	int count = 0;
        	unordered_map<int,int>::iterator it;
        	do{
            	mp[nums[p]] = 1;
            	count++;
            	p = nums[p];
            	it = mp.find(nums[p]);
        	}while(it==mp.end());
        	maxCount = max(count,maxCount);
		}
        
        return maxCount;
    }       
}; 
int main(){ 
    Solution sol = Solution();
//#if(DEBUG & DEBUG1)
    /*cout<<"this is debug1"<<endl;
    vector<int> nums = {5,4,0,3,1,6,2};
    int ans = sol.arrayNesting(nums);
    cout<<"the nums is {5,4,0,3,1,6,2}, and the ans is "<<ans<<endl;*/
//#endif

//#if(DEBUG & DEBUG2)
    cout<<"this is debug2"<<endl;
    vector<int> nums = {0,2,1};
    int ans = sol.arrayNesting(nums);
    cout<<"the nums is {0,1,2}, and the ans is "<<ans<<endl;
//#endif
}

使用visited数组记录插入到s数组中的数字。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005

class Solution{
public:
    int arrayNesting(vector<int>& nums){
		//int visited[MAXN];
		vector<int> visited(MAXN);
    	int maxCount = 1;
    	for(int i=0;i<nums.size();i++){
    		int head = i;
        	int p = head;
            if(visited[nums[p]]!=0)continue;
        	// memset(visited,0,sizeof(visited));
        	int count = 0;
        	do{
            	visited[nums[p]] = 1;
            	count++;
            	p = nums[p];
        	}while(visited[nums[p]] == 0);
        	maxCount = max(count,maxCount);
		}
        
        return maxCount;
    }       
}; 
int main(){ 
    Solution sol = Solution();
//#if(DEBUG & DEBUG1)
    /*cout<<"this is debug1"<<endl;
    vector<int> nums = {5,4,0,3,1,6,2};
    int ans = sol.arrayNesting(nums);
    cout<<"the nums is {5,4,0,3,1,6,2}, and the ans is "<<ans<<endl;*/
//#endif

//#if(DEBUG & DEBUG2)
    cout<<"this is debug2"<<endl;
    vector<int> nums = {0,2,1};
    int ans = sol.arrayNesting(nums);
    cout<<"the nums is {0,2,1}, and the ans is "<<ans<<endl;
//#endif
}

注意：在C++中，不要在类中使用全局变量，否则会出现非常难以察觉的底层错误。比如上述代码的visited数组应该放在类成员函数中。

583 两个字符串的删除操作

思路：

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word2.size()+1, vector<int>(word1.size()+1));
        for(int i=0;i<=word1.size();i++){
            dp[0][i] = i;
        }
        for(int i=0;i<=word2.size();i++){
            dp[i][0] = i;
        }
        for(int i=1;i<=word2.size();i++){
            for(int j=1;j<=word1.size();j++){
                dp[i][j] = min(min(dp[i][j-1]+1, dp[i-1][j]+1), 
                    (word2[i-1]==word1[j-1]?dp[i-1][j-1]:dp[i-1][j-1]+2));
            }
        }
        return dp[word2.size()][word1.size()];
    }
};

587 Erect the Fence(hard)

解法1

https://leetcode.com/problems/erect-the-fence/discuss/1442266/A-Detailed-Explanation-with-Diagrams-(Graham-Scan)

https://www.cnblogs.com/hxsyl/p/3222688.html

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> outerTrees(vector<vector<int>>& trees) {
        sort(trees.begin(),trees.end(),cmp);
        vector<vector<int>> lower, upper;
        for(int i=0;i<trees.size();i++){
            while(lower.size()>=2 && cmp2(lower[lower.size()-2],lower[lower.size()-1], trees[i])<0)
                lower.pop_back();
            while(upper.size()>=2 && cmp2(upper[upper.size()-2],upper[upper.size()-1], trees[i])>0)
                upper.pop_back();
            lower.push_back(trees[i]);
            upper.push_back(trees[i]);
        }
        // 集合合并
        set<vector<int>> st;
        vector<vector<int>> ans;
        st.insert(lower.begin(),lower.end());
        st.insert(upper.begin(),upper.end());
        for(set<vector<int>>::iterator it=st.begin(); it!=st.end(); it++){
            ans.push_back((*it));
        }
        return ans;
    }
private:
    /*
     * 将trees的元素排序，首先按照x递增排序，然后按照y递增排序
     * 这样排序的原因是：我们要用卷包裹Gift Wrapping解决这个问题，因此要找到最外围的元素
     *   很显然，最左边的或者最下边的一定是在外围的。
     */
    static bool cmp(vector<int>& a, vector<int>& b){
        int ax=a[0],ay=a[1];
        int bx=b[0],by=b[1];
        if(ax!=bx){
        	return ax<bx;
		}else{
			return ay<by;
		}
    }
    
    /*
     * 如果ab的斜率大于ac的斜率：返回1
     * 相等：返回0
     * 小于：返回-1
     */
    int cmp2(vector<int> a, vector<int> b, vector<int> c){
        int ax=a[0],ay=a[1];
        int bx=b[0],by=b[1];
        int cx=c[0],cy=c[1];
        int x = (cy-by)*(bx-ax)-(by-ay)*(cx-bx);
        if(x>0)return 1;
        else if(x==0) return 0;
        else return -1;
    }
};

600 不包含连续1的非负整数

解法1

class Solution {
public:
    int findIntegers(int n) {
        int num[2][40], pow2[31]; // pow2[i]表示2的i幂次
        num[1][0] = 0;
        num[0][0] = num[0][1] = num[1][1] = 1;
        pow2[0] = 1;
        for(int i=2;i<40;i++){
            num[0][i] = num[0][i-1]+num[1][i-1];
            num[1][i] = num[0][i-1];
        }
        for(int i=1;i<31;i++) pow2[i] = pow2[i-1]*2;

		n = n+1;
        int k = getBinaryLenOfN(n);
        int res = num[0][k-1]+num[1][k-1];
        do{
            n = n-pow2[k-1];
            int k2 = getBinaryLenOfN(n);
            if(k2==0) break;
            res += (num[0][k2-1]+num[1][k2-1]);
            if(k2 == k-1) break;
            else k = k2;
        }while(k!=0);
        return res;
    }
private:
    // 求出n的二进制形式有几位
    int getBinaryLenOfN(int n){
        int k = 0;
        while(n!=0){
            k++;
            n=n/2;
        }
        return k;
    }
};

解法2

朋友写的rust解法代码

impl Solution {
    pub fn find_integers(n: i32) -> i32 {
        let n = n + 1;
        let b: Vec<_> = format!("{:b}", n).chars().rev().collect();
        let n = b.len();
        let dp: Vec<_> = (0..n)
            .scan((1, 0), |s, _| {
                *s = (s.0 + s.1, s.0);
                Some(*s)
            })
            .collect();
        let mut ans = 0;
        for i in (0..n).rev() {
            if b[i] == '1' {
                ans += dp[i].0;
            }
            if i < b.len() - 1 && b[i] == '1' && b[i + 1] == '1' {
                break;
            }
        }
        ans
    }
}

639 解码方法2

class Solution {
public:
    int numDecodings(string s) {
        vector<long long> dp(s.size());
        dp[0] = getOne(s.substr(0,1));
        if(s.size()==1){
            return dp[0];
        }
        dp[1] = getOne(s.substr(0,1))*getOne(s.substr(1,1)) + getTwo(s.substr(0,2));
        for(int i=2;i<s.size();i++){
            dp[i] = ((dp[i-1]*getOne(s.substr(i,1)))%mod + (dp[i-2]*getTwo(s.substr(i-1,2)))%mod)%mod;
        }
        return dp[s.size()-1];
    }
private:
    static const int mod = 1e9+7;
    int getOne(string s){
        if(s[0] != '*'){
            if(s[0] == '0'){
                return 0;
            }else{
                return 1;
            }
        }
        return 9;
    }
    int getTwo(string s){
        if(s[0]=='0'){ // 0*
            return 0;
        }else if(s[0]=='1'){ 
            if(s[1]!='*'){ // 比如: 12
                return 1;
            }else{ // 比如: 1*
                return 9;
            }
        }else if(s[0]=='2'){
            if(s[1]=='*'){ // 2*
                return 6;
            }else if(s[1] <= '6'){ // 比如: 25
                return 1;
            }else{ // 比如: 27
                return 0;
            }
        }else if(s[0]>='3' && s[0]<='9'){ // 比如: 5*
            return 0;
        }else{
            if(s[1]=='*'){ // 比如: **
                return 15;
            }else if(s[1]>='0' && s[1]<='6'){ // 比如: *5
                return 2;
            }else{ // 比如: *7
                return 1;
            }
        }
    }
};

673 最长递增子序列的个数

解法 1

我将{长度，结尾值}保存进pq优先队列中，比如有一个长度为5的子串，它的结尾是7，那么就把{5, 7}push到pq中。每次考虑以nums[i]为结尾的最长子串时，就要从pq中分析：

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size());
        priority_queue<pair<int,int>> pq; // 保存(长度,结尾值)的优先队列
        int maxLen = 1; // 最长递增子序列的长度起码也是1
        int num = 1; // 最长递增子序列的个数
        dp[0] = 1;
        pq.push({1,nums[0]});

        queue<pair<int,int>> q; // 保存从pq中pop的元素以及应该push到pq中的新元素
        for(int i=1;i<nums.size();i++){
            dp[i] = 1;
            while(!pq.empty()){
                int len = pq.top().first, tail = pq.top().second;
                pq.pop();
                q.push({len, tail});
                if(dp[i] != 1){ // 如果以nums[i]为结尾的子串找到了最长子串
                    if(len < dp[i]-1){
                        break;
                    }
                }
                if(tail<nums[i]){ // 如果tail小于nums[i]，说明nums[i]前面可以时以tail为结尾的子串
                    if(len+1 > maxLen){
                        maxLen = len+1;
                        num = 1;
                    }else if(len+1 == maxLen){
                        num++;
                    }
                    dp[i] = len+1;
                    q.push({dp[i], nums[i]}); 
                }
            }
            if(dp[i] == 1){
                if(dp[i] == maxLen){
                    num++;
                }
                q.push({dp[i], nums[i]});
            }
            while(!q.empty()){
                pair<int,int> p = q.front();
                q.pop();
                pq.push(p);
            }
        }
        return num;
    }
};

以上代码超时了。分析以上代码，发现有很多改进之处，比如我可以用map<int, map<int,int>> mp的数据结构代替pq，因为mp[i]表示长度为i的所有子串,mp[i][j]表示长度为i，以j结尾的子串的个数,mp的键降序排列

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size());
        map<int,map<int,int>,greater<int>> mp;
        dp[0] = 1;
        int maxLen = 1, num = 1;
        mp[1][nums[0]] = 1;
        
        for(int i=1;i<nums.size();i++){
            dp[i] = 1;
            map<int,int> mp2; 
            for(auto it:mp){
                if(dp[i] != 1) break;
                for(auto it2:(it.second)){
                    if(it2.first < nums[i]){
                        if(it.first+1 > maxLen){
                            maxLen = it.first+1;
                            num = it2.second;
                        }else if(it.first+1 == maxLen){
                            num += it2.second;
                        }
                        dp[i] = it.first+1;
                        mp2[nums[i]]+=it2.second;
                    }
                }
            }
            if(dp[i] == 1){
                mp2[nums[i]]++;
                if(dp[i] == maxLen) num++;
            }
            for(auto it:mp2){
                mp[dp[i]][it.first] += it.second;
            }
        }
        return num;
    }
};

678 有效的括号字符串

解法1

我们很自然的会仍然用两个栈记录目前为止不能匹配的字符，也就是*和(，每次出现右括号我们就应该去两个栈匹配可以匹配的左括号。

而*可以作为任何括号，也可以作为空字符串，所以我们应该优先用左括号匹配，所以我们出栈的策略如下：

遇到左括号，直接进栈，记录括号的位置。
遇到星号，直接进栈，记录星号的位置。
遇到右括号：
a: 左括号栈里有元素，直接出栈。
b: 左括号栈里无元素，*栈里有元素，直接出栈。无元素的话就已经匹配失败了。
如果遍历完数组的话，我们可能会发现左括号栈里还有结余元素。如果是20题的情况，已经失败了。但现在我们可能还有一些星号可以作为右括号用，所以我们进行下面的匹配操作：
对左括号栈逐一出栈，然后去看此时星号栈的栈顶，如果栈顶元素的位置大于左括号栈顶元素的位置，说明星号在括号的右侧，可以匹配。否则不可。

class Solution {
public:
    bool checkValidString(string s) {
        stack<int> stk;
        stack<int> stk2;
        for(int i=0;i<s.size();i++){
            if(s[i]=='('){
                stk.push(i);
			}else if(s[i]==')'){
			    if(stk.empty()){
					if(stk2.empty()){
						return false;
					}else{
						stk2.pop();
					}
				}else{
					stk.pop();
				}
			}else if(s[i]=='*'){
				stk2.push(i);
			}
		}
		while(!stk.empty()){
            if(stk2.empty())return false;
			int aindex=stk.top();
			int bindex=stk2.top();
			if(bindex>aindex){
				stk.pop();
				stk2.pop();
			}else{
				return false;
			}
		}
		return true;
    }
};

解法2

反转法：

class Solution {
public:
    bool checkValidString(string s) {
		int rst=0;
		for(auto& c:s){
			if(c=='('){
				rst++;
			}else if(c==')'){
				rst--;
			}else if(c=='*'){
				rst++;
			}
			if(rst<0) return false;
		}
		rst=0;
		reverse(s.begin(),s.end());
		for(auto& c:s){
			if(c==')'){
				rst++;
			}else if(c=='('){
				rst--;
			}else if(c=='*'){
				rst++;
			}
			if(rst<0) return false;
		}
		return true;
	}
};

725 分隔链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        // 计算size
        int size = 0;
        ListNode* p = head;
        while(p != nullptr){
            size++;
            p = p->next;
        }

        int base = size/k;
        int i = 0, num = 0; // i表示链表号，num表示当前链表的数量
        ListNode* cur = head, *pre, *curLink;
        vector<ListNode*> ans;
        while(cur != nullptr){
            int trueNum = base + (1?i<size%k:0);
            if(num < trueNum){
                if(num == 0){
                    curLink = cur;
                    num++;
                    pre = cur;
                    cur = cur->next;
                }else{
                    num++;
                    pre = cur;
                    cur = cur->next;
                }
            }
            if(num == trueNum){
                i++;
                num = 0;
                pre->next = nullptr;
                ans.push_back(curLink);
            }
        }
        for(int i=ans.size();i<k;i++){
            ans.push_back(nullptr);
        }
        return ans;
    }
};

834 Sum of Distances in Tree

https://leetcode.com/problems/sum-of-distances-in-tree/

解法1

采用n次BFS的做法，假如要算i点到其他点的距离之和，就从i点做BFS，然后标记每个遍历到的点的层次（i点是第0层），然后将它们的层次加在一起，就是最终的答案。但是这种做的时间复杂度很高。

解法2

class Solution {
public:
    vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
        vector<int> subtree(n,1),ans(n,0),adj[n];
        for(int i=0;i<edges.size();i++){
            adj[edges[i][0]].push_back(edges[i][1]);
            adj[edges[i][1]].push_back(edges[i][0]);
        }
        ans[0] = dfs(0,adj,subtree,-1); // 默认将0作为整个树的根结点，计算0的ans
        dfs2(0,adj,subtree,ans,-1);
        return ans;
    }
private:
    /* 
     * 计算u点到所有子结点的距离之和
     * 在这个过程中，会计算每个子树的结点数量，答案就保存在subtree中
     * par是u的夫结点
     */
    int dfs(int u,vector<int> adj[],vector<int>& subtree,int par){
        int res = 0;
        for(auto v : adj[u]){
            if(v == par) continue;
            int res_v = dfs(v,adj,subtree,u);
            res+=res_v;
            res+=subtree[v];
            subtree[u]+=subtree[v];
        }
        return res;
    }
    /*
     * 根据u的ans计算u的每个子结点的ans
     */
    void dfs2(int u,vector<int> adj[],vector<int>& subtree,vector<int>& ans,int par){
        for(auto v : adj[u]){
        	if(v==par)continue;
            ans[v] = ans[u]-subtree[v]+subtree[0]-subtree[v];
            dfs2(v,adj,subtree,ans,u);
        }
    }
};

899 Orderly Queue

样例分析

样例1

abd efa  move a
bde faa  move b
def aab  move d
efa abd  move e
faa bde  move f
aab def

样例2

bdc zyxa  move b
dcz yxab  move c
dzy xabc  move d
zyx abcd  move x
zya bcdx  move y
zab cdxy  move z
abc dxyz

样例3

bdc zayxpn  move b
dcz ayxpnb  move c
dza yxpnbc  move d
zay xpnbcd  move y
zax pnbcdy  move x
zap nbcdyx  move p
zan bcdyxp  move n
zab cdyxpn  move z
abc dyxpnz  move a
bcd yxpnza  move b
cdy xpnzab  move c
dyx pnzabc  move d
yxp nzabcd  move p
yxn zabcdp  move x
ynz abcdpx  move y
nza bcdpxy  move n
zab cdpxyn  move z
abc dpxynz  
......
xyn zabcdp  move n
xyz abcdpn  
......
pnx yzabcd  move n
pxy zabcdn
......
abcdnxyz

解法1

class Solution {
public:
    /*
     * 若k==1：s的长度是size，那么s循环左移会产生size个串，比较这size个串中的最小的
     * 若k>=2: 排序
     */
    string orderlyQueue(string s, int k) {
        if(k==1){
            string ans = s;
            for(int i=0;i<s.size();i++){
                ans = min(ans, s.substr(i)+s.substr(0,i));
            }
            return ans;
        }
        sort(s.begin(),s.end());
        return s;
    }
};

1436 旅行终点站

解法1

class Solution {
public:
    /*
     * 把所有的cityA记录在s1中，所有经过的city记录在s2中
     * s2-s1就是答案
     */
    string destCity(vector<vector<string>>& paths) {
        set<string> s1, s2;
        for(auto p:paths){
            s1.emplace(p[0]);
            s2.emplace(p[0]);
            s2.emplace(p[1]);
        }
        auto it1=s1.begin(), it2=s2.begin();
        while(it1!=s1.end() && it2!=s2.end()){
            if((*it1) != (*it2)){
                return *it2;
            }
            it1++;
            it2++;
        }
        return (*it2);
    }
};

解法2

class Solution {
public:
    /*
     * cityA肯定不会是终点
     * 将cityA保存在unordered_set中，然后遍历所有的cityB,
     * 看哪个cityB不在这个unordered_set中
     */
    string destCity(vector<vector<string>>& paths) {
        unordered_set<string> s1;
        for(auto p:paths){
            s1.emplace(p[0]);
        }
        string ans;
        for(auto p:paths){
            if(s1.find(p[1]) == s1.end()){
                ans = p[1];
                break;
            }
        }
        return ans;
    }
};

1894 找到需要补充粉笔的学生编号

https://leetcode-cn.com/problems/find-the-student-that-will-replace-the-chalk/

class Solution {
public:
    int chalkReplacer(vector<int>& chalk, int k) {
        // left: 表示经过完整的m轮后剩下了多少粉笔
        // 保证m+1轮会超出粉笔总数
        long long total = 0;
        for(int i:chalk) total+=i;
        long long left = k%total;

        // 计算第几个学生却粉笔了, 答案是i
        long long sum = chalk[0],i=0;
        while(left>=sum){
            sum += chalk[++i];
        }
        return i;
    }
};

5870 每棵子树内缺失的最小基因值

https://leetcode-cn.com/problems/smallest-missing-genetic-value-in-each-subtree/

基本思路

主要思路是：首先根据parents父亲表示法构造图的邻接表表示法graph；genes存储每个结点的对应树的所有基因，但是为了之后的编程方便，每个结点都默认有0这个基因；ans存储每个结点的最小缺失基因。

采用递归算法dfs，计算一个结点的ans值和genes值，计算方法如下图所示：

class Solution{
public:
    vector<int> smallestMissingValueSubtree(const vector<int> &parents, const vector<int>&nums){
        vector<vector<int>> graph(parents.size(),vector<int>{});
        vector<set<int>> genes(parents.size(),{0});
        vector<int> ans(parents.size());
        for(int i=1;i<parents.size();i++){
            graph[parents[i]].emplace_back(i);
        }
        for(int i=0;i<nums.size();i++){
            genes[i].emplace(nums[i]);
        }
        dfs(0,-1,graph,genes,ans); 
        return ans;
    }
private:
    void dfs(int u, int father, vector<vector<int>>&graph, vector<set<int>>&genes, vector<int>&ans){
        int cur = 0;
        for(const int& v:graph[u]){
            //if(v==father) continue;
            dfs(v, u, graph, genes, ans);
            cur = max(cur, ans[v]);
            for(const int& g:genes[v]){
            	genes[u].emplace(g);
        	}
        }
        auto it = genes[u].lower_bound(cur);
        for(;it!=genes[u].end();it++){
            if(*it != cur){
                ans[u] = cur;
                return;
            }
            cur++;
        }
        ans[u] = cur;
    }
};

上述代码超时了，原因是23-25行的set插入操作。我们在set合并时，永远把小的set合并到大的set中。

class Solution{
public:
    vector<int> smallestMissingValueSubtree(const vector<int> &parents, const vector<int>&nums){
        vector<vector<int>> graph(parents.size(),vector<int>{});
        vector<set<int>> genes(parents.size(),{0});
        vector<int> ans(parents.size());
        for(int i=1;i<parents.size();i++){
            graph[parents[i]].emplace_back(i);
        }
        for(int i=0;i<nums.size();i++){
            genes[i].emplace(nums[i]);
        }
        dfs(0,-1,graph,genes,ans); 
        return ans;
    }
private:
    void dfs(int u, int father, vector<vector<int>>&graph, vector<set<int>>&genes, vector<int>&ans){
        int cur = 0;
        for(const int& v:graph[u]){
            //if(v==father) continue;
            dfs(v, u, graph, genes, ans);
            cur = max(cur, ans[v]);
            if(genes[u].size() < genes[v].size()){
            	genes[u].swap(genes[v]);
        	}
            for(const int& g:genes[v]){
            	genes[u].emplace(g);
        	}
        }
        auto it = genes[u].lower_bound(cur);
        for(;it!=genes[u].end();it++){
            if(*it != cur){
                ans[u] = cur;
                return;
            }
            cur++;
        }
        ans[u] = cur;
    }
};

栈排序

https://leetcode-cn.com/problems/sort-of-stacks-lcci/

解法1

采用手写堆的方法

class SortedStack {
public:
    SortedStack() {
        stk = vector<int>(5005);
        size = 0;
    }
    
    void push(int val) {
        stk[size+1] = val;
        upjust(size+1);
        size++;
    }
    
    void pop() {
        if(isEmpty()) return;
        else if(size == 1){
            size--;
            return;
        }
        swap(stk[1], stk[size]);
        size--;
        downjust(1);
    }
    
    int peek() {
        if(size == 0) return -1;
        return stk[1];
    }
    
    bool isEmpty() {
        return size==0;
    }
private:
    vector<int> stk;
    int size;
    void upjust(int n){
        while(n > 1){
            if(stk[n] < stk[n/2]){
                swap(stk[n], stk[n/2]);
                n = n/2;
            }else{
                break;
            }
        }
    }
    void downjust(int n){
        while(n*2 <= size){
            int i = n*2;
            if(i+1 <= size && stk[i+1]<stk[i]){
                i = i+1;
            }
            if(stk[i] < stk[n]){
                swap(stk[i], stk[n]);
                n = i;
            }else{
                break;
            }
        }
    }
};

/**
 * Your SortedStack object will be instantiated and called as such:
 * SortedStack* obj = new SortedStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->isEmpty();
 */

解法2

采用priority_queue的方法，其实priority_queue底层也是堆实现的

class SortedStack {
public:
    SortedStack() {
        return;
    }
    
    void push(int val) {
        pq.push(val);
    }
    
    void pop() {
        if(!isEmpty()) pq.pop();
    }
    
    int peek() {
        if(isEmpty()) return -1;
        return pq.top();
    }
    
    bool isEmpty() {
        return pq.empty();
    }
private:
    priority_queue<int, vector<int>, greater<int>> pq;
};

展开全文 >>

finalshell-cisoAnyConnection连接到ecnu服务器

2021-08-23

连接到ecnu VPN

1.首先下载ciscoAnyConnection软件，这个软件可以连接到ecnu VPN。下载网址是：

链接：https://pan.baidu.com/s/1khUL60elE1l_WLr8yel81g
提取码：df7l

2.cisco软件中输入ecnu VPN网址：vpn-ct.ecnu.edu.cn

3.点击Connect，然后输入自己的ecnu学号和密码。点击’OK’，然后就连接到VPN了。

finalshell进行ssh连接

1.下载finalshell：http://www.hostbuf.com/downloads/finalshell_install.exe

2.安装后，进行如下操作：

按照步骤执行；其中第4步的proxy代理ip是58.198.176.182。即使连接到ecnu VPN，也不能直接ssh到特定主机，必须要先和跳板机连接，这个proxy代理ip就是跳板机。

这个跳板机的用户名和密码都是proxy。

连接成功后会出现下免得界面：

3.在这个界面的命令行内使用ssh命令连接到私网的特定主机，比如10.11.6.29。

1	ssh 10.11.6.29 -l zhouhuahui # -l选项指定登录主机的用户

要以特定主机登录，必须要让这个主机的管理员创建一个用户名和密码。

4.如果要从主机或跳板机退出登录，只需执行：

logout

展开全文 >>

开源项目推荐

2021-08-23

网址

hellogithub开源月刊（55期）：https://blog.csdn.net/a419240016/article/details/109364091

hellogithub的博客（开源）：https://hellogithub.blog.csdn.net/

展开全文 >>

计算机网络

2021-08-23

网址

（csdn：网络技术）https://blog.csdn.net/qq_45704528/article/details/118635841?utm_medium=distribute.wap_feed.none-task-blog-whitelist_blog-3.nonecase&depth_1-utm_source=distribute.wap_feed.none-task-blog-whitelist_blog-3.nonecase

展开全文 >>

多进程服务器示例

2021-08-22

小写转大写

README

under linux, the server creates a child process by copying the called process by fork() 
to implement a multi-process concurrent server.

function: the client sends any string and the server transfers the string from lowercase 
to UPPERCASE and returns it to the client which prints it on the screen. 

reference: https://blog.csdn.net/Ai_King/article/details/104623632/?utm_term=c%E8%AF%AD%E8%A8%80%E5%A4%9A%E8%BF%9B%E7%A8%8B%E5%AE%9E%E7%8E%B0%E5%B9%B6%E5%8F%91&utm_medium=distribute.pc_aggpage_search_result.none-task-blog-2~all~sobaiduweb~default-0-104623632&spm=3001.4430

client.c

#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <sys/socket.h>
#include <arpa/inet.h>

#include "wrap.h"

#define SERV_IP "127.0.0.1"
#define SERV_PORT 8000

int main(void)
{
    int sfd, len;
    struct sockaddr_in serv_addr;
    char buf[BUFSIZ]; 

    sfd = Socket(AF_INET, SOCK_STREAM, 0);

    bzero(&serv_addr, sizeof(serv_addr));  // set every byte of serv_addr 0                     
    serv_addr.sin_family = AF_INET;                             
    inet_pton(AF_INET, SERV_IP, &serv_addr.sin_addr.s_addr);    
    serv_addr.sin_port = htons(SERV_PORT);                      

    Connect(sfd, (struct sockaddr *)&serv_addr, sizeof(serv_addr));

    while (1) {
        fgets(buf, sizeof(buf), stdin);
        int r = Write(sfd, buf, strlen(buf));       
        //printf("Write r === %d\n", r);
        len = Read(sfd, buf, sizeof(buf));
        //printf("Read len == %d\n", len);
        Write(STDOUT_FILENO, buf, len);
    }

    Close(sfd);

    return 0;
}

server.c

#include <stdio.h>
#include <string.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <signal.h>
#include <sys/wait.h>
#include <ctype.h>
#include <unistd.h>

#include "wrap.h"

#define MAXLINE 8192
#define SERV_PORT 8000

void do_sigchild(int num)
{
    while (waitpid(0, NULL, WNOHANG) > 0);
}

int main(void)
{
    struct sockaddr_in servaddr, cliaddr;
    socklen_t cliaddr_len;
    int listenfd, connfd;
    char buf[MAXLINE];
    char str[INET_ADDRSTRLEN];
    int i, n;
    pid_t pid;
    struct sigaction newact;

    newact.sa_handler = do_sigchild;
    sigemptyset(&newact.sa_mask);
    newact.sa_flags = 0;
    sigaction(SIGCHLD, &newact, NULL);


    listenfd = Socket(AF_INET, SOCK_STREAM, 0);

    int opt = 1;
    setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR, &opt, sizeof(opt));

    bzero(&servaddr, sizeof(servaddr));
    servaddr.sin_family = AF_INET;
    servaddr.sin_addr.s_addr = htonl(INADDR_ANY); // INADDR_ANY indicates all ip in this host
    servaddr.sin_port = htons(SERV_PORT);

    Bind(listenfd, (struct sockaddr *)&servaddr, sizeof(servaddr));

    Listen(listenfd, 20);

    printf("Accepting connections ...\n");
    while (1) {
        cliaddr_len = sizeof(cliaddr);
        connfd = Accept(listenfd, (struct sockaddr *)&cliaddr, &cliaddr_len);
        pid = fork();
        if (pid == 0) {
            Close(listenfd);
            while (1) {
                n = Read(connfd, buf, MAXLINE);
                if (n == 0) {
                    printf("the other side has been closed.\n");
                    break;
                }
                printf("received from %s at PORT %d\n",
                        inet_ntop(AF_INET, &cliaddr.sin_addr, str, sizeof(str)),
                        ntohs(cliaddr.sin_port));

                for (i = 0; i < n; i++)
                    buf[i] = toupper(buf[i]);

                Write(STDOUT_FILENO, buf, n);
                Write(connfd, buf, n);
            }
            Close(connfd);
            return 0;
        } else if (pid > 0) {
            Close(connfd);
        }  else
            perr_exit("fork");
    }
    return 0;
}

wrap.h

#ifndef __WRAP_H_
#define __WRAP_H_

void perr_exit(const char *s);
int Accept(int fd, struct sockaddr *sa, socklen_t *salenptr);
int Bind(int fd, const struct sockaddr *sa, socklen_t salen);
int Connect(int fd, const struct sockaddr *sa, socklen_t salen);
int Listen(int fd, int backlog);
int Socket(int family, int type, int protocol);
ssize_t Read(int fd, void *ptr, size_t nbytes);
ssize_t Write(int fd, const void *ptr, size_t nbytes);
int Close(int fd);
ssize_t Readn(int fd, void *vptr, size_t n);
ssize_t Writen(int fd, const void *vptr, size_t n);
ssize_t my_read(int fd, char *ptr);
ssize_t Readline(int fd, void *vptr, size_t maxlen);

#endif

wrap.c

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <errno.h>
#include <sys/socket.h>

void perr_exit(const char *s)
{
	perror(s);
	exit(-1);
}

int Accept(int fd, struct sockaddr *sa, socklen_t *salenptr)
{
	int n;

/*again:
	if ((n = accept(fd, sa, salenptr)) < 0) {
		if ((errno == ECONNABORTED) || (errno == EINTR))
			goto again;
		else
			perr_exit("accept error");
	}
	return n;*/

	while((n = accept(fd, sa, salenptr)) < 0){
		if ((errno == ECONNABORTED) || (errno == EINTR))
			continue;
		else{
			perr_exit("accept error");
			break;
		}
	}
	return n;
}

int Bind(int fd, const struct sockaddr *sa, socklen_t salen)
{
    int n;

	if ((n = bind(fd, sa, salen)) < 0)
		perr_exit("bind error");

    return n;
}

int Connect(int fd, const struct sockaddr *sa, socklen_t salen)
{
    int n;

	if ((n = connect(fd, sa, salen)) < 0)
		perr_exit("connect error");

    return n;
}

int Listen(int fd, int backlog)
{
    int n;

	if ((n = listen(fd, backlog)) < 0)
		perr_exit("listen error");

    return n;
}

int Socket(int family, int type, int protocol)
{
	int n;

	if ((n = socket(family, type, protocol)) < 0)
		perr_exit("socket error");

	return n;
}

ssize_t Read(int fd, void *ptr, size_t nbytes)
{
	ssize_t n;

/*again:
	if ( (n = read(fd, ptr, nbytes)) == -1) {
		if (errno == EINTR)
			goto again;
		else
			return -1;
	}
	return n;*/

	while((n = read(fd, ptr, nbytes)) == -1){
		if (errno == EINTR)
			continue;
		else 
			return -1;
	}
	return n;
}

ssize_t Write(int fd, const void *ptr, size_t nbytes)
{
	ssize_t n;

/*again:
	if ( (n = write(fd, ptr, nbytes)) == -1) {
		if (errno == EINTR)
			goto again;
		else
			return -1;
	}
	return n;*/

	while((n = write(fd, ptr, nbytes)) == -1){
		if (errno == EINTR)
			continue;
		else 
			return -1;
	}
	return n;
}

int Close(int fd)
{
    int n;
	if ((n = close(fd)) == -1)
		perr_exit("close error");

    return n;
}

ssize_t Readn(int fd, void *vptr, size_t n)
{
	size_t  nleft;              
	ssize_t nread;              
	char   *ptr;

	ptr = vptr;
	nleft = n;

	while (nleft > 0) {
		if ((nread = read(fd, ptr, nleft)) < 0) {
			if (errno == EINTR)
				nread = 0;
			else
				return -1;
		} else if (nread == 0)
			break;

		nleft -= nread;
		ptr += nread;
	}
	return n - nleft;
}

ssize_t Writen(int fd, const void *vptr, size_t n)
{
	size_t nleft;
	ssize_t nwritten;
	const char *ptr;

	ptr = vptr;
	nleft = n;
	while (nleft > 0) {
		if ( (nwritten = write(fd, ptr, nleft)) <= 0) {
			if (nwritten < 0 && errno == EINTR)
				nwritten = 0;
			else
				return -1;
		}

		nleft -= nwritten;
		ptr += nwritten;
	}
	return n;
}

static ssize_t my_read(int fd, char *ptr)
{
	static int read_cnt;
	static char *read_ptr;
	static char read_buf[100];

	if (read_cnt <= 0) {
again:
		if ( (read_cnt = read(fd, read_buf, sizeof(read_buf))) < 0) {
			if (errno == EINTR)
				goto again;
			return -1;
		} else if (read_cnt == 0)
			return 0;
		read_ptr = read_buf;
	}
	read_cnt--;
	*ptr = *read_ptr++;

	return 1;
}

ssize_t Readline(int fd, void *vptr, size_t maxlen)
{
	ssize_t n, rc;
	char    c, *ptr;

	ptr = vptr;
	for (n = 1; n < maxlen; n++) {
		if ( (rc = my_read(fd, &c)) == 1) {
			*ptr++ = c;
			if (c  == '\n')
				break;
		} else if (rc == 0) {
			*ptr = 0;
			return n - 1;
		} else
			return -1;
	}
	*ptr  = 0;

	return n;
}

展开全文 >>

跳表

2021-08-19

跳表

跳表 (SkipList) 是由 William Pugh 提出的。他在论文呢《Skip lists: a probabilistic alternative to balanced trees》中详细的介绍了跳表的结构、插入和删除操作的细节。

在这里插入图片描述

图 a 中，所有元素按顺序排列，被存储在一个链表中，则一次查询最多比较 N 个链表节点；
图 b 中，每隔 2 个链表节点，新增一个额外的指针，该指针指向间距为 2 的下一个节点，如此以来，借助这些额外的指针，一次查询至多只需要 n/2 + 1 次比较；图 c 中，在图 b 的基础上，每隔 4 个链表节点，新增一个额外的指针，指向间距为 4 的下一个节点，一次查询至多需要 n/4 + 2 次比较。

跳表查找

为了在跳跃表中搜索一个关键字，我们从顶层开始，直到找到该搜索关键字或一个比关键字小但下一链接又比关键字大的节点，然后向下移一层并重复这个过程。如此继续，直到搜索成功或在底层搜索失败。

在这里插入图片描述

快速查询的效率是：O(log_n)

引用

《拒绝做SQL boy…》中有一章节讲跳表：https://gitbook.cn/books/5f16777f3ff24476fa473e93/index.html#undefined

图解跳表：http://www.360doc.com/content/20/1204/11/13328254_949434656.shtml

展开全文 >>

redis

2021-08-19

引用

《redis设计与实现》配套网站（包括详细注释的redis源码）：redisbook.com

redis3.0详细注释的代码：https://github.com/huangz1990/redis-3.0-annotated

如何阅读Redis源码：https://blog.huangz.me/diary/2014/how-to-read-redis-source-code.html

W3Cschool的《Redis设计与实现》：https://www.w3cschool.cn/hdclil/cnv2lozt.html

展开全文 >>

javascript语言

2021-08-18

基础

ECMAScript是JS的标准，各个浏览器厂商对ES有自己的实现，比如Chrome的v8，这个v8引擎很快，而且node.js用的也是v8引擎。

JavaScript包含：

ECMAScripte
DOM(Document Object Model)
BOM(Browser Object Model)

JS的特点：

解释型语言
动态语言（变量可以保存任意类型数据，类似于python）
基于原型的面向对象

/*
* 在计算机的页面中输出一个内容
* document.write("ee");
*/

/*
* 在计算机的控制台中输出一个内容
* console.log("ee");
*/

<!DOCTYPE html>
<html>
    <head>
        <meta charset="UTF-8">
        <title></title>
        <!--
            可以将js代码写到外部js文件中；
            可以在不同的页面中同时引用，也可以利用到浏览器的缓存机制
        -->
        <script type="text/javascript" src="../js/1.js"></script>
    </head>
    <body>
        <!---
        可以将js代码写进标签的onclick属性中

        虽然可以这样做，但是结构与行为耦合，不好。
         -->
        <button onclick="alert('ee');">
            点我一下
        </button>

        <!--
            可以将js代码写在超链接的href属性中
        -->
        <a href="javascript:alert('fff');">你也点我一下</a>
        <a href="javascript:;">你也点我一下</a>
    </body>

</html>

1	var a; //声明一个变量

/*
* 在JS中一共有六种数据类型
*   String 
*   Number
*   Boolean
*   Null
*   Undefined
*   Object
*/
var str = "string";
var a = null;
var b; //Undefined类型

/*
* 强制类型转换
*/
var a = 123;
var b = a.toString(); //转为字符串
b = String(a); //转为字符串

a = "123";
b = Number(a);

console.log("type of b = "+typeof b);

/*
 * 同一个{}中的语句要么都执行，要么都不执行。称为代码块
 */
{
    alert("hello");
    console.log("hello");
}

字符串

var str = "abcd"
//返回字符串长度
str.length //out: 4

//返回字符串首次出现的索引
str.indexOf('b',3) //out: -1

//搜索特定值的字符串并返回匹配的位置，支持正则表达式
str.search('ab') //无法设置开始位置参数

//提取字符串
str.substr(start,length)

//转换为大写和小写
str.toUpperCase()
str.toLowerCase()

//删除字符串两端的空白符
str.trim()

Array

Array.prototype.shift函数表示删除第一个元素，并返回第一个元素

Array.prototype.indexOf表示寻找某个元素的下标

Array.prototype.map方法创建一个新数组，其结果是该数组中的每个元素是调用一次提供的函数后的返回值。

var arr = [1,2,3,4]
//从数组中删除最后一个元素
arr.pop()

//在数组结尾处添加一个新的元素
arr.push(5)

//删除首个元素
arr.shift()

//在开头处添加新的元素
arr.unshift(0)

//向数组中添加新的项目
arr.splice(2,0,'apple')

//删除元素
arr.splice(0,1)

//从小到大排序排序
arr.sort(function(a,b){
    return a-b
})

对象

内建对象：Math String Number等
宿主对象

有js的运行环境提供的对象，主要由浏览器提供的对象：

比如 BOM DOM
自定义对象

/*
 * 创建对象
 */
var obj = new Object();

/* 
 向对象中添加属性
 */
obj.name = "孙悟空";

/*
对象字面量
*/
var obj = {
    name:"e",
    age:28
};

/*
函数对象Function
*/
var fun = new Function("console.log('ee');");
fun();

/*
使用函数声明创建一个函数
*/
function fun2(a, b){ //两个参数a,b
    
}

/*
方法
*/
var obj = new Object();
obj.name = "ee";
obj.sayName = function(){
    console.log(obj.name);
}

/*
this
解析器在调用函数每次都会向函数传递与一个this参数
这个对象称为上下文对象
*/
function fun(){
    console.log(this); //输出[object Window]
}
//调用方式不同，this不同
var obj = new Object();
obj.fun = fun;
obj.fun(); //输出[object Object]，其实就是Object对象
//以函数调用，this就是Window，以方法调用，this就是调用的对象
//当以fun()作为构造函数时，this就是fun的实例

Object

Object.create()

具体见：https://www.jianshu.com/p/28d85bebe599

语法：
Object.create(proto, [propertiesObject])
//方法创建一个新对象，使用现有的对象来提供新创建的对象的proto。
参数：

proto : 必须。表示新建对象的原型对象，即该参数会被赋值到目标对象(即新对象，或说是最后返回的对象)的原型上。该参数可以是null， 对象，函数的prototype属性 （创建空的对象时需传null , 否则会抛出TypeError异常）。
propertiesObject : 可选。添加到新创建对象的可枚举属性（即其自身的属性，而不是原型链上的枚举属性）对象的属性描述符以及相应的属性名称。这些属性对应Object.defineProperties()的第二个参数。
返回值：
在指定原型对象上添加新属性后的对象。

常见的六种继承方式

原型链继承

这种方式实现的本质是通过将子类的原型指向了父类的实例。子类的实例就可以通过__proto__访问到父类的实例，这样就可以访问到父类的私有方法，然后再通过__proto__指向父类的prototype就可以获得父类原型上的方法。

<!DOCTYPE html>
<html>
    <head>
        <meta charset="UTF-8">
        <title></title>
        <!--
            可以将js代码写到外部js文件中；
            可以在不同的页面中同时引用，也可以利用到浏览器的缓存机制
        -->
        <script type="text/javascript">
            function Person(name, age){
                this.name = name,
                this.age = age,
                this.play = [1,2,3],
                this.setName = function(){}
            };
            Person.prototype.setAge = function(){};
            function Student(price){
                this.price = price,
                this.setScore = function(){}
            };
            Student.prototype = new Person();
            /*
            当使用new创建对象的时候发生了什么？以Person为例，Person.prototype里面有一个constructor,
            它指向f Person()这个Function，当new发生的时候，会自动创建一个空的对象，设为s吧，然后吧_proto_
            赋值为Person.prototype，这个时候Person.prototype.constructor函数中的this就定位到
            s对象了，然后执行s.prototype.constructor()给s对象的一些属性name,age,play和
            方法setName赋值。其实把Person.prototype赋值给s._proto_就意味着，每个定义的对象都继承自
            Object对象，因为Person.prototype._proto就是一个实例的Object.prototype对象。
            */
            var s1 = new Student(1600);
            var s2 = new Student(1500);
            s1.play.push(4);
            console.log(s1,s2);
        </script>
    </head>
</html>

<!--
1. 上面的s1和s2的play属性是一个实例，改变s1的play也会改变s2的；
2. 但是当s1变为new Person()时，当改变s1.play时，s2.play不会
变，因为s1.play和s2.play不是同一个实例。
3. 若s1和s2都是Person的实例，则s1,play变化时，s2.play不会变化
-->

Person是一个对象，Person.prototype.constructor才是我们定义的那个f Person()函数；Person由Function.prototype.constructor构造而来，所以有prototype属性，同时Person也继承自Function，所以Person._proto_等于Function.prototype。

我们在子类中为父类添加新的方法或者重写父类的方法时，切记一定要先为prototype指定父类的实例。

/*
为父类Person添加新的方法setAge。
*/
Student.prototype = new Person();
Student.prototype.setAge = function(age){
    this.age = age;
}
var s1 = new Student(100);
console.log(s1);

特点：

父类可以新增原型方法、原型属性，子类都能访问到

缺点：

无法实现多继承
来自原型对象的所有属性被所有实例共享
创建子类实例时，无法向父类构造函数传参

prototype的由来

参考：http://www.ruanyifeng.com/blog/2011/06/designing_ideas_of_inheritance_mechanism_in_javascript.html

若没有prototype，则每一个实例对象，都有自己的属性和方法的副本。这不仅无法做到数据共享，也是极大的资源浪费。比如构造函数中设置了name和age, species属性，则每个实例对象改变了自己的属性，并不会影响到别的实例对象。

考虑到这一点，Brendan Eich决定为构造函数设置一个prototype属性。这个属性包含一个对象（以下简称”prototype对象”），所有实例对象需要共享的属性和方法，都放在这个对象里面；那些不需要共享的属性和方法，就放在构造函数里面。比如，species属性就可以放在prototype中。

1	DOG.prototype = { species : '犬科' };

实例对象一旦创建，将自动引用prototype对象的属性和方法。也就是说，实例对象的属性和方法，分成两种，一种是本地的，另一种是引用的。而实例对象引用的属性和方法都放在__proto__中。

如上图所示，当你使用foo构造器构造了一个实例对象f1后，f1显然是通过function foo() 这个构造器（构造函数）创建的，所以f1实例对象中有一个指向function foo()的属性：constructor。但是如果直接把constructor放在实例对象里面，就像name属性一样，那么对于所有foo的实例对象，都会冗余地存储constructor，constructor是一样的，为什么要占用存储空间存储那么多次，所以就把constructor放在了foo.prototype中。

借用构造函数继承

在子类构造函数中调用父类的call()函数实现继承

<!DOCTYPE html>
<html>
    <head>
        <meta charset="UTF-8">
        <title></title>
        <script type="text/javascript">
            function Person(name, age){
                this.name = name,
                this.age = age,
                this.play = [1,2,3],
                this.setName = function(){}
            };
            Person.prototype.setAge = function(){};
            function Student(name,age,price){
                Person.call(this,name,age);
                this.price = price;
                this.setPrice = function(){};
            };
            var s1 = new Student("e",20,100);
            console.log(s1.setAge);
        </script>
    </head>
</html>
<!--
只能继承父类的属性和方法，不能继承父类原型的属性和方法
-->

特点：

解决了原型链继承中子类实例共享父类引用属性的问题
创建子类实例时，可以向父类传递参数
可以实现多继承（call多个父类对象）

缺点：

只能继承父类的属性和方法，不能继承父类原型的属性和方法
无法实现函数复用，每个子类都有父类实例函数的副本，影响性能。

原型链+借用构造函数的组合继承

通过调用父类构造，继承父类的属性并保留传参的优点，然后通过将父类实例作为子类原型，实现函数复用。

<!DOCTYPE html>
<html>
    <head>
        <meta charset="UTF-8">
        <title></title>
        <script type="text/javascript">
            function Person(name, age){
                this.name = name,
                this.age = age,
                this.play = [1,2,3],
                this.setName = function(){}
            };
            Person.prototype.setAge = function(){};
            Person.prototype.objectEle = [1,2,3];
            function Student(name,age,price){
                Person.call(this,name,age);
                this.price = price;
                this.setPrice = function(){};
            };
            Student.prototype = new Person();
            Student.prototype.constructor = Student;
            Student.prototype.sayHellow = function(){};
            var s1 = new Student("zhou",20,100);
            var s2 = new Student("xu",30,50);

            s1.objectEle.push(4);
            console.log(s1.sayHellow==s2.sayHellow);
            console.log(s1.objectEle==s2.objectEle);
            console.log(s1.setName==s2.setName);
            console.log(s2);
        </script>
    </head>
</html>

这是结果。我们可以看到，每个对象的构造函数是存在于它的__proto__中的。

如果每个Person也通过组合继承的方式继承自Object，那么Student也可以继承Object的属性且不是共享实例的。

特点：

经过这种继承方式，Student对象可以继承Person对象的属性和方法，且不是共享实例的，但是继承了Person对象的原型属性或方法的实例。
可以传参
函数可复用

缺点：

调用了两次父类构造函数

组合继承优化

<!DOCTYPE html>
<html>
    <head>
        <meta charset="UTF-8">
        <title></title>
        <script type="text/javascript">
            function Person(name, age){
                this.name = name,
                this.age = age,
                this.play = [1,2,3],
                this.setName = function(){}
            };
            Person.prototype.setAge = function(){
                console.log("modify age");
            }
            function Student(name,age,price){
                Person.call(this,name,age);
                this.price = price;
                this.setPrice = function(){};
            };
            Student.prototype = Object.create(Person.prototype); //Object.create(Person.prototype)继承了Person.prototype的所有属性和方法
            Student.prototype.constructor = Student;
            var s1 = new Student("zhou",20,100);
            console.log(s1);
        </script>
    </head>
</html>

Student继承了Person原型的所有属性和方法，这是最完美的继承方法。

总结

果然，组合继承优化才是最合适的继承方案。

把父类的非prototype属性作为子类的非prototype属性，这样就使得每个子类实例不会共享父类的非prototype属性，这就解决了原型链继承的一个缺点：子类实例共享父类属性。
通过在子类构造函数中调用FatherClass.call(this)来实现1功能，这样就可以向父类构造函数中传参，解决了原型链继承的不能向父类构造函数传参的缺点。
通过ChildClass.prototype = Object.create(FatherClass.prototype)代码，得到这样的原型链：ChildClass.prototype(初始为空，通过ChildClass.prototype.func1 = function()可以添加属性)
ChildClass.prototype.__proto__（这个就是FatherClass.prototype）。

这样的话，所有子类实例既可以共享父类prototye中的属性，又不用在每次实例化子类的时候两次实例化父类；可以方便地通过ChildClass.prototype.func1 = function() 代码扩充子类原型，而不影响父类原型，非常简洁。

还有一点，每次定义对象的时候，要把数据属性放在构造函数中，把函数属性放在prototype中，这样配合使用组合继承优化，非常方便。在我看vue源码的时候，就发现，很多对象的定义都是遵循上述原则的，原因是，函数可以共享使用，而数据在所有实例中不能共享。

看一个官网上组合继承优化的例子。

// Shape - 父类(superclass)
function Shape() {
  this.x = 0;
  this.y = 0;
}

// 父类的方法
Shape.prototype.move = function(x, y) {
  this.x += x;
  this.y += y;
  console.info('Shape moved.');
};

// Rectangle - 子类(subclass)
function Rectangle() {
  Shape.call(this); // call super constructor.
}

// 子类续承父类
Rectangle.prototype = Object.create(Shape.prototype);
Rectangle.prototype.constructor = Rectangle;

var rect = new Rectangle();

console.log('Is rect an instance of Rectangle?',
  rect instanceof Rectangle); // true
console.log('Is rect an instance of Shape?',
  rect instanceof Shape); // true
rect.move(1, 1); // Outputs, 'Shape moved.'

DOM

文档对象模型

查找HTML元素

通过id查找HTML元素

1	document.getElementById('id名称');

通过标签名查找HTML元素

1	document.getElementByTagName('tag')

通过类名查找HTML元素

1	document.getElementByClassName('class')

DOM HTML

创建动态的HTML内容：

1	document.write('Hello')

改变HTML元素内容

1
2
3

var a = document.getElementById('id')
var b = a.innerHTML
b.innerHTML = 新的内容

改变元素属性

1 2	var a = document.getElementById('id') a.setAttibute('属性名','新的属性值')

DOM CSS

改变CSS样式

1 2	var a = document.getElementById('id') a.style.backgroundColor = 'blue'

DOM事件

下面是一个使用DOM事件的例子

1	<div id="coordiv" style="float:left;width:199px;height:99px;border:1px solid #c3c3c3" onmousemove="cnvs_getCoordinates(event)" onmouseout="cnvs_clearCoordinates()"></div><br />

DOM事件体现了浏览器端的交互。

BOM

浏览器对象模型

window: 浏览器窗口对象，其成员包括所有的全局变量，函数和对象
screen：屏幕对象
location：位置对象，用于获取当前页面的URL地址，还可以把浏览器重定向到新的指定页面

history

<!--
获得历史记录信息
-->
<button onclick="history.back()">
    back
</button>
<button onclick="history.forward()"
    forward
</button>

navigator：

setTimeout()异步方法

function func(){
    //code
}
var tim = 3000 //3s
setTimeout('func', tim) //延迟一段时间后执行func函数

setInterval()

与setTimeout()方法类似，但这是每隔一段时间就执行程序。

异步方法

异步方法一般要求回调函数

有个很重要的点：比如

function getDogZhuliangProp() {
    // 为给定 ID 的 user 创建请求
    var res
    axios.get('/dog/zhuliang/props')
        .then(function (response) {
            res = eval(response.data)
        })
        .catch(function (error) {
            console.log(error);
        });
    return res
}

我想通过http请求获取数据，然后赋值给res,返回，但是上面的代码是错的，
原因是，用到了axios用到了ajax请求，这是异步的，这意味着当执行axios.get()时
会并行地执行return res，这就导致res并没有数据，却直接返回了。

js中的class

js的class仅仅为一个语法糖，是在原先构造函数的基础上出现的class，仅仅如此。所以使用构造函数构造类，或者使用class语法糖构造类都是相同的。具体还是使用prototype和this来进行模拟类。

类声明

class Rectangle {
	constructor(height, width) {
		this.height = height;
		this.width = width;
	}
}

匿名类

let Rectangle = class {
	constructor(height, width) {
		this.height = height;
		this.width = width;
	}
}

static

为一个静态方法，该静态new出的来的对象不能进行使用。

class Point {
	constructor(x, y){
		this.x = x;
		this.y = y;
	};

	static distance(a, b){
		const dx = a.x - b.x;
		const dy = a.y - b.y;
		return Math.hypot(dx, dy);	// 毕达哥拉斯定理
	}
}
// 使用
const p1 = new Point(5,5);
const p2 = new Point(10,10);
console.log(Point.distance(p1,p2));

extends

类不可继承没有构造函数的对象

class Animal {
	constructor(name) {
		this.name = name;
	}

	speak() {	// 由于是在类中定义，function关键字可以省去
		console.log(this.name);
	}
}
// 创建DOg父类
class Dog extends Animal {
	speak() {
		console.log(this.name);
	}
}

super

使用super调用超类

js中的跨域问题

什么是跨域

跨域是指从一个域名的网页去请求另一个域名的资源。比如从www.baidu.com 页面去请求 www.google.com 的资源。但是一般情况下不能这么做，它是由浏览器的同源策略造成的。

所谓同源是指，域名，协议，端口均相同。

为什么要跨域

既然有安全问题，那为什么又要跨域呢？有时公司内部有多个不同的子域，比如一个是location.company.com ,而应用是放在app.company.com , 这时想从 app.company.com去访问 location.company.com 的资源就属于跨域。

解决跨域问题

跨域资源共享（CORS）

CORS背后的基本思想就是使用自定义的HTTP头部让浏览器与服务器进行沟通，从而决定请求或响应是应该成功还是失败。服务器端对于CORS的支持，主要就是通过设置Access-Control-Allow-Origin来进行的。如果浏览器检测到相应的设置，就可以允许Ajax进行跨域的访问。

//指定允许其他域名访问
'Access-Control-Allow-Origin:*'//或指定域
//响应类型
'Access-Control-Allow-Methods:GET,POST'
//响应头设置
'Access-Control-Allow-Headers:x-requested-with,content-type'

jsonp

JSONP的原理：通过script标签引入一个js文件，这个js文件载入成功后会执行我们在url参数中指定的函数，并且会把我们需要的json数据作为参数传入。所以jsonp是需要服务器端的页面进行相应的配合的。（即用javascript动态加载一个script文件，同时定义一个callback函数给script执行而已。）

在js中，我们直接用XMLHttpRequest请求不同域上的数据时，是不可以的。但是，在页面上引入不同域上的js脚本文件却是可以的，jsonp正是利用这个特性来实现的。

ajax是要求服务器发送回来一个json文件，但是jsonp是引用服务器的一个php代码，这个代码到了浏览器端后，然后浏览器端以自己的php代码中的数据为参数，来这执行这个回调函数。因此，要实现jsonp，浏览器端要指明回调函数，服务器端要在代码中体现数据。

jquery实现jsonp

$.ajax()方法
1
2
3
4
5
6
7
8
9
$.ajax({
url:'http://外域.com/xxx.php',
dataType:"jsonp",
jsonp: "callback",
jsonpCallback:"ooo",
success:function(data){
console.log(data);
}
});
其中，jsonp: "callback"是设置路径里的参数名。你这里写callback，那么jQuery发送请求的时候路径里就用callback=

还有，jsonpCallback:"ooo"是设置函数名。你这里写ooo，那么php必须返回ooo为函数名的内容。
$.get()方法

$.get()方法的基本用法是同域名抓数据，是真正的ajax原理。而高级用法就是抓jsonp数据。写法是：
1
2
3
$.get('http://外域.com/xxx.php', {各种数据}, function(data) {
console.log(data);
}, 'jsonp');
$.getJSON()方法

$.getJSON()方法跟$.get()方法类似，区别在于：

1、$.getJSON()的最后一个参数不用写，而$.get()方法的最后一个参数必须是’jsonp’。

2、$.getJSON()虽然省掉了最后一个参数，但这时候，你需要在路径中带上callback=?或者abc=?这样的字眼，这样jQuery会自动判断，既然你带上了参数，而且参数值是问号，那么jQuery就认为你想搞jsonp勾当，如果你不加任何参数，或者参数值不是问号，那么jQuery就认为你不想搞jsonp勾当，那么这时候$.getJSON()方法就全等于$.get(…,…, ‘json’)方法。

jsonp的优缺点

优点：它不像XMLHttpRequest对象实现的Ajax请求那样受到同源策略的限制

缺点：它只支持GET请求而不支持POST等其它类型的HTTP请求；它只支持跨域HTTP请求这种情况，不能解决不同域的两个页面之间如何进行JavaScript调用的问题。

js中的运行时上下文context，以及call,apply,bind

以前遇到过，当函数通过对象的方法执行的时候，this是这个对象，当函数作为全局函数的时候，this是window。这就是js中的运行时上下文。

apply, call

apply, call完全一样，但是语法稍有不同。

在 javascript 中，call 和 apply 都是为了改变某个函数运行时的上下文（context）而存在的，换句话说，就是为了改变函数体内部 this 的指向。
JavaScript 的一大特点是，函数存在「定义时上下文」和「运行时上下文」以及「上下文是可以改变的」这样的概念。

function fruits() {}
 
fruits.prototype = {
    color: "red",
    say: function() {
        console.log("My color is " + this.color);
    }
}
 
var apple = new fruits;
apple.say();    //My color is red

但是如果我们有一个对象banana= {color : “yellow”} ,我们不想对它重新定义 say 方法，那么我们可以通过 call 或 apply 用 apple 的 say 方法：

banana = {
    color: "yellow"
}
apple.say.call(banana);     //My color is yellow
apple.say.apply(banana);    //My color is yellow

类（伪）数组使用数组方法

Javascript中存在一种名为伪数组的对象结构。比较特别的是 arguments 对象，还有像调用 getElementsByTagName , document.childNodes 之类的，它们返回NodeList对象都属于伪数组。不能应用 Array下的 push , pop 等方法。但是我们能通过 Array.prototype.slice.call 转换为真正的数组的带有 length 属性的对象，这样 domNodes 就可以应用 Array 下的所有方法了。

1	var domNodes = Array.prototype.slice.call(document.getElementsByTagName("*"));

bind

bind()最简单的用法是创建一个函数，使这个函数不论怎么调用都有同样的this值。

MDN的解释是：bind()方法会创建一个新函数，称为绑定函数，当调用这个绑定函数时，绑定函数会以创建它时传入 bind()方法的第一个参数作为 this，传入 bind() 方法的第二个以及以后的参数加上绑定函数运行时本身的参数按照顺序作为原函数的参数来调用原函数。

var foo = {
    bar : 1,
    eventBind: function(){
        $('.someClass').on('click',function(event) {
            /* Act on the event */
            console.log(this.bar);      //1
        }.bind(this));
    }
}

用js实现bind

//bind源码实现
Function.prototype.bind = function (){
    var self = this //this就是Function的引用
    var context = [].shift.call(arguments) //arguments中的第一个参数就是要绑定的this
    var args = [].slice.call(arguments)
    return function(){ //bind是一个Function
        self.apply(context,[].concat.call(args,[].slice.call(arguments)))
    }
}

节流函数与防抖函数

function throttle(fn,delay){
    var pre = Date.now()
    return () => {
        var now = Date.now()
        if(now-pre >= delay){
            //执行fn
            fn.apply(this,arguments)
            pre = now
        }
    }
}

debounce: function (fn, delay) {
    var timer = null
    return () => {
        if (timer) {
            clearTimeout(timer)
        }
        timer = setTimeout(() => {
            fn.apply(this, arguments)
        }, delay)
    }
}

为什么经常用fn.apply(this)的写法

因为给事件加回调函数fn的时候，不知道调用这个函数的是window还是定义fn的对象，但是不管是哪个，fn函数内的this肯定都是定义fn的那个对象，所以直接使用fn.apply(this)肯定没有错。

注意：要注意词法作用域的问题，比如上面debounce函数第3行和第7行，要用箭头函数来使this按照词法作用域来绑定到外层的对象，防止在调用回调的时候，this指向window对象。

js实现排序

快排

function quickSort(arr,begin,end){
    var len = end-begin
    if(len <= 1){
        return
    }
    var i = begin, j = end-1
    while(i<j){
        while(arr[i]<=arr[begin])i++
        while(arr[j]>=arr[begin])j--
        if(i>=end){
            i = begin
            j = end-1
            while(i<j){
                var temp = arr[i]
                arr[i] = arr[j]
                arr[j] = temp
                i++
                j--
            }
            return
        }
        if(j<begin) return
        if(i<j){
            var temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
        }else{
            var temp = arr[0]
            arr[0] = arr[j]
            arr[j] = temp
            quickSort(arr,begin,j)
            quickSort(arr,j,end)
        }
    }
}

展开全文 >>

设计模式

2021-08-18

发布订阅模式

其实24种基本的设计模式中并没有发布订阅模式，它是观察者模式的一个变体。

订阅者（Subscriber）把自己想订阅的事件注册（Subscribe）到调度中心（Topic），当发布者（Publisher）发布该事件（Publish topic）到调度中心，也就是该事件触发时，由调度中心统一调度（Fire Event）订阅者注册到调度中心的处理代码。

例子：猎人工会

/* 猎人工会是调度中心
 * 猎人是发布者和订阅者
 * 猎人发布主题（猎物），订阅相应的主题
 */

//定义一家猎人工会
//主要功能包括任务发布大厅(topics)，以及订阅任务(subscribe)，发布任务(publish)
let HunterUnion = {
    type: 'hunt',
    topics: Object.create(null),
    subscribe: function (topic, fn){
        if(!this.topics[topic]){
            this.topics[topic] = [];  
        }
        this.topics[topic].push(fn);
    },
    publish: function (topic, money){
        if(!this.topics[topic])
            return;
        for(let fn of this.topics[topic]){
            fn(money)
        }
    }
}

//定义一个猎人类
//包括姓名，级别
function Hunter(name, level){
    this.name = name
    this.level = level
}
//猎人可在猎人工会发布订阅任务
Hunter.prototype.subscribe = function (topic, fn){
    console.log(this.level + '猎人' + this.name + '订阅了狩猎' + topic + '的任务')
    HunterUnion.subscribe(topic, fn)
}
Hunter.prototype.publish = function (topic, money){
    console.log(this.level + '猎人' + this.name + '发布了狩猎' + topic + '的任务')
    HunterUnion.publish(topic, money)
}

//猎人工会走来了几个猎人
let hunterMing = new Hunter('小明', '黄金')
let hunterJin = new Hunter('小金', '白银')
let hunterZhang = new Hunter('小张', '黄金')
let hunterPeter = new Hunter('Peter', '青铜')

//小明，小金，小张分别订阅了狩猎tiger的任务
hunterMing.subscribe('tiger', function(money){
    console.log('小明表示：' + (money > 200 ? '' : '不') + '接取任务')
})
hunterJin.subscribe('tiger', function(money){
    console.log('小金表示：接取任务')
})
hunterZhang.subscribe('tiger', function(money){
    console.log('小张表示：接取任务')
})
//Peter订阅了狩猎sheep的任务
hunterPeter.subscribe('sheep', function(money){
    console.log('Peter表示：接取任务')
})

//Peter发布了狩猎tiger的任务
hunterPeter.publish('tiger', 198)

//猎人们发布(发布者)或订阅(观察者/订阅者)任务都是通过猎人工会(调度中心)关联起来的，他们没有直接的交流。

参考：https://blog.csdn.net/hf872914334/article/details/88899326

例子：发布订阅的封装

// global.js
var Event = (function(){
    var list = {},
          listen,
          trigger,
          remove;
          listen = function(key,fn){
            if(!list[key]) {
                list[key] = [];
            }
            list[key].push(fn);
        };
        trigger = function(){
            var key = Array.prototype.shift.call(arguments),
                 fns = list[key];
            if(!fns || fns.length === 0) {
                return false;
            }
            for(var i = 0, fn; fn = fns[i++];) {
                fn.apply(this,arguments);
            }
        };
        remove = function(key,fn){
            var fns = list[key];
            if(!fns) {
                return false;
            }
            if(!fn) {
                fns && (fns.length = 0);
            }else {
                for(var i = fns.length - 1; i >= 0; i--){
                    var _fn = fns[i];
                    if(_fn === fn) {
                        fns.splice(i,1);
                    }
                }
            }
        };
        return {
            listen: listen,
            trigger: trigger,
            remove: remove
        }
})();

// a.js
var a = (function(){
    var count = 0;
    var button = document.getElementById("count");
    button.onclick = function(){
        Event.trigger("add",count++);
    }
})();

// b.js
var b = (function(){
    var div = document.getElementById("showcount");
    Event.listen('add',function(count){
        div.innerHTML = count;
    });
})();

<!doctype html>
<html lang="en">
 <head>
  <meta charset="UTF-8">
  <title>Document</title>
  <script src="global.js"></script>
 </head>
 <body>
    <button id="count">点将我</button>
    <div id="showcount"></div>
    <script src = "a.js"></script>
    <script src = "b.js"></script>
 </body>
</html>

点击count button，相当与发布了一个add消息，然后在b.js中订阅add消息的函数就会被调度中心执行。因此如果想要count button取消对add消息的订阅，只需要在调度中心中remove就好了。

参考：https://www.cnblogs.com/itgezhu/p/10947405.html

例子：jquery中的发布订阅

需求：我（订阅者）后天结婚，规划了3件事情，需要（发布者）后天点击提交按钮后执行这三件事。
分析：提前写好三个方法，未来某段时间触发三个方法。

let $pond1 = $.Callbacks();//创建一个事件池

//给提交按钮注册
$('.submit').click(function(){
    $pond1.fire();//触发事件池中的方法
});
let fn1 = function(){console.log(1)};
let fn2 = function(){console.log(2)};
let fn3 = function(){console.log(3)};
$pond1.add(fn1);//将事件添加进事件池
$pond1.add(fn2);
$pond1.add(fn3);
let fn4 = function(){console.log(4)};
$pond1.add(fn4);

$pond1.remove(fn3);//移除事件

关于$.Callbacks()的具体使用，可以参考：https://segmentfault.com/a/1190000004331027
这里面详细讲解了$.Callbacks()实例的各个方法：add(), fire(), fireWith(), empty(), has(), remove(), disable()等。

参考：https://www.jianshu.com/p/d755909b85f8