• 刷题/笔试常（自）用模板

    常用模板

    标签（空格分隔）： c++

    并查集

    • 加路径压缩
        class DSU{
        public:
            void add(int x){
                if(far.count(x) == 0) far[x] = -1;
            } 
    
            int find(int x){
                int root = x;
                while(far[root] != -1) root = far[root];
                while( root != x){
                    int ori = far[x];
                    far[x] = root;
                    x = ori;
                }
                return root;
            }
    
            void merge(int x, int y){
                int fx = find(x);
                int fy = find(y);
                if(fx != fy) far[fy] = fx;
            }
    
            bool isCon(int x, int y){
                return find(x) == find(y);
            }
        private:
            unordered_map<int, int> far;
    };

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    字符串分割

    • 以 空格/非大小写英文字母 为间隔进行分割字串（可以自动省略前面的非法字符串与结尾的非法字符串)
    • 结果返回到vector中
    vector<string> splitStr(string s) {
	int sSize = s.size();
	int left = 0;
	int right = 0;
	vector<string> tempS;

	// 先除非法
	while (right < sSize && !((s[right] <= 'z' && s[right] >= 'a') || (s[right] <= 'Z' && s[right] >= 'A') || (s[right] <= '9' && s[right] >= '0')))
	{
		right++;
	}
	left = right;
	while (right < sSize)
	{
		// 中间合法push_back
		while (right < sSize && ((s[right] <= 'z' && s[right] >= 'a') || (s[right] <= 'Z' && s[right] >= 'A') || (s[right] <= '9' && s[right] >= '0')))
		{
			right++;
		}
		tempS.push_back(s.substr(left, right - left));
		// 最后非法判断退出
		while (right < sSize && !((s[right] <= 'z' && s[right] >= 'a') || (s[right] <= 'Z' && s[right] >= 'A') || (s[right] <= '9' && s[right] >= '0')))
		{
			right++;
		}
		left = right;
	}
	return tempS;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    排列与组合

    • 排列，注意出口条件为到达nums.size()，而且不需要一开始就包空的子集，index指标也用不到，每次都需要从头开始
    
vector<vector<int>> res;
void dfs(vector<int>& nums, vector<bool> vis, vector<int> path){
    if(path.size() == nums.size()){  // 达到长度，开始push
        res.push_back(path);
        return;
    }
    for(int i=0; i<nums.size(); i++){  // 不停变换先取哪个
        if(vis[i] || (i && nums[i] == nums[i-1] && !vis[i-1])) continue;
        vis[i] = true;
        path.push_back(nums[i]);
        dfs(nums, vis, path);
        path.pop_back();
        vis[i] = false;
    }

    return;
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
    int n_size = nums.size();
    vector<int> path={};
    vector<bool> vis(n_size, false);
    sort(nums.begin(), nums.end());
    dfs(nums, vis, path);
    return res;
}



    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 组合，注意由于每次枚举放入的都可以只是一部分，所以出口条件不是很重要，可以分成两种写法。
    // 模板写法
vector<vector<int>> res;
void dfs(vector<int>&nums, vector<bool> vis, vector<int>path, int index){
    if(index >= nums.size()) return;  // 其实不用判断，因为for循环里有判断
    else{
        for(int i=index; i<nums.size(); i++){  
            if((i && nums[i] == nums[i-1] && !vis[i-1])) continue;  // 不用判断 vis[i]，因为是以index为开头 
            vis[i] = true;
            path.push_back(nums[i]);
            res.push_back(path);  // 每个子集都要包进去
            dfs(nums, vis, path, i+1);
            path.pop_back();  // 回溯删除
            vis[i] = false;
        }
    }
    return;
}


vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    int n_size = nums.size();
    vector<bool> vis(n_size, false);
    vector<int> path ={};  // 空的也需要包
    res.push_back(path);
    sort(nums.begin(), nums.end());
    dfs(nums, vis, path, 0);
    return res;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    // 精简写法
vector<vector<int>> res;
void dfs(vector<int>&nums, vector<bool> vis, vector<int>path, int index){
    for(int i=index; i<nums.size(); i++){  // 用for循环里的判断表示出口
        if((i && nums[i] == nums[i-1] && !vis[i-1])) continue;
        vis[i] = true;
        path.push_back(nums[i]);
        res.push_back(path);
        dfs(nums, vis, path, i+1);
        path.pop_back();
        vis[i] = false;
    }

    return;
}


vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    int n_size = nums.size();
    vector<bool> vis(n_size, false);
    vector<int> path ={};
    res.push_back(path);
    sort(nums.begin(), nums.end());
    dfs(nums, vis, path, 0);
    return res;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    DSF遍历Board，就是暴力DFS+标记

    // 200. 岛屿数量
void dfs_200(vector<vector<char>>& grid, int x, int y) {
	if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size()) return;  // 超出边界，返回
	if (grid[x][y] != '1') return;  // 非陆地（海水/已经标记过），返回
	grid[x][y] = '2';  // 访问到了，标记
	dfs_200(grid, x - 1, y);  // 往外扩散
	dfs_200(grid, x, y - 1);
	dfs_200(grid, x + 1, y);
	dfs_200(grid, x, y + 1);
	return;
}

int numIslands(vector<vector<char>>& grid) {
	int rows = grid.size(), cols = grid[0].size();
	int res_200 = 0;
	for (int i = 0; i < rows; i++) {
		for (int j = 0; j < cols; j++) {
			if (grid[i][j] == '1') {  // 有陆地，进岛
				res_200++;
				dfs_200(grid, i, j);
			}

		}
	}
	return res_200;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    sort函数中自定义数据类型 与 priority_queue中自定义数据类型 排序

    • sort函数中默认排序
    	vector<int> res = { 1,4,5,2,6,3 };
	sort(res.begin(), res.end());  // 默认从小到大
	sort(res.begin(), res.end(), greater<int>());  // 从大到小

    • 1
    • 2
    • 3
    • sort函数中自定义数据类型排序
    #include
vector<vector<int>> intervals = { {1,1}, {2,1}, {1, 2} };
sort(intervals.begin(), intervals.end(), [](const vector<int> &v1, const vector<int> &v2) {
	if (v1[0] == v2[0]) return v1[1] > v2[1];  // 降序排列，若第一个元素相等，则按第二个元素降序排序  
	return v1[0] < v2[0];  // 升序排列 对于第一个元素 从小到大 升序排列
});
for (auto inter : intervals) {
	cout << "inter val1: " << inter[0] << " " << "inter val2: " << inter[1] << endl;
}

// 自己写结构体，sort()中需要加括号
struct temp_comp {
	bool operator()(int a, int b) {
		return a > b;
	}

};

vector<int> res = { 1,4,5,2,6,3 };
sort(res.begin(), res.end());  // 默认从小到大
sort(res.begin(), res.end(), temp_comp());  // 从大到小
priority_queue<int, vector<int>, temp_comp> pq;  // 而优先队列中 tmep_comp 则不需要加括号，注意 此时 pq 为小根堆，从小到大，与sort函数相反。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • priority_queue 默认大根堆
     priority_queue<int>  // 大根堆
//降序队列，大顶堆
priority_queue <int,vector<int>,less<int> >q;  // 与 sort 函数中的相比 少了括号
//升序队列，小顶堆
priority_queue <int,vector<int>,greater<int> > q;

    • 1
    • 2
    • 3
    • 4
    • 5
    • priority_queue中自定义数据类型排序
    #include
struct comp {
	bool operator()(ListNode *a, ListNode *b) {  // 重载（）运算符
		return a->val < b->val;  // 大根堆的写法，最前面的是值最大的，是与sort里的相反。
	}
};
//  priority_queue<元素类型，元素存储方式，比较规则> 变量名;
priority_queue < ListNode*, vector<ListNode*>, comp> heap;  

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    自建大根堆 priority_queue

    // 自建大根堆 
// 215. 数组中的第K个最大元素
void max_heapify(vector<int>& nums, int pos, int end) {
	int left_pos = 2 * pos + 1;
	int right_pos = 2 * pos + 2;
	int max_pos = pos;  // 初始化 max_pos
	if (left_pos <= end && nums[left_pos] > nums[max_pos]) {  // 找到 最大的pos，若需要改成最小堆，把这里的大于改成小于即可
		max_pos = left_pos;
	}
	if (right_pos <= end && nums[right_pos] > nums[max_pos]) {
		max_pos = right_pos;
	}
	if (max_pos == pos) return;  // max_pos 没变直接返回
	int temp = nums[max_pos];  // 改变了就需要进行交换
	nums[max_pos] = nums[pos];
	nums[pos] = temp;
	max_heapify(nums, max_pos, end);  // 对交换后的pos进行heapify
}

void build_heap(vector<int>& nums, int end) {
	for (int i = (end - 1) / 2; i >= 0; i--) {  // 注意刚开始 i 应该是 (end-1)/2
		max_heapify(nums, i, end);  // 对每一位进行 heapify
	}
}

int findKthLargest_maxHeap(vector<int>& nums, int k) {
	int n_size = nums.size();
	build_heap(nums, n_size-1);  // 堆初始化，里面存放最后一位的位置
	int res;
	for (int i = k; i > 0; i--) {
		res = nums[0];  // 暂时存放结果
		int temp = nums[0];  // 与最后一位交换
		nums[0] = nums[n_size - 1];
		nums[n_size - 1] = temp;
		n_size--;  // 缩减 size
		max_heapify(nums, 0, n_size-1);
	}
	return res;
} 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    TRIE 前缀树

    // 208. 实现 Trie (前缀树)
class Trie {
public:
	Trie() {
		isEnd = false;
		memset(next, false, sizeof(next));
	}

	void insert(string word) {
		Trie* node = this;  // 指向已经开的节点，对于每个已经开的节点都会有一个26长度的数组
		for (auto chr : word) {
			if (node->next[chr - 'a'] == nullptr) node->next[chr - 'a'] = new Trie;
			node = node->next[chr - 'a'];  // 对于每个字符串的结尾，其实都是对应下一个 trie 节点，只不过里面的 next 都是空的
		}
		node->isEnd = true;  // 给下一个 trie 的 isEnd 赋值
	}

	bool search(string word) {
		Trie* node = this;
		for (auto chr : word) {
			if (node->next[chr - 'a'] == nullptr) return false;
			node = node->next[chr - 'a'];
		}
		return node->isEnd;  // 返回也是返回末尾新开的trie里的值
	}

	bool startsWith(string prefix) {
		Trie* node = this;
		for (auto chr : prefix) {
			if (node->next[chr - 'a'] == nullptr) return false;
			node = node->next[chr - 'a'];
		}
		return true;
	}
private:
	bool isEnd;
	Trie* next[26];
}; 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    回文字符串系列

      1. 最长回文子串
      • 中心扩散法，确定每一个点，随便先左后右或者先右后左，最后两边扩展。 时间O(N^2)，空间O(1)
      1. 分割回文串
      • dp预处理，然后再dfs暴力搜索符合条件的，但是我不知道为什么dfs的时间复杂度是O(N*2^N)

    KMP算法

    /*  KMP算法  */
/* KMP算法的精髓就在于对于每个从头开始的连续子串寻找最长公共前后缀，生成next数组，
数组中的每个元素表示此元素之前的字串对应最长公共前后缀长度，
由于每个字串都是从首字符开始，故最长公共前后缀长度也就对应前缀长度，对应为字符串前缀下一个字符的下标。
其中next数组中对于首元素默认设置为-1，表示移动到头的前一个进行匹配，第二个元素默认设置为0，一个字符不存在前后缀。
在以下函数中用于生成字符串p的next数组，i代表后缀查找，j用于前缀查找 */
int GetNext(string p, vector<int>& next) {
    next[0] = -1;   // 初始化 
    int i = 0;
    int j = -1;
    while (i < p.size() - 1) {
        if (j == -1 || p[i] == p[j]) {
            i++;
            j++;
            next[i] = j;  // 由于前缀是从首字符开始的，故j的大小就代表了公共前后缀的长度
        } else {
            j = next[j];  // 不匹配的话，就往前退，寻找合适的且匹配的最长公共前缀，j最小是-1，表示与首字符匹配
        }
    }
    return next[i];
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    线段树模板

    // 307. 区域和检索 - 数组可修改
class NumArray {
public:
// 307. 区域和检索 - 数组可修改
    NumArray(vector<int>& nums): s_nums(nums.begin(), nums.end()), n_size(nums.size()){
        s_tree.resize(tree_size);
        bulid_tree(s_nums, 0, n_size - 1, 0);
    }

    void bulid_tree(vector<int>& nums, int left, int right, int node){
        if(left == right){
            s_tree[node] = nums[left];
            return;
        }
        int left_node = 2 * node + 1;
        int right_node = 2 * node + 2;
        int mid = left + (right - left) / 2;
        bulid_tree(nums, left, mid, left_node);
        bulid_tree(nums, mid+1, right, right_node);
        s_tree[node] = s_tree[left_node] + s_tree[right_node];
        return;
    }

    // O(logN)
    void update_tree(vector<int>& nums, int left, int right, int node, int index, int val){  
        if(left == right){
            s_tree[node] = val;
            nums[left] = val;
            return;
        }

        int mid = left + (right - left) / 2;
        int left_node = 2 * node + 1;
        int right_node = 2 * node + 2;
        if(index > mid){
            update_tree(nums, mid + 1, right, right_node, index, val);
        }
        else{
            update_tree(nums, left, mid, left_node, index, val);
        }
        s_tree[node] = s_tree[left_node] + s_tree[right_node];
        return;
    }

    // O(logN)
    int query_tree(vector<int>& nums, int left, int right, int node, int L, int R){
        if(L > right || R<left)
            return 0;
        else if (left == right)
            return s_tree[node];
        else if (left >= L && right <= R)  // 这里应该把更小区间的 left-right 返回
            return s_tree[node];
        int mid = left + (right - left) / 2;
        int left_node = 2 * node + 1;
        int right_node = 2 * node + 2;
        return query_tree(nums, left, mid, left_node, L, R) + query_tree(nums, mid + 1, right,right_node, L, R);
    }
    
    void update(int index, int val) {
        update_tree(s_nums, 0, n_size-1, 0, index, val);
    }
    
    int sumRange(int left, int right) {
        return query_tree(s_nums, 0, n_size - 1, 0, left, right);
    }
public:
    int n_size;
    int tree_size = pow(10, 5);
    vector<int> s_tree;
    vector<int> s_nums;
}; 


// 729. 我的日程安排表 I
class MyCalendar {
private:
    unordered_map<int, int> tree;
    unordered_map<int, int> lazy;

public:
    MyCalendar() {

    }
    int query(int left, int right, int L, int R, int node){
        if(left > R || right < L)
            return 0;
        else if (left >= L && right <= R)
            return tree[node];
        else{
            int mid = left + (right - left) / 2;
            int left_node = 2 * node + 1;
            int right_node = 2 * node + 2;
            if(lazy[node]){
                tree[left_node] += lazy[node];
                lazy[left_node] += lazy[node];
                tree[right_node] += lazy[node];
                lazy[right_node] += lazy[node];
                lazy[node] = 0;
            }
            int left_max = query(left, mid, L, R, left_node);
            int right_max = query(mid+1, right, L, R, right_node);
            return max(left_max, right_max);
        }
    }

    void update(int left, int right, int L, int R, int node){
        if(left > R || right < L)
            return;
        else if (left >= L && right <= R){
            tree[node]++;
            lazy[node]++;
        }
        else{
            int mid = left + (right - left) / 2;
            int left_node = 2 * node + 1;
            int right_node = 2 * node + 2;
            if(lazy[node]){
                tree[left_node] += lazy[node];
                lazy[left_node] += lazy[node];
                tree[right_node] += lazy[node];
                lazy[right_node] += lazy[node];
                lazy[node] = 0;
            }
            update(left, mid, L, R, left_node);
            update(mid+1, right, L, R, right_node);
            tree[node] = tree[left_node] + tree[right_node];
        }
    }
    
    bool book(int start, int end) {
        if (query(0, 1e9, start, end-1, 0) >= 1)  //query(值域下界, 值域上界, 固定区间下界, 固定区间上界, 起始node)  
            return false;
        update(0, 1e9, start, end-1, 0);
        return true;
    }
};

// 732. 我的日程安排表 III
class MyCalendarThree {
    private:
        unordered_map<int, int> tree;
        unordered_map<int, int> lazy;

    public:
        MyCalendarThree()
        {

    }
    
    void update(int left, int right, int L, int R, int node){
        if (L > right || R < left)
            return;
        else if (L <= left && R >= right){  // 懒更新,指的是分段的区间在设置的里面
            tree[node]++;
            lazy[node]++;
        }
        else{  // 非懒更新
            int mid = left + (right - left) / 2;
            int left_node = 2 * node + 1;
            int right_node = 2 * node + 2;
            update(left, mid, L, R, left_node);
            update(mid+1, right, L, R, right_node);
            tree[node] = lazy[node] + max(tree[left_node], tree[right_node]);
        }
    }

    int book(int start, int end) {
        update(0, 1e9, start, end-1, 0);
        return tree[0];
    }
};


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172

    最长公共子序列问题（LCS）与最长递增子序列问题（LIS）

    // 最长公共子序列问题，若不加限制，则朴素解法，使用动态规划，O(M*N)
// 若加以限制，则可转化为 LIS，使用动态规划+二分法，O(M*logM)
// LCS 与 LIS 问题
// 1143. 最长公共子序列
int longestCommonSubsequence(string text1, string text2) {
	int s1_size = text1.size();
	int s2_size = text2.size();
	// 初始化，dp[0][0] 公共串为0， dp[0][i]与dp[i][0] 公共串也都为0
	vector<vector<int>> dp(s1_size+1, vector<int>(s2_size+1, 0));
	for (int i = 0; i < s1_size; i++) {
		for (int j = 0; j < s2_size; j++) {
			if (text1[i] == text2[j]) dp[i + 1][j + 1] = dp[i][j] + 1;
			else dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
		}
	}
	return dp[s1_size][s2_size];
}

// 300. 最长递增子序列
int lengthOfLIS(vector<int>& nums) {
	int n_size = nums.size();
	vector<int> dp(n_size, INT32_MIN);
	dp[0] = nums[0];
	int right_end=0;  // 生成的最后dp不一定就是最长递增子序列，不过保存的right_end可以就理解成曾经能达到的最长长度
	for (int i = 1; i < n_size; i++) {
		if (nums[i] > dp[right_end]) {
			right_end++;
			dp[right_end] = nums[i];
		}
		else {
			int left = 0, right=right_end;
			while (left < right)
			{
				int mid = left + (right - left) / 2;
				if (dp[mid] < nums[i]) left = mid + 1;
				else right = mid;
			}
			dp[right] = nums[i];
		}
	}
	return right_end + 1;
}

// 1713. 得到子序列的最少操作次数
// 使用 朴素LCS做法，O(M*N) TLE 了。数据量 M 与 N 的长度都是 1e6
int minOperations_LCS(vector<int>& target, vector<int>& arr) {
	int tar_size = target.size();
	int arr_size = arr.size();
	vector<vector<int>> dp(tar_size + 1, vector<int>(arr_size + 1, 0));
	for (int i = 0; i < tar_size; i++) {
		for (int j = 0; j < arr_size; j++) {
			if (target[i] == arr[j]) dp[i + 1][j + 1] = dp[i][j] + 1;
			else dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
		}
	}
	return tar_size - dp[tar_size][arr_size];
}

// 转化为 LIS 来做，可以
int minOperations_LCS2LIS(vector<int>& target, vector<int>& arr) {
	int tar_size = target.size();
	int arr_size = arr.size();
	unordered_map<int, int> umap;
	// tar 的索引是递增的，所以可以考虑存住索引 用最长递增数列来做，复杂度降到 O(M*logM)
	for (int i = 0; i < tar_size; i++) umap[target[i]] = i;
	vector<int> v_arr;
	// 映射 arr 中的元素，对于存在于 tar 中的元素标记索引，并存下来。
	for (int i = 0; i < arr_size; i++) {
		if (umap.count(arr[i])) v_arr.push_back(umap[arr[i]]);
	}
	// 在从 tar 得到的映射数组中寻找最长递增序列（此时这个最长递增序列就对应着tar的最长公共序列，LIS就对应着 LCS）
	int v_arr_size = v_arr.size();
	// 为空或者只有一个，就直接返回了。
	if (v_arr_size < 2) return tar_size - v_arr_size;
	vector<int> dp(v_arr_size, 0);
	int right_end = 0;
	dp[right_end] = v_arr[0];
	for (int i = 1; i < v_arr_size; i++) {
		if (v_arr[i] > dp[right_end]) {
			right_end++;
			dp[right_end] = v_arr[i];
		}
		else {
			int left = 0, right = right_end;
			while (left < right)
			{
				int mid = left + (right - left) / 2;
				if (dp[mid] < v_arr[i]) left = mid + 1;
				else right = mid;
			}
			dp[left] = v_arr[i];
		}
	}
	return tar_size - right_end - 1;
}


// 926. 将字符串翻转到单调递增 
// 就是 LIS 的做法，不过修改了 二分的做法，详细可以参考二分模板
int minFlipsMonoIncr(string s) {
	int s_size = s.size();
	vector<int> dp(s_size, 0);
	int right_end = 0;
	dp[right_end] = s[0];
	for (int i = 1; i < s_size; i++) {
		if (s[i] >= dp[right_end]) {
			right_end++;
			dp[right_end] = s[i];
		}
		else {
			int left = 0, right = right_end;
			while (left < right)
			{
				int mid = left + (right - left) / 2;
				if (dp[mid] <= s[i]) left = mid + 1;
				else right = mid;
			}
			dp[left] = s[i];
		}
	}
	return s_size - right_end - 1;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123

    二分模板

    我自己常用的二分模板：

        int left = 0, right = right_end;
    while (left < right)
    {
        int mid = left + (right - left) / 2;
        if (dp[mid] < s[i]) left = mid + 1;
        else right = mid;
    }
    /*
        跳出时，left == right
        1. 若数组中只有一个数与s[i] 相等，则left就是对应的位置。
        2. 若数组中有多个数与s[i] 相等，则left就是对应最左边的位置。
        3. 若数组没有数与s[i] 相等，则left就是对应大于s[i]的最左位置的数。
    */

    while (left < right)
    {
        int mid = left + (right - left) / 2;
        if (dp[mid] <= s[i]) left = mid + 1; // 与上面对比，只在这里改成了 小于等于
        else right = mid;
    }
    /*
        跳出时，left == right
        1. 若数组中只有一个数与s[i] 相等，则left就是对应大于s[i]的最左位置的数。
        2. 若数组中有多个数与s[i] 相等，则left就是对应大于s[i]的最左位置的数。
        3. 若数组没有数与s[i] 相等，则left就是对应大于s[i]的最左位置的数。
    */



    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    set 与 map 相关的排序

    
// set 自定义数据类型排序
class person
{
public:
	person(string name, int age)
	{
		this->m_name = name;
		this->m_age = age;
	}
	string m_name;
	int m_age;
};

struct mycompare{
	bool operator()(const person & p1, const person& p2) const {
		if (p1.m_age == p2.m_age) return p1.m_name < p2.m_name;
		return p1.m_age < p2.m_age;
	}
};

struct mycompare2 {
	bool operator()(const pair<person, string> & p1, const pair<person, string> & p2) const {
		return p1.second < p2.second;
	}
};

void test_set() {
	vector<int> a = { 3, 1, 2, 4 };
	set<int> default_set;
	set<int, less<int>> less_set;
	set<int, greater<int>> greater_set;

	for (auto num : a) {
		default_set.insert(num);
		less_set.insert(num);
		greater_set.insert(num);
	}

	cout << "Default_iter: ";  // 默认从小的到大哦 less
	for (auto iter : default_set) {  // .begin(), .end() 表示指针
		cout << iter << " ";
	}
	cout << endl;

	cout << "Less_iter: ";
	for (auto iter : less_set) {  // .begin(), .end() 表示指针
		cout << iter << " ";
	}
	cout << endl;

	cout << "Greater_iter: ";
	for (auto iter : greater_set) {  // .begin(), .end() 表示指针
		cout << iter << " ";
	}
	cout << endl;

	cout << "自定义数据类型" << endl;
	cout << "++++++++++++++++++++++++++++++++++++++++++++++++" << endl;
	// 自定义数据类型
	set<person, mycompare> p_set;
	person p1("sss", 35);
	person p2("aaa", 10);
	person p3("bbb", 20);
	person p4("ccc", 46);
	person p5("ddd", 82);
	person p6("eee", 35);

	p_set.insert(p1);
	p_set.insert(p2);
	p_set.insert(p3);
	p_set.insert(p4);
	p_set.insert(p5);
	p_set.insert(p6);

	for (auto iter : p_set) {
		cout << "age: " << iter.m_age << " name: " << iter.m_name << endl;
	}

}

// map 自定义数据类型排序
void test_map() {
	// default map
	map<int, string> default_map;
	default_map[3] = "sss";
	default_map[2] = "ccc";
	default_map[1] = "bbb";
	default_map[1] = "aaa";

	// 并不存在 key 相同，然后再对value进行排序的情况，因为key相同，value会被覆盖。:)
	// 所以默认对 key 进行从小到大排序， less
	cout << "default map: " << endl;
	for (auto iter : default_map) {
		cout << "Map key: " << iter.first << " value: " << iter.second << endl;
	}

	// 对 key 进行从大到小排序， greater
	map<int, string, greater<int>> default_great_map;
	default_great_map[3] = "sss";
	default_great_map[2] = "ccc";
	default_great_map[1] = "bbb";
	default_great_map[1] = "aaa";
	cout << "default greate map: " << endl;
	for (auto iter : default_great_map) {
		cout << "Map key: " << iter.first << " value: " << iter.second << endl;
	}

	// 自定义数据类型排序，与set类似，自己定义好比较的struct
	map<person, string, mycompare> person_map;
	person p1("sss", 35);
	person p2("aaa", 10);
	person p3("bbb", 20);
	person p4("ccc", 46);
	person p5("ddd", 82);
	person p6("eee", 35);
	person_map[p1] = "111";
	person_map[p2] = "333";
	person_map[p3] = "222";
	person_map[p4] = "888";
	person_map[p5] = "555";
	person_map[p6] = "666";

	cout << "person map: " << endl;
	for (auto iter : person_map) {
		cout << "Map key: age = " << iter.first.m_age << " name = "<< iter.first.m_name <<  " value: " << iter.second << endl;
	}

	// 根据 value 进行排序
	vector<pair<person, string>> v(person_map.begin(), person_map.end());
	sort(v.begin(), v.end(), mycompare2());
	cout << "person map sort by value: " << endl;
	for (auto iter : v) {
		cout << "Map key: age = " << iter.first.m_age << " name = " << iter.first.m_name << " value: " << iter.second << endl;
	}


} 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138

    sscanf(const char * , string, char[])函数

    // 例题： 636. 函数的独占时间
	//使用c_str()函数， c_str函数的返回值是const char*。
	//c_str()函数返回一个指向正规C字符串的指针, 内容与本string串相同。
	// sscanf 函数详解 https://blog.csdn.net/lxzh12345/article/details/24122969

	string s = "123abcABCabc";
	char buf[20];  // 一定得是足够长的 char 数组
	sscanf(s.c_str(), "%[1-9a-z]", buf);  
	printf("%s\n", buf);
	// 输出 123abc，原因是到达大写字母时就停了。

	char str[50];  // 一定得是足够长的 char 数组
	sscanf("123456abcdedfBCDEF", "%[^A-Z]", str);
	printf("%s\n", str);
	// 输出 123456abcdedf，原因是到达大写字母时就停了。

	int a, b, c;
	sscanf("2006:03:18", "%d:%d:%d", &a, &b, &c);
	printf("%d %d %d\n", a, b, c);
	// 输出 2006 3 18

	char sztime1[16], sztime2[16];
	sscanf("2006:03:18 - 2006:04:18", "%s - %s", sztime1, sztime2);
	printf("%s %s\n", sztime1, sztime2);
	// 输出 2006:03:18 2006:04:18 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    字符是不能加字符的，这样只是ascci的相加

    
	string s = "";
	s += ('a' + 's');  
	cout << s << endl;  // 输出结果是错误的

	string s = "";
	s += 'a' ;
	s += 's'  
	cout << s << endl;  // 输出结果是正确的


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    scanf 函数详解

    参考链接

    	string s = "123abcABCabc";
	char buf[20];  // 一定得是足够长的 char 数组
	sscanf(s.c_str(), "%[1-9a-z]", buf);  
	printf("%s\n", buf);
	// 输出 123abc，原因是到达大写字母时就停了。

	char str[50];  // 一定得是足够长的 char 数组
	sscanf("123456abcdedfBCDEF", "%[^A-Z]", str);
	printf("%s\n", str);
	// 输出 123456abcdedf，原因是到达大写字母时就停了。

	int a, b, c;
	sscanf("2006:03:18", "%d:%d:%d", &a, &b, &c);
	printf("%d %d %d\n", a, b, c);
	// 输出 2006 3 18

	char sztime1[16], sztime2[16];
	sscanf("2006:03:18 - 2006:04:18", "%s - %s", sztime1, sztime2);
	printf("%s %s\n", sztime1, sztime2);
	// 输出 2006:03:18 2006:04:18 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    字符是不能加字符的，这样只是ascci的相加

    	string s = "";
	s += ('a' + 's');  
	cout << s << endl;  // 输出结果是错误的，为空

	string s = "";
	s += 'a' ;
	s += 's'  
	cout << s << endl;  // 输出结果是正确的

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    找到最大与次大值

    class Solution {
    public int maxProduct(int[] nums) {
        int a = -1, b = -1;
        for (int x : nums) {
            if (x > a) {
                b = a; a = x;  // 这里就是相当于 a 存的是最大值，b 存的是次大值
            } else if (x > b) {
                b = x;
            }
        }
        return (a - 1) * (b - 1);
    }
} 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
  • 相关阅读:
    深度学习与深度强化学习
    好的代码是优质资产、莫让代码成为负债
    星辰天合受邀参加红帽2023中国区合作伙伴大会
    代码随想录算法训练营第23期day14|二叉树层序遍历、226.翻转二叉树、101. 对称二叉树
    技术分享 | app自动化测试（Android）–显式等待机制
    FreeRTOS介绍 和 将FreeRTOS移植到STM32F103C8T6
    Haproxy+Nginx搭建Web集群部署
    ＜1＞ c++ 笔记 stl::map
    机器学习（20）---神经网络详解
    从 internal 修饰符一探 kotlin 的可见性控制
  • 原文地址：https://blog.csdn.net/qq_38762282/article/details/126558078