面试常见高频算法题总结
- 格式：pdf
- 大小：142.88 KB
- 文档页数：5
⾯试常见⾼频算法题总结
⼀、链表相关
1.链表反转
class Solution {
public ListNode reverseList(ListNode head) {
// base case
if(head == null || head.next == null) return head;
ListNode first = head;
ListNode result = null;//建⽴⼀个新的节点⽤来存放结果
ListNode second = null;
while(first != null){ //遍历输⼊链表，开始处理每⼀个节点
second = first.next; //先处理第⼀个节点first，所以需要⼀个指针来存储first的后继
first.next = result; //将first放到新链表头节点的头部
result = first; //移动新链表的头指针，让它始终指向新链表头部
first = second; //继续处理原链表的节点，即之前指针存放的后继，循环往复
}
return result;
}
}
2.k个⼀组翻转链表(⼒扣 25) --------⽐较难
3.判断链表是否有环
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {//设置快慢指针，若有环⼀定会在环⾥⾯相遇。否则会有null值
if(head==null) return false;
ListNode walker = head;
ListNode runner = head;
while(runner.next!=null && runner.next.next!=null) {
walker = walker.next;
runner = runner.next.next;
if(walker==runner) return true;
}
return false;
}
}
//也可以采⽤hashmap把每⼀个节点存储起来，如果地址相同则存在节点
⼆、数组、字符串巧妙解法相关
1.不使⽤除法实现除⾃⾝外数组元素的乘积（⼒扣 238）
public class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] res = new int[n];
res[0] = 1;
for (int i = 1; i < n; i++) {
res[i] = res[i - 1] * nums[i - 1];
}
int right = 1;
for (int i = n - 1; i >= 0; i--) {
res[i] *= right;
right *= nums[i];
}
return res;
}
}
⼆、树相关
1.给定⼀颗⼆叉搜索树，返回该⼆叉搜索树第K⼤的节点
//思路：⼆叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。
// 所以，按照中序遍历顺序找到第k个结点就是结果。
public class Solution {
int index = 0; //计数器
TreeNode KthNode(TreeNode root, int k)
{
if(root != null){ //中序遍历寻找第k个
TreeNode node = KthNode(root.left,k);
if(node != null)
return node;
index ++;
if(index == k)
return root;
node = KthNode(root.right,k);
if(node != null)
return node;
}
return null;
}
}
2.⼆叉树最⼩深度
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left; * TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
//为什么采⽤分治的思想⽽不是求数最⼤深度思想，因为可能为单链表（链表是特殊树）没法处理
class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
return (left == 0 || right == 0) ? left + right + 1//为什么可以写成left + right + 1
: Math.min(left,right) + 1; //因为left 跟right 必有⼀个为0，所以..
}
}
3.⼆叉树最⼤深度
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
} else{
return 1+ Math.max(maxDepth(root.left), maxDepth(root.right));
}
}
}
三、动态规划相关
1.两个字符串的最长公共⼦序列长度
class Solution {
//dp[i][j]表⽰ 0-(i-1) 0-(j-1)之间最长⼦序列
public int longestCommonSubsequence(String s1, String s2) {
int[][] dp = new int[s1.length() + 1][s2.length() + 1];
for (int i = 0; i < s1.length(); ++i)
for (int j = 0; j < s2.length(); ++j)
if (s1.charAt(i) == s2.charAt(j)) dp[i + 1][j + 1] = 1 + dp[i][j];
else dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
return dp[s1.length()][s2.length()];
}
}
2.求连续⼦数组的最⼤和
class Solution {
public static int maxSubArray(int[] A) {
int maxSoFar=A[0], maxEndingHere=A[0];
for(int i=1;i
maxEndingHere = Math.max(A[i], maxEndingHere+A[i]);
maxSoFar = Math.max(maxEndingHere, maxSoFar);
}
return maxSoFar;
}
}
四、排序
1.快排
public static void quickSort(int[] list, int left, int right) {
if (left < right) {
// 分割数组，找到分割点
int point = partition(list, left, right);
// 递归调⽤，对左⼦数组进⾏快速排序
quickSort(list, left, point - 1);
// 递归调⽤，对右⼦数组进⾏快速排序
quickSort(list, point + 1, right);
}
}
/**
* 分割数组，找到分割点
*/ public static int partition(int[] list, int left, int right) {
// ⽤数组的第⼀个元素作为基准数
int first = list[left];
while (left < right) {
while (left < right && list[right] >= first) {
right--;
}
// 交换
swap(list, left, right);
while (left < right && list[left] <= first) {
left++;
}
// 交换
swap(list, left, right);
}
// 返回分割点所在的位置
return left;
}
/**
* 交换数组中两个位置的元素
*/
public static void swap(int[] list, int left, int right) {
int temp;
if (list != null && list.length > 0) {
temp = list[left];
list[left] = list[right];
list[right] = temp;
}
}
2.⼆路归并排序
public class MergeSort {
/**
* 归并排序（Merge Sort）与快速排序思想类似：将待排序数据分成两部分，继续将两个⼦部分进⾏递归的归并排序；然后将已经有序的两个⼦部分进⾏合并，最终完成排序。
* 其时间复杂度与快速排序均为O(nlogn)，但是归并排序除了递归调⽤间接使⽤了辅助空间栈，还需要额外的O(n)空间进⾏临时存储。从此⾓度归并排序略逊于快速排序，但是归并排序是⼀种稳定的排序算法，快速排序则不然。
* 所谓稳定排序，表⽰对于具有相同值的多个元素，其间的先后顺序保持不变。对于基本数据类型⽽⾔，⼀个排序算法是否稳定，影响很⼩，但是对于结构体数组，稳定排序就⼗分重要。例如对于student结构体按照关键字score进⾏⾮降序排序：
*/
public static void main(String[] args) {
int[] list = {50, 10, 90, 30, 70};
System.out.println("************归并排序************");
System.out.println("排序前：");
display(list);
System.out.println("排序后：");
mergeSort(list, new int[list.length], 0, list.length - 1);
display(list);
}
/**
* 归并排序算法
* @param list 待排序的列表
* @param tempList 临时列表
* @param head 列表开始位置
* @param rear 列表结束位置
*/
public static void mergeSort(int[] list, int[] tempList, int head, int rear) {
