数据结构与算法面试系列-01
数据结构与算法面试系列-01
1. 什么是数据结构？
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
数据结构（data structure）是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。
简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。
数据的逻辑结构和物理结构是数据结构的两个密切相关的方面，同一逻辑结构可以对应不同的存储结构。算法的设计取决于数据的逻辑结构，而算法的实现依赖于指定的存储结构。
数据结构的研究内容是构造复杂软件系统的基础，它的核心技术是分解与抽象。
通过分解可以划分出数据的3个层次；再通过抽象，舍弃数据元素的具体内容，就得到逻辑结构。类似地，通过分解将处理要求划分成各种功能，再通过抽象舍弃实现细节，就得到运算的定义。
上述两个方面的结合可以将问题变换为数据结构。这是一个从具体（即具体问题）到抽象（即数据结构）的过程。
然后，通过增加对实现细节的考虑进一步得到存储结构和实现运算，从而完成设计任务。这是一个从抽象（即数据结构）到具体（即具体实现）的过程。
2. 描述一下什么是链式存储结构？
链接存储结构的含义是在计算机中用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的），它不要求逻辑上相邻的元素在物理位置上也相邻。
链式存储结构的优点主要是插入和删除简单，前提条件是知道操作位置，时间复杂度是O(1)，如果不知道操作位置则要定位元素，时间复杂度为O(n)，没有容量的限制，可以使用过程中动态分配的内存空间，不用担心溢出问题，但是它并不能实现随机读取，同时空间利用率不高。
3. 说说几种常见的排序算法和复杂度？
1）快速排序
原理：快速排序采用的是一种分治的思想，通过依次排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
选定一个合适的值（理想情况下选择中间值最好，但实际中一般使用数组第一个值），称为“枢轴”（pivot）。
基于这个值将数组分为两部分，较小的分在左边，较大的分在右边，如此一轮下来，这个枢轴的位置一定在最终位置上。
对两个子数组分别重复上述过程，直到每个数组只有一个元素，排序完成。
复杂度：O(n)
特点：快速排序是平时最常使用的一种排序算法，因它速度快，效率高的一种排序算法。
2）冒泡排序
原理：冒泡排序采用的事两个相邻的值进行比较，将值大的交换到右侧。就是逐一比较交换，进行内外两次循环，外层循环为遍历所有数值，逐个确定每个位置，内层循环为确定位置后遍历所有后续没有确定位置的数字，与该位置的值进行比较，只要比该位置的值小，就位置交换。
复杂度：O(n^2)，最佳时间复杂度为O(n)
特点：冒泡排序在实际开发中使用比较少，更适合数据量比较少的场景，因其效率比较低，但逻辑简单，方便记忆。
3）直接插入排序
原理：直接插⼊排序是从第二个数字开始，逐个取出，插入到之前排好序的数组中。
复杂度：O(n^2)，最佳时间复杂度为O(n)
4）直接选择排序
原理：直接选择排序是从第一个位置开始遍历位置，找到剩余未排序的数组中最小值，将最小值做交换位置。
复杂度：O(n^2)
特点：类似冒泡排序其逻辑简单，但效率低，适合少量数据排序。
4. Java 递归遍历目录下的所有文件？
import java.io.File;
public class ListFiles {
public static void listAll(File directory) {
if(!(directory.exists() && directory.isDirectory())) {
throw new RuntimeException("目录不存在");
}
File[] files = directory.listFiles();
for (File file : files) {
System.out.println(file.getPath() + file.getName());
if(file.isDirectory()) {
listAll(file);
}
}
}
public static void main(String[] args) {
File directory = new File("E:\\Program Files (x86)");
listAll(directory);
}
}
5. 什么是树？
树是一种重要的非线性数据结构，它是数据元素（在树中称为结点）按分支关系组织起来的结构，类似自然界中的真实的树。
树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。
树在计算机领域中也得到广泛应用，如在编译源程序时，可用树表示源程序的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。
树是由一个或多个结点组成的有限集合：
1）必有一个特定的称为根(ROOT)的结点；
2）剩下的结点被分成n>=0个互不相交的集合T1、T2、......Tn，而且， 这些集合的每一个又都是树。树T1、T2、......Tn被称作根的子树(Subtree)。
树的递归定义如下：
1、至少有一个结点，称为根；
2、其它是互不相交的子树。
树结构的特点是每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前趋。
6. 什么是二叉树？
二叉树是指每个结点最多有两个子树的有序树。
通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。
二叉树常被用作二叉查找树和二叉堆。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。
二叉树的第i层至多有2的（i-1）次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。
7. 二叉树基本概念是什么？
先序遍历（深度优先遍历）：前、中、后这三个词是针对根节点的访问顺序而言的先访问根结点，再访问左子结点，最后访问右子结点。
中序遍历：先访问左子结点，再访问根结点，最后访问右子结点。
后序遍历：先访问左子结点，再访问右子结点，最后访问根结点。
层序遍历（广度优先遍历）：先访问树的第一层结点，再访问树的第二层结点……一直访问到最下面一层的结点。在同一层结点中，以从左到右的顺序依次访问。
8. 树和二叉树有什么区别和联系？
1、两者性质不同
树是一种数据结构；二叉树是每个结点最多有两个子树的一种树结构。
2、结点数目不同
树的每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点。而二叉树的每个结点最多有两个子树。
树和二叉树的联系：树都可用二叉链表作为存储结构，对比各自的结点结构可以看出，以二叉链表作为媒介可以导出树和二叉树之间的一个对应关系。
从物理结构来说，树和二叉树的二叉链表是相同的，只是对指针的逻辑解释不同而已。从树的二叉链表表示的定义而言，任何一棵和树对应的二叉树，其右子树一定为空。
1）树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
2）树的结点无左、右之分，而二叉树的结点有左、右之分。
9. 什么是冒泡排序算法？
冒泡排序是一种简单基础的排序算法，比较相邻的两个元素，如果前面的比后面的大，则交换两个元素；
对每个相邻的元素都进行这样的比较操作，从开始的一对到最后一对，这样最后的元素会是本次遍历完剩下最大的元素；
针对所有的元素执行上述步骤，除了已经指派出来的最大元素或序列，其中序列排在最末尾。
重复以上步骤直至排序完成。
10. Java 中如何编写一个冒泡排序算法？
Java中实现冒泡排序算法代码如下：
public class Test {
static final int SIZE = 10;
public static void bubbleSort(int[] a) {
int temp;
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length - i - 1; j++) {
if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
System.out.println("第" + i + "步排序结果：");
for (int k = 0; k < a.length; k++) {
System.out.print(" " + a[k]);
}
System.out.println("\n");
}
}
public static void main(String[] args) {
int[] arrays = new int[SIZE];
int i;
for (i = 0; i < SIZE; i++) {
arrays[i] = (int) (100 + Math.random() * (100 + 1));
}
System.out.print("排序前的数组为：\n");
for (i = 0; i < SIZE; i++) {
System.out.print(arrays[i] + " ");
}
System.out.print("\n");
bubbleSort(arrays);
System.out.print("排序后的数组为：\n");
for (i = 0; i < SIZE; i++) {
System.out.print(arrays[i] + " ");
}
System.out.print("\n");
}
}
运行结果如下：
排序前的数组为：
172 197 128 196 127 180 102 142 110 134
第0步排序结果：
172 128 196 127 180 102 142 110 134 197
第1步排序结果：
128 172 127 180 102 142 110 134 196 197
第2步排序结果：
128 127 172 102 142 110 134 180 196 197
第3步排序结果：
127 128 102 142 110 134 172 180 196 197
第4步排序结果：
127 102 128 110 134 142 172 180 196 197
第5步排序结果：
102 127 110 128 134 142 172 180 196 197
第6步排序结果：
102 110 127 128 134 142 172 180 196 197
第7步排序结果：
102 110 127 128 134 142 172 180 196 197
第8步排序结果：
102 110 127 128 134 142 172 180 196 197
第9步排序结果：
102 110 127 128 134 142 172 180 196 197
排序后的数组为：
102 110 127 128 134 142 172 180 196 197
11. 【字节跳动】Java 如何实现链表归并排序？
归并排序可以说是链表排序中最佳的选择，能够保证最好和最坏时间复杂度都是nlogn，而且在数组排序中广受开发人反感的空间复杂度在链表排序中也从O(n)降到了O(1)。
归并排序的一般分为四步：
1）将需要排序数组（链表）取中点并一分为二，拆分为两个链表：head和second两个子链表；
2）使用递归方式对左半部分子链表进行归并排序；
3）使用递归方式对右半部分子链表进行归并排序；
4）将两个半部分子链表进行合并（merge），得到结果。
首先用快慢指针（快慢指针思路，快指针一次走两步，慢指针一次走一步，快指针在链表末尾时，慢指针恰好在链表中点）的方法找到链表中间节点，然后使用递归对两个子链表排序，把两个排好序的子链表合并成一条有序的链表。
程序代码，为了方便输出查看结果，使用Gson包，不需要可以去除相关代码：
import com.google.gson.Gson;
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class LinkedInsertSort {
/**
* @author 公众号：Java精选
* @param args
*/
public static void main(String[] args) {
ListNode node = new ListNode(4);
node.next = new ListNode(3);
LinkedInsertSort lss = new LinkedInsertSort();
System.out.println(new Gson().toJson(lss.mergeSort(node)));
}
public ListNode mergeSort(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode mid = getMid(head);// 获取链表中间节点
// 把链表从之间拆分为两个链表：head和second两个子链表
ListNode second = mid.next;
mid.next = null;
// 对两个子链表排序
ListNode left = mergeSort(head);
ListNode right = mergeSort(second);
return merge(right, left);
}
// 两个有序链表的归并
private ListNode merge(ListNode l1, ListNode l2) {
// 辅助节点，排好序的节点将会链接到dummy后面
ListNode dummy = new ListNode(0);
ListNode tail = dummy;// tail指向最后一个排好序的节点
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next; // 移动tail指针
}
if (l1 != null)
tail.next = l1;
else
tail.next = l2;
return dummy.next;
}
// 返回链表之间节点
private ListNode getMid(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode slow = head;
ListNode faster = head.next;
while (faster != null && faster.next != null) {
slow = slow.next;
faster = faster.next.next;
}
return slow;
}
}
输出结果
{"val":3,"next":{"val":4}}
12. 打印出 100-999 所有的水仙花个数。
所谓水仙花数是指一个三位数，其各位数字立方和等于该数本身。例如：153是一个水仙花数，因为153=1的三次方＋5的三次方＋3的三次方。
程序分析：
利用for循环控制100-999个数，每个数分解出个位，十位，百位。
程序代码
public class Demo02 {
public static void main(String args[]) {
for (int i = 100; i <= 999; i++)
if (shuixianhua(i) == true)
System.out.println(i + " ");
}
public static boolean shuixianhua(int x) {
int i = 0, j = 0, k = 0;
i = x / 100;
j = (x % 100) / 10;
k = x % 10;
if (x == i * i * i + j * j * j + k * k * k)
return true;
else
return false;
}
}
运行结果
153 370 371 407
13. 将一个正整数分解质因数。例如：输入90,打印出90=233*5。
程序分析：
对n进行分解质因数，应先找到一个最小的质数i，然后按下述步骤完成：
1）如果这个质数恰等于n，则说明分解质因数的过程已经结束，打印出即可。
2）如果n > i，但n能被i整除，则应打印出i的值，并用n除以i的商,作为新的正整数你,重复执行第一步。
3）如果n不能被i整除，则用i+1作为i的值,重复执行第一步。
程序代码
import java.util.Scanner;
public class Demo03 {
private static Scanner in;
public static void fenjie(int n) {
for (int i = 2; i <= n; i++) {
if (n % i == 0) {
System.out.print(i);
if(n!=i){
System.out.print("*");
}
fenjie(n/i);
}
}
System.exit(0);
}
public static void main(String[] args) {
in = new Scanner(System.in);
System.out.println("请输入N的值：");
int n = in.nextInt();
System.out.print( "分解质因数：" + n +"=");
fenjie(n);
}
}
运行结果
请输入N的值：
100
分解质因数：100=2*2*5*5
14. 输入一行字符，分别统计出其中英文字母、空格、数字和其它字符的个数。
程序分析：
利用for循环语句,if条件语句。
程序代码
import java.util.Scanner;
public class Demo04 {
private static Scanner in;
private static int digital, character, blank, other;
public static void main(String[] args) {
System.out.println("请输入一个字符串");
in = new Scanner(System.in);
String str = in.nextLine();
char[] ch = str.toCharArray();
count(ch);
}
public static void count(char[] arr) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] >= '0' && arr[i] <= '9') {
digital++;
} else if ((arr[i] >= 'a' && arr[i] <= 'z')
|| (arr[i] >= 'A' && arr[i] <= 'Z')) {
character++;
} else if (arr[i] == ' ') {
blank++;
} else {
other++;
}
}
System.out.println("数字个数：" + digital);
System.out.println("英文字母个数：" + character);
System.out.println("空格个数：" + blank);
System.out.println("其他字符个数：" + other);
}
}
运行结果
请输入一个字符串
123456 blog.yoodb.com _
数字个数：6
英文字母个数：12
空格个数：2
其他字符个数：3
15. 输入三个整数x,y,z，请把这三个数由小到大输出。
程序分析：
我们想办法把最小的数放到x上，先将x与y进行比较，如果x>y则将x与y的值进行交换，然后再用x与z进行比较，如果x>z则将x与z的值进行交换，这样能使x最小。
程序代码
import java.util.Arrays;
import java.util.Scanner;
public class Demo05 {
private static Scanner in;
public static void main(String[] args) {
System.out.println("请输入三个数：");
in = new Scanner(System.in);
int[] arr = new int[3];
for (int i = 0; i < 3; i++) {
arr[i] = in.nextInt();
}
Arrays.sort(arr);
for (int i=0;i<arr.length;i++) {
System.out.print(arr[i] + " ");
}
}
}
或
import java.util.Scanner;
public class Demo051 {
private static Scanner in;
public static void main(String[] args) {
System.out.println("请输入三个数：");
in = new Scanner(System.in);
int[] arr = new int[3];
for (int i = 0; i < 3; i++) {
arr[i] = in.nextInt();
}
int x = arr[0], y = arr[1], z = arr[2];
if (x > y) {
int t = x;
x = y;
y = t;
}
if (x > z) {
int t = x;
x = z;
z = t;
}
if (y > z) {
int t = y;
y = z;
z = t;
}
System.out.print(x + " " + y + " " + z);
}
}
运行结果
请输入三个数：
4
8
6
4 6 8
16. 【字节跳动】Java 如何求出两个字符串的最长公共子串长度？
假设有两个字符串分别是s1和s2，求出两个字符串的最长公共子串长度。
例如：s1=aesdwwqddf，str2=awsdwwqdde，那么s1和s2的最长公共子串为sdwwqdd，最长公共子串长度为7。
程序代码
public class CommonStr {
public static void main(String[] args) {
CommonStr lss = new CommonStr();
String s1 = "aesdwwqddf", s2 = "awsdwwqdde";
int len = lss.getCommonStrLength(s1, s2);
System.out.println("最长公共子串长度为：" + len);
}
public int getCommonStrLength(String s1, String s2) {
s1 = s1.toLowerCase();
s2 = s2.toLowerCase();
int len1 = s1.length(), len2 = s2.length();
String min = null;
String max = null;
String target = null;
min = len1 <= len2 ? s1 : s2;
max = len1 > len2 ? s1 : s2;
for (int i = min.length(); i >= 1; i--) {
for (int j = 0; j <= min.length() - i; j++) {
target = min.substring(j, j + i);
for (int k = 0; k <= max.length() - i; k++) {
if (max.substring(k, k + i).equals(target)) {
return i;
}
}
}
}
return 0;
}
}
输出结果
最长公共子串长度为：7
17. 两个乒乓球队进行比赛，各出三人。甲队为a,b,c三人，乙队为x,y,z三人。已抽签决定比赛名单。有人向队员打听比赛的名单。a说他不和x比，c说他不和x,z比，请编程序找出三队赛手的名单。
程序分析：
根据不同队员进行对比，如果不符合条件，遍历另一队员进行判断。
程序代码
public class Demo07 {
static char[] m = { 'a', 'b', 'c' };
static char[] n = { 'x', 'y', 'z' };
public static void main(String[] args) {
for (int i = 0; i < m.length; i++) {
for (int j = 0; j < n.length; j++) {
if (m[i] == 'a' && n[j] == 'x') {
continue;
} else if (m[i] == 'a' && n[j] == 'y') {
continue;
} else if ((m[i] == 'c' && n[j] == 'x')
|| (m[i] == 'c' && n[j] == 'z')) {
continue;
} else if ((m[i] == 'b' && n[j] == 'z')
|| (m[i] == 'b' && n[j] == 'y')) {
continue;
} else
System.out.println(m[i] + " vs " + n[j]);
}
}
}
}
或
public class Demo071 {
public String a, b, c;
public Demo071(String a, String b, String c) {
this.a = a;
this.b = b;
this.c = c;
}
public static void main(String[] args) {
Demo071 arr_a = new Demo071("a", "b", "c");
String[] b = { "x", "y", "z" };
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
Demo071 arr_b = new Demo071(b[i], b[j], b[k]);
if (!arr_b.a.equals(arr_b.b) & !arr_b.b.equals(arr_b.c)
& !arr_b.c.equals(arr_b.a) & !arr_b.a.equals("x")
& !arr_b.c.equals("x") & !arr_b.c.equals("z")) {
System.out.println(arr_a.a + " vs " + arr_b.a);
System.out.println(arr_a.b + " vs " + arr_b.b);
System.out.println(arr_a.c + " vs " + arr_b.c);
}
}
}
}
}
}
运行结果
a vs z
b vs x
c vs y
18. 打印出如下图案（菱形）？
程序分析：
先把图形分成两部分来看待，前四行一个规律，后三行一个规律，利用双重for循环，第一层控制行，第二层控制列。
*
***
*****
*******
*****
***
*
程序代码
public class Demo08 {
public static void main (String[]args){
int lay = 7;
for(int m = 1; m <=(lay+1)/2; m++){
for(int b = 1; b <=(lay+1)/2-m ; b++)
System.out.print(" ");
for(int c = 1; c <= m*2-1; c++)
System.out.print("*");
System.out.println();
}
for(int d =(lay+1)/2-1;d >= 1; d --){
for(int b = 1; b <= (lay+1)/2-d; b++)
System.out.print(" ");
for(int c = (lay+1)/2-d; c <=(lay+1)/2-2+d; c ++)
System.out.print("*");
System.out.println();
}
}
}
运行结果
*
***
*****
*******
*****
***
*
19. Java 中如何计算输出 9*9 口诀？
程序分析
分行与列考虑，共9行9列，i控制行，j控制列。
程序代码
package com.jingxuan.system;
public class jiujiu {
public static void main(String[] args) {
int i = 0;
int j = 0;
for (i = 1; i <= 9; i++) {
for (j = 1; j <= i; j++)
System.out.print(i + "*" + j + "=" + i * j + "\t");
System.out.println();
}
}
}
执行结果
1*1=1
2*1=2 2*2=4
3*1=3 3*2=6 3*3=9
4*1=4 4*2=8 4*3=12 4*4=16
5*1=5 5*2=10 5*3=15 5*4=20 5*5=25
6*1=6 6*2=12 6*3=18 6*4=24 6*5=30 6*6=36
7*1=7 7*2=14 7*3=21 7*4=28 7*5=35 7*6=42 7*7=49
8*1=8 8*2=16 8*3=24 8*4=32 8*5=40 8*6=48 8*7=56 8*8=64
9*1=9 9*2=18 9*3=27 9*4=36 9*5=45 9*6=54 9*7=63 9*8=72 9*9=81
20. 企业发放的奖金根据利润提成。利润(I)低于或等于10万元时，奖金可提10%；利润高于10万元，低于20万元时，低于10万元的部分按10%提成，高于10万元的部分，可可提成7.5%；20万到40万之间时，高于20万元的部分，可提成5%；40万到60万之间时高于40万元的部分，可提成3%；60万到100万之间时，高于60万元的部分，可提成1.5%，高于100万元时，超过100万元的部分按1%提成，从键盘输入当月利润I，求应发放奖金总数？
程序分析：利用数轴来分界，定位。注意定义时需把奖金定义成长整型。
程序代码如下：
package com.yoodb.util;
import java.util.Scanner;
public class Demo02 {
private static Scanner s;
public static void main(String[] args) {
s = new Scanner(System.in);
System.out.print("请输入该月的利润：（万元）");
int I = s.nextInt();
long sum = 0;
if (I <= 100000) {
sum = I / 100 * 10;
} else if (I < 200000) {
sum = (long) (100000 / 100 * 10 + (I - 100000) / 100 * 7.5);
} else if (I < 400000) {
sum = (long) (100000 / 100 * 10 + 100000 / 100 * 7.5 + (I - 200000) / 100 * 5);
} else if (I < 600000) {
sum = (long) (100000 / 100 * 10 + 100000 / 100 * 7.5 + 200000 / 100 * 5 + (I - 400000) / 100 * 3);
} else if (I < 1000000) {
sum = (long) (100000 / 100 * 10 + 100000 / 100 * 7.5 + 200000 / 100 * 5 + 200000 / 100 * 3
+ (I - 600000) / 100 * 1.5);
} else {
sum = (long) (100000 / 100 * 10 + 100000 / 100 * 7.5 + 200000 / 100 * 5 + 200000 / 100 * 3
+ 400000 / 100 * 1.5 + (I - 1000000) / 100);
}
System.out.println("该月发放的奖金为：" + sum);
}
}
运行结果如下：
请输入该月的利润：（万元）120
该月发放的奖金为：10
