精华内容
下载资源
问答
  • LeetCode 1202 交换字符串中的元素

    千次阅读 2021-01-18 10:52:01
    LeetCode 1202 交换字符串中的元素 题目链接 给你一个字符串 s,以及该字符串中的一些「索引对」数组 pairs,其中 pairs[i] = [a, b] 表示字符串中的两个索引(编号从 0 开始)。 你可以 任意多次交换 在 pairs 中...

    LeetCode 1202 交换字符串中的元素

    题目链接

    给你一个字符串 s,以及该字符串中的一些「索引对」数组 pairs,其中 pairs[i] = [a, b] 表示字符串中的两个索引(编号从 0 开始)。

    你可以 任意多次交换 在 pairs 中任意一对索引处的字符。

    返回在经过若干次交换后,s 可以变成的按字典序最小的字符串。

    示例 1:

    输入:s = "dcab", pairs = [[0,3],[1,2]]
    输出:"bacd"
    解释: 
    交换 s[0] 和 s[3], s = "bcad"
    交换 s[1] 和 s[2], s = "bacd"
    

    示例 2:

    输入:s = "dcab", pairs = [[0,3],[1,2],[0,2]]
    输出:"abcd"
    解释:
    交换 s[0] 和 s[3], s = "bcad"
    交换 s[0] 和 s[2], s = "acbd"
    交换 s[1] 和 s[2], s = "abcd"
    

    示例 3:

    输入:s = "cba", pairs = [[0,1],[1,2]]
    输出:"abc"
    解释:
    交换 s[0] 和 s[1], s = "bca"
    交换 s[1] 和 s[2], s = "bac"
    交换 s[0] 和 s[1], s = "abc"
    

    DFS+排序~
    可以把每一个索引对当作两个点连一条边,这样就可以用题目所给条件建图,我们只需要遍历所有联通块,显然对某个联通块的所有字符,可以任意交换位置,即只需要记录此联通块包含的所有字符和所有位置,然后分别排序再一一对应即可,AC代码如下:

    class Solution {
    public:
        static const int N = 1e5 + 5;
        vector<int> G[N], pos;
        vector<char> v;
        map<int, char> mp;
        int vis[N];
    
        void dfs(int x) {
            vis[x] = 1;
            v.push_back(mp[x]);
            pos.push_back(x);
            for (auto y:G[x]) {
                if (!vis[y]) dfs(y);
            }
        }
    
        string smallestStringWithSwaps(string s, vector<vector<int>> &pairs) {
            string ans;
            ans.resize(s.size());
            for (int i = 0; i < s.size(); i++) mp[i] = s[i];
            for (auto i:pairs) G[i[0]].push_back(i[1]), G[i[1]].push_back(i[0]);
            for (int i = 0; i < s.size(); i++) {
                v.clear();
                pos.clear();
                if (!vis[i]) {
                    dfs(i);
                    sort(v.begin(), v.end());
                    sort(pos.begin(), pos.end());
                    for (int j = 0; j < v.size(); j++) ans[pos[j]] = v[j];
                }
            }
            return ans;
        }
    };
    
    展开全文
  • python 替换字符串中的元素

    千次阅读 2020-07-03 09:41:31
    python 替换字符串中的元素 def str_replace(old_str,old,new):     """     在 old_str 字符串中,把 old 替换成 new     :param old_str:原字符串   &...

    python 替换字符串中的元素

    def str_replace(old_str,old,new):
        """
        在 old_str 字符串中,把 old 替换成 new
        :param old_str:原字符串
        :param old:被替换的字符
        :param new:替换后的字符
        :return:替换后的字符串
        """
        new_str = old_str.replace(old,new)
        # print("new_str:",new_str)
        return new_str
    if __name__ == '__main__':
        old_str = '2020年7月1日'
        old = "2020"
        new = "二零二零"
        new_str = str_replace(old_str, old, new)
    
    展开全文
  • 并查集解决1202. 交换字符串中的元素

    1202. 交换字符串中的元素

    给你一个字符串 s,以及该字符串中的一些「索引对」数组 pairs,其中 pairs[i] = [a, b] 表示字符串中的两个索引(编号从 0 开始)。

    你可以 任意多次交换 在 pairs 中任意一对索引处的字符。

    返回在经过若干次交换后,s 可以变成的按字典序最小的字符串。

    示例 1:
    输入:s = “dcab”, pairs = [[0,3],[1,2]]
    输出:“bacd”
    解释:
    交换 s[0] 和 s[3], s = “bcad”
    交换 s[1] 和 s[2], s = “bacd”

    示例 2:
    输入:s = “dcab”, pairs = [[0,3],[1,2],[0,2]]
    输出:“abcd”
    解释:
    交换 s[0] 和 s[3], s = “bcad”
    交换 s[0] 和 s[2], s = “acbd”
    交换 s[1] 和 s[2], s = “abcd”

    示例 3:
    输入:s = “cba”, pairs = [[0,1],[1,2]]
    输出:“abc”
    解释:
    交换 s[0] 和 s[1], s = “bca”
    交换 s[1] 和 s[2], s = “bac”
    交换 s[0] 和 s[1], s = “abc”

    提示:
    1 <= s.length <= 10^5
    0 <= pairs.length <= 10^5
    0 <= pairs[i][0], pairs[i][1] < s.length
    s 中只含有小写英文字母

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/smallest-string-with-swaps
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    代码(含注释题解)

    class UnionFind {//并查集
    private:
        int size;
        vector<int> parent;
        vector<int> rank;
    
    public:
        UnionFind(int _size):size(_size) {
            rank.resize(size, 0);
            parent.resize(size);
            for(int i = 0; i < size; i++) {
                parent[i] = i;
            }
        }
    
        int find(int x) {
            int root = x;
            while (root != parent[root]) {
                root = parent[root];
            }
    
            while(x != root) {//路径压缩
                int tmp = parent[x];
                parent[x] = root;
                x = tmp;
            }
            return root;
        }
    
        void unionSetMerge(int x, int y) {
            int px = find(x);
            int py = find(y);
            if(px == py) {
                return;
            }
    
            if(rank[px] < rank[py]) {
                swap(px, py);
            }
            parent[py] = px;
    
            //按秩合并
            if (rank[px] == rank[py]) {
                rank[px] += 1;
            }
        }
    };
    
    class Solution {
    public:
        string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
            if(pairs.size() == 0) {
                return s;
            }
    
            int length = s.length();
            UnionFind unionFind(length);
            for(auto& pair: pairs) {
                unionFind.unionSetMerge(pair[0], pair[1]);
            }//基于并查集将字符的**索引值**进行集合划分
    
            unordered_map<int, vector<int>> connectedComponents;
            for(int i = 0; i < length; i++) {
                connectedComponents[unionFind.find(i)].emplace_back(s[i]);
            }//建立索引值所在的集合标识与字符之间的哈希映射
    
            for(auto& [key, arr]: connectedComponents) {
                sort(arr.begin(), arr.end(), greater<int>());//从大到小排序
            }//对同一集合内的字符进行排序(这里从大到小,然后逆序输出同一集合内的字符)
            for(int i = 0; i < length; i++) {
                int root = unionFind.find(i);
                //根据当前的索引值,找到所在的集合,然后在集合内找到字典序最小的字符进行替换
                s[i] = connectedComponents[root].back();
                connectedComponents[root].pop_back();
                //字符替换后,集合将删除相应的字符
            }
            return s;//最后将得到排序后的字符串
        }
    };
    
    展开全文
  • LeetCode 1202. 交换字符串中的元素(并查集)

    千次阅读 多人点赞 2020-05-10 21:18:05
    给你一个字符串 s,以及该字符串中的一些「索引对」数组 pairs,其中 pairs[i] = [a, b] 表示字符串中的两个索引(编号从 0 开始)。 你可以 任意多次交换 在 pairs 中任意一对索引处的字符。 返回在经过若干次交换...

    1. 题目

    给你一个字符串 s,以及该字符串中的一些「索引对」数组 pairs,其中 pairs[i] = [a, b] 表示字符串中的两个索引(编号从 0 开始)。

    你可以 任意多次交换 在 pairs 中任意一对索引处的字符。

    返回在经过若干次交换后,s 可以变成的按字典序最小的字符串。

    示例 1:
    输入:s = "dcab", pairs = [[0,3],[1,2]]
    输出:"bacd"
    解释: 
    交换 s[0] 和 s[3], s = "bcad"
    交换 s[1] 和 s[2], s = "bacd"
    
    示例 2:
    输入:s = "dcab", pairs = [[0,3],[1,2],[0,2]]
    输出:"abcd"
    解释:
    交换 s[0] 和 s[3], s = "bcad"
    交换 s[0] 和 s[2], s = "acbd"
    交换 s[1] 和 s[2], s = "abcd"
    
    示例 3:
    输入:s = "cba", pairs = [[0,1],[1,2]]
    输出:"abc"
    解释:
    交换 s[0] 和 s[1], s = "bca"
    交换 s[1] 和 s[2], s = "bac"
    交换 s[0] 和 s[1], s = "abc"
     
    提示:
    1 <= s.length <= 10^5
    0 <= pairs.length <= 10^5
    0 <= pairs[i][0], pairs[i][1] < s.length
    s 中只含有小写英文字母
    

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/smallest-string-with-swaps
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    2. 解题

    参考:数据结构–并查集(Disjoint-Set)

    相关题目:
    LeetCode 959. 由斜杠划分区域(并查集)
    程序员面试金典 - 面试题 17.07. 婴儿名字(并查集)

    • 把同一个集合中的排序,然后放回去
    class dsu
    {
    public:
    	vector<int> f;
    	dsu(int n)
    	{
    		f.resize(n);
    		for(int i = 0; i < n; ++i)
    			f[i] = i;
    	}
    	int find(int x)
    	{
    		if(x == f[x])
    			return x;
    		return f[x] = find(f[x]);
    	}
    	void merge(int x, int y)
    	{
    		int fx = find(x), fy = find(y);
            f[fx] = fy;
    	}
    };
    class Solution {
    public:
        string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        	int n = s.size(), i, fatherid;
        	dsu uni(n);
        	for(i = 0; i < pairs.size(); ++i)
                uni.merge(pairs[i][0],pairs[i][1]);
        	unordered_map<int,multiset<char>> m;
        	for(i = 0; i < n; ++i)
        	{
                // fatherid = uni.f[i];//错误解,使用之前必须先压缩一次
        		fatherid = uni.find(i);
        		m[fatherid].insert(s[i]);
        	}
        	for(i = 0; i < n; ++i)
        	{
        		// fatherid = uni.f[i];//这样也行,上面已经压缩
                fatherid = uni.find(i);
        		s[i] = *m[fatherid].begin();
        		m[fatherid].erase(m[fatherid].begin());
        	}
        	return s;
        }
    };
    

    352 ms 46.6 MB

    展开全文
  • 比如list元素是123a,456b,789c 想取出含有a的元素,怎么做谢谢了
  • 就是比如给定一个字符串比如“abcdrtyyacde”我们需要判断在这个字符串里是否出现重复的字符首先我们肯定会想到用两个循环,外层循环遍历串中的每一个字符,然后再通过内层循环从每一层外层循环后逐次判断比较是否有...
  • 给你一个字符串 s,以及该字符串中的一些「索引对」数组 pairs,其中 pairs[i] = [a, b] 表示字符串中的两个索引(编号从 0 开始)。 你可以 任意多次交换 在 pairs 中任意一对索引处的字符。 返回在经过若干次交换...
  • 删除字符串中某个元素

    千次阅读 2020-04-15 16:08:57
    删除字符串中某个元素 第一种: Replace()语法 str.replace(old, new, max) ...返回字符串中的 old(旧字符串) 替换成 new(新字符串)后生成的新字符串,如果指定第三个参数max,则替换不超过 max 次。 例子 去除...
  • 统计字符串中元素的个数

    千次阅读 2019-06-19 23:34:38
    d = 'abcdakkawu' l = {} # 创建一个空字典,键为元素,值为该元素出现的次数 for i in set(d): # 通过集合去重,知道... l[i] = d.count(i) # 添加字典,键为元素,值为该元素字符串中的个数 print(l) ...
  • 统计字符串中重复元素出现次数

    千次阅读 2019-04-24 13:26:28
    首先输入一个字符串,然后使用toCharArray()方法将其转换成字符数组,后遍历数组,创建HashMap集合存放字符和过元素出现次数、、、 public class TestDemo { public static void main(String[] args) { ...
  • 1.将字符串中所有重复元素的字符删除,只留下出现一次字符 C语言是实现这个算法过程有很多,比如说暴力拆解,新申请数组等等 今天小编给大家主要说说如何新申请数组简单理解这个算法 首先这个数组长度是不确定...
  • # 内含分隔符的字符串 str1 = 'a,s,d,f,g,h,d,f' sep = ',' list1 = set(str1.spilt(sep) str2 = sep.join(str2) print(type(str2), str2)  
  • Java删除输入的字符串中重复的元素使用数组的相关操作删除所输入的字符串中的重复元素代码分析 使用数组的相关操作删除所输入的字符串中的重复元素 在学习数组的相关知识后我开始尝试写一点有趣的东西来巩固自己学习...
  • 查询字符串中元素出现次数 str1 = input("请输入字符串:") list1 = [] for i in str1: list1.append(i) d = {} for k in list1: for v in k: if v in d: d[v] += 1 else: d[v] = 1 print(d)
  • 如有个字段用来存储多个用户 ID,并且是以逗号分隔,例:1,2,3,现要移除指定某个 ID 3. 核心代码 /* * @ClassName Test * @Desc TODO 移除指定用户 ID * @Date 2019/8/31 14:58 * @Version 1.0 ...
  • 统计String每个单词出现...输入描述:输入一个字符串,例如:“a b A v” 输出描述: v:1 :3 b:1 a:2 def countEach(strs) : dic = {} strs = strs.lower() lens = len(strs) i = 0 while i < lens : if...
  • public static void main(String[] args) {... * 在当前字符串中,用后面替换掉字符串中所有出现前面,返回新字符串 */ String replace = str.replace(",", "@"); System.out.println(replace); Sys
  • python统计字符串中某个元素的个数

    千次阅读 2018-12-16 20:16:35
  • * 现在有两个用户输入的字符串,将这两个字符串中重复的元素取出来赋给另一个字符串 * @author 万星明 * @version 1.0 * @time */ public class Work7 { static Scanner sc = new Scanner(System.in); public...
  • json字符串中数组元素获取

    千次阅读 2018-07-16 09:14:04
    2.创建字符串的实体类(以下仅创建其中某一个属性实体类) import java.util.List; public class TestVo { private List<Data> errorMessages; public List<Data> getErrorMessages() { return ...
  • python 对字符串list中的元素进行排序

    千次阅读 2020-12-02 16:17:59
    python 对字符串list中的元素进行排序引言利用`sort() 函数`对list进行排序利用`sorted() 函数`对list进行排序`sorted()函数`的可迭代对象iterable为字典时字典 in 操作符按照字符串中的数字的大小进行排序 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 33,335
精华内容 13,334
关键字:

字符串中的元素