面试常用算法(java)
1. 排序
1. 冒泡排序（O(n2)）
把最大的沉到最后，两两交换
public void bubbleSort(int[] nums) {
// 外层循环控制排序的轮数
for (int i = nums.length - 1 ; i > 0; i--) {
boolean isSorted = true;
// 内层循环每次将未排序序列中最大的数冒泡到最后端
for (int j = 0; j nums[j+1]) {
swap(nums,j,j+1);
isSorted = false;
}
}
if (isSorted) {
break;
}
}
}
2. 快速排序(O(nlogn))
哨兵
public void quickSort(int[] nums,int l, int r) {
if (l < r) {
int q = partition(nums,l,r);
quickSort(nums,l,q-1);
quickSort(nums,q+1,r);
}
}
private int partition(int[] nums, int l, int r) {
// 临界值，哨兵
int tmp = nums[l];
int i = l, j = r;
while (i != j) {
// 都带等号
while (i < j && tmp <= nums[j]) {
j--;
}
while (i = nums[i]) {
i++;
}
if (i < j) {
swap(nums,i,j);
}
}
// 将基准数归位，放在中间位置
nums[l] = nums[i];
nums[i] = tmp;
return i;
}
3. 选择排序(O(n2))
每次选出最小的放到端点处
public void selectSort(int[] nums) {
for (int i = 0 ; i < nums.length; i++) {
int index = i;
for (int j = i+1; j < nums.length;j++) {
// 找出最小的，放在端点处
if (nums[j] < nums[index]) {
index = j;
}
}
swap(nums,i,index);
}
}
4. 插入排序(O(n2))
把当前的数(nums[i])插入到之前已经排好序的数组中
public void insertSort(int[] nums) {
for (int i = 1; i 0 && nums[j-1] > tmp) {
nums[j] = nums[j-1];
j--;
}
nums[j] = tmp;
}
}
5. 二分插入排序(O(nlogn))
public void binaryInsertSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
int tmp = nums[i];
int l = 0, r = i-1;
// l <= r
while (l <= r) {
int mid = l + (r-l)/2;
if (nums[mid] = l; j--) {
nums[j+1] = nums[j];
}
// 插入
nums[l] = tmp;
}
}
链表：
1. 判断相交
相同的尾节点
2. 找到交点
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode l1 = pHead1, l2 = pHead2;
while (l1 != l2) {
l1 = (l1 == null) ? pHead2 : l1.next;
l2 = (l2 == null) ? pHead1 : l1.next;
}
return l1;
}
3. 判断环
快慢指针
4. 找到环的入口
public ListNode EntryNodeOfLoop(ListNode pHead)
{
if (pHead == null || pHead.next == null || pHead.next.next ==null) {
return null;
}
ListNode fast = pHead.next.next;
ListNode slow = pHead.next;
// 判断有环
while (slow != fast) {
if (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
else {
return null;
}
}
fast = pHead;
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
5. 链表反转
public ListNode ReverseList(ListNode head) {
ListNode pre = null, next = null, reverseHead = null;
ListNode pNode = head;
while (pNode != null) {
next = pNode.next;
pNode.next = pre;
pre = pNode;
pNode = next;
if (pNode == null) {
reverseHead = pre;
}
}
return reverseHead;
}
6. 删除链表中的重复节点
7. 倒数第k个节点
一个先走k-1步，另一个再开始，第一个到头的时候第二个所在的位置
public ListNode FindKthToTail(ListNode head,int k) {
if (head == null || k < 0) {
return null;
}
ListNode p1 = head,p2= head;
for (int i = 0 ; i < k; i++) {
if (p1 == null ){
return null;
}
p1 = p1.next;
}
while (p1 != null) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
8. 合并两个有序链表
public ListNode Merge(ListNode list1,ListNode list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
if (list1.val <= list2.val) {
list1.next = Merge(list1.next,list2);
return list1;
}
else {
list2.next = Merge(list1,list2.next);
return list2;
}
}
9. 复制链表
二叉树：
https://blog.csdn.net/weixin_39795049/article/details/89036538
作者：Nicole_sss
相关文章
Serafina
2021-03-06
Miki
2020-07-14
Serafina
2020-03-27
Isabella
2021-05-28
Radinka
2023-07-20
Tertia
2023-07-21
Xylona
2023-07-21
Rabia
2023-07-21
Linnea
2023-07-21
Jennifer
2023-07-21
Jayne
2023-07-21
Maleah
2023-07-21
Bella
2023-07-21
Coral
2023-07-21
Talia
2023-07-21
Valora
2023-07-21
Summer
2023-07-21
Rose
2023-07-22
