目錄

一、iota函數(shù)

1. 函數(shù)解析

?①? 迭代器類型(補(bǔ)充)

② 頭文件

③? 參數(shù)

2. 函數(shù)用途與實(shí)例

二、sort函數(shù)

1、 函數(shù)解讀

2、實(shí)現(xiàn)倒序排列

2.1 greater?與 less 模板參數(shù)

2.2??lambda表達(dá)式

三、下標(biāo)綁定排序（zip） --- 833.字符串中的查找與替換

---

一、iota函數(shù)

1. 函數(shù)解析

①? 迭代器類型(補(bǔ)充)

ForwardIterator ：ForwardIterator為正向迭代器，它只支持加操作不支持減操作；

② 頭文件

#include <numeric>      // std::iota

③? 參數(shù)

first：第一個(gè)參數(shù)是指向區(qū)間中的第一個(gè)位置的迭代器

last：第二個(gè)參數(shù)是指向區(qū)間最后一個(gè)位置的后一個(gè)位置的迭代器，也就一個(gè)左閉右開的區(qū)間

val：第三個(gè)參數(shù)傳入?yún)^(qū)間第一個(gè)位置的值?

2. 函數(shù)用途與實(shí)例

將首元素為val，公差為1的連續(xù)遞增序列依次分配給區(qū)間 [first, last)?

#include<iostream>
#include<vector>
#include <numeric>      // std::iota
int main()
{
	std::vector<int> v(10);
	//分別將 0 1 2 3 4 5 6 7 8 9 填入?yún)^(qū)間 [ v.begin(), v.end() )
	std::iota(v.begin(), v.end(), 0);
	for (auto x : v) std::cout << x << ' ';
	std::cout << std::endl;

	int arr[10];
	std::iota(arr, arr + 10, 0);
	for (auto x : arr) std::cout << x << ' ';
	return 0;
}

二、sort函數(shù)

?1、 函數(shù)解讀

① 函數(shù)實(shí)現(xiàn)了默認(rèn)升序對(duì)一個(gè)左閉右開的區(qū)間 [first, last) 進(jìn)行排序

② 可通過仿函數(shù)重載operator< 或operator> 實(shí)現(xiàn)自定義數(shù)據(jù)排序

③ sort函數(shù)底層實(shí)現(xiàn)為快速排序，即為不穩(wěn)定排序，等效元素相對(duì)位置可能會(huì)發(fā)生改變，若要實(shí)現(xiàn)穩(wěn)定排序，可以使用stable_sort函數(shù)

2、實(shí)現(xiàn)倒序排列

2.1 greater?與 less 模板參數(shù)

#include<iostream>
#include<vector>
#include<algorithm>     //sort函數(shù)的頭文件
#include<functional>    //greater算法的頭文件
int main()
{
	std::vector<int> v = {3, 2, 6, 1, 8, 5, 2, 6};
	std::sort(v.begin(), v.end(), std::greater<int>());
	for (auto x : v) std::cout << x << ' ';
	return 0;
}

2.2??lambda表達(dá)式

#include<iostream>
#include<vector>
#include<algorithm>     //sort函數(shù)的頭文件
#include <numeric> 

using namespace std;
int main() {
	vector<int> id(10);
	// 0 1 2 3 4 5 6 7 8 9
	iota(id.begin(), id.end(), 0);
	// 9 8 7 6 5 4 3 2 1 0
	sort(id.begin(), id.end(), [&](int i, int j) {return id[i] > id[j]; });
	for (auto x : id) cout << x;
	return 0;
}

三、下標(biāo)綁定排序（zip） --- 833.字符串中的查找與替換

你會(huì)得到一個(gè)字符串?s?(索引從 0 開始)，你必須對(duì)它執(zhí)行?k?個(gè)替換操作。替換操作以三個(gè)長度均為?k?的并行數(shù)組給出：indices,?sources,??targets。

要完成第?i?個(gè)替換操作:

1. 檢查?子字符串??sources[i]?是否出現(xiàn)在?原字符串?s?的索引?indices[i]?處。
2. 如果沒有出現(xiàn)，?什么也不做?。
3. 如果出現(xiàn)，則用?targets[i]?替換?該子字符串。

例如，如果?s = "abcd"?，?indices[i] = 0?,?sources[i] = "ab"，?targets[i] = "eee"?，那么替換的結(jié)果將是?"eeecd"?。

所有替換操作必須?同時(shí)?發(fā)生，這意味著替換操作不應(yīng)該影響彼此的索引。測試用例保證元素間不會(huì)重疊?。

• 例如，一個(gè)?s = "abc"?，??indices = [0,1]?，?sources = ["ab"，"bc"]?的測試用例將不會(huì)生成，因?yàn)?"ab"?和?"bc"?替換重疊。

在對(duì)?s?執(zhí)行所有替換操作后返回?結(jié)果字符串?。

子字符串?是字符串中連續(xù)的字符序列。

示例 1：

輸入：s = "abcd", indices = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
輸出："eeebffff"
解釋：
"a" 從 s 中的索引 0 開始，所以它被替換為 "eee"。
"cd" 從 s 中的索引 2 開始，所以它被替換為 "ffff"。

解題思路：由于前面的字符替換可能使字符串下標(biāo)發(fā)生改變，所以考慮從后往前替換字符串s，即從大到小遍歷indices的數(shù)，并將下標(biāo)從indices[i]開始長度為sources[i].size()的s的字串與sources[i]比較，若相等，則特?fù)Q成targets[i]

法一? 下標(biāo)數(shù)組：（由于沒有考慮到indices數(shù)組元素重復(fù)的問題，現(xiàn)在這個(gè)方法已經(jīng)不行了，如果給大家?guī)聿槐?，請諒解?/strong>

class Solution {
public:
    string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {
        int n = indices.size();
 
        vector<int> id(n);
        iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&](int i, int j)  {return indices[i] > indices[j];});
        vector<int> used(s.size(), 0);
        for (auto i : id) {    //i為indices倒序之后的下標(biāo)
            int j = indices[i], len = sources[i].size();
            if (s.substr(j, len) == sources[i] && !used[j]) {
                s.replace(j, len, targets[i]);
                used[j] = true;
            }
        }
        return s;
    }
};

class Solution {
public:
    string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {
        int n = indices.size();
        vector<tuple<int, string, string>> zip;
        for (int i = 0; i < n; i++) zip.push_back({indices[i], sources[i], targets[i]});
        sort(zip.begin(), zip.end(), greater<tuple<int, string, string>>());
        
        for (auto& [i, source, target] : zip) {    
            int len = source.length();
            if (s.substr(i, len) == source) {
                s.replace(i, len, target);
            }
        }
        return s;
    }
};