写点什么

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

用户头像
Android架构
关注
发布于: 2021 年 11 月 05 日

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;


}


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

反转链表

《Android学习笔记总结+最新移动架构视频+大厂安卓面试真题+项目实战源码讲义》
浏览器打开:qq.cn.hn/FTe 免费领取
复制代码


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

用户头像

Android架构

关注

还未添加个人签名 2021.10.31 加入

还未添加个人简介

评论

发布
暂无评论
Android程序员面试字节跳动,准备好这些算法面试题准过!