笔试编程（一） | 二分查找、数组相关
发布时间：2020-12-15 06:40:26 所属栏目：Java 来源：网络整理
导读：最近有小伙伴在公众号后台留言需要准备一些面试相关的文章，其实在面试相关的文章准备笔者早有打算。在春节后，笔者会针对大数据领域相关的求职面试准备一些面试题，同时分享一些面试经验，希望能帮助到大家。 今天先分享一些笔试中经常遇到的一些编程题，包
|
最近有小伙伴在公众号后台留言需要准备一些面试相关的文章，其实在面试相关的文章准备笔者早有打算。在春节后，笔者会针对大数据领域相关的求职面试准备一些面试题，同时分享一些面试经验，希望能帮助到大家。 今天先分享一些笔试中经常遇到的一些编程题，包括解题思路和代码实现，下图是本次分享的大纲：
二分查找法 二分查找又称折半查找,它是一种效率较高的查找方法。前提：（1）必须采用顺序存储结构（2）必须按关键字大小有序排列? 原理：将数组分为三部分，依次是中值（所谓的中值就是数组中间位置的那个值）前，中值，中值后，将要查找的值和数组的中值进行比较，若小于中值则在中值前面找，若大于中值则在中值后面找，等于中值时直接返回。然后依次是一个递归过程，将前半部分或者后半部分继续分解为三部分。 public class BinarySearch {
//循环实现二分查找
public static int binarySearch(int[] arr,int x) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int middle = (low + high) / 2;
if (x == arr[middle]) {
return middle;
} else if (x < arr[middle]) {
high = middle - 1;
} else {
low = middle + 1;
}
}
//无法查到数据
return -1;
}
//递归实现二分查找
public static int binarySearch(int[] dataset,int data,int beginIndex,int endIndex) {
int midIndex = (beginIndex + endIndex) / 2;
if (data < dataset[beginIndex] || data > dataset[endIndex] || beginIndex > endIndex) {
return -1;
}
if (data < dataset[midIndex]) {
return binarySearch(dataset,data,beginIndex,midIndex - 1);
} else if (data > dataset[midIndex]) {
return binarySearch(dataset,midIndex + 1,endIndex);
} else {
return midIndex;
}
}
public static void main(String[] args) {
int[] arr = {6,12,33,87,90,97,108,561};
System.out.println("循环查找：" + (binarySearch(arr,87) + 1));
System.out.println("递归查找" + binarySearch(arr,3,arr.length - 1));
}
}
? 常见的数组相关编程题 1. 对正整数进行分解质因数 // 如传入100,打印出2*2*5*5
/** 思路:
* 首先找到一个最小的质数i
* 1. 如果这个质数恰等于num,则说明分解质因数的过程已经结束,打印出即可
* 2. 如果num > i,但num能被i整除,则打印出i的值,并用num除以i的商,作为新的正整数num,重复执行第一步
* 3. 如果num不能被i整除,则用i+1作为i的值,重复执行第一步
**/
public static void t0(int num) {
for (int i = 2; i <= num; i++) {
while (num != i) {
if (num % i == 0) {
System.out.print(i + "*");
num = num / i;
} else {
break;
}
}
}
System.out.println(num);
}
? 2. 在一个给定的从1到100的整型数组中，快速找到缺失的数字 ? /**思路:
* 1. 首先对集合进行升序排序
* 2. 在没有确实数字的情况下,`排序后`相邻间的两数字差值应为1,需要处理的是差值大于1的 [差值为1和差值为0的不需要处理]
*
* @param arr 正整数数组 如int[] list = {1,10,4,2,8,13};
**/
public static void t1(int[] arr) {
if (arr != null) {
ArrayList<Integer> nums = new ArrayList<Integer>();
int length = arr.length;
if (length == 1) {
System.out.println(nums);
}
Arrays.sort(arr);
for (int i = 0; i < length; i++) {
if (i != length - 1) {
int now = arr[i];
int step = arr[i + 1] - now;
if (step > 1) {
int x = 0;
while (x < step - 1) {//注意临界值的处理
x++;
nums.add(now + x);
}
}
}
}
System.out.println(nums);
}
}
? 3. 对字符串进行中的数字进行正序排序，并且字符串中字母的位置不变 //如，43a6f9d8,输出34a6f8d9
/**思路:
* 1. 先遍历字符串取出其中的数字放进一个集合,然后对集合进行正序排序
* 2. 再次遍历字符串,遇到字符为数字的,取出数字字符集合numChars中的第一个元素(索引j=0)放在此位置,并对numChars下一个取出的元素索引定位为j++
**/
public static String t3(String str) {
if (StringUtils.isBlank(str)) {
return str;
}
ArrayList<Character> numChars = new ArrayList<>();
char[] chars = str.toCharArray();
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
if (Character.isDigit(c)) {
numChars.add(c);
}
}
Collections.sort(numChars);
StringBuilder builder = new StringBuilder();
for (int i = 0,j = 0; i < chars.length; i++) {
char c = chars[i];
if (Character.isDigit(c)) {
builder.append(numChars.get(j));
j++;
} else {
builder.append(c);
}
}
return builder.toString();
}
? ? 4. 在一个未排序的整型数组中,找到最大和最小的数字 // 如，int[] list = {-2,1,99,-1,13,0}；输出max: 99 ; min: -2
/**思路:
* 1. 初始化最大数字max和最小数字min为数组中第一个元素
* 2. 将max和数组中"下一个"元素next比较,如果next>max,则max=next
* 3. 将min和数组中"下一个"元素next比较,如果next<min,则min=next
**/
public static void t4(int[] arr) {
if (arr != null) {
int length = arr.length;
if (length == 1) {
System.out.println("the max num and min num both are: " + arr[0]);
} else {
int max = 0;
int min = 0;
for (int i = 0; i < length; i++) {
int num = arr[i];
if (i == 0) {
max = num;
min = num;
} else {
if (num > max) {
max = num;
}
if (num < min) {
min = num;
}
}
}
System.out.println("max num is: " + max + " ; min num is: " + min);
}
}
}
? ? 5. 一个整型数组中，找到一个所有成对的数字，满足它们的和等于一个给定的数字 //如，int[] arr = {-2,13},sum为3; 找出 -1和4,1和2即可;
//如，int[] arr = {1,0},sum为3; 找出1和2,3和0即可
public static void t5_0(int[] arr,int sum) {
if (arr != null) {
int length = arr.length;
Arrays.sort(arr);
HashSet<String> set = new HashSet<>();
for (int i = 0,j = length - 1; i < j; ) {
int tmpSum = arr[i] + arr[j];
if (tmpSum == sum) {
//如果只获取其中一对元素和等于sum直接return
//return arr[i] + "+" + arr[j] + "=" + sum;
//如果是获取所有并且不重复可以采取这种
set.add(arr[i] + "+" + arr[j] + "=" + sum);
//避免进入死循环
i++;
j--;
} else if (tmpSum < sum) {
i++;
} else {
j--;
}
}
System.out.println(set);
}
}
? ? 6. 如果一个数组包含多个重复元素，找到这些重复的数字 //如，int[] arr = {1,0}；输出0,3即可
public static void t6(int[] arr) {
if (arr != null) {
int length = arr.length;
Arrays.sort(arr);
HashSet<Integer> res = new HashSet<>();
for (int i = 0; i < length; i++) {
if (i != length - 1) {
int now = arr[i];
int next = arr[i + 1];
if (now == next) {
res.add(now);
}
}
}
System.out.println(res);
}
}
? ? 7. Java 实现从一个给定数组中删除重复元素 //如，int[] arr = {1,0}；输出 4
public static void t7(int[] arr) {
if (arr != null) {
int length = arr.length;
Arrays.sort(arr);
ArrayList<Integer> res = new ArrayList<>();
ArrayList<Integer> repeatNums = new ArrayList<>();
for (int i = 0; i < length; i++) {
int now = arr[i];
res.add(now);
if (i != length - 1) {
int next = arr[i + 1];
if (now == next) {
repeatNums.add(now);
}
}
}
res.removeAll(repeatNums);
System.out.println(res);
}
}
? ? 8. Java实现数组反转 public static Object t8(int[] arr) {
if (arr != null) {
// 可以采用t8_t方法比较通用
//t8_t(arr,arr.length);
int i = 0;
for (int j = arr.length - 1; j > i; ++i) {
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
--j;
}
}
return ArrayUtils.toString(arr);
}
private static void t8_t(int[] arr,int startIndexInclusive,int endIndexExclusive) {
if (arr != null) {
int i = startIndexInclusive < 0 ? 0 : startIndexInclusive;
for (int j = Math.min(arr.length,endIndexExclusive) - 1; j > i; ++i) {
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
--j;
}
}
}
? ? 关注微信公众号：大数据学习与分享，获取更对技术干货 ? （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
