1、

题目描述

对于一个字符串，请设计一个高效算法，找到第一次重复出现的字符。

给定一个字符串(不一定全为字母)A及它的长度n。请返回第一个重复出现的字符。保证字符串中有重复字符，字符串的长度小于等于500。

测试样例：

"qywyer23tdd",11

返回：y

分析：hashset不允许又重复元素加入。

import java.util.*;public class FirstRepeat {    public char findFirstRepeat(String A, int n) {        char[] a=A.toCharArray();		HashSet

2、

春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。

给定一个红包的金额数组gifts及它的大小n，请返回所求红包的金额。

若没有金额超过总数的一半，返回0。

测试样例：

[1,2,3,2,2],5

返回：2

分析：先进行排序，当某个金额多于一半的时候，数组的中间值必定是多于一一半的值，注意考虑没有超过一半的情况，返回0。

import java.util.*; public class Gift {    public int getValue(int[] gifts, int n) {        Arrays.sort(gifts);            int ans = gifts[n/2];            int num = 0;            for(int i = 0; i < gifts.length; i++) {                if(gifts[i] == ans) {                    num++;                }            }            return num <= n/2 ? 0 : ans;    }}

3、

请设计一个复杂度为O(n)的算法，计算一个未排序数组中排序后相邻元素的最大差值。

给定一个整数数组A和数组的大小n，请返回最大差值。保证数组元素个数大于等于2小于等于500。

测试样例：

[9,3,1,10],4

返回：6

分析：数组长度等于2则直接返回二者只和的绝对值，否则对数组内元素先进行排序，然后两两做差放进List，最后排序list，输出最后一个元素即为最大。

/**     * 寻找最大差值     * @param A     * @param n     * @return     */	public static int findMaxDivision(int[] A, int n) {		int m=0;		int a = 0;		Arrays.sort(A);		if (n==2) {			return Math.abs(A[0]-A[1]);			}else {			List temp=new ArrayList<>();			for (int i = 0; i < n-1; i++) {				m=Math.abs(A[i]-A[i+1]);				temp.add(m);							}			Collections.sort(temp);			a=(int) temp.get(temp.size()-1);			return a;	        		}	}

4、

题目描述

世界上有10种人，一种懂二进制，一种不懂。那么你知道两个int32整数m和n的二进制表达，有多少个位(bit)不同么？ 

输入例子:

1999 2299

输出例子:

7

分析：两数做异或运算，0^1=1；1^0=1；1^1=0 即相同为1，不同为0，最后统计1的个数即可。

/**     * 获得两个整形二进制表达位数不同的数量     *      * @param m 整数m     * @param n 整数n     * @return 整型     */    public int countBitDiff(int m, int n) {      int s=m^n;      int count=0;        while(s>0){            s=s&(s-1);            count++;        }     return count;    }

5、

题目描述

对于一个字符串，和字符串中的某一位置，请设计一个算法，将包括i位置在内的左侧部分移动到右边，将右侧部分移动到左边。

给定字符串A和它的长度n以及特定位置p，请返回旋转后的结果。

测试样例：

"ABCDEFGH",8,4

返回："FGHABCDE"

分析：首先关键位置不能大于字符串长度，然后根据特定位置进行字符串截取即可。

public String rotateString(String A, int n, int p) {        if (p>n) {	    	return null;		    	}	    	String str1=A.substring(0,p+1);	    	String str2=A.substring(p+1, n);	    	return str2+str1;    }

6、

题目描述

小东和三个朋友一起在楼上抛小球，他们站在楼房的不同层，假设小东站的楼层距离地面N米，球从他手里自由落下，每次落地后反跳回上次下落高度的一半，并以此类推知道全部落到地面不跳，求4个小球一共经过了多少米？(数字都为整数)

给定四个整数A,B,C,D，请返回所求结果。

测试样例：

100,90,80,70

返回：1020

分析：首先不要对距离取整，也就是遇到小数的情况取整会损失一定距离。不管是几个小球，先拿一个来分析，假设第一次是N，第二次就是N/2，第三次是N/4，依次类推。可以看出距离是一个首项是N，公比是1/2的等比数列，根据等比数列求和公式Sn=a1（1-q^n）/(1-q)这里需要考虑极限的情况，也就是小球反跳次数n无穷大时，q^n趋于0，所以求和公式变为Sn=a1/(1-q)，所以小球距离S=N+N/(1-1/2)=3N。

import java.util.*;public class Balls {    public int calcDistance(int A, int B, int C, int D) {        return 3*(A+B+C+D);    }}

7、

题目描述

现定义数组单调和为所有元素i的f(i)值之和。这里的f(i)函数定义为元素i左边(不包括其自身)小于等于它的数字之和。请设计一个高效算法，计算数组的单调和。

给定一个数组A同时给定数组的大小n，请返回数组的单调和。保证数组大小小于等于500，同时保证单调和不会超过int范围。

测试样例：

[1,3,5,2,4,6],6

返回：27

分析：先来解释一下题目，根据给的样例，从数组的第一个元素开始1，左边没有元素。3左边有一个元素且小于3，所以结果为1，接下来是5，左边两个元素且都小于5，结果为4，接下来是2，左边有三个元素，但只有一个小于2，结果为1，以此类推，最终结果为1+4+1+6+15=27。

倒序取数组元素，然后判断左边元素是否小于它，小于的元素相加，最后再相加所有结果，时间复杂度为O（n^2）

import java.util.*;public class MonoSum {    public int calcMonoSum(int[] A, int n) {        int sum=0;	    	for (int j = 0; j < n; j++) {					    		for (int i = n-2; i >= 0; i--) {	    			if (A[i]<=A[n-1]) {	    				System.out.println(A[i]);	    				sum=sum+A[i];	    			}	    		}	    		n--;			}		return sum;    }}

8、

有一个字符串例如“sdabisjabmla”，请计算相邻“ab”的个数。

例如：输入“sdabisjabmla”，判断相邻“ab”的个数，输出1。

分析：判断字符串不为空，字符串长度等于2还是小于2，还是大于2.难度不大。主要是各种情况的考虑。

/**	  * 寻找相邻字符串个数	  * @param str	  * @param same	  * @return	  */	 public static int Samecount(String str,String same){		 int count=0;		 if (str==null) {			return -1;		 }else if (str.length()==2) {			if (same.equals(str)) {				return 1;			}		 }else if (str.length()>2) {			for (int i = 0; i < str.length()-1; i++) {				if (str.substring(i, i+2).equals(same)) {					count++;				}			}		 }else{			return 0;		 }		 return count;	 }

9、

给定一个字符串数组，例如｛“this”，“is”，“a”，“dog”，“is”,“this”｝，请依次输出每个元素出现的次数，本例输出

this:2

is:2

a:1

dog:1

分析：第一次做这个题目完全想偏了，想着用hashset，后来面试官提示用hashmap，当时没想起来，后来又想了想，可以用hashmap的key存储每个元素，value存储出现次数，每次存储元素之前需要根据key检查一下是否已经存在，存在的话就把value加1，最后按数组的元素顺序查找map里面的value并输出。

/**	  * 寻找数组元素每个元素的出现次数并按出现顺序输出	  * @param str	  * @return	  */	 public static HashMap sameCount(String[] str){		 HashMap
    
      hm=new HashMap<>();		 int count=0;		 for (int i = 0; i < str.length; i++) {			if (hm.containsKey(str[i])) {				int c=hm.get(str[i]);				hm.put(str[i],c+1);			}else {				hm.put(str[i],1);			}		}		return hm;	 }//调用的时候String[] s={"this","a","is","a","a","this"};		HashMap map=sameCount(s);		for (int i = 0; i < map.size(); i++) {			System.out.println(s[i]+":"+map.get(s[i]));		}