《剑指offer》– 第一个只出现一次的字符、数组中只出现一次的数字、字符流中第一个不重复的字符、数组中重复的数字

《剑指offer》– 第一个只出现一次的字符、数组中只出现一次的数字、字符流中第一个不重复的字符、数组中重复的数字

一、第一个只出现一次的字符:

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账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号