map 容器的用法

map 根据 value 排序：借助vector实现

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
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
 
// 自定义比较函数，按照值从小到大排序
bool compareByValue(const std::pair<int, int>& a, const std::pair<int, int>& b) {
    return (a.second < b.second); // 这里假设值为int类型
}
 
int main() {
    std::map<int, int> myMap;
    
    // 添加元素到myMap
    myMap[1] = 50;
    myMap[2] = 30;
    myMap[3] = 70;
    myMap[4] = 90;
    
    // 将myMap转换为vector
    std::vector<std::pair<int, int>> vec(myMap.begin(), myMap.end());
    
    // 使用自定义比较函数对vec进行排序
    std::sort(vec.begin(), vec.end(), compareByValue);
    
    // 输出结果
    for (auto& pair : vec) {
        std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
    }
    
    return 0;
}

去重

1
2
3
4
if(it.second!=num){
    s.erase(s.find(it.first),m[it.first]);
}

string里的四个 find 函数

  • find_first_of()：正向查找在原字符串中第一个与指定字符串（或字符）中的某个字符匹配的字符，返回它的位置。若查找失败，则返回npos。
  • find_last_of()：逆向查找在原字符串中最后一个与指定字符串（或字符）中的某个字符匹配的字符，返回它的位置。若查找失败，则返回npos。
  • find_first_not_of()：正向查找在原字符串中第一个与指定字符串（或字符）中的任一字符都不匹配的字符，返回它的位置。若查找失败，则返回npos。
  • find_last_not_of()：正向查找在原字符串中最后一个与指定字符串（或字符）中的任一字符都不匹配的字符，返回它的位置。若查找失败，则返回npos。

普通stirng.find函数查找返回第一个的位置，查不到返回npos（-1）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class cmp1 {
	public:
    bool operator()(const int& a, const int& b) const {
        return (a > b); // 根据第一个元素（key）进行降序排列
    }
};
class cmp2 { //这个无法匹配m2，map的第三个排序参数是针对key值的。
	public:
    bool operator()(const pair<int,int>& a, const pair<int,int>& b) const {
        return (a.first > b.first); // 根据第一个元素（key）进行降序排列
    }
};

int main(void)
{
	map<int,int,cmp1> m2;
}

3039. 进行操作使字符串为空

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
 class Solution {
public:
    static bool m_cmp(const pair<char,int>& p1,const pair<char,int>& p2)
    {
        return p1.second>p2.second;
    }
    string lastNonEmptyString(string s) {
    string sp = s;
	map<char,int> m;
	for(int i=0;i<s.size();i++)
	{
		m[sp[i]]++;
	}
	vector<pair<char,int> > v(m.begin(),m.end());
	sort(v.begin(),v.end(),m_cmp);
	int num = v.front().second;

	map<int,char> m2;
    for(vector<pair<char,int> >::iterator it = v.begin();it!=v.end();it++)
    {
        if(it->second==num) m2.insert(make_pair(sp.find_last_of(it->first),it->first));
        else break;
    }
    string s2 = "";
    for(auto it :m2){
    	s2=s2+it.second;
	}
    return s2;
    }
};

更简单的版本

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
class Solution {
public:
    string lastNonEmptyString(string s) {
    int cnt[26]{},last[26]{};

	for (int i=0;i<s.size();i++)
	{
		int t = s[i]-'a';
		cnt[t]++;
		last[t] = i;
	}
	//最大频率数
	int mx = -1;
	vector<int> v;
	for(int i=0;i<26;i++) if(mx<cnt[i]) mx = cnt[i];
	
	//最大频率数的字符，将其最后一次出现的位置传到v
	for(int i=0;i<26;i++){
		if(cnt[i]==mx) v.push_back(last[i]);
	}
	//对位置排序
	sort(v.begin(),v.end(),less<>());
    string t(v.size(),0);
	//依次读入字符
	for (int i = 0; i < v.size(); i++) {
        t[i] = s[v[i]];
    }
	return t;

    }
};

作者：灵茶山艾府
链接：https://leetcode.cn/problems/apply-operations-to-make-string-empty/solutions/2643734/tong-ji-zi-mu-chu-xian-ci-shu-he-zui-hou-0r5g/

记忆化搜索例题

AcWing 901. 滑雪

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
#include<iostream>
#include<cstring>
using namespace std;
const int N = 310;
int h[N][N];
int f[N][N];//记忆化数组
int dis[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
int m,n;
int dp(int x,int y)
{
	int &v = f[x][y];
	if(v!=-1) return v; //此处为记忆化的关键。

	v = 1; //别忘了赋初值 
	for(int i=0;i<4;i++){
		int tx = x+dis[i][0];
		int ty = y+dis[i][1];
		if(tx>=0&&tx<n&&ty>=0&&ty<m&&h[tx][ty]<h[x][y]){
			v = max(v,dp(tx,ty)+1); //此处是记录的发起点
		}
	}
	return v;
		
}

int main(void)
{

	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			scanf("%d",&h[i][j]);
		}
	}
	memset(f,-1,sizeof f);
	int res = -1;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			res = max(res,dp(i,j));
	cout<<res;
	return 0;
}

Problem: 100220. 相同分数的最大操作数目 II

​

暴力dfs：

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
#include<iostream>
#include<vector>
#include<climits>
#include<queue>
using namespace std;

int mx = -1;
deque<int> f1(deque<int> a) //delete front2
{
	int sum = a[0] + a[1];
	a.pop_front();
	a.pop_front();
	a.push_front(sum);
	return a;
}
deque<int> f2(deque<int> a)//delete back2
{
	int n = a.size()-1;
	int sum = a[n]+a[n-1];
	a.pop_back();
	a.pop_back();
	a.push_front(sum);
	return a;	
}
deque<int> f3(deque<int> a)//delete front1 + back1
{
	int sum = a.front() + a.back();
	a.pop_front();
	a.pop_back();
	a.push_front(sum);
	return a;		
}
//返回数组，同时添加数组的第一个元素，存储本次处理后的sum

void dfs(deque<int> a,int step,int sum)
{
	if(a.size()<=1){
		if(mx<step)	mx = step;
		return ;
	}		
	
	deque<int> b ;//保证原数组数据干净。
    
    
	b = f1(a); //按第一种方式处理
	int t_sum = b[0];
	b.pop_front();//收到队头总和元素，去掉deque里多余的队头元素。
	
	if(t_sum!=sum)//不相等，不符合条件
	{
		if(mx<step){
			mx = step;
		}
	}
	else {
		dfs(b,step+1,sum); //相等，符合条件，继续
	}
	
	
	
	b = f2(a);//按第二种方式处理
	t_sum = b[0];
	b.pop_front();
	if(t_sum!=sum)
	{
		if(mx<step){
			mx = step;
		}
	
	}
	else {
		dfs(b,step+1,sum);
	}
	
	b = f3(a);//按第三种方式处理
	t_sum = b[0];
	b.pop_front();
	if(t_sum!=sum)
	{
		if(mx<step){
			mx = step;
		}

	}
	else {
		dfs(b,step+1,sum);
	}
	

}
int main(void)
{
	vector<int> v = {3,2,6,1,4};
	deque<int>d {v.begin(),v.end()};
	dfs(d,0,f1(d)[0]);
	dfs(d,0,f2(d)[0]);
	dfs(d,0,f3(d)[0]);
	cout<<mx;
	
}

520 / 549 个通过的测试用例

借助deque的暴力dfs

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
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N = 2010;
//f(l,r) l与r中间的最大值
int f[N][N];
int dfs(const vector<int>& nums,int l,int r,int target)
{
	if(l>=r) return 1;
	int &t = f[l][r];
	if(t!=-1) return t;
	int res = 1; 
	if(nums[l]+nums[l+1]==target){
		res = max(res,dfs(nums,l+2,r,target)+1);
	}  
	if(nums[r]+nums[r-1]==target){
		res = max(res,dfs(nums,l,r-2,target)+1);
	}
	if(nums[l]+nums[r]==target){
		res = max(res,dfs(nums,l+1,r-1,target)+1);
	}
	t = res;
	return res;
	
}
int main(void)
{
	vector<int> nums = {2,2,3,2,4,2,3,3,1,3};
	memset(f,-1,sizeof f);
	int l = 0,r = nums.size()-1; 
	int res = max(max(dfs(nums,l+2,r,nums[l]+nums[l+1]),dfs(nums,l,r-2,nums[r]+nums[r-1]))
					,dfs(nums,l+1,r-1,nums[l]+nums[r]));
	cout<<res;

}

AC

二分

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
#include<stdio.h>
int left_bound_k(int* nums,int numsSize,int target)
{
	int left = 0 ,right = numsSize;
	while(left<right)
	{
		int mid = left+(right-left)/2;
		if(nums[mid]==target) right = mid;
		else if(nums[mid]>target) right = mid;
		else if(nums[mid]<target) left = mid+1;
	}
	return nums[left]==target?left:-1;
    	
}
int right_bound_k(int* nums,int numsSize,int target)
{
	int left = 0 ,right = numsSize;
	while(left<right)
	{
		int mid = left+(right-left)/2;
		if(nums[mid]==target) left = mid+1;
		else if(nums[mid]>target) right = mid;
		else if(nums[mid]<target) left = mid+1;
	}	
	if (left - 1 < 0 || left - 1 >= nums.size())  return -1;
	return nums[left - 1] == target ? (left - 1) : -1;
}
int left_bound_b(int* nums,int numsSize,int target)
{
	int left = 0 ,right = numsSize-1;
	while(left<=right)
	{
		int mid = left+(right-left)/2;
		if(nums[mid]==target) right = mid-1;
		else if(nums[mid]<target) left = mid+1;
		else if(nums[mid]>target) right= mid-1;
	}	
	if(left==numsSize) return -1;
	return left;
}
int right_bound_b(int* nums,int numsSize,int target)
{
	int left = 0 ,right = numsSize-1;
	while(left<=right)
	{
		int mid = left+(right-left)/2;
		if(nums[mid]==target) left = mid+1;
		else if(nums[mid]>target) right = mid-1;
		else if(nums[mid]<target) left = mid+1;
	}	
	if(left-1<0||left-1>=nums.size()) return -1;
	return ums[left-1]!=target?left-1:-1;
}
int common_merge(int* nums,int numsSize,int target)
{
    int left = 0; 
    int right = numsSize - 1; // 注意
 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target) return mid; 
        else if (nums[mid] < target) left = mid + 1; // 注意
        else if (nums[mid] > target) right = mid - 1; // 注意
    }
    return -1;
} 
 

}

  1. 计算 mid 时需要防止溢出，代码中 left + (right - left) / 2 就和 (left + right) / 2 的结果相同，但是有效防止了 left 和 right 太大，直接相加导致溢出的情况。

  2. 为什么 while 循环的条件中是 <=，而不是 <

    while(l<r) : 初始化r的值 r = nums.size 相当于左闭右开，[left,right) ，right 不能取到初始值

    while(l<=r) : 初始化r的值r = nums.size -1 相当于左闭右闭，[left,right] ,right 可以取到初始的最大值。

  3. 停止搜索的区间？

    找到了目标值的时候可以终止：

    1
    2
    if(nums[mid] == target)
        return mid;

    但如果没找到，就需要 while 循环终止，然后返回 -1。那 while 循环什么时候应该终止？

    ==搜索区间为空的时候应该终止==，意味着你没得找了，就等于没找到嘛。

    • while(left <= right) 的终止条件是 left == right + 1，写成区间的形式就是 [right + 1, right]，或者带个具体的数字进去 [3, 2]，可见这时候区间为空。所以这时候 while 循环终止是正确的，直接返回 -1 即可。
    • while(left < right) 的终止条件是 left == right，写成区间的形式就是 [right, right]，或者带个具体的数字进去 [2, 2]，这时候区间非空，还有一个数 2，但此时 while 循环终止了。也就是说区间 [2, 2] 被漏掉了，索引 2 没有被搜索，如果这时候直接返回 -1 就是错误的。

    当然，如果你非要用 while(left < right) 也可以，我们已经知道了出错的原因，就打个补丁好了：

    1
    2
    3
    4
    5
    6
    //...
    while(left < right) {
        // ...
    }
    return nums[left] == target ? left : -1;//判断漏掉的那个数是不是符合目标值

  4. 为什么 left = mid + 1，right = mid - 1？我看有的代码是 right = mid 或者 left = mid，没有这些加加减减，到底怎么回事，怎么判断？

    答：这也是二分查找的一个难点，不过只要你能理解前面的内容，就能够很容易判断。

    刚才明确了「搜索区间」这个概念：

    • 如果搜索区间是两端都闭的，即 [left, right]。那么当我们发现索引 mid 不是要找的 target 时，下一步当然去搜索区间 [left, mid-1] 或者区间 [mid+1, right]， 因为 mid 已经搜索过，应该从搜索区间中去除。

    • 如果搜索区间左闭右开，即[left, right]，则可以搜索区间[mid+1,right) 和 [left,mid) 。因为右边界不会被搜索到。

      关注点在于 mid 作为左右边界时的变化，即是否有必要+1 -1 。

  5. 为什么求右侧边界最后返回 left - 1 而不像左侧边界的函数，返回 left？而且我觉得这里既然是搜索右侧边界，应该返回 right 才对。

    答：首先，while 循环的终止条件是 left == right，所以 left 和 right 是一样的。

    至于 left 是否要减1，关键在于if (nums[mid] == target) 语句，

    1
    2
    3
    4
    // 增大 left，锁定右侧边界
    if (nums[mid] == target) {
        left = mid + 1;
        // 这样想: mid = left - 1

    因为我们对 left 的更新必须是 left = mid + 1，就是说 while 循环结束时，nums[left] 一定不等于 target 了，而 nums[left-1] 可能是 target。

    至于为什么 left 的更新必须是 left = mid + 1，当然是为了把 nums[mid] 排除出搜索区间，这里就不再赘述

  6. 左闭右闭的时候：循环结束条件相比左闭右开的left == right 变成了 left == right +1 ，即left-1 == right。

    • 求右侧边界的函数条件里，仍然是left = mid + 1 。所以结果 left - 1

    • 求左侧边界的函数条件，是right = mid - 1 ，将 right 转换为 left ，右：

      left - 1 = mid -1 ，即left = mid 。

      所以结果是left

    由上可知，结果取left还是right，其实根据循环条件结束的判断来看，两者可以互相换算，是一样的。

    取left后是否要 - 1，要看nums[mid]==target判断语句的内容，是 left 还是 right。（实际上就是看左闭右开还是左闭右闭，也就是< 还是 <= 。

快来参与讨论吧~