面试题38： 数字在排序数组中出现的次数

统计一个数字在排序数组中出现的次数。

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        //System.out.println(getFirstK(array,k,0,array.length-1));
        //System.out.println(getLastK(array,k,0,array.length-1));
        int start = getFirstK(array,k,0,array.length-1);
        int end = getLastK(array,k,0,array.length-1);
        if (start==-1||end==-1) {//表名并没有找到指定的k值
            return 0;
        }
        return end-start+1;
    }

    public int getFirstK(int [] array , int k,int low,int high){
        int mid = (high+low)/2;
        while(low<=high){
            if(array[mid]==k){
                判断该数的前一个数是否与该数相等
                if(mid==0||(mid>0&&array[mid-1]!=k)){
                    return mid;
                }else {
                    high=mid-1;
                }
            }else if (array[mid]<k) {
                low = mid+1;
            }else {
                high = mid-1;
            }
            mid = (high+low)/2;
        }
        return -1;
    }

    public int getLastK(int [] array , int k,int low,int high){
        int mid = (high+low)/2;
        while(low<=high){
            if(array[mid]==k){
                //判断该数的后一个数是否与该数相等
                if(mid==array.length-1||(mid<array.length-1&&array[mid+1]!=k)){
                    return mid;
                }else {
                    low=mid+1;
                }
            }else if (array[mid]<k) {
                low = mid+1;
            }else {
                high = mid-1;
            }
            mid = (high+low)/2;
        }
        return -1;
    }
}

面试题39： 二叉树的深度

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */
public class Solution {
    public int TreeDepth(TreeNode root) {
        if (root==null) {
            return 0;
        }else {
            int leftheight = TreeDepth(root.left);//获取左节点的高度
            int rightheight = TreeDepth(root.right);//获取右节点的高度
            return Max(leftheight,rightheight)+1;
        }
    }

    public int Max(int a,int b){
        return a>b?a:b;
    }
}

面试题40：数组中只出现一次的数字

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {

        if (array==null||array.length<2) {
            return;
        }

        //数组所有元素的异或结果，实际上就是两个只出现一次的数字异或的结果。
        int resultXOR = 0;
        for (int i = 0; i < array.length; i++) {
            resultXOR ^= array[i];
        }
        System.out.println(resultXOR);

        int index = FindBit1(resultXOR);
        System.out.println(index);

        for (int i = 0; i < array.length; i++) {
            if(isBitof1(array[i], index)){
                num1[0] ^= array[i];
            }else {
                num2[0] ^= array[i];
            }
        }
        System.out.println(num1[0]+" "+num2[0]);

    }

    //可能异或结果二进制中可能存在多个1，找出最低位的哪一个1。
    public int FindBit1(int num){
        int indexBit=0;
        while ((num&1)==0&&(indexBit<32)) {
            num = num>>1;
            ++indexBit;
        }
        return indexBit;
    }

    //通过该函数将数组一分为二
    public boolean isBitof1(int num,int indexBit){
        num = num>>indexBit;
        return (num&1)==1;
    }
}

面试题41：和为S的两个数字VS和为s的连续正数序列

输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {

        ArrayList<Integer> arrayList = new ArrayList<>();
        if (array==null) {
            return arrayList;
        }

        //保存乘积为最小的哪一组数据
        int tempsum=Integer.MAX_VALUE;
        int templow=0;
        int temphigh=0;

        //判断是否存在这样的数据
        boolean flag = false;

        //定义两个指针，分别向中间移动
        int low=0;
        int high=array.length-1;

        while(high>low){
            long currSum = array[low]+array[high];
            if (currSum==sum) {
                int temp = array[low]*array[high];
                if (temp<tempsum) {//找出最小的哪一组数据
                    tempsum = temp;
                    templow = array[low];
                    temphigh = array[high];
                    flag=true;
                }
                high--;
                low++;
            }else if(currSum>sum){
                high--;
            }else {
                low++;
            }
        }

        if (flag) {
            arrayList.add(templow);
            arrayList.add(temphigh);
        }
        return arrayList;
    }
}

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {

        ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();

        if (sum<3) {
            return arrayLists;
        }

        int small=1;
        int big=2;

        int mid = (1+sum)/2;//因为至少需要两个数字，因此我们的small只能小于中间值
        int curSum = small+big;

        while (small<mid&&big<sum) {
            if (curSum==sum) {
                arrayLists.add(PrintSequence(small,big));
            }

            while (curSum>sum&&small<mid&&big<sum) {
                curSum -= small;
                small++;
                if (curSum==sum) {
                    arrayLists.add(PrintSequence(small,big));
                }
            }

            big++;
            curSum+=big;
        }

        return arrayLists;
    }


    public ArrayList<Integer> PrintSequence(int small,int big){
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = small; i <= big; i++) {
            arrayList.add(i);
        }
        return arrayList;
    }
}

面试题42：翻转单词顺序列

JOBDU最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

public class Solution {
    public String ReverseSentence(String str) {
        if (str==null) {
            return new String();
        }

        int low=0;//定位单词开始
        int high=0;//定位单词结束

        char[] array = str.toCharArray();

        while (high<array.length) {
            if(array[high]!=' '){
                high++;
            }else {//遇到空格，一个单词结束，进行交换
                ReverseString(array,low,high-1);
                low = high+1;
                high = low;
            }
        }
        //最后一个单词翻转
        ReverseString(array,low,high-1);

        //整个字符串进行翻转
        ReverseString(array,0,array.length-1);

        return new String(array);
    }


    public void ReverseString(char[] array, int low,int high){
        while (low<high) {
            char temp = array[low];
            array[low] = array[high];
            array[high] = temp;
            low++;
            high--;
        }
    }
}

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

public class Solution {
    public String LeftRotateString(String str,int n) {
        if (str==null||n<0) {
            return new String("");
        }

        if (str.length()==0) {
            return new String("");
        }

        if(n==0){
            return str;
        }

        char[] chs = str.toCharArray();

        if (n>=chs.length) {
            n = n%chs.length;
            if(n==0){
                return str;
            }
        }

        ReverseString(chs, 0,n-1);//选择n之前的字符串
        ReverseString(chs, n,chs.length-1);//选择n之后的字符串
        ReverseString(chs, 0,chs.length-1);//旋转整个字符串

        return new String(chs);
    }

    public void ReverseString(char[] array, int low,int high){
        while (low<high) {
            char temp = array[low];
            array[low] = array[high];
            array[high] = temp;
            low++;
            high--;
        }
    }
}

面试题43：n个骰子的点数

import java.util.ArrayList;

public class Demo43 {

    public static void main(String[] args) {
        System.out.println(new Demo43().PrintProbability(2));
    }

    public ArrayList<Double> PrintProbability(int number){

        ArrayList<Double> arrayList = new ArrayList<>();

        final int MaxValue = 6;//骰子投掷的最大值
        if(number<1)
            return arrayList;

        int[][] arr = new int[2][];
        arr[0] = new int[MaxValue*number+1];//0~6n
        arr[1] = new int[MaxValue*number+1];

        //初始化
        for (int i = 0; i < MaxValue*number+1; i++) {
            arr[0][i]=0;
            arr[1][i]=0;
        }


        int flag = 0;
        for (int i = 1; i <= MaxValue; i++) {//只有一个骰子的时候，123456的次数都为1
            arr[flag][i]=1;
        }


        //有两个以上的骰子时
        for (int n = 2; n <= number; n++) {//n为骰子
            //当有n个骰子时，小于n的数都没有了，最小值都为n
            for (int j = 0; j < n; j++) {
                arr[1-flag][j]=0;
            }


            for (int j = n; j <= MaxValue*n; j++) {//n~6n范围内的数据

                arr[1-flag][j]=0;//先清空之前的数据

                for (int j2 = 1; j2 <=j && j2<=MaxValue; j2++) {

                    arr[1-flag][j] += arr[flag][j-j2];

                }
            }

            flag = 1-flag;
        }

        double tatal = Math.pow(MaxValue, number);
        for (int i = number; i <= MaxValue*number; i++) {
            double ratio = arr[flag][i]/tatal;
            arrayList.add(ratio);
        }

        return arrayList;
    }


}

面试题44：扑克牌顺子

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何。为了方便起见,你可以认为大小王是0。

import java.util.Arrays;
public class Solution {
    public boolean isContinuous(int [] numbers) {

        if (numbers==null || numbers.length==0) {
            return false;
        }
        /** * 使用的是快速排序，如果数组比较小的情况，使用的是插入排序。 */
        Arrays.sort(numbers);

        int NumberOf0 = 0;
        int NumberOfGap = 0;
        //统计0的个数
        for (int i = 0; i < numbers.length&&numbers[i]==0; i++) {
            NumberOf0++;
        }

        //统计间隔数目
        int small = NumberOf0;
        int big = small+1;
        while (big<numbers.length) {
            //如果存在两个数相等，则不可能是顺子
            if (numbers[small]==numbers[big]) {
                return false;
            }
            NumberOfGap += numbers[big]-numbers[small]-1;
            small=big;
            big++;
        }
        return NumberOf0>=NumberOfGap?true:false;
    }
}

面试题45：孩子们的游戏(圆圈中最后剩下的数)

每年六一儿童节,NowCoder都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为NowCoder的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到NowCoder名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？

public class Solution {
        /** * 用数学方法解决 * F(1) = 0 (N=1) * F(N) = (F(N-1)+M) (N>1) * @param n 表示n个数字（0~n-1） * @param m 表示每次删除第m个数字 * @return 返回最后剩下的一个数字 */
    public int LastRemaining_Solution(int n, int m) {
        if(n<1||m<1){
            return -1;
        }
        int last = 0;//只有1个人时

        for (int i = 2; i <= n; i++) {
            last = (last+m)%i;
        }
        return last;
    }
}

面试题47：不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

public class Solution {
    public int Add(int num1,int num2) {
        int sum=0;
        int carry = 0;

        do {
            sum = num1^num2;//各位相加，但不进位
            carry = (num1&num2)<<1;//进位，但不相加
            num1 = sum;
            num2 = carry;
        } while (num2!=0);
        return num1;
    }
}

原文链接：https://blog.csdn.net/scgaliguodong123_/article/details/48597429

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。