龙空技术网

Android程序员面试字节跳动,准备好这些算法面试题准过

你今天搬砖了吗 88

前言:

眼前咱们对“android算法面试题”都比较看重,朋友们都需要剖析一些“android算法面试题”的相关资讯。那么小编在网络上汇集了一些对于“android算法面试题””的相关资讯,希望姐妹们能喜欢,我们一起来学习一下吧!

又到了金九银十面试旺季了,只有你准备充分了,那么你想要的机会才有机会入你怀中。

下面是数据结构与算法的正菜部分:

一、找出数组中重复的数字

在一个长度为n的数组里的所有数字都在0~n-1的范围内。找出数组中任意一个重复的数字。

注意:如果题目改成找出数组中重复的数字的话,就需要和面试官沟通,我是找出所有重复的数字还是只需要找出一个就好了。

排序法

先把原数组进行一次排序,再对排序好的数组从头到尾进行遍历,很容易找到重复的数字,排序长度为n的数组需要O(nlogn)的时间。

哈希表法

可以借助哈希表解决该问题,从头到尾扫描该数组,判断该扫描到的数是否存在于该哈希表中,如果不存在则放于该哈希表中,如果存在则为重复元素。这个算法的时间复杂度是O(n),但却是以大小为O(n)的空间复杂度为代价。

交换法

如果没有重复元素的话,那么重排该数组后,数字i会出现在下标i的位置。如果有重复元素的话,下标i的位置可能不止一个数字,也可能没有数字。

从头到尾扫描数组,扫描到下标为i的数字(用m表示)看是否等于i,如果是则接着扫描下一个数字,如果不是,再拿它和下标为m的那个数字比较,如果相等,则找到一个重复数字,如果不相等,就和它交换。重复这样的操作,直到找到重复的数字。

代码实例:

如果不存在重复元素的话,返回-1(具体返回的值可以和面试官沟通)

public int getDuplicateNumber(int[] numbers){        int len = numbers.length;        if(numbers == null || len <= 0) return -1;        for(int i=0;i<len;i++){            if(numbers[i] < 0 || numbers[i] > len-1)                return -1;        }                for(int i=0;i<len;i++){                        while(numbers[i] != i){                if(numbers[i] == numbers[numbers[i]]){                    return numbers[i];  //找到重复元素                }                else {                    //交换numbers[i]和numbers[numbers[i]]的值                    int temp = numbers[i];                    numbers[i] = numbers[temp];                    numbers[temp] = temp;                }            }                    }        return -1;    }
二、不能修改数组找出重复的数字

在一个长度为n+1的数组里的所有数字都在1~n的范围内。找出数组中任意一个重复的数字。不能改变原数组并且不可借助大小超过O(n)的辅助空间。

二分法

因为长度是n+1,所以该数组至少有一个重复的数字。可以根据长度进行一半一半的分割。比如长度为8的数组,把它分两半:1-4,5-7。先在数组中找在1-4范围内的数的个数,如果超过4个说明重复的数字在1-4中。这样就缩小了范围,之后继续二分,在数组中分别找1-2,3-4这两组数字的个数,直到找到一个重复的数字。

public int getDuplicateNumber2(int[] numbers){        int len = numbers.length;        if(numbers == null || len <= 0) return -1;        int start = 1;        int end = len-1;                while(end >= start){            int middle = ((end - start) >> 1)+start;            int count = countRange(numbers,len,start,middle);            if(end == start){                if(count > 1) return start;  //找到重复元素                else break;            }            if(count >(middle-start+1))                end = middle;            else                start = middle+1;                }        return -1;    }    private int countRange(int[] numbers, int len, int start, int end) {        if(numbers == null)            return 0;        int count = 0;        for(int i=0;i<len;i++){            if(numbers[i]>=start && numbers[i]<=end)                ++count;        }        return count;    }
倒数第K个节点

在一个单链表中找到倒数第k个节点

很容易想到先遍历一次链表节点个数n,第二次遍历只需要找第n-k+1个节点。

当你说出这个想法的时候,面试官肯定会提示你他期待的答案是只允许遍历一次链表

关键点:是否可以想到使用两个指针,移动过程中两个所在位置始终相差k-1的距离。当前一个指针移到尾部时,后一个指针正好指向倒数第k个结点。

    public ListNode findKthTail(ListNode pHead, int k){        if(pHead == null || k<=0) return null;        ListNode pAHead = pHead;              ListNode pBehind = null;                //使前面的指针快与后面的节点k-1个节点位        for(int i=0;i<k-1;i++){            if(pAHead.next != null){  //容易忽视隐藏的边界条件,有可能k的值大于节点数                pAHead = pAHead.next;            }else{                return null;            }           }        //让两个指针始终保持k-1个节点位,等前面的节点到尾节点时,后一个节点到达倒数第k个节点        pBehind = pHead;        while(pAHead.next != null){            pAHead = pAHead.next;            pBehind = pBehind.next;        }        return pBehind;    }

引申:如果让一次遍历找链表的中间结点可以使用类似的方法。只需要在指针移动时,前一个指针一次移动两个节点,后一个指针一次移动一个节点。前一个指针到达尾部时,后一个指针到达中间节点。

反转链表

反转一个单链表,返回它的头节点。

很容易想到的是直接反转,后一个节点指向前一个节点。但是会有一个问题,到为尾节点的时候,会发生链表中断,这是因为尾节点的下一个结点为空。

关键点:要将前一个节点保存下来,所以要使用三个指针

public ListNode reverseListNode(ListNode pHead){        if(pHead ==null) return null;        ListNode pNewHead = null;        ListNode pPre = null;        ListNode pCur = pHead;                while(pCur !=null){            ListNode pNext = pCur.next;            if(pNext == null){  //找到新的头节点                pNewHead = pCur;              }            pCur.next = pPre;  //反转            pPre = pCur;            pCur = pNext;                    }        return pNewHead;    }

是否可以想到添加一个指针来保存之前的节点是解题的关键。

总结

最后为了帮助大家深刻理解Android相关知识点的原理以及面试相关知识,这里放上我搜集整理的2019-2020BAT 面试真题解析,我把大厂面试中常被问到的技术点整理成了PDF,包知识脉络 + 诸多细节。

节省大家在网上搜索资料的时间来学习,也可以分享给身边好友一起学习。

《960全网最全Android开发笔记》

《379页Android开发面试宝典》

《507页Android开发相关源码解析》

腾讯、字节跳动、阿里、百度等BAT大厂 2019-2020面试真题解析

以上内容均可以免费领取;

直接私信我【资料】一键领取:【Android超硬核面试资料】

标签: #android算法面试题