Go Java算法之字符串中第一个唯一字符详解

目录
  • 字符串中第一个唯一字符
  • 方法一：哈希表（Java）
  • 方法二：队列（Go）

字符串中第一个唯一字符

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

  • 示例 1：

输入: s = "leetcode"

输出: 0

  • 示例 2:

输入: s = "loveleetcode"

输出: 2

  • 示例 3:

输入: s = "aabb"

输出: -1

提示:

1 <= s.length <= 105

s 只包含小写字母

方法一：哈希表（Java）

在第一次遍历时，我们使用哈希映射统计出字符串中每个字符出现的次数。

在第二次遍历时，我们只要遍历到了一个只出现一次的字符，那么就返回它的索引，否则在遍历结束后返回 -1。

class Solution {
    public int firstUniqChar(String s) {
        Map<Character, Integer> frequency = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < s.length(); ++i) {
            if (frequency.get(s.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;
    }
}

n：字符串长度

Σ：字符集

时间复杂度：O（n）

空间复杂度：O(∣Σ∣)

方法二：队列（Go）

我们也可以借助队列找到第一个不重复的字符。队列具有「先进先出」的性质，因此很适合用来找出第一个满足某个条件的元素。

具体地，我们使用与方法二相同的哈希映射，并且使用一个额外的队列，按照顺序存储每一个字符以及它们第一次出现的位置。

当我们对字符串进行遍历时，设当前遍历到的字符为 c，如果 c 不在哈希映射中，我们就将 c 与它的索引作为一个二元组放入队尾

否则我们就需要检查队列中的元素是否都满足「只出现一次」的要求，即我们不断地根据哈希映射中存储的值（是否为 -1）选择弹出队首的元素，直到队首元素「真的」只出现了一次或者队列为空。

type pair struct {
    ch  byte
    pos int
}
func firstUniqChar(s string) int {
    n := len(s)
    pos := [26]int{}
    for i := range pos[:] {
        pos[i] = n
    }
    q := []pair{}
    for i := range s {
        ch := s[i] - 'a'
        if pos[ch] == n {
            pos[ch] = i
            q = append(q, pair{ch, i})
        } else {
            pos[ch] = n + 1
            for len(q) > 0 && pos[q[0].ch] == n+1 {
                q = q[1:]
            }
        }
    }
    if len(q) > 0 {
        return q[0].pos
    }
    return -1
}

n：字符串长度

Σ：字符集

时间复杂度：O（n）

空间复杂度：O(∣Σ∣)

以上就是Go Java算法之字符串中第一个唯一字符详解的详细内容，更多关于Go Java算法字符串唯一字符的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Go和Java算法详析之分数到小数

    目录 分数到小数 方法一:模拟竖式计算(Java) 方法一:模拟竖式计算(Go) 总结 分数到小数 给定两个整数,分别表示分数的分子 numerator 和分母 denominator,以 字符串形式返回小数 . 如果小数部分为循环小数,则将循环的部分括在括号内. 如果存在多个答案,只需返回 任意一个 . 对于所有给定的输入,保证 答案字符串的长度小于 104 . 示例 1: 输入:numerator = 1, denominator = 2 输出:"0.5" 示例 2: 输入:num

  • Go Java算法之单词规律示例详解

    目录 单词规律 方法一:哈希表(Java) 方法一:哈希表(GO) 单词规律 给定一种规律 pattern 和一个字符串 s ,判断 s 是否遵循相同的规律. 这里的 遵循 指完全匹配,例如, pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律. 示例1: 输入: pattern = "abba", s = "dog cat cat dog" 输出: true 示例 2: 输入:pattern = "abba"

  • Go Java算法之二叉树的所有路径示例详解

    目录 二叉树的所有路径 方法一:深度优先遍历搜索(Java) 方法二:广度优先遍历(Go) 二叉树的所有路径 给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径. 叶子节点 是指没有子节点的节点. 示例 1: 输入:root = [1,2,3,null,5] 输出:["1->2->5","1->3"] 示例 2: 输入:root = [1] 输出:["1"] 提示: 树中节点的数目在范围 [1,

  • Go Java算法之单词搜索示例详解

    Go Java算法之单词搜索示例详解

    目录 单词搜索 算法:DFS回溯(Java) 算法:DFS回溯(Go) 单词搜索 给定一个 m x n 二维字符网格 board 和一个字符串单词 word .如果 word 存在于网格中,返回 true :否则,返回 false . 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格.同一个单元格内的字母不允许被重复使用. 示例 1: 输入:board = [["A","B","C",&quo

  • Go Java算法之解码方法示例详解

    目录 解码方法 方法一:动态规划(Java) 方法二:动态规划——优化(go) 解码方法 一条包含字母 A-Z 的消息通过以下映射进行了 编码 : 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" 要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法).例如,"11106" 可以映射为: "AAJF" ,将消息分组为 (1 1 1

  • Go Java算法之比较版本号方法详解

    目录 比较版本号 方法一:字符串切割(Java) 方法二:双指针(Go) 比较版本号 给你两个版本号 version1 和 version2 ,请你比较它们. 版本号由一个或多个修订号组成,各修订号由一个 '.' 连接.每个修订号由 多位数字 组成,可能包含 前导零 .每个版本号至少包含一个字符. 修订号从左到右编号,下标从 0 开始,最左边的修订号下标为 0 ,下一个修订号下标为 1 ,以此类推.例如,2.5.33 和 0.1 都是有效的版本号. 比较版本号时,请按从左到右的顺序依次比较它们的

  • Go Java算法之字符串中第一个唯一字符详解

    目录 字符串中第一个唯一字符 方法一:哈希表(Java) 方法二:队列(Go) 字符串中第一个唯一字符 给定一个字符串 s ,找到 它的第一个不重复的字符,并返回它的索引 .如果不存在,则返回 -1 . 示例 1: 输入: s = "leetcode" 输出: 0 示例 2: 输入: s = "loveleetcode" 输出: 2 示例 3: 输入: s = "aabb" 输出: -1 提示: 1 <= s.length <= 10

  • java实现输出字符串中第一个出现不重复的字符详解

    java实现输出字符串中第一个出现不重复的字符详解 比如:输入name输出n,输入teeter输出r,输入namename输出null 具体实现代码如下: import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String str = in.next(); for(int i =0 ; i < str.l

  • python正则表达式从字符串中提取数字的思路详解

    python从字符串中提取数字 使用正则表达式,用法如下: ## 总结 ## ^ 匹配字符串的开始. ## $ 匹配字符串的结尾. ## \b 匹配一个单词的边界. ## \d 匹配任意数字. ## \D 匹配任意非数字字符. ## x? 匹配一个可选的 x 字符 (换言之,它匹配 1 次或者 0 次 x 字符). ## x* 匹配0次或者多次 x 字符. ## x+ 匹配1次或者多次 x 字符. ## x{n,m} 匹配 x 字符,至少 n 次,至多 m 次. ## (a|b|c) 要么匹配

  • Java list与set中contains()方法效率案例详解

    list.contains(o) :遍历集合所有元素,用每个元素和传入的元素进行 equals 比较,如果集合元素有 n 个,则会比较 n 次,所以时间复杂度为 O(n) .方法源码如下: // ArrayList 中的方法 public boolean contains(Object o) { return indexOf(o) >= 0; } public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size;

  • 用Java正则去掉字符串中重复出现的字符

    String str = "abcdeabcdeabcdeaaaaaadddddceeeeabcccccccacadaeec"; str = str.replaceAll(reg, ""); System.out.println(str); str = str.replaceAll("(?s)(.)(?=.*\\1)", ""); (?s)(.)(?=.*\1) (?s) 开启单行模式 DOTALL 让. 号匹配任意字符 (.

  • Java类继承关系中的初始化顺序实例详解

    Java类继承关系中的初始化顺序实例详解

    本文实例讲述了Java类继承关系中的初始化顺序.分享给大家供大家参考,具体如下: Java类初始化的顺序经常让人犯迷糊,现在本文尝试着从JVM的角度,对Java非继承和继承关系中类的初始化顺序进行试验,尝试给出JVM角度的解释. 非继承关系中的初始化顺序 对于非继承关系,主类InitialOrderWithoutExtend中包含了静态成员变量(类变量)SampleClass 类的一个实例,普通成员变量SampleClass 类的2个实例(在程序中的顺序不一样)以及一个静态代码块,其中静态代码块

  • java后台如何利用Pattern提取所需字符详解

    目录 写在处理问题的前面 遇到的问题,如何提取? 1.首先进行简单测试 2.项目内容测试 3.进行实操 附:JAVA Pattern正则获取大括号中内容 总结 写在处理问题的前面 由于项目功能迭代,导致原来的页面当中ID命名规则,与当前命名规则不同(ps:既然要用到原来的东西,为什么在设计的时候没有考虑到兼容的问题,无语),所以需要将原来的所有ID提取出来. 遇到的问题,如何提取? 查找了许多方法之后,感觉使用Pattern提取比较符合需求.于是开始尝试. 1.首先进行简单测试 String s

  • Java正则环视和反向引用功能与用法详解

    本文实例讲述了Java正则环视和反向引用功能与用法.分享给大家供大家参考,具体如下: 环视 1.环视概念 环视,又称为零宽断言,简称断言. 环视强调位置(前面或后面),必须匹配环视表达式,才能匹配成功. 环视可认为是虚拟加入到它所在位置的附加判断条件,并不消耗正则的匹配字符. 2.环视基础表达式 (?=Expression) 顺序肯定环视,表示所在位置右侧能够匹配Expression (?!Expression) 顺序否定环视,表示所在位置右侧不能匹配Expression (?<=Express

  • JavaScript实现找出字符串中第一个不重复的字符

    此算法仅供参考,小菜基本不懂高深的算法,只能用最朴实的思想去表达. //找出字符串中第一个不重复的字符 // firstUniqueChar("vdctdvc"); --> t function firstUniqueChar(str){ var str = str || "", i = 0, k = "", _char = "", charMap = {}, result = {name: "",i

  • Java简单统计字符串中汉字，英文字母及数字数量的方法

    本文实例讲述了Java简单统计字符串中汉字,英文字母及数字数量的方法.分享给大家供大家参考,具体如下: package org.zhy.demo.algorithm; /** * 有一个字符串,其中包含中文字符.英文字符和数字字符,请统计和打印出各个字符的个数 * * @author Administrator * */ public class Str { public static void main(String[] args) { String str = "adasfAAADFD阿萨德

随机推荐