剑指Offer-第一个只出现一次的字符位置

题目描述

在一个字符串(1<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置

思路

思路一:

使用整型数组对出现次数进行统计。

思路二:

使用BitSet对出现次数进行统计。 0,1,更多

代码实现

package String;

import java.util.BitSet;

/**
 * 第一个只出现一次的字符位置
 * 在一个字符串(1<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置
 */
public class Solution51 {
    public static void main(String[] args) {
        Solution51 solution51 = new Solution51();
        String str = "eabbaecdffd";
        System.out.println(solution51.FirstNotRepeatingChar_2(str));
    }

    /**
     * 使用BitSet对出现次数进行统计    0,1,更多
     * 对应ASCII码表的256个字符
     *
     * @param str
     * @return
     */
    public int FirstNotRepeatingChar_2(String str) {
        BitSet bs1 = new BitSet(256);
        BitSet bs2 = new BitSet(256);
        for (char c : str.toCharArray()) {
            if (!bs1.get(c) && !bs2.get(c)) {
                bs1.set(c);     // 0 0
            } else if (bs1.get(c) && !bs2.get(c)) {
                bs2.set(c); // 0 1
            }
        }
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (bs1.get(c) && !bs2.get(c))
                return i;
        }
        return -1;
    }

    /**
     * 使用整型数组对出现次数进行统计
     * 对应ASCII码表的256个字符
     * 数组的index就是字符, 值为字符出现的次数
     *
     * @param str
     * @return
     */
    public int FirstNotRepeatingChar(String str) {
        int[] cnts = new int[256];
        for (int i = 0; i < str.length(); i++) cnts[str.charAt(i)]++;
        for (int i = 0; i < str.length(); i++) if (cnts[str.charAt(i)] == 1) return i;
        return -1;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏积累沉淀

必须掌握的八种排序(3-4)--简单选择排序,堆排序

3、简单选择排序 (1)基本思想:在要排序的一组数中,选出最小的一个数与第一个位置的数交换; 然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第...

22590
来自专栏小樱的经验随笔

【Java数据结构学习笔记之一】线性表的存储结构及其代码实现

应用程序后在那个的数据大致有四种基本的逻辑结构: 集合:数据元素之间只有"同属于一个集合"的关系 线性结构:数据元素之间存在一个对一个的关系 树形结构:数...

32150
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java提高十七】Set接口集合详解

三、Set接口 Set是一种不包括重复元素的Collection。它维持它自己的内部排序,所以随机访问没有任何意义。与List一样,它同样运行nu...

37990
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-18(02)总结Map,HashMap,HashMap与Hashtable区别,Collections工具类

(8)Hashtable和HashMap的区别? package cn.itcast_07; import java.util.Hashtable; /* *...

31250
来自专栏用户3030674的专栏

java类集框架(ArrayList,LinkedList,Vector区别)

主要分三类:集合(set)、列表(List)、映射(Map) 1.集合:没有重复对象,没有特定排序方式 2.列表:对象按索引位置排序,可以有重复对象 3.映射...

29420
来自专栏nnngu

算法06 五大查找之:二分查找

二分查找属于顺序表查找,二分查找也称为折半查找。二分查找的时间复杂度为O(log2n)   1、二分查找的定义 什么是二分查找呢?二分查找的基本思想是:在有序表...

35480
来自专栏好好学java的技术栈

”365算法每日学计划”:02打卡-线性表(赠书活动第①期预告)

14130
来自专栏一英里广度一英寸深度的学习

二叉树添加删除节点Python

采用递归调用实现二叉树添加、删除节点。文章采用Python对象引用方式实现指针结构的创建。

47120
来自专栏陈树义

3.Java集合总结系列:Set接口及其实现

一、Set接口 Set 接口与 List 接口相比没有那么多操作方法,比如: 1、List 接口能直接设置或获取某个元素的值,而Set接口不能。 2、List ...

40650
来自专栏赵俊的Java专栏

不用加减乘除做加法

20940

扫码关注云+社区

领取腾讯云代金券