C++实现LeetCode(49.群组错位词)

[LeetCode] 49. Group Anagrams 群组错位词

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]

Note:

  • All inputs will be in lowercase.
  • The order of your output does not matter.

这道题让我们群组给定字符串集中所有的错位词，所谓的错位词就是两个字符串中字母出现的次数都一样，只是位置不同，比如 abc，bac, cba 等它们就互为错位词，那么如何判断两者是否是错位词呢，可以发现如果把错位词的字符顺序重新排列，那么会得到相同的结果，所以重新排序是判断是否互为错位词的方法，由于错位词重新排序后都会得到相同的字符串，以此作为 key，将所有错位词都保存到字符串数组中，建立 key 和当前的不同的错位词集合个数之间的映射，这里之所以没有建立 key 和其隶属的错位词集合之间的映射，是用了一个小 trick，从而避免了最后再将 HashMap 中的集合拷贝到结果 res 中。当检测到当前的单词不在 HashMap 中，此时知道这个单词将属于一个新的错位词集合，所以将其映射为当前的错位词集合的个数，然后在 res 中新增一个空集合，这样就可以通过其映射值，直接找到新的错位词集合的位置，从而将新的单词存入结果 res 中，参见代码如下：

解法一：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string, int> m;
        for (string str : strs) {
            string t = str;
            sort(t.begin(), t.end());
            if (!m.count(t)) {
                m[t] = res.size();
                res.push_back({});
            }
            res[m[t]].push_back(str);
        }
        return res;
    }
};

下面这种解法没有用到排序，用一个大小为 26 的 int 数组来统计每个单词中字符出现的次数，然后将 int 数组转为一个唯一的字符串，跟字符串数组进行映射，这样就不用给字符串排序了，参见代码如下：

解法二：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string, vector<string>> m;
        for (string str : strs) {
            vector<int> cnt(26);
            string t;
            for (char c : str) ++cnt[c - 'a'];
            for (int i = 0; i < 26; ++i) {
                if (cnt[i] == 0) continue;
                t += string(1, i + 'a') + to_string(cnt[i]);
            }
            m[t].push_back(str);
        }
        for (auto a : m) {
            res.push_back(a.second);
        }
        return res;
    }
};

到此这篇关于C++实现LeetCode(49.群组错位词)的文章就介绍到这了,更多相关C++实现群组错位词内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(78.子集合)

    [LeetCode] 78. Subsets 子集合 Given a set of distinct integers, S, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example, If S = [1,2,3], a solution is:

  • C++实现LeetCode(47.全排列之二)

    [LeetCode] 47. Permutations II 全排列之二 Given a collection of numbers that might contain duplicates, return all possible unique permutations. Example: Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ] 这道题是之前那道 Permutations 的延伸,由于输入数组有可能出现重复数字,如果按照之前的

  • C++实现LeetCode(40.组合之和之二)

    [LeetCode] 40. Combination Sum II 组合之和之二 Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. Each number in candidates may only be u

  • C++实现LeetCode(144.二叉树的先序遍历)

    [LeetCode] 144. Binary Tree Preorder Traversal 二叉树的先序遍历 Given a binary tree, return the preorder traversal of its nodes' values. Example: Input:  [1,null,2,3] 1 \ 2 / 3 Output:  [1,2,3] Follow up: Recursive solution is trivial, could you do it iterat

  • C++实现LeetCode(41.首个缺失的正数)

    [LeetCode] 41. First Missing Positive 首个缺失的正数 Given an unsorted integer array, find the smallest missing positive integer. Example 1: Input: [1,2,0] Output: 3 Example 2: Input: [3,4,-1,1] Output: 2 Example 3: Input: [7,8,9,11,12] Output: 1 Note: Your

  • C++实现LeetCode(90.子集合之二)

    [LeetCode] 90. Subsets II 子集合之二 Given a collection of integers that might contain duplicates, S, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example

  • C++实现LeetCode(94.二叉树的中序遍历)

    [LeetCode] 94. Binary Tree Inorder Traversal 二叉树的中序遍历 Given a binary tree, return the inorder traversal of its nodes' values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] Follow up: Recursive solution is trivial, could you do it iteratively

  • C++实现LeetCode(112.二叉树的路径和)

    [LeetCode] 112. Path Sum 二叉树的路径和 Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Note: A leaf is a node with no children. Example: Given the below bi

  • C++实现LeetCode(49.群组错位词)

    [LeetCode] 49. Group Anagrams 群组错位词 Given an array of strings, group anagrams together. Example: Input: ["eat", "tea", "tan", "ate", "nat", "bat"], Output: [ ["ate","eat",&quo

  • 使用Python微信库itchat获得好友和群组已撤回的消息

    具体代码如下所述: #coding=utf-8 import itchat from itchat.content import TEXT from itchat.content import * import sys import time import re import os msg_information = {} face_bug=None #针对表情包的内容 # 这里的TEXT表示如果有人发送文本消息() # TEXT 文本 文本内容(文字消息) # MAP 地图 位置文本(位置分享

  • 使用python3调用wxpy模块监控linux日志并定时发送消息给群组或好友

    使用python3调用wxpy模块,监控linux日志并定时发送消息给群组或好友,具体代码如下所示: #!/usr/bin/env python3 # -*- coding: utf-8 -*- from __future__ import unicode_literals from threading import Timer from wxpy import * import requests import subprocess import time from PIL import Ima

  • Linux文件权限与群组修改命令详解

    Linux文件权限与群组修改命令详解

    在Linux中,一切皆为文件(目录也是文件),每个文件对用户具有可读(read).可写(write).可执行(execute)权限.目录的执行操作表示是否有权限进入该目录,文件的可执行表示是否可以运行该文件.文件都会从属于一个用户和一个用户组,每个文件针对文件的拥有者.所属组以及其他用户组具有特定的权限. 如上图,除去第一个表示文件类型的字符外,后面的字符均以三个为一组,是『rwx』 的三个参数的组合.[ r ]代表可读(read).[ w ]代表可写(write).[ x ]代表可执行(exe

  • Android实现IM多人员组合的群组头像

    Android实现IM多人员组合的群组头像

    说明: 此头像类似微信群组头像,整个头像由组内前N位人员的头像组合而成,可用网络或本地图片进行组合,最终显示为一个头像整体,看效果图: 一.自定义整体头像的ViewGroup,计算并保存宽高(重写onMeasure): @Override protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) { mWidth = getWidth(widthMeasureSpec); mHeight = getHeight(h

  • javascript中layim之查找好友查找群组

    javascript中layim之查找好友查找群组

    目前layui官方暂没提供layim查找好友页面的结构与样式,我个人好奇心极强,自己弄了一套,现在上传与大家分享.小生不是做前端的,有些方面不够全面,请各位大神指点一二! 先呈上效果图压压惊 Layim查找好友.查找群组.添加好友.加入群组: 附上源码,积分下载 一.绑定用户成员列表 /** html代码 */ <textarea title="用户模版" id="LAY_Friend" style="display:none;">

  • Python使用wxpy模块实现微信两两群组消息同步功能(推荐)

    Python使用wxpy模块实现微信两两群组消息同步功能(推荐)

    wxpy也是一个python的模块,利用它我们可以做很多有意思的事情,今天通过本文给大家介绍Python使用wxpy模块实现微信两两群组消息同步功能. 安装模块: pip install wxpy 注意:需要同步的微信群需要保存到通讯录中 以下是自己闲来无事写的代码,暂时还存在以下几个问题,有能优化的大佬可以讨论下: 1.暂时同步不了大文件,测试发现超过40M的文件无法同步: 2.频发发送消息时可能导致有的消息丢失: 3.项目不稳定,有时会掉线,脚本需要重启后重新登录微信 直接上代码 impor

  • go mod 使用私有gitlab群组的解决方案

    由于go对私有gitlab的仓库支持不好,得使用下面这些步骤 设置git使用 ssh协议 git config --global url."git@gitlab.com:".insteadOf https://gitlab.com/ 添加ssh key 到gitlab ssh-keygen 会生成 id_rsa.pub cat ~/.ssh/id_rsa.pub 粘贴到gitlab 右上角头像 Setting -> SSH keys,或者打开链接https://gitlab.co

  • SQL实现LeetCode(196.删除重复邮箱)

    [LeetCode] 196.Delete Duplicate Emails 删除重复邮箱 Write a SQL query to delete all duplicate email entries in a table named Person, keeping only unique emails based on its smallest Id. +----+------------------+ | Id | Email            | +----+------------

  • python实现简单聊天应用 python群聊和点对点均实现

    python实现简单聊天应用 python群聊和点对点均实现

    后续代码更新和功能添加会提交到个人github主页,有兴趣可以一起来完善! 如果只是拿过去运行看结果,请注意平台相关性以及python版本号,本示例开发运行平台为win7x86_64 pycharm community,python版本号为3.5!!! TALK IS CHEAP, SHOW YOU MY CODE: 客户端 #coding:utf-8 ''' file:client.py.py date:2017/9/11 11:01 author:lockey email:lockey@12

随机推荐