第一个只出现一次的字符
目录
题目
在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置。
思路
建立一个哈希表，第一次扫描的时候，统计每个字符的出现次数。第二次扫描的时候，如果该字符出现的次数为1，则返回这个字符的位置。
知识普及
ASCII码表里的字符总共有多少个?
标准ASCII码字符集总共的编码有128个，包括32个通用控制符，10个十进制数码，52个英文大小写字母和34个专用符号。
ASCII码的长度呢是一个字节，共8位，理论上可以表示256个字符，但是许多时候只谈128个，其原因是这样的：
在计算机中，数字和字符本来是不加区分的。一个ACSII码在机器中，可能是字符，也可能做数字使用。为了兼顾这两种用途，也为了操作方便，规定ASCII码都是正的（正数）。
在计算机内数值表示规定中，第一位是符号位，该位为1表示负值，表示正值就是0了。这样还有7位可以用于编码，于是就有128个。后来，为了纳入更多的字符，就把第一位也用上了，成了“扩展ASCII”又有128个，这些值都是负的了。
代码
public class singleNumber {
public static void main(String[] args) {
System.out.println(singleNumber("abaccdeff"));
}
public static Character singleNumber(String str) {
if (str == null || str.length() < 1) {
throw new IllegalArgumentException("Arg should not be null or empty");
}
Map<Character,Integer> map = new LinkedHashMap<>();
for (int i = 0; i < str.length(); i++) {
if (!map.containsKey(str.charAt(i))) {
map.put(str.charAt(i), 1);
}
else
{
map.put(str.charAt(i),map.get(str.charAt(i))+1);
}
}
//找出现次数为1的
for (int i = 0; i < str.length(); i++) {
if (map.get(str.charAt(i)) == 1) {
return str.charAt(i);
}
}
throw new RuntimeException("不对");
}
}
方法2
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
public class Main {
public static void main(String[] args) {
System.out.println(get("alibaba"));
System.out.println(get("taobao"));
System.out.println(get("aabbccd"));
System.out.println(get("ddbbdd"));
System.out.println(get("ahsdkdhask"));
}
/**
* 返回第一个不重复的字符
* @param s 所求的字符串
* @return 如果有返回该字符，如果不存在不重负的字符，返回null
*/
public static Character get(String s) {
// 判断边界条件
if (s == null || s.length() < 1) {
// 抛出异常
throw new IllegalArgumentException("should not be null or empty");
}
Map<Character, Integer> map = new LinkedHashMap<Character, Integer>();
int len = s.length();
for (int i = 0; i < len; i++) {
char c = s.charAt(i);
Integer already = map.get(c);
already = (already == null) ? 0 : already;
map.put(s.charAt(i), ++already);
}
Set<Map.Entry<Character, Integer>> entries = map.entrySet();
for (Map.Entry<Character, Integer> entry : entries) {
if (entry.getValue() == 1) {
return entry.getKey();
}
}
return null;
}
}
方法3 数组的代码
public class Main {
//输出0代表没有满足条件的
public static char findFirstNoRepeatChar(String str){
if(str == null || str.trim().length()==0){
return '0';
}
int []counts = new int[26];
str = str.toLowerCase(); //防止出现大小写混乱的情况
int len = str.length();
for(int i = 0; i < len; i++){
counts[str.charAt(i) - 'a']++;
}
for(int i = 0; i < len; i++){
if(counts[str.charAt(i) - 'a'] == 1){
return str.charAt(i);
}
}
return '0';
}
public static void main(String[] args) {
System.out.println(findFirstNoRepeatChar("abaccdeff"));
}
}
课后习题1 删除在第二个字符串中出现过的所有字符
定义一个函数，输入两个字符串，从第一个字符串中删除在第二个字符串中出现过的所有字符。例如从第一个字符串"We are students"中删除第二个字符串“aeiou”中出现过的字符得到的结果就是“W r stdnts”。
public class twoString {
public static void main(String[] args) {
// TODO Auto-generated method stub
//注意String、StringBuffer、StringBuilder的区别
StringBuilder str1=new StringBuilder("we are student");
StringBuilder str2=new StringBuilder("aeiou");
for(int i=0;i<str1.length();i++){
for(int j=0;j<str2.length();j++){
if(str2.charAt(j)==str1.charAt(i)){
str1.replace(i, i+1, "");
}
}
}
System.out.println(str1);
}
}
package com.yt.dayPractice;
import java.util.ArrayList;
import java.util.Scanner;
public class RemString {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str1 = "";
String str2 = "";
ArrayList<Character> list = new ArrayList<>();
while (in.hasNext()) {
str1 = in.nextLine();
str2 = in.nextLine();
if (str1 == "") return;
if (str2 == "") return ;
for (int i = 0; i < str1.length(); i++) {
//如果str2中不包含str1.charAt[i],就将这个字符添加到list中
if (!(str2.contains(str1.charAt(i) + ""))) {
list.add(str1.charAt(i));
}
}
//遍历list，将list中的元素输出
for (int k = 0; k < list.size(); k++) {
System.out.print(list.get(k) + "");
}
}
}
}
课后习题2 去掉字符串中重复的字符
Java去掉字符串中重复的字符
package FifthWork;
import java.util.Scanner;
public class FifthWork {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
String s=scan.nextLine();
StringBuilder sb=new StringBuilder(s);
for(int i=0;i<sb.length()-1;i++){
for(int j=i+1;j<sb.length();j++){
if(sb.charAt(i)==sb.charAt(j)){
sb.deleteCharAt(j);
j--;
}
}
}
System.out.println("new string: "+sb);
}
}
用ASCII码 O(n)的时间复杂度
public class Test1 {
public static void main(String[] args) {
String str = "google";
Boolean[] booleans = new Boolean[1000];
for (int i = 0; i < booleans.length; i++) {
booleans[i] = false;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < str.length(); i++) {
if(booleans[Integer.valueOf(str.charAt(i))] == false){
sb.append(str.charAt(i));
booleans[Integer.valueOf(str.charAt(i))] = true;
}
}
// StringBuilder sb = new StringBuilder();
// for (int i = 0; i < booleans.length; i++) {
// if (booleans[i] == true) {
// sb.append((char) i);
// }
// }
System.out.println(sb);
}
课后习题3变位词
题目：在英语中，如果两个单词中出现的字母相同，并且每个字母出现的次数也相同，那么这两个单词互为变位词。例如，silent和listen，evil和live等互为变位词。请完成一个函数，判断输入的两个字符串是不是互为变位词。
解法步骤如下：
（1）新建一个HashMap，对输入的两个字符串进行判断处理；遍历第一个字符串中的每个字符，对应的map值加一。
（2）遍历第二个字符串，扫描到每个字符，map中对应值减一。
（3）对于字符串一中的每个字符，遍历其值，都是0返回true，反之返回false。
public class anagram {
public static void main(String[] args) {
System.out.println(anagram("evil","live"));
}
public static boolean anagram(String str1,String str2){
if(str1 == null || str1.length() < 1 || str2 == null || str2.length() < 1) {
return false;
}
if(str1.length() != str2.length())
{
return false;
}
Map<Character,Integer> map=new HashMap<>();
for(int i=0;i<str1.length();i++) {
if(map.containsKey(str1.charAt(i))) {
int value=map.get(str1.charAt(i));
map.put(str1.charAt(i), value+1);
}else {
map.put(str1.charAt(i), 1);
}
}
for(int i=0;i<str2.length();i++) {
if(map.containsKey(str2.charAt(i))) {
int value=map.get(str2.charAt(i));
map.put(str2.charAt(i), value-1);
}
}
for(int i=0;i<str1.length();i++) {
if(map.get(str1.charAt(i))!=0) {
return false;
}
}
return true;
}
}
代码2
public class Test2 {
public static void main(String[] args) {
System.out.println(isAnagram("eats", "tea"));
}
public static Boolean isAnagram(String s, String t)
{
if(s.length() != t.length()) {
return false;
}
int[] counter= new int[26];
//26个小写英文字母
for(int i = 0; i<s.length(); i++)
{
counter[s.charAt(i)-'a']++;
//也可用两个统计表分别统计，最后比较两个统计表是否相等
counter[t.charAt(i)-'a']--;
}
for(int count:counter)
{
if(count != 0) {
return false;
}
}
return true;
}
}
LeetCode 上的代码
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] str1 = s.toCharArray();
char[] str2 = t.toCharArray();
Arrays.sort(str1);
Arrays.sort(str2);
return Arrays.equals(str1, str2);
}
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] table = new int[26];
for (int i = 0; i < s.length(); i++) {
table[s.charAt(i) - 'a']++;
}
for (int i = 0; i < t.length(); i++) {
table[t.charAt(i) - 'a']--;
if (table[t.charAt(i) - 'a'] < 0) {
return false;
}
}
return true;
}
京公网安备 11010502036488号