JAVA常考点之数据结构与算法【JAVA面试】
Java技术迷（JavaFans1024）整理
出处：https://blog.csdn.net/qq_34279303/article/details/114680758
已获原作者授权转载
今天主要给大家讲解JAVA常考点之数据结构与算法，内容有点小长，希望大家耐心看完哈~
目录
1、二分查找 1
2、冒泡排序 3
3、层序遍历二叉树 4
4、选择排序 5
5、反转单链表 6
6、插入排序 7
7、判断链表是否有环 8
8、快速排序 11
9、求二叉树最大的深度（宽度） 12
10、爬楼梯 13
11、合并两个有序链表 14
12、数组的最大子序和 16
13、求两个数的最大公约数与最小公倍数 17
14、堆排序 18
15、最长回文子串 20
1、二分查找
优点是比较次数少，查找速度快，平均性能好；
其缺点是要求待查表为有序表，且插入删除困难。
因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
使用条件：查找序列是顺序结构，有序。
时间复杂度
采用的是分治策略
最坏的情况下两种方式时间复杂度一样：O(log2 N)
最好情况下为O（1）
空间复杂度
算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数
非递归方式：
由于辅助空间是常数级别的所以：
空间复杂度是O(1);
递归方式：
递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的：
空间复杂度：O(log2N )
（1）非递归实现
public static int binarySearch(int[] arr, int key) {int low = 0;int high = arr.length - 1;//当要查询的数小于最小值或大于最大值时，直接返回，不需要进入while循环内部if (key < arr[low] || key > arr[high]) {return -1;}while (low <= high) {int middle = (low + high) / 2;if (key == arr[middle]) {return middle;} else if (key < arr[middle]) {high = middle - 1;} else {low = middle + 1;}}return -1;}
（2）递归实现
public static int recursionBinarySearch(int[] arr, int key, int low, int high) {int middle = (low + high) / 2;if (key < arr[low] || key > arr[high]) {return -1;}if (key == arr[middle]) {return middle;} else if (key < arr[middle]) {return recursionBinarySearch(arr, key, low, middle - 1);} else {return recursionBinarySearch(arr, key, middle + 1, high);}}
2、冒泡排序
比较两个相邻的元素，若第二个元素比第一个元素小，则交换两者的位置，第一轮比较完成后，最大的数会浮到最顶端。排除此最大数，继续下一轮的比较。
时间复杂度：O(N^2)
空间复杂度：O(1)
为稳定排序
可以为冒泡排序进行优化，当某一趟未发生交换时，则说明数组已经有序了，无需再进行排序。
public static void bubbleSort(int[] arr) {//一共需要进行n-1趟循环for (int i = 0; i < arr.length - 1; i++) {//假设本次循环中，没有发生交换boolean flag = false;//本次循环一共需要比较n-i-1次for (int j = 0; j < arr.length - i - 1; j++) {if (arr[j + 1] < arr[j]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;//本次循环发生交换了flag = true;}}//如果本次循环后，未发生交换，则表明数组有序，退出排序if (!flag) {break;}}}
3、层序遍历二叉树
结点类
class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}}
层序遍历（非递归）
public void layerOrder(TreeNode root) {LinkedList<TreeNode> list = new LinkedList<>();TreeNode t;if (root != null) {list.push(root);}while (!list.isEmpty()) {t = list.removeFirst();System.out.print(t.getValue());if (t.getLeft() != null) {list.addLast(t.getLeft());}if (t.getRight() != null) {list.addLast(t.getRight());}}}
4、选择排序
第一轮从整个数组中选择最小的数，与第一个数交换。
第二轮排除第一个数，从剩下来的数中选择最小的数，与第二个数交换。
以此类推。
时间复杂度：O(N^2)
空间复杂度：O(1)
为稳定排序
时间复杂度：O(N^2)
空间复杂度：O(1)
为稳定排序
可以为冒泡排序进行优化，当某一趟未发生交换时，则说明数组已经有序了，无需再进行排序。
public static void selectSort(int[] a) {for (int i = 0; i < a.length - 1; i++) {//假设当前下标代表最小的数int min = i;for (int j = i + 1; j < a.length; j++) {if (a[j] < a[min]) {min = j;}}if (min != i) {int temp = a[i];a[i] = a[min];a[min] = temp;}}}
5、反转单链表
结点类
public static class ListNode {int val;ListNode next;ListNode(int val) {this.val = val;}}
这里我们采用两种方法，分别是迭代与递归。
（1）迭代
从链表头部开始处理，我们需要定义三个连续的结点pPre，当前需要反转的结点pCur，下一个需要反转的结点pFuture和一个永远指向头结点的pFirst。每次我们只需要将pPre指向pFuture，pCur指向pFirst，调整头结点pFirst，调整当前需要反转的结点为下一个结点即pFuture，最后调整pFuture为pCur的next结点。
/*** 迭代方式** @param head 翻转前链表的头结点* @return 翻转后链表的头结点*/public ListNode reverseList(ListNode head) {if (head == null) {return null;}//始终指向链表的头结点ListNode pFirst = head;//三个结点中的第一个结点ListNode pPre = pFirst;//当前需要反转的结点ListNode pCur = head.next;//下一次即将需要反转的结点ListNode pFuture = null;while (pCur != null) {pFuture = pCur.next;pPre.next = pFuture;pCur.next = pFirst;pFirst = pCur;pCur = pFuture;}return pFirst;}
（2）递归
递归与迭代不同，递归是从链表的尾结点开始，反转尾结点与前一个结点的指向。
/*** 递归方式** @param head 翻转前链表的头结点* @return 翻转后链表的头结点*/public ListNode reverseList2(ListNode head) {if (head == null || head.next == null) {return head;}ListNode pNext = head.next;head.next = null;ListNode reverseListNode = reverseList2(pNext);pNext.next = head;return reverseListNode;}
6、插入排序
（1）两层for循环
public static void insertSort(int[] a) {for (int i = 1; i < a.length; i++) {int cur = i;int t = a[i];for (int j = i - 1; j >= 0; j--) {if (t < a[j]) {a[j + 1] = a[j];cur = j;}}//cur位置是最后空出来的，将本次待插入的数t放进去即可a[cur] = t;}}
（2）内层使用while循环（不太好理解）
public static void insertSort2(int[] a) {for (int i = 1; i < a.length; i++) {int temp = a[i];int j = i - 1;while (j >= 0 && temp < a[j]) {a[j + 1] = a[j];j--;}a[j + 1] = temp;}}
7、判断链表是否有环
节点类：
static class ListNode {public int val;public ListNode next;ListNode(int val) {this.val = val;this.next = null;}}
（1）使用额外空间来判断链表中是否有环
思路：遍历整个链表，将每一次遍历的节点存入Set中，利用Set存入相同元素返回false的特性，判断链表中是否有环。
public boolean hasCycle(ListNode head) {Set<ListNode> set = new HashSet<>();while (head != null) {boolean result = set.add(head);if (!result) {return true;}head = head.next;}return false;}
由于遍历，导致时间复杂度为O(n)，由于使用了Set集合，空间复杂度为O(n)。
（2）使用快慢指针。
思路：快慢指针都从头节点开始，快指针一次走两步，慢指针一次，如果慢指针能够追赶上快指针，则证明链表中有环。
public boolean hasCylce2(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;//如果慢指针追赶上快指针的话，则说明有环if (fast == slow) {return true;}}return false;}
拓展问题1：
如果链表有环，找出环的入口节点。
思路：快慢指针的相遇点到环入口的距离等于头节点到环入口的距离，那么在头节点和相遇点各设一个相同步伐的指针，他们相遇的那个节点就是环入口。
public ListNode getEntrance(ListNode head) {ListNode slow = head;ListNode fast = head;boolean isCycle = false;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;//如果慢指针追赶上快指针的话，则说明有环if (fast == slow) {isCycle = true;break;}}if (isCycle) {slow = head;while (slow != fast) {slow = slow.next;fast = fast.next;}return slow;}return null;}
拓展问题2：
若链表有环，求出环的长度。
思路：若链表有环，得到环入口，然后让指针指向环入口，指针遍历完重新回到环入口的路程即环的长度。
public int getCylceLength(ListNode head) {int length = 0;ListNode cycleNode = getEntrance(head);if (cycleNode != null) {ListNode temp = cycleNode;while (true) {temp = temp.next;length++;if (temp == cycleNode) {break;}}}return length;}
8、快速排序
在数组中选定一个基准数，通过一次排序后，基准数左边的元素都比基准数小，基准数右边的元素都比基准数大。
最差时间复杂度O(N^2)
平均时间复杂度O(N*log2N)
为不稳定排序
public static void quickSort(int[] a, int left, int right) {if (left > right) {return;}//以数组第一个元素为基准点int key = a[left];int i = left;int j = right;while (i < j) {//j位于最右边，向左边进行遍历，直到找到一个小于基准数的元素，取其下标while (i < j && a[j] >= key) {j--;}//i位于最左边，向右边进行遍历，直到找到一个大于基准数的元素，取其下标while (i < j && a[i] <= key) {i++;}//若找到以上两个数，则交换他们if (i < j) {int temp = a[i];a[i] = a[j];a[j] = temp;}}//此时离开while循环，说明i==j，将a[i]与基准数进行交换a[left] = a[i];a[i] = key;//对左边进行递归排序quickSort(a, left, i - 1);//对右边进行递归排序quickSort(a, i + 1, right);}
9、求二叉树最大的深度（宽度）
（1）递归实现
/*** 求二叉树的深度（使用递归）** @param root* @return*/public int getHeight(TreeNode root) {if (root == null) {return 0;}int leftHeight = getHeight(root.getLeft());int rightHeight = getHeight(root.getRight());return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}
（2）非递归实现
按照层序遍历的思想，记录某一层的元素总数与本层中已经遍历过的元素个数，当两者相等时，深度自增。
也可用于求二叉树的最大宽度，遍历的同时取每层元素总数的最大值即可。
/*** 求二叉树的深度（不使用递归）** @param root* @return*/public int getHeight2(TreeNode root) {if (root == null) {return 0;}LinkedList<TreeNode> list = new LinkedList<>();list.offer(root);//最大宽度留备用int max=0;//二叉树的深度int level = 0;//本层中元素总数int size = 0;//本层已经访问过的元素个数int cur = 0;while (!list.isEmpty()) {size = list.size();max=Math.max(max,size);cur = 0;while (cur < size) {TreeNode node = list.poll();cur++;if (node.getLeft() != null) {list.offer(node.getLeft());}if (node.getRight() != null) {list.offer(node.getRight());}}level++;}System.out.println("二叉树最大宽度为:"+max);return level;}
10、爬楼梯
题目描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例：输入3，输出3
走法：
（1）1，1，1
（2）1，2
（3）2，1
思考：
第n阶楼梯的爬法 =（第n-1阶楼梯的爬法+第n-2阶楼梯的爬法）
（1）递归（可能会出现超时情况）
public int climbStairs(int n) {if (n == 0 || n == 1) {return n;}if (n == 2) {return 2;}return climbStairs(n - 1) + climbStairs(n - 2);}
（2）动态规划
public int climbStairs2(int n) {if (n == 0 || n == 1) {return 1;}int[] a = new int[n + 1];a[0] = 1;a[1] = 1;for (int i = 2; i <= n; i++) {a[i] = a[i - 1] + a[i - 2];}return a[n];}
11、合并两个有序链表
结点类
static class ListNode {int val;ListNode next;ListNode(int val, ListNode next) {this.val = val;this.next = next;}
（1）非递归解法
public static ListNode mergeList2(ListNode l1, ListNode l2) {ListNode head = new ListNode(-1, null);ListNode temp = head;//第一个while,只要l1和l2都还有元素时，依据大小进行合并while (l1 != null && l2 != null) {if (l1.val < l2.val) {head.next = l1;l1 = l1.next;} else {head.next = l2;l2 = l2.next;}head = head.next;}//第二个while,此时l1已经为空，则将l2剩余的结点合并到新链表中while (l2 != null) {head.next = l2;head = head.next;l2 = l2.next;}//第三个while,此时l2已经为空，则将l1剩余的结点合并到新链表中while (l1 != null) {head.next = l1;head = head.next;l1 = l1.next;}return temp.next;}
（2）递归解法
public static ListNode mergeList(ListNode l1, ListNode l2) {//递归的最小规模解if (l1 == null) {return l2;}if (l2 == null) {return l1;}//递归的规模分解if (l1.val <= l2.val) {l1.next = mergeList(l1.next, l2);return l1;} else {l2.next = mergeList(l1, l2.next);return l2;}}
12、数组的最大子序和
题目描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
使用动态规划法：
假设sum（i，j）表示nums数组中从i到j的元素之和，那么我们必须遵循的条件是sum（i，j-1）>0，我们可以认为sum（i，j）有可能是最大子序和，需要和其满足这个条件的情况进行比较。如果sum（i，j-1）<0，我们就抛弃nums[i]到nums[j-1]之间的元素（两端也抛弃，抛弃之前，先与最大值进行比较，防止出现数组全负数的情况）。再从nums[j]开始，即求sum（j，k）的最大值，如果sum（i，k-1）<0，我们就再从nums[k]开始，以此类推。
public static int getMaxSum(int[] a) {int max = a[0];int cur = a[0];for (int i = 1; i < a.length; i++) {if (cur > 0) {cur += a[i];} else {cur = a[i];}if (cur > max) {max = cur;}}return max;}
13、求两个数的最大公约数与最小公倍数
（1）最大公约数
使用相减法
/*** 相减法*/public static int getMaxCommonDivisor(int x, int y) {while (x != y) {if (x > y) {x = x - y;} else {y = y - x;}}return x;}
（2）最小公倍数
基于定理 两数乘积=最大公约数*最小公倍数
public static int getMinCommonMultiple(int x, int y) {return x * y / getMaxCommonDivisor(x, y);}
14、堆排序
时间复杂度：O( N*logN )
空间复杂度：O(1)
为不稳定排序
注意点：
（1）初始化大顶堆时 是从最后一个有子节点开始往上调整最大堆。
（2）而堆顶元素(最大数)与堆最后一个数交换后，需再次调整成大顶堆，此时是从上往下调整的。
（3）不管是初始大顶堆的从下往上调整，还是堆顶堆尾元素交换，每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换，交换之后都可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整。
package day1024;/*** 堆排序*/public class Solution {public static void heapSort(int[] a) {//从第一个非叶子节点开始，从下往上，从右向左调整堆for (int i = a.length / 2 - 1; i >= 0; i--) {adjust(a, i, a.length);}//构建完堆后，需要首先交换堆顶元素与尾元素，然后除堆尾元素，再次进行堆的调整for (int j = a.length - 1; j > 0; j--) {//交换堆顶元素与尾元素swap(a, 0, j);//再次对堆进行排序，每次都需要排除有序的元素adjust(a, 0, j);}}/*** 调整节点a[i]，其左节点a[2i+1]，右节点a[2i+2],且左右子节点均在length范围内*/public static void adjust(int[] a, int i, int length) {//先是该节点的左节点b，然后是b的左节点，for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {//如果该节点有右节点的话，并且右节点最大时，将k指向右节点if (k + 1 < length && a[k] < a[k + 1]) {k++;}//此时a[k]已经是左右两节点最大的节点if (a[k] > a[i]) {//交换两元素swap(a, i, k);//由于交换节点与子节点，导致子节点构成的堆乱序，因此将元素下标改为其子节点下标i = k;} else {break;}}}/*** 交换数组中的两个元素*/public static void swap(int[] a, int m, int n) {int temp = a[m];a[m] = a[n];a[n] = temp;}public static void main(String[] args) {int[] a = {-7, 11, 44, 7, -89, 34, 12, 67, 90, 34, 67, -89, 3, 1, 9, 0, 4, 2, -7, 95, 700, 21, 65, -900};heapSort(a);for (int temp : a) {System.out.print(temp + " ");}}}
15、最长回文子串
要求：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例 1：
输入: "babad"
输出: "bab"
这里我们采用动态规划。
主要思路：
（1）声明一个布尔类型的二维数组dp，boolean[][] dp = new boolean[len][len]，len为字符串s的长度，那么如果dp[i][j]为true时，则表示字符串s从第i个位置开始到第j个位置结束之间的子字符串为回文子串。
如：s="abac"，那么此时dp声明为dp[4][4]，那么dp[0][0],dp[1][1],dp[2][2],dp[3][3],dp[0][2]都为true,表示对应位置的字母都是回文子串，那么这里最大长度的回文子串为aba。
（2）如果dp[i][j]为true，那么dp[i+1][j-1]也必定为true，即“abba”为回文子串，那么“bb”也为回文子串。因此我们的状态转移方程为dp[i+1][j-1]=true&&s.charAt(i)==s.charAt(j) => dp[i][j]为true。
（3）如果j-i<=2时，即可能为回文的字符串最大长度为3时，如果有s.charAt(i)==s.charAt(j)，就直接断定dp[i][j]=true，并不需要dp[i+1][j-1]=true。即当s="abad",i=0;j=2,s.charAt(0)==s.charAt(2)，则直接判定aba为回文字符串，即dp[0][2]=true。
（4）使用两层for循环，外层循环指示器i控制所求字符串的开始位置，内层循环指示器j控制所求字符串的结束位置。但不是简单的使得i从0开始，i++，j=i，j++，而是需要i从最大值开始，即字符串的长度-1开始，i--，j=i，j++，先求出小范围内下标大的dp情况，再求出大范围内下标小的情况，因为后者依赖前者。例如dp[0][3]依赖dp[1][2]的值。
public static String longestPalindrome(String str) {int len = str.length();boolean[][] dp = new boolean[len][len];//回文串最大长度，开始下标，结束下标int max = 0;int start = 0;int stop = 0;//先从下标大的元素开始，因为dp[0][8]依赖dp[2][6]for (int i = len - 1; i >= 0; i--) {for (int j = i; j < len; j++) {if (str.charAt(i) == str.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {dp[i][j] = true;if (max < j - i + 1) {max = j - i + 1;start = i;stop = j;}}}}return str.substring(start, stop + 1);}
往
期
推
荐
1、
2、
3、
4、
5、
6、
7、
1、
2、
3、
4、
5、
6、
7、
点分享
点收藏
点点赞
点在看