hexo搭建博客

2021-12-28

从0到1搭建hexo博客（前提是有github账号，且已和本地git相关联）

python封装算法包（可import）

2021-12-28

External Libraries>site-packages>ccm_scripts

打包自己的python算法，通过import就能使用

python调用c语言代码

2021-12-28

原本的机器学习项目都用python写好，老板这边又出了个新需求，将部分核心代码抽出来，用C编写，然后通过dll的方式引用，目的就是为了隐藏部分核心代码。

set

用法：不重复、自动排序的集合；
my_set.insert(sth); // 插入
my_set.find(sth) == my_set.end(); // 判断在集合中不存在S

拓扑建图

 struct GraphNode {
    int val;
    vector<GraphNode*> courses;
    GraphNode(int x) : val(x) {} // 构造函数
};
// vector<GraphNode*> graph;

vector作栈

vec.push_back(x);
vec[vec.size() - 1]; // vec.back() (首部元素引用可用 vec.front())
vec.pop_back();
*max_element(vec.begin(), vec.end()); // 求数组中的最大值

优先队列

priority_queue q; // 大顶堆从大到小降序
priority_queue<int, vector, greater > q; // 小顶堆从小到大升序
priority_queue<pair<int, int> > q; // pair中先比较第1个降序再比较第2个降序
如果要遍历的话，只能够pop push
访问队首元素 q.top()

集合

无序没有重复的

unordered_set<int> num_set;
for (const int& num : nums) { // 去重
    num_set.insert(num);
}
num_set.count(num - 1) // 判断集合中是否存在

9.23

75：荷兰国旗问题

9.24

146：优先队列、双向链表
169：投票算法

9.25

152：动态规划
215：随机快排、堆排序
234：反转链表

9.27

动态规划简单题

9.28

贪心简单题（模拟）

10.2

秋叶收藏集叶子 dp
739 单调栈

10.3

647 马拉车算法[https://www.jianshu.com/p/392172762e55]

10.19

239 滑动窗口最大值
单调栈动态规划

// 双向队列
ArrayDeque<Integer>deq;
deq.isEmpty();
deq.getLast();
deq.getFirst();
deq.addLast();
deq.removeLast();

10.20

84 柱状图中的最大矩形

// 栈
Stack<Integer> stack = new Stack();
stack.empty();
stack.peek();
stack.push(new Integer(i));

10.26

回溯有点不懂

java
StringBuilder s;
s.add(); // 可改变大小
hashSet 哈希表
append()

11.1

二叉树序列化与反序列化

java 队列
Queue<String> q = new LinkedList<String>(); 
q.offer("a"); // add
q.poll(); // remove抛出异常 poll返回null
q.peek(); // 第一个元素q.element()
for(String s:q) // 遍历

二叉树

一. leetcode 113 路径总和2

前序遍历：

先处理当前结点（将该结点push到路径数组中，并且累加其结点值）；
再进行下一步的遍历；

完成当前结点的遍历后，回溯（将该结点pop出路径数组，并且更新结点值和）。
一般代码结构如下：

void preOrder(TreeNode* root, vector<vector<int>>& result, vector<int>& path, int sum, int cur_sum) {
        if (root == NULL) return;
        path.push_back(root->val); // 更新路径
        cur_sum += root->val; // 更新当前和
        // 当前和与要求和相同，并且为叶子结点
        if (cur_sum == sum && root->left == NULL && root->right == NULL) {
            result.push_back(path);
        }
        preOrder(root->left, result, path, sum, cur_sum);
        preOrder(root->right, result, path, sum, cur_sum);
        // 左右子树都遍历完成后，在路径中删除当前值
        path.pop_back();
        cur_sum -= root->val;
    }

二. leetcode 236 二叉树的最近公共祖先

分别以题目给出的两个结点为目标，对二叉树进行前序遍历，直到找到该目标，并且记录路径；
从头到尾对比两个路径，遇到的最后一个相同的即为最近公共祖先。

三. leetcode 114 二叉树展开为链表

递归主要讨论的是左子树与右子树都拉直后的连接过程，忽略具体拉直过程，每个递归返回的有用信息是该树右子树的最后一个结点指针。

/**
 * 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:
    void preOrder(TreeNode* node, TreeNode* &last) {
        if (!node) return;
        // 判断该结点是否为叶子结点
        // 是则为该子树的最后一个结点
        // 返回
        if (!node->left && !node->right) {
            last = node;
            return;
        }
        TreeNode* left = node->left;
        TreeNode* right = node->right;
        TreeNode* left_last = NULL;
        TreeNode* right_last = NULL; // 左右子树的最后一个结点
        // 前序遍历左子树
        if (left) {
            preOrder(left, left_last);
            node->left = NULL;
            node->right = left;
            last = left_last;
        }
        // 前序遍历右子树
        if (right) {
            preOrder(right, right_last);
            if (left_last) // 没有该判断 报错！last没有初始化，为空
                last->right = right;
            last = right_last;
        }
    }
    void flatten(TreeNode* root) {
        TreeNode * last;
        preOrder(root, last);
    }
};

图

一. leetcode 199 二叉树的右视图

图的宽度搜索（BFS）：

使用队列queue，pair存储结点与层数；
将当前结点的左右结点分别push到队列中，同时记录层数；
按先进先出的顺序访问结点；
不断更新该层的最后一个结点；

得到结果数组。
一般代码结构为：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans; // 按层遍历的最后一个结点
        queue<pair<TreeNode*, int> > myQueue;
        if (!root)return ans;
        myQueue.push(make_pair(root, 0));
        while (!myQueue.empty()) {
            TreeNode* cur_node = myQueue.front().first;
            int cur_depth = myQueue.front().second;
            myQueue.pop();
            if (ans.size() == cur_depth) { // 首次遇到在cur_depth层的结点 将结点值push到数组中
                ans.push_back(cur_node->val);
            }
            else { // 更新ans[cur_depth]的值
                ans[cur_depth] = cur_node->val;
            }
            if (cur_node->left) { // 存在左子树
                myQueue.push(make_pair(cur_node->left, cur_depth + 1));
            }
            if (cur_node->right) { // 存在左子树
                myQueue.push(make_pair(cur_node->right, cur_depth + 1));
            }
        }
        return ans;
    }
};

二分查找

一. leetcode 35 搜索插入位置

标准二分查找法(重点：分析出未找到target值时，插入位置索引总是begin);
一般模板:

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int begin = 0, end = nums.size() - 1;
        int mid = 0;
        while (begin <= end) {
            mid = (begin + end) / 2;
            if (target < nums[mid]) {
                end = mid - 1;
            }
            else if (target > nums[mid]) {
                begin = mid + 1;
            }
            else return mid;
        }
        return begin;
    }
};

二、leetcode 34 在排序数组中查找元素的第一个和最后一个位置

分别找左右边界，二分查找加入相等的处理判断;

// 找左边界
        while (begin <= end) {
            mid = (begin + end) / 2;
            // 前半部分
            if (nums[mid] > target) {
                end = mid - 1;
            }
            // 后半部分
            else if (nums[mid] < target) {
                begin = mid + 1;
            }
            // 相等的情况
            // 左边界要么就是mid，要么在前半部分
            else {
                // mid为左边界
                if (mid == 0 || nums[mid - 1] < target) {
                    left = mid;
                    break;
                }
                // 前半部分还有target值，继续二分查找
                else {
                    end = mid - 1;
                }
            }
        }

三、leetcode 33 搜索旋转排序数组

有点窒息的分类,二分查找的框架，每种情况都要清晰地讨论。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int begin = 0, end = nums.size() - 1;
        int mid = 0;
        while (begin <= end) {
            mid = (begin + end ) / 2;
            // 目标小于中间值
            if (target < nums[mid]) {
                // 前半部分为顺序区间，后半部分为旋转区间
                if (nums[begin] <= nums[mid]) { // 注意！！等号表示mid与begin值相同时
                    // 在顺序区间中找
                    // 顺序区间内的最小值<=target，则在顺序区间中找
                    if (nums[begin] <= target) end = mid - 1;
                    // 在旋转区间中找
                    else {
                        begin = mid + 1;
                    }
                }
                // 后半部分为顺序区间，前半部分为旋转区间
                // 后半部分所有值都大于nums[mid] 即大于target
                // target一定在前半部分
                else {
                    end = mid - 1;
                }
            }
            // 目标大于中间值
            else if (target > nums[mid]) {
                // 前半部分为顺序区间，后半部分为旋转区间
                // 前半部分所有值都小于nums[mid] 即小于target
                // target一定在后半部分
                if (nums[begin] < nums[mid]) {
                    begin = mid + 1;
                }
                // 后半部分为顺序区间，前半部分为旋转区间
                else {
                    // 在旋转区间中找
                    // nums[end]是顺序区间中最大元素
                    // 该最大元素都比target小的话
                    // 则直接在旋转区间中找
                    if (nums[end] < target) end = mid - 1;
                    // 否则在该顺序区间中找
                    else {
                        begin = mid + 1;
                    }
                }
            }
            else return mid;
        }
        return -1;
    }
};

二叉搜索树

插入结点代码

void BST_insert(TreeNode* root, TreeNode* insert_node) {
        if (root->val > insert_node->val) {
            if (root->left) BST_insert(root->left, insert_node);
            else root->left = insert_node;
        }
        else {
            if (root->right) BST_insert(root->right, insert_node);
            else root->right = insert_node;
        }
    }

查找结点代码

二、leetcode 315 计算右侧小于当前元素的个数

在插入的过程中计算小于当前结点值的结点数,不是获取当前结点的count_small值（记录的是整棵树中小于当前结点的值，而不是在插入他之前）。

class Solution {
public:
    // 计算右侧小于当前元素的个数
    // 反转数组
    // 将问题转换为：计算左侧小于当前元素的个数
    // 建立二叉搜索树,在建立的过程中，记录
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        int count_small;
        TreeNode(int x) : val(x), left(NULL), right(NULL), count_small(0) {}
     };
    
    void BST_insert(TreeNode* node, TreeNode* insert_node, int & count) {
        if (node->val >= insert_node->val) {
            node->count_small++;
            if (node->left) BST_insert(node->left, insert_node, count);
            else node->left = insert_node;
        }
        else {
            count += node->count_small + 1;
            if (node->right) BST_insert(node->right, insert_node, count);
            else node->right = insert_node;
        }
    }
    
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> ans;
        if (nums.size() == 0) return ans;
        reverse(nums.begin(), nums.end());
        TreeNode* root = new TreeNode(nums[0]);
        ans.push_back(0);
        for (int i = 1; i < nums.size(); i++) {
            TreeNode * newNode =  new TreeNode(nums[i]);
            int count_small = 0;
            BST_insert(root, newNode, count_small);
            ans.push_back(count_small);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

哈希表

一、 leetcode 409 最长回文串

哈希表存放字符串s中各个不同的字母出现的次数；

遍历哈希表,根据出现次数的偶数/奇数，结合回文串的性质，得出最长回文串。

class Solution {
public:
    int longestPalindrome(string s) {
        map<char, int> mp;
        for (int i = 0; i < s.length(); i++) {
            mp[s[i]]++;
        }
        map<char, int>::iterator it;
        int sum = 0;
        bool flag = false;
        for (it = mp.begin(); it != mp.end(); it++) {
            if (it->second % 2 == 0) { // 该字母出现次数为偶数次
                sum += it->second; // 可构成回文
            }
            else { // 该字母出现次数为奇数次
                if (flag) { // 已存在中间值
                    sum += it->second - 1; // 除掉中间值外 其他可构成回文
                }
                else {
                    sum += it->second;
                    flag = true;
                }
            }
        }
        return sum;
    }
};

二、leetcode 290 单词规律

分析字符串与模式字母的正确匹配情况与错误情况：

map<string, char> mp; // 存储字符串对应的模式字母
bool used[128] = {0}; // 标记模式字母是否出现过
模式字母未出现过：当前字符串却曾经出现过，则有字符串对应了多个模式字母，错误；
模式字母出现过：当前字符串不曾出现，或者当前字符串不对应相应模式字母，错误；

三、leetcode 49 字母异位词分组

map<string, int> mp; // 哈希表：基础字符串，对应在结果中的索引
vector<vector > res; // 结果数组
字符串排序,作为map的key.

四、leetcode 3 无重复字符的最长子串

滑动窗口法：

确定左边界，遍历右边界，数组存储字母在该窗口中是否出现过；
当遍历过程中遇到出现过的字母，则右移左边界，直到找到该字母的位置;

当遍历过程中遇到出现过的字母，更新最大无重复子串长度。

五、leetcode 187 重复的DNA序列

ACGT四种情况，即二进制两位数可表示这4种不同的字母；
不同的DNA序列可转化为对应不同的二进制数;
使用哈希表存储出现的次数。

六、leetcode 76 最小覆盖子串

滑动窗口法+哈希表:
根据条件更新左边界：当前S窗口s_map[begin_str] < T字符串中的t_map[begin_str]；或出现T字符串中没有的字母；
遍历右边界，在每次遍历完成后，判断该窗口是否符合要求。

class Solution {
public:
    bool is_window_ok(int x[], int y[], vector<int> vec) {
        for (int i = 0; i < vec.size(); i++) {
            if (x[vec[i]] > y[vec[i]]) return false;
        }
        return true;
    }
    
    string minWindow(string s, string t) {
        int t_map[128] = {0}; // 记录t字符串中各字母出现的次数
        int s_map[128] = {0}; // 记录s字符串窗口中各字母出现的次数
        vector<int> charvec; // 记录t中出现过的字母
        for (int i = 0; i < t.length(); i++) {
            if (t_map[t[i]] == 0) charvec.push_back(t[i]);
            t_map[t[i]]++;
        }
        int begini = 0; // 窗口左边界
        int min_len = s.length() + 1; // 结果字符串长度
        string res = "";
        // 遍历右边界
        for (int i = 0; i < s.length(); i++) {
            s_map[s[i]]++;
            while (begini < i) {
                if (t_map[s[begini]] == 0) { // 窗口首字母在t字符串中不存在
                    begini++;
                }// 窗口首字母在窗口字符串中出现次数>在t字符串出现次数
                else if (s_map[s[begini]] > t_map[s[begini]]) {
                    s_map[s[begini]]--;
                    begini++;
                }
                else break;
            }
            // cout<<s.substr(begini, i - begini + 1)<<endl;
            if (is_window_ok(t_map, s_map, charvec)) {
                int cur_len = i - begini + 1;
                if (res == "" || cur_len < min_len) {
                    min_len = cur_len;
                    res = s.substr(begini, cur_len);
                }
            }
        }
        return res;
    }
};

递归

一、 leetcode 78 子集

不考虑递归过程，直接根据结果来实现程序。
求子集：

考虑当前元素是否应该加到子集中：加或不加，分别递归；

递归结束条件是：index>=nums.size()。

class Solution {
public:
    void generate (int i, vector<int> nums, vector<int> items, vector<vector<int>> &res) {
        if (i >= nums.size()) { // 当索引超出nums边界
            res.push_back(items);
            return;
        }
        items.push_back(nums[i]); // 当前子集选择nums[i]
        generate (i + 1, nums, items, res); // 进行下一步递归
        items.pop_back(); // 当前子集不选择nums[i]
        generate (i + 1, nums, items, res); // 进行下一步递归
    }
    
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int> > res;
        vector<int> items;
        generate (0, nums, items, res);
        return res;
    }
};

二、leetcode 90 子集 II

先对nums排序，使用set<vector>对一致的子集去重。

if (res_set.find(items) == res_set.end()) {
                res.push_back(items);
                res_set.insert(items);
            }

三、leetcode 40 组合总和 II

典型的递归题：

以开始位置start索引遍历候选数组，当当前索引未加入到路径中，并且加入候选值不会大于target值，则选择该索引位置的值，并进行下一步的递归；

递归结束条件是path值==target值，并且当前path首次出现(排序 set约束)。

class Solution {
public:
    // 递归函数
    // 候选数组，开始位置，目标数值，结果数组，当前子集
    void backtracking(vector<int> candidates, int start, int target, vector<vector<int> >& res, vector<int>& path, bool help[], set<vector<int> >& res_set) {
        // 达到目标
        if ( target == 0 && res_set.find(path) == res_set.end()) {
            res.push_back(path);
            res_set.insert(path);
            return;
        }
        for (int i = start; i < candidates.size() && target-candidates[i] >= 0; i++){
            // 满足条件：当前值未使用 并且 子集和仍然小于target
            if (!help[i] && target - candidates[i] >= 0) {
                path.push_back(candidates[i]); // 将当前值放入子集中
                help[i] = true;
                backtracking(candidates, i+1, target - candidates[i], res, path, help, res_set);
                path.pop_back(); // 取出该值，进行新一轮选择
                help[i] = false;
            }
        }
    }
    /*
    sort(candidates.begin(),candidates.end()); // 将数组排序
    backtracking(candidates, 0, target, res, path, help, res_set);
    */
};

四、leetcode 22. 括号生成

典型递归题：
给出n对左右括号的合理摆放顺序。

每一步有2种选择：’(‘或’)’，对两种选择分别进行下一步递归；
递归结束条件为：目标字符串长度到达2*n；

剪枝：去除不必要的递归步骤：只有n个左括号与n个右括号，超出的直接不做处理；左括号数不大于右括号数的，不可再选择’)’。

class Solution {
public:
    void generate(string item, int left, int right, vector<string>& res) {
        if (left == 0 && right == 0) { // 当字符串成功放置n个左括号与n个右括号
            res.push_back(item);
            return;
        }
        if (left > 0) // 当左括号尚未完成
            generate(item + '(', left - 1, right, res);
        if (left < right) // 当左括号数>右括号数
            generate(item + ')', left, right - 1, res);
    }
    
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        generate("", n, n, res);
        return res;
    }
};

五、leetcode 51. N皇后

N皇后问题，典型的递归回溯法：
关键点在于在递归之前，对当前mark标记数组与location结果状态的保存，以便在回溯阶段对状态进行复原，以进行下一步的递归。

class Solution {
public:
    int dir[8][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, // 上下左右
                    {-1, -1}, {-1, 1}, {1, -1}, {1, 1}}; // 左上 右上 左下 右下
    // 在(x,y)位置放置queue
    // 在(x,y)位置的八个方向延伸出去 都标志为-1 表示不可放置queue
    void put_down_the_queue(int x, int y, vector<vector<int> >& mark) {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < mark.size(); j++) {
                int index_x = x + dir[i][0] * j;
                int index_y = y + dir[i][1] * j;
                if (index_x < 0 || index_x >= mark.size()) continue;
                if (index_y < 0 || index_y >= mark[0].size()) continue;
                mark[index_x][index_y] = -1;
            }
        }
    }
    
    // 递归函数
    // k：完成k个皇后的放置
    // n：共n个皇后
    // location：当前摆放结果
    // res：最终结果
    // mark：标记数组
    void generate(int k, int n, vector<string>& location, vector<vector<string> >& res, vector<vector<int> >& mark) {
        if (k == n) {
            res.push_back(location);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (mark[k][i] == 0) {
                vector<vector<int> > temp_mark = mark; // 存储当前的mark数组(在递归过程中会改变)
                put_down_the_queue(k, i, mark);
                location[k][i] = 'Q';
                generate(k + 1, n, location, res, mark); // 递归
                mark = temp_mark; // 返回原本mark数组
                location[k][i] = '.';  // 返回原本的location
            }
        }
    }
    
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string> > res; // 存储最终结果
        vector<vector<int> > mark; // 标记棋盘是否可以放置皇后的二维数组
        vector<string> location; // 存储某个摆放结果
        // 初始化
        for (int i = 0; i < n; i++) {
            mark.push_back((vector<int>()));
            for (int j = 0; j < n; j++) {
                mark[i].push_back(0);
            }
            location.push_back("");
            location[i].append(n, '.'); // location初始化为n个"."
        }
        generate(0, n, location, res, mark);
        return res;
    }
};

六、leetcode 315 计算右侧小于当前元素的个数

归并排序思想：
在merge两个子数组的同时，更新counts数组：
当插入前半部分区间值sub_vec1[x]时，表示后半部分 y之前的所有值都已放置在vec中，
则证明y之前都小于sub_vec1[x],因此对应值索引位置更新+y。

class Solution {
public:
    void merge_two_vec(vector<pair<int, int> > sub_vec1, vector<pair<int, int> > sub_vec2, vector<pair<int, int> >& vec, vector<int>& ans) {
        int x = 0, y = 0;
        while (x < sub_vec1.size() && y < sub_vec2.size()) {
            // 此时插入前半部分区间值sub_vec1[x]
            // y之前的所有值都已放置在vec中
            // 证明都小于sub_vec1[x]
            // 因此更新+y
            if (sub_vec1[x].first <= sub_vec2[y].first) {
                ans[sub_vec1[x].second] += y; // 对应索引位置更新
                vec.push_back(sub_vec1[x]);
                x++;
            }
            // 此时插入后半部分区间值sub_vec2[x]
            else {
                vec.push_back(sub_vec2[y]);
                y++;
            }
        }
        // 处理剩余元素
        while (x < sub_vec1.size()) {
            ans[sub_vec1[x].second] += y; // 对应索引位置更新
            vec.push_back(sub_vec1[x]);
            x++;
        }
        while (y < sub_vec2.size()) {
            vec.push_back(sub_vec2[y]);
            y++;
        }
    }
    
    void merge_sort(vector<pair<int, int> >& vec, vector<int>& ans) {
        if (vec.size() < 2) return; // 当拆分后的数组大小<=1，则直接返回
        // 拆分为2个数组
        int mid = vec.size() / 2;
        vector<pair<int, int> > sub_vec1;
        vector<pair<int, int> > sub_vec2;
        for (int i = 0; i < mid; i++) {
            sub_vec1.push_back(vec[i]);
        }
        for (int i = mid; i < vec.size(); i++) {
            sub_vec2.push_back(vec[i]);
        }
        merge_sort(sub_vec1, ans);
        merge_sort(sub_vec2, ans);
        vec.clear(); // 清空 以存放归并后的数组
        merge_two_vec(sub_vec1, sub_vec2, vec, ans);
    }
    
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> ans;
        if (nums.size() == 0) return ans;
        vector<pair<int, int> > vec;
        for (int i = 0; i < nums.size(); i++) {
            ans.push_back(0); // 初始化结果数组
            vec.push_back(make_pair(nums[i], i)); // 存储nums[i]与对应索引i
        }
        merge_sort(vec, ans);
        return ans;
    }
};

搜索

一、 leetcode 200. 岛屿数量

基础DFS解法:

// DFS找到从（x,y）出发连接的'1'，即一个岛屿
void DFS(vector<vector<char>>& grid, vector<vector<int> >& seen, int x, int y) {
    seen[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int next_x = x + dirs[i][0];
        int next_y = y + dirs[i][1];
        // 超出边界
        if (next_x < 0 || next_x >= grid.size() || next_y < 0 || next_y >= grid[0].size()) 
            continue;
        // 已访问过
        if (seen[next_x][next_y]) continue;
        // 是岛屿 继续DFS
        if (grid[next_x][next_y] == '1') {
            DFS(grid, seen, next_x, next_y);
        }
    }
}

基础BFS解法:

// BFS找到从（x,y）出发连接的'1'，即一个岛屿
    void BFS(vector<vector<char>>& grid, vector<vector<int> >& seen, int x, int y) {
    queue<pair<int, int> > mq;
    mq.push(make_pair(x, y));
    seen[x][y] = 1; // 入队标志
    while (!mq.empty()) {
        int cur_x = mq.front().first;
        int cur_y = mq.front().second;
        mq.pop();
        for (int i = 0; i < 4; i++) {
            int next_x = cur_x + dirs[i][0];
            int next_y = cur_y + dirs[i][1];
            // 超出边界
            if (next_x < 0 || next_x >= grid.size() || next_y < 0 || next_y >= grid[0].size()) 
                continue;
            // 是岛屿 继续DFS
            if (!seen[next_x][next_y] && grid[next_x][next_y] == '1') {
                mq.push(make_pair(next_x, next_y)); // 入队
                seen[next_x][next_y] = 1;
            }
        }
    }
}

二、leetcode 127. 单词接龙

建立图关系：差一个字母的单词有关系；

BFS

class Solution {
public:
    // 建立单词间关系图：相差一个字母的单词为一组
    void construct_graph(map<string, vector<string> >& graph, vector<string>& wordList, int len) {
        // 初始化graph
        for (int i = 0; i < wordList.size(); i++) {
            for (int j = 0; j < len; j++) {
                string temp = wordList[i];
                temp[j] = '*'; // 替换为‘*’,作为key
                if (graph.count(temp) == 0) {
                    vector<string> vec;
                    vec.push_back(wordList[i]);
                    graph[temp] = vec;
                }
                else graph[temp].push_back(wordList[i]);
            }
        }
        return;
    }
    
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int len = beginWord.length();
        map<string, vector<string> > graph; // 单词，相差一个字母的其他单词表
        wordList.push_back(beginWord); // 也需考虑beginWord
        construct_graph(graph, wordList, len);
        // 进行BFS
        queue<pair<string, int> > q; // 队列(单词，当前步数)
        set<string> visit; // 是否访问过
        q.push(make_pair(beginWord, 1));
        visit.insert(beginWord);
        while (!q.empty()) {
            string cur_s = q.front().first;
            int cur_step = q.front().second;
            q.pop();
            if (cur_s == endWord) {
                return cur_step;
            }
            for (int i = 0; i < len; i++) { // 替换每个字母为'*', 都存在路径
                string temp_s = cur_s;
                temp_s[i] = '*';
                vector<string> neighbors = graph[temp_s];
                for (int j = 0; j < neighbors.size(); j++) {
                    if (visit.find(neighbors[j]) == visit.end()) {
                        q.push(make_pair(neighbors[j], cur_step + 1));
                        visit.insert(neighbors[j]);
                    }
                }
            }
        }
        return 0;
    }
};

升级leetcode 126. 单词接龙 II

记录单词接龙的路径：

使用vector作为BFS数组，建立Qitem数据结构，同时存储(word, step, parent_pos);
map<string, int> visit 记录到某单词的最短路径;

三、leetcode 473. 火柴拼正方形

DFS会超时，可使用二进制法。

class Solution {
public:
    bool makesquare(vector<int>& nums) {
        if (nums.size() < 4) return false; // 个数不足4
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        if (sum % 4 != 0) return false; // 和不为4的倍数
        int target = sum / 4;
        vector<int> ok_subset;
        vector<int> ok_half;
        int all = 1 << nums.size();
        for (int i = 0; i < all; i++) {
            int sum = 0;
            for (int j = 0; j < nums.size(); j++) {
                if (i & (1 << j)) { // i代表的集合中存在第j个元素
                    sum += nums[j]; // 求该集合的和
                }
            }
            if (sum == target) ok_subset.push_back(i); // 和 = target，保存i集合
        }
        // 使4条边两两结合
        for (int i = 0; i < ok_subset.size(); i++) {
            for (int j = i + 1; j < ok_subset.size(); j++) {
                if ((ok_subset[i] & ok_subset[j]) == 0) { // 子集中存在的值不重合
                    ok_half.push_back((ok_subset[i] | ok_subset[j]));
                }
            }
        }
        // 使两部分两两结合 组成正方形
        for (int i = 0; i < ok_half.size(); i++) {
            for (int j = i + 1; j < ok_half.size(); j++) {
                if ((ok_half[i] & ok_half[j]) == 0) { // 子集中存在的值不重合
                    return true;
                }
            }
        }
        return false;
    }
};

动态规划

一、leetcode 70. 爬楼梯

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        // dp状态数组：dp[i]表示到达i级阶梯有多少方法
        vector<int> dp(n + 1, 0);
        // 初始化
        dp[0] = 1; // 爬一个台阶
        dp[1] = 2; // 爬2个台阶或分别爬1个台阶
        // 状态转移
        // dp[i]的值为dp[i - 1]再爬1个 + dp[i - 2]爬2个
        for (int i = 2; i < n; i++) {
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        return dp[n - 1];
    }
};

二、leetcode 198. 打家劫舍

dp[i]表示 [0, i]范围内的最高金额;

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        // dp状态数组
        // dp[i]表示[0, i]的最高金额
        vector<int> dp(nums.size());
        // 初始化
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        // 状态转移
        // i-1被偷，则不能偷i
        // i-2被偷，可以偷i
        for (int i = 2; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.size() - 1];
    }
};

三 leetcode 53. 最大子序和

dp[i]:以nums[i]为结尾的最大子序和;

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        // dp状态数组
        // dp[i]:以nums[i]为结尾的最大子序和
        vector<int> dp(nums.size());
        // 初始化
        dp[0] = nums[0];
        int res = dp[0];
        // 状态转移
        // dp[i]的值是以i-1为结尾的最大子序和+当前nums[i] 或者 以当前nums[i]开头
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(dp[i - 1] + nums[i], nums[i]);
            if (res < dp[i]) {
                res = dp[i];
            }
        }
        return res;
    }
};

五、120. 三角形最小路径和

自底向上；
triangle直接作为状态数组，triangle[i][j]表示从底部到当前位置的最短路径长度；
状态转移方程为triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);
最终结果为triangle[0][0].

六、300. 最长上升子序列

dp[i]:以nums[i]为结尾的最长上升子序列，结尾需要遍历dp，得出最大长度.

七、64. 最小路径和

自底向上；
grid[i][j]只可能从右侧或者下方回来，
状态转移方程：grid[i][j] += min(grid[i][j + 1], grid[i + 1][j]);

八、leetcode 174. 地下城游戏

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size();
        if (m == 0) return 0;
        int n = dungeon[0].size();
        // dp[i][j]：从该位置到P 所需的初始点数
        vector<vector<int>> dp(m, vector<int>(n));
        dp[m - 1][n - 1] = max(1, 1 - dungeon[m - 1][n - 1]);
        // 初始化
        // 最后一列
        for (int i = m - 2; i >= 0; i--) {
            // 当后一个所需血量可以被当前房间内抵消时，初始血量设置为1
            // 否则计算出相差血量，作为该位置的初始血量(dp[i][n - 1])
            dp[i][n - 1] = max(1, dp[i + 1][n - 1] - dungeon[i][n - 1]);
        }
        // 最后一行
        for (int j = n - 2; j >= 0; j--) {
            dp[m - 1][j] = max(1, dp[m - 1][j + 1] - dungeon[m - 1][j]);
        }
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                int dp_min = min(dp[i + 1][j], dp[i][j + 1]);
                dp[i][j] = max(1, dp_min - dungeon[i][j]);
            }
        }
        return dp[0][0];
    }
};

Trie树(字典树)

模板：

# define TRIE_MAX_CHAR_NUM 26
struct TrieNode {
    TrieNode * child[TRIE_MAX_CHAR_NUM]; // 孩子数组 后续26个字母
    bool is_end; // 单词结束标志
    TrieNode(): is_end(false) { // 构造函数 初始化
        for (int i = 0; i < TRIE_MAX_CHAR_NUM; i++) {
            child[i] = 0;
        }
    }
};
class TrieTree {
private:
    TrieNode _root;
    vector<TrieNode *> _node_vec; // 为了析构
    TrieNode * new_node() {
        TrieNode * node = new TrieNode();
        _node_vec.push_back(node);
        return node;
    }

public:
    TrieTree() {
    }
    ~TrieTree() {
        for (int i = 0; i < _node_Vec.size(); i++) {
            delete _node_vec[i];
        }
    }
    // 插入一个单词
    void insert(const char *word) {
        TrieNode *ptr = &_root; // 获取Trie树根节点
        while (*word) { // 直到到达单词尾部
            int pos = *word - 'a';
            if (!ptr->child[pos]) { // 空 新建
                ptr->child[pos] = new_node();
            }
            ptr = ptr->child[pos]; // 到达子节点位置
            word++; // word位置递增
        }
        ptr->is_end = true; // 标记单词结束
    }
    // 搜索单词是否存在
    bool search(const char *word) {
        TrieNode* ptr = &_root;
        while (*word) {
            if (!ptr->child[*word - 'a']) return false;
            ptr = ptr->child[*word - 'a'];
            word++;
        }
        return ptr->is_end;
    }
    // 判断是否存在该前缀
    bool startsWith(const char *prefix) {
        TrieNode* ptr = &_root;
        while (*prefix) {
            if (!ptr->child[*prefix - 'a']) return false;
            ptr = ptr->child[*prefix - 'a'];
            prefix++;
        }
        return true;
    }
}

二、leetcode 211. 添加与搜索单词 - 数据结构设计

DFS查找带有“.”的字符串在字典树中是否存在。

bool dfs_search(TrieNode* ptr, string word, int i) {
        if (i >= word.length()) {
            if (ptr->is_end) return true;
            return false;
        }
        if (word[i] != '.') {  
            if (ptr->child[word[i] - 'a']) { // 匹配并且下一步为true
                if (dfs_search(ptr->child[word[i] - 'a'], word, i + 1)) return true;
            }
        }
        else { // 点字符 可匹配任意后续字母
            // 遍历后续字母 dfs
            for (int j = 0; j < TRIE_MAX_CHAR_NUM; j++) {
                if (ptr->child[j]) {  // 每一个可能的后续字符
                    if (dfs_search(ptr->child[j], word, i + 1)) return true;
                }
            }
        }
        return false;
    }

并查集

一、leetcode 547. 朋友圈

class Solution {
public:
    vector<int> friends;
    vector<int> _size; // 各子树规模
    int findfather(int x) {
        while (friends[x] != x) {
            friends[x] = friends[friends[x]]; // 路径压缩
            x = friends[x];
        }
        return x;
    }
    void union_two(int a, int b) {
        int a_father = findfather(a);
        int b_father = findfather(b);
        if (a_father == b_father) return;
        if (_size[a_father] < _size[b_father]) { // 小的向大的合并 以减小查询复杂度
            friends[a_father] = b_father;
            _size[b_father] += _size[a_father];
        }
        else {
            friends[b_father] = a_father;
            _size[a_father] += _size[b_father];
        }
        /*for (int i = 0; i < friends.size(); i++) { // 更新所有以b_father为父母的friends值
            if (friends[i] == b_father) {
                friends[i] = a_father; 
            }
        }*/
    }
    int findCircleNum(vector<vector<int>>& M) {
        int n = M.size();
        // 并查集初始化
        for (int i = 0; i < n; i++) {
            friends.push_back(i);
            _size.push_back(1); // 本身大小1
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (M[i][j]) {
                    union_two(i, j);
                }
            }
        }
        // 找不同father总数
        map<int, int> mp;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (mp.find(findfather(friends[i])) == mp.end()) {
                res++;
                mp[findfather(friends[i])] = 1;
            }
        }
        return res;
    }
};

线段树

参考链接

leetcode 307. 区域和检索 - 数组可修改

求数组区间和：建立/更新/查询线段树

class NumArray {
private:
    vector<int> _values; // 线段树数组
    int _right_end; // 保存右边界
public:
    /// 构建线段树
    // value：线段树数组(存储区间和)
    // nums：用来构建线段树的数组(已知)
    // pos：在线段树数组value中的当前位置
    // left,right：nums数组中的区间左右边界
    void build_segment_tree(vector<int>& value, vector<int>& nums, int pos, int left, int right) {
        if (left == right) {
            value[pos] = nums[left];
            return;
        }
        int mid = (left + right) / 2;
        build_segment_tree(value, nums, 2 * pos + 1, left, mid); // 构建左子树
        build_segment_tree(value, nums, 2 * pos + 2, mid + 1, right); // 构建右子树
        value[pos] = value[2 * pos + 1] + value[2 * pos + 2]; // 合并
    }
    
    /// 线段树求和
    // value:线段树数组
    // pos：在value中的下标位置
    // left,right：nums数组的当前区间范围
    // qleft,qright：待查询区间
    // [left,right]因递归不断在缩小，[qleft,qright]不变
    int sum_range_segment_tree(vector<int>& value, int pos, int left, int right, int qleft, int qright) {
        if (qleft > right || qright < left) { // 区间不相交
            return 0;
        }
        if (qleft <= left && qright >= right) { // 区间有重叠部分
            return value[pos];
        }
        int mid = (left + right) / 2;
        return sum_range_segment_tree(value, 2 * pos + 1, left, mid, qleft, qright) + sum_range_segment_tree(value, 2 * pos + 2, mid + 1, right, qleft, qright);
    };
    
    /// 线段树更新
    // value:线段树数组
    // pos：在value中的下标位置
    // left,right：nums数组的当前区间范围
    // index：nums更新的下标值
    // new_val
    void updata_segment_tree(vector<int>& value, int pos, int left, int right, int index, int new_value) {
        if (index == left && index == right) { // 当前区间为待更新点
            value[pos] = new_value;
            return;
        }
        int mid = (left + right) / 2;
        if (mid >= index) updata_segment_tree(value, 2 * pos + 1, left, mid, index, new_value);
        else updata_segment_tree(value, 2 * pos + 2, mid + 1, right, index, new_value);
        value[pos] = value[2 * pos + 1] + value[2 * pos + 2];
    }
    
    NumArray(vector<int>& nums) {
        if (nums.size() == 0) return;
        int n = nums.size() * 4; // 一般线段树大小是原数组大小长度的4倍
        for (int i = 0; i < n; i++) {
            _values.push_back(0);
        }
        _right_end = nums.size() - 1;
        build_segment_tree(_values, nums, 0, 0, _right_end);
    }
    
    void update(int i, int val) {
        updata_segment_tree(_values, 0, 0, _right_end, i, val);
    }
    
    int sumRange(int i, int j) {
        return sum_range_segment_tree(_values, 0, 0, _right_end, i, j);
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(i,val);
 * int param_2 = obj->sumRange(i,j);
 */

二、leetcode 1157. 子数组中占绝大多数的元素

线段树中存储在当前区间中，通过打擂法胜出的值；
在query过程中，找到查询区间中，出现次数最多的值x；
哈希表indices_map存储值与对应的索引数组；
在索引数组中找到在[left, right]区间内的个数，判断是否符合要求即可。

贪心

在每一步做出在当前来看的最优选择。

一、leetcode 455. 分发饼干

class Solution {
public:
    // g:需求因子数组
    // s:糖果数组
    // 贪心思想：用最小的饼干量满足需求
    // 双指针：child cookie
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int child = 0, cookie = 0;
        while (child < g.size() && cookie < s.size()) {
            if (g[child] <= s[cookie]) { // 当前饼干量满足孩子需求
                child++;
                cookie++;
            }
            // 当前饼干量无法满足孩子需求 则也无法满足后续孩子需求
            // 是个废饼干
            else {
                cookie++;
            }
        }
        return child;
    }
};

二、leetcode 376. 摆动序列

状态机 + 贪心：从左到右的遍历过程中，若持续下降/上升，选取最右边界作为摆动序列的一部分，以使摆动序列最长；

三、leetcode 402. 移掉K位数字

栈 + 贪心：从左到右遍历（高位到低位）,如果对应数字大于下一位数字，则应该把该数字去掉，以取得最小数

四、leetcode 55. 跳跃游戏

当前位置cur_pos,当前可以到达的范围nums[cur_pos] + cur_pos,找到该范围中可以到达最远位置的下标值，作为跳跃目标。
升级题:leetcode 45. 跳跃游戏 II

六、leetcode 871. 最低加油次数

贪心+最大堆（有点跳跃游戏的思想：你尽管走，不够了就加）

class Solution {
public:
    // 贪心：在不得不加的时候加最多的油，使加油次数最少
    // station:0:距离起点的位置；1:油站所拥有的油量
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        priority_queue<int> Q; // 存储油量的最大堆
        int res = 0; 
        vector<int> temp(2);
        temp[0] = 0;
        temp[1] = startFuel;
        stations.push_back(temp);
        temp[0] = target;
        temp[1] = 0;
        stations.push_back(temp);
        sort(stations.begin(), stations.end()); // 从起点到终点
        int fuel = startFuel;
        for (int i = 1; i < stations.size(); i++) {
            int dis = stations[i][0] - stations[i - 1][0]; // 此次需要走的距离
            while (!Q.empty() && fuel < dis) { // 当前油量无法满足 则从最大堆中选取最大油量来加
                fuel += Q.top();
                Q.pop();
                res++;
            }
            if (Q.empty() && fuel < dis) return -1; // 加满油也无法前进dis
            fuel -= dis;
            Q.push(stations[i][1]); // 将油量放入最大堆
        }
        return res;
    }
};

其他

leetcode 122 买卖股票的最佳时机 II
leetcode 881 救生艇
 leetcode 316. 去除重复字母
 leetcode 435. 无重叠区间
贪心(区间调度):优先选择end小的(首先根据end升序排序)，使剩下的区间最多，则移除区间最少，与452类似.
leetcode 659. 分割数组为连续子序列
 leetcode 861. 翻转矩阵后的得分
（难）321/330/757

面经刷题

洗牌算法

注意分号的使用，当以”(“、”[“、”/“、”+”、”-“为行的开头，可能与前一行形成调用或者元素引用。

arr=[1,2,3,4,5,6]
function myShuffle(arr){
    for(let i=arr.length;i;i--){
        let j = Math.floor(Math.random()*i);
        [arr[i-1],arr[j]]=[arr[j],arr[i-1]];
    }
    return arr
}
myShuffle(arr)

CSS两列布局

将content右栏margin-left，main主栏float,sidebar定宽并设置float，margin-left;

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>菜鸟教程(runoob.com)</title>
	
<style>
*{
	margin:0;
	padding:0
	}
.main {
	float:left;
	width:100%;
	}
.main .content{
	margin-left:200px;
	}
.sidebar{
	width:200px;
	float:left; // 先设置float布局，下一步margin-left才有效
	margin-left:-100%; // 向左移动一个屏幕的距离
	}
</style>
	
</head>
<body>
<div class="main">
	<div class="content">
		content-right
	</div>
</div>
<div class="sidebar">
	sidebar-leftsidebar-leftsidebar-left
</div>
</body>
</html>

这他娘的为啥不行！无语

*{
	margin:0;
	padding:0
	}
.main {
	overflow:hidden;
    border: 1px solid red;
	}
.content{
	background:red;
	margin-left:200px;
	height: 200px;
	}
.sidebar{
	float:left;
	width:200px;
	height: 200px;
	background:skyblue;
	}

content右栏position:absolute,left:200px

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>菜鸟教程(runoob.com)</title>
	
<style>
*{
	margin:0;
	padding:0
	}
.content{
	position:absolute;
	left:200px;
	right:0;
	top:0;
	}
.sidebar{
	width:200px;
	}
</style>
	
</head>
<body>
<div class="content">
	content-right
</div>
<div class="sidebar">
	sidebar-leftsidebar-leftsidebar-left
</div>
</body>
</html>

flex布局：设置sidebar的order为-1，长度为200px;content右栏flex:1；

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>菜鸟教程(runoob.com)</title>
	
<style>
*{
	margin:0;
	padding:0
	}
.main{
	display:flex;
	}
.content{
	flex:1; // 我的理解是：在没有其他元素的情况下，flex-grow:1可以霸占剩余区域
	}
.sidebar{
	flex:0 0 200px;
	order:-1;
}
</style>
	
</head>
<body>
<div class="main">
	<div class="content">
		content-right
	</div>
	<div class="sidebar">
		sidebar-leftsidebar-leftsidebar-left
	</div>
</div>
</body>
</html>

浏览器渲染过程

参考链接

解析HTML文档->DOM树；（JS脚本的加载会阻塞DOM树的生成）
解析CSS规则->CSSOM树；（会阻塞涉及CSS的JS脚本与对应DOM树的构建)
CSS解析与DOM解析可同时进行;
构建渲染树：遍历DOM树，对每个节点查找对应的CSS规则（去除display:none,script,meta,link;visibility或opacity隐藏的节点依然存在）
回流：（布局）在设备视口确切位置与尺寸大小；
绘制：将可见节点转换为屏幕的具体像素，绘制在浏览器上。

触发：

开始渲染；
浏览器窗口变化；
DOM元素添加或删除；
元素尺寸大小，位置；
元素内部内容改变；
style属性改变。

如何优化：

css样式改变最小化；
动画元素脱离文档流；
先在脱离文档流的情况下构建好，再插入到主文档中:
（display:none/fragment构建子树/拷贝到脱离文档的节点中）
避免触发同步布局事件;
css3硬件加速（GPU加速）。

typeOf的返回值

undefined,string,number,boolen,function,object(null,array);
基本类型：string number boolen null undefined;
引用类型：function object array data regexp;

BFC

参考链接
块级格式化上下文：盒子模型，独立的块，包含内部所有元素，除了被包含在新BFC下的元素；隔离的独立容器，不受外部元素的影响，内部也不会影响到外部元素。
特性：
在垂直方向上一个接一个放置；
属于一个BFC的相邻margin会重叠（防止外边距合并）
不与外部float box重叠(自适应两栏)；
计算内部float box的高度(清除浮动)
产生方法：
float不为none;
position:absolute,fixed;
display:inline-block,table-cell,flex,table-caption,inline-flex;
overflow不为visible;

观察者模式与发布-订阅模式

参考链接
相同点：Observer订阅，Subject接受事件，以及notify通知观察者；
不同，
观察者模式同步，发布者与订阅者直接连接，单个应用程序空间中实现；
发布-订阅模式异步，中间有消息代理进行通信，松散耦合，交叉应用模式。

函数运算符优先级等综合练习

参考链接

function Foo() {
    getName = function () { alert (1); };
    return this;
}
Foo.getName = function () { alert (2);};
Foo.prototype.getName = function () { alert (3);};
var getName = function () { alert (4);};
function getName() { alert (5);}
 
//请写出以下输出结果：
Foo.getName();
getName();
Foo().getName();
getName();
new Foo.getName();
new Foo().getName();
new new Foo().getName();

Foo.getName() // 2

静态属性与静态方法在没有初始化实例时就能访问；
要调用公有属性、公有方法，必须new；公有方法不能调用私有属性与方法；
外部不可调用私有属性和方法。

getName() // 4

函数声明发生变量提升，被同名函数表达式覆盖；

Foo.getName() // 1

Foo()函数执行返回window全局对象，其中getName覆盖函数；

getName() // 1

全局对象的getName()函数；

new Foo.getName() // 2

运算符优先级：.=new有参>new无参>函数调用
所以

先Foo.getName得到静态方法；
再new得到该方法的实例；
最后调用。

new Foo().getName() // 3

先new有参,初始化Foo实例(实例返回引用类型this，则为实例对象)；
.操作符，获得函数getName(沿原型链)；
执行函数；

new new Foo().getName() // 3

先new有参（第2个new），初始化Foo实例；
.操作符，获得函数getName(沿原型链)；
new无参（第1个new),得到该方法实例；
最后调用。

什么是闭包？优缺点？

定义

匿名函数引用了它的包含函数内的变量，该函数在外部被调用时，产生了闭包，可以使用包含函数的变量，使其可以常驻内存，不随函数销毁而销毁。

优点

变量长期驻扎在内存中；
私有成员避免污染全局变量；
缺点
变量占用内存，导致性能下降；循环引用Html元素会内存泄漏；
闭包是操作包含函数变量的共有方法，不能随意改变该变量值；

三次握手四次挥手

参考链接

进程与线程

进程表示资源调度的基本单位，线程是CPU调度的最小单位；
进程内即同一进程的线程数据共享，而不同进程之间数据不共享；
进程表示程序进入到CPU后：获取程序上下文+CPU执行+保存程序上下文的过程；
线程则是在CPU执行过程中，分为不同的块；
进程消耗较大的计算机资源；
进程：互斥锁、信号量；

promise

参考链接
状态仅由异步操作的结果决定resolve/reject 不可更改可实现回调链
用维护状态、传递状态的方式使回调函数能及时调用
简单、灵活
then catch Promise.all Promise.race

箭头函数

简化了函数定义，相当于匿名函数；
不同的是匿名函数的this为windows或为undefined，
而这个this按照词法作用域绑定了，即指向外层调用者。

generator生成器

参考链接
特性：function与函数名之间又一个*号，函数内部yield表达式；
功能：自动生成并返回迭代器，调用next方法开始运行，移动迭代器指针，直到移到函数末尾，返回undefined。
如果给next传参数，那么该参数作为上一个yield语句的返回值；
注：为异步操作。

vue双向数据绑定

遍历data对象；
添加Observer对象：Object.defineProperty()数据劫持————getter、setter；
getter中初始化Watcher，用于依赖收集Dep；setter触发数据变更事件notify通知Watcher，用于派发更新；
手写一个单例模式
直接执行函数，闭包封装instance
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var A;
(function(name){
var instance;
A=function(name){
if(instance){
return instance;
}
instance=this
this.name=name
}
}());
var a=new A();
var b=new A(); // a===b

变量提升

var,let,function都会发生变量提升；
var：变量声明首先进入内存，相当于提升到了当前作用域顶部，但是没有初始化和赋值；
可以在还没有声明赋值时调用该变量，值为undefined；
let：也存在变量声明，不同的是出现暂时性死区，在赋值之前不允许该值调用；
function：变量提升，同时函数赋值也放到了顶部。

JS事件循环

JavaScipt是单线程的；
同步任务：在执行栈中按顺序执行，后面的任务必须等待前面任务执行完成；
异步任务：挂载出来的任务，不会进入主线程，而进入任务队列；当异步任务完成，则在任务队列中增加进入标志，主线程可在同步任务执行完成后，读取该任务到执行栈中，执行回调函数；

settimeout异步任务，在经过等待的时间后，才有可能被读取到执行栈中，或者是继续等待执行栈中同步任务与任务队列前面的异步任务执行结束。

node.js事件循环

nextTick:在读取任务队列前进行，即在所有异步任务之前；
setImediate:在下一个eventloop时执行，即所有异步任务之后。

原型链

所有的构造函数都有存在一个原型对象，prototype指针指向该原型对象；
由该函数构造的实例都可继承原型对象，__proto__指向；
该原型对象存在constructor属性指回构造函数。
原型链即原型对象为另外一个对象的实例，构成原型链条；
当读取当前实例属性或方法时，从实例，到原型，再由下至上去父类的原型中找，最终到Object的原型；
因为所有函数都由Object继承而来，原型链的最顶部是Object的原型。

es6

键头函数的this指向和普通函数的区别

Vue Router生命周期

网页的优化

怎么判断数组

webpack原理？有没有自己配过

项目整理

统一入口平台

如何部署项目pm2

带有负载均衡功能的Node应用的进程管理器，避免多个终端同时开启，并且可以实现进程永远活着。

npm run pm2 // npm启动pm2
pm2 deploy deploy.yaml production setup  // 首次部署项目
pm2 start 项目启动文件 --name myname//启动node项目
pm2 list // 列出pm2管理的所有进程信息

权限多选树

el-tree组件的改进;封装新el-tree与el-select，得到mutil-select-tree;
为实现调用该多选树的父组件与相应子组件的通信：
父->子传递数据：
父组件在引用时，设置组件属性:data=xxx；子组件中设置props-data 同名属性；
(加冒号表示属性为变量或表达式)
子->父传递数据：
子组件定义事件childevent：emit(“eventname”,事件中携带的数据);子组件绑定方法@click=’childevent’;父组件在引用子组件时定义@childevent，并编写相应的取数据代码。
组件间调用方法：设置refs。

传片系统

路由懒加载

异步组件：将代码分段，防止打包文件过大；使用工厂函数引入全局/局部组件，当需要该组件时，才调用工厂函数，执行异步解析组件，并保存供未来渲染。

vuex

定义：状态管理模式，集中式存储管理应用的所有组件的状态，并保证状态以一种可预测的方式发生变化；
解决问题：多个视图依赖同一状态，不同视图需要对同一状态进行操作；
state：在计算属性中获得状态：this.$store.state.count/…mapState({});
getter：认为是store的计算属性，根据依赖值缓存，对state进行过滤等操作；
使用方法：this.$store.getters.doneTodosCount/this.$store.getters.getTodoById(2)/…mapGetters([]);
mutation：更改状态的唯一方式是提交mutation，同步操作，事件类型+回调函数；
触发：store.commit({
type: ‘increment’,
amount: 10
}) /
…mapMutations([])
action:提交mutation，可以包含任意异步操作；
触发：store.dispatch(‘increment’)/…mapActions([])

页面权限控制

钩子函数，在每一个路由变化中，判断是否存在token；
true：不为登录页则获取当前用户信息；
false：不在白名单中则跳转回登录页；
router.beforeEach(async(to,from,next))

vue生命周期钩子函数

beforeCreated created beforeMounted mounted beforeUpdated updated beforeDestoryed destroyed
created创建实例，获取data属性；（在这里执行DOM操作时一定要放在Vue.nextTick()回调函数中；
mounted渲染DOM，获取el属性。

vue-router钩子函数

全局：beforeEach,afterEach;
路由：beforeEnter,afterEnter;
组件：beforeRouteEnter,beforeRouteUpdate,beforeRouteLeave.

nextTick

原理：Vue异步执行DOM更新，当数据改变时，Vue开启队列，存放与该事件循环相关的数据改变；
当下一次事件循环tick中，再清空该队列，并且执行相关操作。
使用情况：created中涉及DOM操作；在数据变化后中需要进行涉及随数据改变的DOM的操作；

AJAX

通过少量数据交换，实现页面部分的异步更新；
vue.js 2.0 推荐使用axios;
基本使用方法：axios.post(url,{}).then().catch();
请求配置项：url,method,baseURL,headers,params,data,timeout,responseType;
响应信息：data，status,statusText,headers,config;
可设置拦截器:axios.interceptors.request.use()；
可默认设置配置：axios.default.baseURL;

http头部信息

请求：
User-Agent浏览器信息；
Accept：接受的数据格式；
Content-Type:服务器文件类型；
connection：连接形式：保持连接keep-alive/关闭close；
Authorization：客户端回应身份验证信息；
If-None-Match:对应Etag，判断上次的资源标志是否有更改；
If-Modified-Since：对应Last-Modified，判断上次的更改时间后是否有更改；
响应：
status：服务器处理结果；
Expires：实体过期时间；
Cache-Control：告诉客户端缓存规则；
Last-Modified:最近一次修改时间；
Etag：资源标志；
Age：距离上次缓存没更新的时间；

vue-cli脚手架快速搭建项目

可自动生成vue项目，webpack打包；

vue全家桶

vue-cli+vue-router+vuex+ElementUI

chart组件式开发

定义子组件并引出

export default{
name:…,
props:{ // 自定义图表组件传递属性给echart：
className:{
type:String,
default:’…’
}
}
data(){
return {

    }
}
methods:{

}

}

父组件中引入子组件

import
再引出给别的组件作子组件
要设置:components:{children}
页面中使用```

chart resize防抖

mounted阶段:

this.__resizeHandler = debounce(() => { // 防抖
      if (this.chart) {
        this.chart.resize()
      }
    }, 100)
window.addEventListener('resize', this.__resizeHandler) // 添加事件监听

beforeDestory:

if (!this.chart) {
      return
    }
window.removeEventListener('resize', this.__resizeHandler) // 移除事件监听
this.chart.dispose()
this.chart = null

el-tabs 选项卡切换

 <el-tabs v-model="activeName" type="card" @tab-click="handleClick">
 	<el-tab-pane v-for="item in tabMapOptions" :key="item.key" :label="item.label" :name="item.key">
        <keep-alive>
          <tab-pane v-if="item.key==='yes'" />
          <tann-pane v-if="item.key==='no'" />
        </keep-alive>
    </el-tab-pane>
</el-tabs>

tab-pane与tann-pane为子组件，以v-if判断item.key，显示对应的界面。
keep-alive 对经常使用的界面保存组件状态，直接从缓存中读取，避免重复渲染。

SCSS

CSS预处理器，先有SASS，后有SCSS；
分段加载scss文件，将其组合为完整的css规则；

$嵌入变量，#{}嵌入字符串;
&表示父选择器;
可嵌套;
引入：@import …;
mixin声明需要复用的CSS声明，include调用该片段：@mixin @include;
继承：%style @extend
可用操作符计算样式；
命名空间内嵌套属性；
@if @else @for;
方法定义@function;

服务器读取图片

this.$http.get('http://localhost:8088/project/image/byname/' + this.piclocal,
    { responseType: 'arraybuffer' }).then(response => {
        const data = response.data
        console.log(response)
        this.url = 'data:image/png;base64,' + btoa(new Uint8Array(data).reduce((data, byte) => data + String.fromCharCode(byte), ''))
    })

后台将byte数组传送给前端，前台解析图片在页面上展示：
btoa方法转换base-64编码；
reduce为Array对象的一个方法，接受一个函数作为累加器，数组从左到右开始累加,
reduce(function(total,currentValue,currentIndex,arr),initialValue);

字节面经

css怎么实现动画

animation设置
animation-duration:动画时间；
animation-delay:动画延迟播放时间；
animation-timing-function:速度时间函数linear；
animation-direction:进行下一个动画方向alternative；
animation-iteration-count:重复播放次数infinite；
animation-play-state:动画状态paused|running;
transition设置
transition: property duration timing-function delay
在hover上设置变化属性;

css怎么画三角形

.triangle {
	width:0;
	height:0;
	border-width:0 50px 100px 50px;
	border-color:transparent transparent red transparent;
	border-style:solid;
}

css怎么画圆形

.circle {
	width:100px;
	height:100px;
	border-radius:50%;
	background:red;
}

css画扇形

利用border 设置radius,其他border颜色设置为transparent，可得出一个90度的扇形；

.sector
{
	width:0;
	height:0;
	border-width:50px 50px 50px 50px;
	border-color:transparent yellow transparent transparent;
	border-style:solid;
	border-radius:50%;
	transform:rotate(-45deg);
}

画多个角度的
不知道为啥？？不行！！！

.circle {
	width:100px;
	height:100px;
	position:relative:
	overflow:hidden;
	border-radius:50%;
	background:red;
	}
.slice
{
	position:relative;
	transform-origin:0% 100%;
	overflow:hidden;
	top:0;
	right:0;
	width:50%;
	height:50%;
}
.slice-one
{
	background:green;
	transform:rotate(30deg) skewY(-30deg);
}

setTimeout setInterval requestAnimationFrame的区别

setTimeout在一段时间过后执行某种操作，setInterval以一定的时间间隔执行某种操作；
setInterval即使执行报错，也会循环执行；
使用上述两个进行动画操作，控制DOM，会有掉帧、抖动的情况，因为JS事件循环机制，操作不一定会在特定时间内执行，还有固定时间的原因；
所以引入requestAnimationFrame，提供动画API；
与setTimeout的几点区别：

JS引擎；GUI引擎，与显示屏刷新频率保持一致；
页面隐藏或最小化时，在后台执行；屏幕刷新任务停止；
以固定的时间刷新界面；自动优化。

javascript

2020-05-07

vue

2020-04-14

模板语法

v-html:用于输出html代码；
v-bind:绑定属性，用以响应更新属性值；
1. 样式class————v-bind:class={‘class1’:use}/v-bind:class=’activeClassName’];
2. 样式id；
3. href；
4. 内联样式；
v-if、v-else、v-else-if；
v-model：双向数据绑定，view绑定model值，model监听view变化；
v-on：事件处理器；
v-show：根据条件展示元素；
v-for：循环迭代对象、整数；

属性

计算属性computed

与methods区别：methods在页面重新渲染时运行，computed依赖缓存，只有相关依赖值发生变化时重新获取；
可设置set函数，在获得值时设置其他值；get函数得到值的格式；

监听属性watch

组件

全局组件：Vue.component(‘tagName’,options)；
局部组件：components:{
‘tagName’:componentName
}
组件间传值：父->子：props属性设置；
子->父：自定义事件;
在子组件中定义childMethod，其中调用this.$emit(‘toParent’);
在父组件中模板v-on绑定toParent方法；
即能实现在子组件中调用方法时，父组件能够接收到消息；

directives注册指令

路由

定义路由组件；
定义路由；
创建router实例；
创建和挂载；
过渡&动画

html

2020-03-24

HTML基础

框架

<!DOCTYPE html>
<html>
<head></head>
<body></body>
</html>

HTML元素

属性：class，id，name…

CSS样式

行内>内部(style)>外部样式优先级(link)

图片

1	<img src="图片位置" alt="无图片时的替代文字">

表格

<table>
<tr>
    <th colspan="2">Head</th>
</tr>
<tr>
    <th>Head1</th>
    <th>Head2</th>
</tr>
<tr>
    <td>row1,cell1></td>
    <td>row1,cell2></td>
</tr>
<tr>
    <td>row2,cell1></td>
    <td>row2,cell2></td>
</tr>
</table>

列表

有序：<ol type='A/a/I/i/'>
无序：<ul style='list-style-type:disc/circle/square/'>
自定义:<dl><dt><dd>

块级元素与行内元素

块级元素

霸占一行，不能与其他任何元素并列
接受宽高，不设置则为父级元素的100%
div,p,h1,table

行内元素

与其他行内元素并列
不设置宽高，默认宽度为文字的宽度
在垂直方向的padding和margin会失效
img,b,a,td,span

HTML表单和输入

HTML框架

1 2	<iframe src="" width="" height="" frameborder="0" name="framename"></iframe> <p><a href="www.baidu.com" target="">Baidu</a></p>

在浏览器窗口内显示嵌套窗口；

HTML脚本

<script>定义客户端脚本；
document.write可以直接在html输出，但是必须在html输出流中，以防覆盖整个文本；
定义函数可触发事件响应，可处理HTML样式；
<noscript>定义不支持脚本浏览器输出的文本；

HTML实体

&entity_name 或 &#entity_number
&lt 或 &#60
&nbsp

HTML URL

因特网服务类型：//域主机.因特网域名:port/服务器路径/资源名称
字符编码后通过因特网发送：ASCll字符集编码，非ASCll字符使用%后跟2位十六进制数；+表示空格；

XHTML 正确标记，格式良好

结构： DOCTYPE强制；html xmlns属性规定命名空间；必须有<html><head><title><body>;
元素语法： 元素名小写，元素闭合，嵌套，一定有个根元素；
属性语法： 属性名小写，属性值引号，不允许属性简写；

HTML5

Canvas画布

<canvas>
使用JS绘制图像：
c=document.getElementById(“myCanvas”);
创建context对象：ctx=c.getContext(“2d”);
绘制红色矩形：ctx.fillStyle=”#FF0000”;
ctx.fillRect(0,0,150,75);
画线： ctx.moveTo(0,0);
ctx.lineTo(200,100);
ctx.stroke();
画圆：ctx.beginPath();
ctx.arc(95,50,40,0,2*Math.PI);
ctx.stroke();
文本：ctx.font=”30px Arial”;
ctx.fillText(“Hello World”,10,50);
/ctx.strokeText(“Hello World”,10,50);//空心
渐变： // 创建渐变
var grd=ctx.createLinearGradient(0,0,200,0);/
var grd=ctx.createRadialGradient(75,50,5,90,60,100);//圆渐变
grd.addColorStop(0,”red”);
grd.addColorStop(1,”white”);

    // 填充渐变
    ctx.fillStyle=grd;
    ctx.fillRect(10,10,150,80);

图像：drawImage(image,x,y)；

拖放

拖放物：draggable=”true”,ondragstart(setData存放拖放物id)；
拖放目的地：ondragover(允许防止preventDefault)ondrop(getData获取拖放物id，加入到当前DOM中)

地理位置

navigator.geolocation.getCurrentPosition(showPosition,showError);

视频

<video width="320" height="240" controls>
  <source src="movie.mp4" type="video/mp4">
  <source src="movie.ogg" type="video/ogg">
您的浏览器不支持Video标签。
</video>

方法：paused(),play()；
属性：width

新的Input类型

color
date
datetime
datetime-local
email
month
number
range
search
tel
time
url
week

新的表单元素

datalist:与input元素配合，定义选项列表；
keygen：用于表单密钥对生成器字段；
output：特殊输出计算name相同的值；

新的表单属性

form 新属性：
autocomplete
novalidate
input 新属性：
autocomplete
autofocus
form
formaction
formenctype
formmethod
formnovalidate
formtarget
height 与 width
list
min 与 max
multiple
pattern (regexp)
placeholder
required
step

添加语义元素

<header>
<nav>
<section>
<article>
<aside>
<figcaption>
<figure>
<footer>

web存储

localStorage - 用于长久保存整个网站的数据，保存的数据没有过期时间，直到手动去除。
sessionStorage - 用于临时保存同一窗口(或标签页)的数据，在关闭窗口或标签页之后将会删除这些数据。
setItem(key,value);
getItem(key);
removeItem(key);
clear();
key(index);
length;

WebSocket

TCP协议；
两次握手：客户端发送包含建立websocket的HTTP请求头，服务端解析请求头，往回发送应答信息，则建立websocket连接；
双方可通过该连接通道自由传递信息；
直到一方主动关闭；
websocket属性：readyState,bufferedAmount;
webSocket事件：onopen,onmessage,onerror,onclose;
webSocket方法：send(),close();

set

拓扑建图

vector作栈

优先队列

集合

9.23

9.24

9.25

9.27

9.28

10.2

10.3

10.19

10.20

10.26

11.1

二叉树

一. leetcode 113 路径总和2

二. leetcode 236 二叉树的最近公共祖先

三. leetcode 114 二叉树展开为链表

图

一. leetcode 199 二叉树的右视图

二. leetcode 207 课程表

二分查找

一. leetcode 35 搜索插入位置

二、leetcode 34 在排序数组中查找元素的第一个和最后一个位置

三、leetcode 33 搜索旋转排序数组

二叉搜索树

一、leetcode 449 序列化和反序列化二叉搜索树

二、leetcode 315 计算右侧小于当前元素的个数

哈希表

一、 leetcode 409 最长回文串

二、leetcode 290 单词规律

三、leetcode 49 字母异位词分组

四、leetcode 3 无重复字符的最长子串

五、leetcode 187 重复的DNA序列

六、leetcode 76 最小覆盖子串

递归

一、 leetcode 78 子集

二、leetcode 90 子集 II

三、leetcode 40 组合总和 II

四、leetcode 22. 括号生成

五、leetcode 51. N皇后

搜索

二、leetcode 127. 单词接龙

升级leetcode 126. 单词接龙 II

三、leetcode 473. 火柴拼正方形

动态规划

一、leetcode 70. 爬楼梯

二、leetcode 198. 打家劫舍

四、leetcode 322. 零钱兑换

五、120. 三角形最小路径和

六、300. 最长上升子序列

七、64. 最小路径和

八、leetcode 174. 地下城游戏

Trie树(字典树)

一、leetcode 208. 实现 Trie (前缀树)

二、leetcode 211. 添加与搜索单词 - 数据结构设计

并查集

一、leetcode 547. 朋友圈

线段树

二、leetcode 1157. 子数组中占绝大多数的元素

三、leetcode 218. 天际线问题

贪心

一、leetcode 455. 分发饼干

二、leetcode 376. 摆动序列

三、leetcode 402. 移掉K位数字

四、leetcode 55. 跳跃游戏

五、leetcode 452. 用最少数量的箭引爆气球

六、leetcode 871. 最低加油次数

其他

面经刷题

洗牌算法

CSS两列布局

将content右栏margin-left，main主栏float,sidebar定宽并设置float，margin-left;

content右栏position:absolute,left:200px

flex布局：设置sidebar的order为-1，长度为200px;content右栏flex:1；

浏览器渲染过程

typeOf的返回值

BFC

三次握手四次挥手