大数据算法题——数据结构_数据结构要写代码吗

数据结构

关于数据结构方面，一般考察都是手写代码。这个建议大家在面试之前一定要牢牢地记住怎么写，一定要自己多写几遍，另外尝试在纸上手写代码，手写代码和使用IDEA写代码地感觉是完全不一样的。另外需要掌握的是算法的思想和流程。

1. *冒泡排序？

算法思想：

1. 将序列中所有元素两两比较，将最大的放在最后面。
2. 将剩余序列中所有元素两两比较，将最大的放在最后面。
3. 重复第二步，直到只剩下一个数。

/**
 * 冒泡排序：两两比较，大者交换位置，则每一轮循环结束后最大的数会移动到最后
 * 时间复杂度为 O(n^2)  空间复杂度为 O(1)
 */
 private static void bubbleSort(int[] arr){
 	//外层循环 length-1 次
 	for(int i=0;i<arr.length-1;i++){
 	//外层每循环一次最后都会安排一个数
 	//所以内层循环length-1-i 次
 		for(int j=0;j<arr.length-1-i;j++){
 			if(arr[j]>arr[j+1]){
 				int temp = arr[j];
 				arr[j] = arr[j+1];
 				arr[j+1] = temp;
 			}
 		}
 	}
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

技巧

注意时间复杂度为O(n^2)。

2. 二分查找？

1.算法概念

二分查找算法也称为折半搜索，二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。请注意这种算法是建立在有序数组基础上的。

2.算法思想

1. 搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束。
2. 如果某一特定元素大于话会或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
3. 如果在某一步骤数组为空，则代表找不到。
4. 这种搜索算法每一次比较都使搜索范围缩小一半。

public static int binarySearch(int srcArray,int des){
	int low=0;
	int height=srcArray.length-1;
	while(low<=height){
		int middle=(low+height)/2;
		if(des==srcArray[middle]){
			return middle;
		}else if(des<srcArray[middle]){
			height=middle-1;
		}else{
			low=middle+1;
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

技巧

注意时间复杂度为O(log n)。

3. 递归的方式实现？

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,data,midIndex+1,endIndex);
	}else{
		return midIndex;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

技巧

递归也是手写代码的算法题中经常考察的点。需要能够掌握。

4. *单链表反转？

class ListNode{
	int val;
	ListNode next;
	ListNode(int x){
	val = x;
	}
}
public static ListNode reverseList(ListNode head){
	ListNode prev=null;
	while(head !=null){
		ListNode temp=head.next;
		head.next=prev;
		prev=head;
		head=temp;
		}
		return prev;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

技巧

在面试手写代码时经常会考。建议能够掌握。

5. 插入排序？

1. 初始时假设第一个记录自成一个有序序列，其余记录为无序序列。
2. 接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中。
3. 直至最后一个记录插入到有序序列中为止。

public static void insertSort(int[] a){
	int temp;
	for(int i=1;i<a.length;i++){
		for(int j=i;j>0;j--){
		if(a[j-1]>a[j]){
			temp=a[j-1];
			a[j-1]=a[j]
			a[j]=temp
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

技巧

需要能够掌握算法的过程，以及代码的书写。

6.选择排序？

把最小或者最大的选择出来。

1. 对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录与第一个记录的位置进行交换；
2. 接着对不包括第一个记录以外的其他记录进行第二轮比较，得到最小的记录并与第二个记录进行位置交换；
3. 重复该过程，直到进行比较的记录只有一个时为止。

public static void selectSort(int[] a){
	if(a==null || a.length<=0){
		return;
	}
	for(int i=0;i<a.length;i++){
		int min=i;
		for(int j=i+1;j<a.length;j++){
			if(a[j]<a[min]){
				min=j;
				}
			}
			if(i !=min){
			int tmp=a[min];
			a[min]=a[i];
			a[i]=tmp;
			}
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

技巧

需要能够掌握算法的过程，以及代码的书写。

7. 什么是队列？

就是一种简单的数据结构，采用的调度策略是先来先进，先进先出。

8. *二叉树的概念和特点？

1.二叉树概念

二叉树是一种非常重要的数据结构，它同时具有数组和链表各自的特点：它可以像数组一样快速查找，也可以像链表一样快速添加。但是他也有自己的缺点：删除操作复杂。所谓二叉树的层数，就是深度。具体二叉树分类如下：

• 二叉树：是每个节点最多有两个子树的有序树，在使用二叉树的时候，数据并不是随便插入到节点中的，一个节点的左子节点的关键值必须小于此节点，右子节点的关键值必须大于或者是等于此节点，所以又称二叉查找树，二叉排序树，二叉搜索树。
• 完全二叉树：若设二叉树的高度为h，除第h层外，其它各层（1~h-1）的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
• 满二叉树：除了叶结点外每一个节点都有左右子叶且叶子结点都处于最底层的二叉树。

2.二叉树的特点

1. 数执行查找，删除，插入的时间复杂度都是O(logN)。
2. 遍历二叉树的方法包括前序，中序，后序。
3. 非平衡数指的是根的左右两边的子节点的数量不一致。
4. 在非空二叉树中，第i层的结点总数不超过2i，i>=i。
5. 深度为h的二叉树最多有2h个结点（h>=1），最少有h个结点。
6. 对于任意一颗二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1。

9. 给你一个数组里面有奇数，偶数，写一个算法实现奇数全在最左侧，偶数全在最右侧？

/*定义一个方法，接收一个int数组，在方法内新建一个数组，
	将传进来的数组中的元素装进去，但是要求奇数在左边偶数在右边。
	最后返回这个新数组。在mian方法中调用定义数组，调用该方法，获取返回值，
	并遍历输出返回的数组*/
public class Test34{
	public static void main(String[] args){
	int[] arr={1,2,3,4,5,6,7,8,9,0};
	int[] newArr=newArray(arr);
	//遍历数组
	for (int i=0;i<newArr.length;i++){
		System.out.print(newArr[i]+"\t");
	}
}
public static int[] newArray(int[] arr){
	int[] newArr=new int[arr.length];//定义新的数组
	//定义两个变量
	int index1=0;
	int index2=arr.length-1;
	for(int i=0;i<arr.length;i++){
		if(arr[i]%2!=0){
			//奇数放到新数组的左边
			newArr[index1]=arr[i];
			//索引值++
			index1++;
		}else{
			//偶数放到新数组的右边
			newArr[index2]=arr[i];
			//索引值--
			index2--;
			}
		}
		return newArr;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

技巧

比较基础的算法面试题。需要通过多练习来提高自己编码能力。

10. Java 数据结构

Java 主要有以下一些数据结构：

1.数组

2.链表

3.栈和队列

4.二叉树

5.堆和堆栈

6.散列表

7.红黑树

技巧

需要了解 Java 的一些数据结构类型。具体数据结构的理解，不是大数据开发工程师的重点。但如果想要进大厂（BAT类型），建议加强算法学习。