起风网面试题29：数组中出现次数超过一半的数字
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
//判断输入
if(array==null||array.length==0){
return 0;
}
//先假设为第1个
int result = array[0];
int times = 1;
for (int i = 1; i < array.length; i++) {
if (times==0) {
result = array[i];
times++;
}else {
if (result==array[i]) {
times++;
}else {
times--;
}
}
}
if (!CheckMoreThanHalf(array,result)) {//如果没有超过一半
return 0;
}
return result;
}
//检查是否超过一半
public boolean CheckMoreThanHalf(int[] array,int result){
int times = 0;
for (int i = 0; i < array.length; i++) {
if (array[i]==result) {
times++;
}
}
boolean isMoreThanHalf = true;
if (times*2<=array.length) {
isMoreThanHalf = false;
}
return isMoreThanHalf;
}
}面试题30：最小的K个数
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> arrayList = new ArrayList<>();
//判断输入是否合法
if (input==null||input.length==0||k>input.length||k<=0) {
return arrayList;
}
//判断输入的长度是否与数组相等
if (k==input.length) {
for (int i = 0; i < k; i++) {
arrayList.add(input[i]);
}
Collections.sort(arrayList);
return arrayList;
}
int index = Partition(input,0,input.length-1);
while (k!=index) {
if (k>index) {//说明k在index的右边
index = Partition(input,index+1,input.length-1);
}else {//说明k在index的左边
index = Partition(input,0,index-1);
}
}
for (int i = 0; i < k; i++) {
arrayList.add(input[i]);
}
Collections.sort(arrayList);
return arrayList;
}
//选择一个关键字，想尽办法将它放到一个位置，使得它左边的值都比它小，
//右边的值都比它大，我们称这个关键字叫枢轴。
public int Partition(int[] arr,int low,int high){
if(arr == null || low<0 || high>=arr.length){
return 0;
}
int pivotkey;
pivotkey = arr[low];//选取第一个记录作枢轴记录
while(low<high)//从表的两端向中间扫描
{
while(low<high && arr[high]>=pivotkey){//如果大于枢轴值，则下标减一，否则，跳出循环。
high--;
}
Swap(arr, low, high);//交换
while (low<high && arr[low]<pivotkey){//如果小于枢轴值，则下标加一，否则，跳出循环。
low++;
}
Swap(arr, low, high);//交换
}
return low;
}
public void Swap(int[] arr,int low,int high){
int temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
}面试题31：连续子数组的最大和
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
if (array==null||array.length==0) {
return 0;
}
int finalMax=Integer.MIN_VALUE;//初始化为最小值
int currentSum=0;
for (int i = 0; i < array.length; i++) {
//如果之前的总和小于0，表明负数加上array[i]比array[i]还小，直接舍去。
if (currentSum<=0) {
currentSum = array[i];
}
else {
currentSum += array[i];
}
if (currentSum>finalMax) {
finalMax = currentSum;
}
}
return finalMax;
}
}面试题32： 整数中1出现的次数（从1到n整数中1出现的次数）
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。
public class Solution {
/** * 计算十位上1的个数有多少个？ * 102 1*10个 10~19 * 112 1*10+(2+1)个 10~19、110 111 112 * 122 (1+1)*10个 10~19、110~119 * @param n * @return */
public int NumberOf1Between1AndN_Solution(int n) {
if(n<=0)
return 0;
int counts=0;
int factor = 1;
int lowerNum=0;
int currNum=0;
int higherNum=0;
//102
while (n/factor!=0) { //factor=1 10 100
lowerNum = n-(n/factor)*factor; //0 2 2
currNum = (n/factor)%10; //2 0 1
higherNum = n/(factor*10); //10 1 0
switch (currNum) {
case 0://由更高数字决定
counts += higherNum*factor;
break;
case 1://由更高数字和更低数字决定
counts += higherNum*factor+lowerNum+1;
break;
default://由更高数字决定
counts += (higherNum+1)*factor;
break;
}
factor *=10;
}
return counts;
}
}面试题33： 把数组排成最小的数
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
import java.util.Comparator;
import java.util.TreeSet;
public class Solution {
public String PrintMinNumber(int [] numbers) {
StringBuilder stringBuilder = new StringBuilder();
if(numbers==null||numbers.length==0){
return new String(stringBuilder);
}
String[] strings = new String[numbers.length];
TreeSet<String> sets = new TreeSet<>(
new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
String combine1 = o1+o2;
String combine2 = o2+o1;
char[] c1 = combine1.toCharArray();
char[] c2 = combine2.toCharArray();
for (int i = 0; i < combine1.length();i++) {
if (c1[i] < c2[i]) {
return -1;
}
else if (c1[i] > c2[i]){
return 1;
}
}
return -1;
}
});
for (int i = 0; i < numbers.length; i++) {
strings[i] = Integer.toString(numbers[i]);
sets.add(strings[i]);
System.out.println(strings[i]);
}
for (String set : sets) {
System.out.println(set);
stringBuilder.append(set);
}
return new String(stringBuilder);
}
}面试题34：丑数
把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
public class Solution {
public int GetUglyNumber_Solution(int index) {
if (index<=0) {
return 0;
}
//用于保存丑数
int[] uglyNumbers = new int[index];
uglyNumbers[0] = 1;//第一个丑数为1
int nextUglyIndex = 1;//下一个丑数的索引
int multiply2 = 0;
int multiply3 = 0;
int multiply5 = 0;
while (nextUglyIndex < index) {
//[0]=1 [1]=2 [2]=3 [3]=4 [4]=5 [5]=6
//0[2] 0[3] 0[5]
//1[4] 0[3] 0[5]
//1[4] 1[6] 0[5]
//2[6] 1[6] 0[5]
//2[6] 1[6] 1[10]
//3[8] 2[9] 1[10]
int min = Min(uglyNumbers[multiply2]*2,
uglyNumbers[multiply3]*3, uglyNumbers[multiply5]*5);
uglyNumbers[nextUglyIndex] = min;//取三者的最小者作为下一个丑数
while (uglyNumbers[multiply2]*2<=uglyNumbers[nextUglyIndex]) {
multiply2++;
}
while (uglyNumbers[multiply3]*3<=uglyNumbers[nextUglyIndex]) {
multiply3++;
}
while (uglyNumbers[multiply5]*5<=uglyNumbers[nextUglyIndex]) {
multiply5++;
}
nextUglyIndex++;
}
int ugly = uglyNumbers[nextUglyIndex-1];
return ugly;
}
public int Min(int number1,int number2,int number3){
int min=number1;
if (number2<min) {
min = number2;
}
if (number3<min) {
min = number3;
}
return min;
}
}面试题35： 第一个只出现一次的字符位置
在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符的位置。若为空串，返回-1。位置索引从0开始
public class Solution {
public int FirstNotRepeatingChar(String str) {
if (str==null||str.length()>1000) {
return -1;
}
if (str.length()==0) {
return -1;
}
char[] chs = str.toCharArray();
//用于存放每字符的次数
int[] hashtable = new int[256];
//初始化
for (int i = 0; i < hashtable.length; i++) {
hashtable[i]=0;
}
for (int i = 0; i < chs.length; i++) {
hashtable[chs[i]]++;
}
for (int i = 0; i < chs.length; i++) {
if(hashtable[chs[i]]==1){
return i;
}
}
return -1;
}
}面试题36： 数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
public class Solution {
public int InversePairs(int [] array) {
if (array==null || array.length==0) {
return 0;
}
//辅助数组
int[] temp = new int[array.length];
//初始为原始值的副本
for (int i = 0; i < temp.length; i++) {
temp[i] = array[i];
}
int count = InversePairsCore(array, temp, 0, array.length-1);
return count;
}
//合并array到temp中
public int InversePairsCore(int[] array,int[] temp,int start,int end){
//只有一个数的时候，直接将改值赋于temp中，逆序直接为零。
if (start==end) {
temp[start] = array[start];
return 0;
}
int length = (end+start)/2;//取中
//将存储与temp中的数据进行合并到array
int left = InversePairsCore(temp, array, start, length);//左边子数组的个数
int right = InversePairsCore(temp, array, length+1, end);//右边子数组的个数
//i初始化为前半段的最后一个数字的下标
int i = length;
//j初始化为后半段的最后一个数字的下标
int j = end;
int indexCopy = end;
int count=0;
while (i>=start && j>=length+1) {
if (array[i]>array[j]) {
temp[indexCopy--] = array[i--];
count += j-length;
}else {
temp[indexCopy--] = array[j--];
}
}
while (i>=start) {
temp[indexCopy--] = array[i--];
}
while (j>=length+1) {
temp[indexCopy--] = array[j--];
}
return left+right+count;
}
}面试题37：两个链表的第一个公共结点
输入两个链表，找出它们的第一个公共结点。
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if (pHead1==null||pHead2==null) {
return null;
}
int length1 = 0;
int length2 = 0;
//假设pHead1为短链表，pHead2为长链表。
ListNode shortNode = pHead1;
ListNode longNode = pHead2;
//统计长短链表的长度
while (shortNode!=null) {
length1++;
shortNode = shortNode.next;
}
while (longNode!=null) {
length2++;
longNode = longNode.next;
}
//计算长度差
int diffLen = (length1>length2)?(length1-length2):(length2-length1);
shortNode = pHead1;
longNode = pHead2;
if (length1>length2) {
shortNode = pHead2;
longNode = pHead1;
}
//先让长链表走diffLen步
for (int i = 0; i < diffLen; i++) {
longNode = longNode.next;
}
while (longNode!=null&&shortNode!=null) {
if (longNode==shortNode) {
return longNode;
}
longNode=longNode.next;
shortNode=shortNode.next;
}
return null;
}
}
原文链接：https://blog.csdn.net/scgaliguodong123_/article/details/48448355
本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。
评论前必须登录！
立即登录