一、第一个只出现一次的字符:
1、题目:
在一个字符串(0<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).
2、代码实现:
public class Test8 {
public int FirstNotRepeatingChar(String str) {
if(str.length()==0){
return -1;
}
HashMap<Character, Integer> map = new HashMap<Character,Integer>();
for(int i=0;i<str.length();i++){
if(map.containsKey(str.charAt(i))){
int time = map.get(str.charAt(i));
map.put(str.charAt(i),++time);
}else{
map.put(str.charAt(i), 1);
}
}
int pos=-1;
for(int i=0;i<str.length();i++){
char c = str.charAt(i);
if(map.get(c)==1){
return i;
}
}
return pos;
}
}
二、数组中只出现一次的数字:
1、题目:
一个整型数组里除了两个数字之外,其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。
2、解题思路:
参考牛客网的“披萨大叔”:https://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811
首先:位运算中异或的性质:两个相同数字异或=0,一个数和0异或还是它本身。
当只有一个数出现一次时,我们把数组中所有的数,依次异或运算,最后剩下的就是落单的数,因为成对儿出现的都抵消了。
依照这个思路,我们来看两个数(我们假设是AB)出现一次的数组。我们首先还是先异或,剩下的数字肯定是A、B异或的结果,这个结果的二进制中的1,表现的是A和B的不同的位。我们就取第一个1所在的位数,假设是第3位,接着把原数组分成两组,分组标准是第3位是否为1。如此,相同的数肯定在一个组,因为相同数字所有位都相同,而不同的数,肯定不在一组。然后把这两个组按照最开始的思路,依次异或,剩余的两个结果就是这两个只出现一次的数字。
3、代码实现:
public class Test1 {
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
if(array==null ||array.length<2)
return ;
//对数组所有数组进行异或
int temp=0;
for(int i=0;i<array.length;i++){
temp^=array[i];
}
//从左向右移动,获取第一个为1的位数
int index=findFirstBits(temp);
for(int i=0;i<array.length;i++){
if(isBit(array[i],index)){
num1[0]^=array[i];
}else{
num2[0]^=array[i];
}
}
}
private boolean isBit(int num, int indexOf1) {
num = num >>indexOf1;
return (num & 1) == 1;
}
//从左向右移动,获取第一个为1的位数
private int findFirstBits(int num) {
int indexBit = 0;
while((num & 1)==0 && indexBit<(8<<2)){
num = num>>1;//将num右移1位(也即除以2),然后再将结果赋值给num
++indexBit;
}
return indexBit;
}
}
三、字符流中第一个不重复的字符:
1、题目:
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符”go”时,第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时,第一个只出现一次的字符是”l”。
2、解题思路:
一个字符占8位,因此不会超过256个,可以申请一个256大小的数组来实现一个简易的哈希表。时间复杂度为O(n),空间复杂度O(n).
3、代码实现:
public class Test12 {
//一个字符占8位,因此不会超过256个,可以申请一个256大小的数组来实现一个简易的哈希表。时间复杂度为O(n),空间复杂度O(n).
int[] hashtable = new int[256];//每一个位置初始值都是0
StringBuilder builder = new StringBuilder();
//Insert one char from stringstream
public void Insert(char ch){
builder.append(ch);
hashtable[ch] +=1;
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce(){
char[] str = builder.toString().toCharArray();
for(char ch:str){
if(hashtable[ch]==1){
return ch;
}
}
return '#';
}
}
四、数组中重复的数字:
1、题目:
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。
2、代码实现:
public class Test22 {
//第一种方法:
//不需要额外的数组或者hashtable来保存,题目里写了数组里数字的范围保证在0 ~ n-1 之间,
//所以可以利用现有数组设置标志,当一个数字被访问过后,可以设置对应位上的数 + n,之后再遇到相同的数时,
//会发现对应位上的数已经大于等于n了,那么直接返回这个数即可。
//将第一个重复的数字放在duplication的0号下标中。
public boolean duplicate(int numbers[],int length,int [] duplication) {
for(int i=0;i<length;i++){
int index = numbers[i];
if(index>=length){
index = index-length;
}
if(numbers[index] >= length){
duplication[0]=index;
return true;
}
numbers[index]=numbers[index]+length;
}
return false;
}
//第二种方法:需要重新开拓一个数组
public boolean duplicate1(int numbers[],int length,int [] duplication) {
boolean[] k = new boolean[length];
for(int i=0;i<length;i++){
if(k[numbers[i]]==true){
duplication[0]=numbers[i];
return true;
}
k[numbers[i]]=true;
}
return false;
}
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114691.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...