1.选择排序将已排序部分定义在左端，然后选择未排序部分的最小元素和未排序部分的第一个元素交换。
2.冒泡排序将已排序部分定义在右端，在遍历未排序部分的过程执行交换，将最大元素交换到最右端。
3.插入排序将已排序部分定义在左端，将未排序部分元的第一个元素插入到已排序部分合适的位置。
一. 冒泡排序
- 从头开始比较每一对相邻元素，如果第1个比第2个大，就交换它们的位置
✓ 执行完一轮后，最末尾那个元素就是最大的元素 - 忽略 1 中曾经找到的最大元素，重复执行步骤 1，直到全部元素有序
public static void bubbleSort(int[] array){
for ( int i = 0; i< array.length-1; i++ ){
for ( int j = 0; j < array.length-1-i; j++ ) {
if ( array[j] > array[j+1] ){
int tem = array[j];
array[j] = array[j+1];
array[j+1] = tem;
}
}
}
}
static void bubbleSort(Integer[] array) {
for (int end = array.length - 1; end > 0; end--) {
for (int begin = 1; begin <= end; begin++) {
if (array[begin] < array[begin - 1]) {
int tmp = array[begin];
array[begin] = array[begin - 1];
array[begin - 1] = tmp;
}
}
}
}
优化一: 如果序列已经完全有序，可以提前终止冒泡排序
static void bubbleSort2(Integer[] array) {
for (int end = array.length - 1; end > 0; end--) {
boolean sorted = true;
for (int begin = 1; begin <= end; begin++) {
if (array[begin] < array[begin - 1]) {
int tmp = array[begin];
array[begin] = array[begin - 1];
array[begin - 1] = tmp;
sorted = false;
}
}
if (sorted) break;
}
}
优化二: 如果序列尾部已经局部有序，可以记录最后1次交换的位置，减少比较次数
static void bubbleSort3(Integer[] array) {
for (int end = array.length - 1; end > 0; end--) {
// sortedIndex的初始值在数组完全有序的时候有用
int sortedIndex = 1;
for (int begin = 1; begin <= end; begin++) {
if (array[begin] < array[begin - 1]) {
int tmp = array[begin];
array[begin] = array[begin - 1];
array[begin - 1] = tmp;
sortedIndex = begin;
}
}
end = sortedIndex;
}
}
二. 选择排序
首先在未排序序列中找到最小元素，存放到排序序列的起始位置;
然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。
public static void selectSort(int[] array){
for ( int i = 0; i<array.length; i++ ){
int minIndex = I;
for ( int j = i; j < array.length; j++ ) {
if( array[minIndex] > array[j] ) {
minIndex = j; // 将最小数的索引保存
}
}
int tem = array[minIndex];
array[minIndex] = array[I];
array[i] = tem;
}
}
三. 插入排序
public static void insertSort(int[] array){
for ( int i= 1; i<array.length; i++){
for(int j= i; j>0 && array[j-1] > array[j] ; j--){
int tem = array[j-1];
array[j-1] = array[j];
array[j] = tem;
}
}
}
优化:将【交换】转为【挪动】
① 先将待插入的元素备份
② 头部有序数据中比待插入元素大的，都朝尾部方向挪动1个位置
③ 将待插入元素放到最终的合适位置
public static void insertSort2(int[] array){
for (int i = 1; i < array.length; i++) {
int e = array[i];// 寻找元素e的插入合适位置;
int j;
for(j = i; j>0 && array[j-1] > e; j--){
array[j] = array[j-1];
}
array[j] = e;
}
}
因为插入排序可以提前结束循环,所以当数据中逆序对的数量极少时，插入排序的效率特别高;甚至速度比 O (nlogn) 级别的快速排序还要快;
// 对arr[l...r]的区间使用InsertionSort排序
public static void sort(Comparable[] arr, int l, int r){
for( int i = l + 1 ; i <= r ; i ++ ){
Comparable e = arr[i];
int j = I;
for( ; j > l && arr[j-1].compareTo(e) > 0 ; j--)
arr[j] = arr[j-1];
arr[j] = e;
}
}
四. 归并排序
① 不断地将当前序列平均分割成2个子序列
✓ 直到不能再分割（序列中只剩1个元素）
② 不断地将2个子序列合并成一个有序序列
✓ 直到最终只剩下1个有序序列
public static void mergeSort(int[] array) {
_sort(array, 0, array.length - 1);
}
//递归使用归并排序,对arr[l...r]的范围进行排序
public static void _sort(int[] array, int l, int r) {
if (l >= r) return;
int mid = (r - l) / 2 + l;// (r+l)/2
_sort(array, l, mid);
_sort(array, mid + 1, r);
_merge(array, l, mid, r);
}
// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
public static void _merge(int[] arr, int l, int mid, int r) {
int[] aux = Arrays.copyOfRange(arr,l,r+1);
// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
int i = l, j = mid+1;
for( int k = l ; k <= r; k ++ ){
if( i > mid ){ // 如果左半部分元素已经全部处理完毕
arr[k] = aux[j-l]; j ++;
}
else if( j > r ){ // 如果右半部分元素已经全部处理完毕
arr[k] = aux[i-l]; i ++;
}
else if( aux[i-l] < aux[j-l] ) { // 左半部分所指元素 < 右半部分所指元素
arr[k] = aux[i-l]; i ++;
}
else{ // 左半部分所指元素 >= 右半部分所指元素
arr[k] = aux[j-l]; j ++;
}
}
}
优化：
// 递归使用归并排序,对arr[l...r]的范围进行排序
private static void sort(int[] arr, int l, int r) {
// 优化2: 对于小规模数组, 使用插入排序
if (r - l <= 15) {
InsertionSort.sort(arr, l, r);
return;
}
int mid = (l + r) / 2;
sort(arr, l, mid);
sort(arr, mid + 1, r);
// 优化1: 对于arr[mid] <= arr[mid+1]的情况,不进行merge
// 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
if (arr[mid] > arr[mid + 1])
_merge(arr, l, mid, r);
}
Merge Sort是我们学习的第一个O(nlogn)复杂度的算法。它可以在1秒之内轻松处理100万数量级的数据。 注意：不要轻易尝试使用SelectionSort, InsertionSort或者BubbleSort处理100万级的数据，否则，你就见识了O(n^2)的算法和O(nlogn)算法的本质差异：）
归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。
五. 快速排序
① 从序列中选择一个轴点元素（pivot）
✓ 假设每次选择 0 位置的元素为轴点元素
② 利用 pivot 将序列分割成 2 个子序列
✓ 将小于 pivot 的元素放在pivot前面（左侧）
✓ 将大于 pivot 的元素放在pivot后面（右侧）
✓ 等于pivot的元素放哪边都可以
③ 对子序列进行 ① ② 操作
✓ 直到不能再分割（子序列中只剩下1个元素）
【注意】 在轴点左右元素数量比较均匀的情况下，同时也是最好的情况，时间复杂度O(nlogn)。 如果轴点左右元素数量极度不均匀，比如已经排好序的数组，最坏的情况时间复杂度就会降到 O(n^2)。 为了降低最坏情况的出现概率，一般采取的做法是 随机选择轴点元素。
public static void sort(Integer[] arr) {
sort(arr, 0, arr.length - 1);
}
// 递归使用快速排序,对arr[l...r]的范围进行排序
private static void sort(Integer[] arr, int l, int r) {
// 对于小规模数组, 使用插入排序
if (r - l <= 15) {
InsertionSort.sort(arr, l, r);
return;
}
// if (l >= r) return;
int p = partition(arr, l, r);
sort(arr, l, p - 1);
sort(arr, p + 1, r);
}
// 对arr[l...r]部分进行partition操作
// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
private static int partition(Integer[] arr, int l, int r) {
// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
swap(arr, l, (int) (Math.random() * (r - l + 1)) + l);
Integer v = arr[l];
int j = l; // arr[l+1...j] < v ; arr[j+1...i) > v
for (int i = l + 1; i <= r; i++) {
if (arr[i] < v) {
j++;
swap(arr, j, i);
}
}
swap(arr, l, j);
return j;
}
【注意】
当数组中有大量重复元素的时候我们就会发现，此时无论我们将等于V的元素放到左边还是右边都会造成分配的极度不平衡，此时该算法又会退化为接近O(n^2)，如下图所示：
三路快排
三路快排
public static void sort(Integer[] array) {
_quickSort(array, 0, array.length - 1);
}
// 递归使用快速排序,对arr[l...r]的范围进行排序
public static void _quickSort(Integer[] array, int l, int r) {
if (l >= r) return;
// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
Random random = new Random();
Integer ranInt = random.nextInt(r - l + 1) + l;
swap(array, l, ranInt);
Integer e = array[l];// 比较基准
int lt = l; // arr[l+1...lt] < v
int gt = r + 1; // arr[gt...r] > v
int i = l + 1; // arr[lt+1...i) == v
while (i < gt) {
if (array[i] < e) {
swap(array, i, lt + 1);
lt++;
I++;
} else if (array[i] > e) {
swap(array, i, gt - 1);
gt--;
} else {// arr[i] == v
I++;
}
}
swap(array, l, lt);
_quickSort(array, l, lt - 1);
_quickSort(array, gt, r);
}
public static void swap(Integer[] array, int l, int r) {
Integer tem = array[l];
array[l] = array[r];
array[r] = tem;
}
六、 二分查找
public static int binarySearch(Integer[] arr, Integer target){
int l = 0, r = arr.length - 1; // 在[l...r]的范围里寻找target
while(l <= r){ // 当 l == r时,区间[l...r]依然是有效的
int mid = l + (r - l) / 2;
if(arr[mid] == target) return mid;
if(target > arr[mid])
l = mid + 1; // target在[mid+1...r]中; [l...mid]一定没有target
else // target < arr[mid]
r = mid - 1; // target在[l...mid-1]中; [mid...r]一定没有target
}
return -1;
}
链表问题
141
思路： 使用快慢指针，龟兔赛跑；
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
206
反转链表
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while(curr != null){
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
92.
解题思路：
我们可以将反转部分的各个节点头插到反转部分的前一个节点，具体做法如下：
我们需要三个指针pre、cur和next，pre指针永远指向反转部分的前一个节点，cur则用来遍历反转部分，next永远指向cur的下一个节点：
第一步，先将cur的next指向next的next：
第二步，将next的next指向pre->next：
注意这里的next的next指向的一定是pre的next，而不是cur，因为cur的位置是一直往后走的，只有指向pre的next才是头插。
第三步，将pre的next指向next
最后我们的cur其实并不用再往后走了。
以上操作总共需要执行right - left次，因为一共有right - left个节点需要反转。
最后返回dumbNode的next即可
public ListNode reverseBetween(ListNode head, int m, int n) {
if(head == null) return null;
ListNode dummy = new ListNode(0); // create a dummy node to mark the head of this list
dummy.next = head;
ListNode pre = dummy; // make a pointer pre as a marker for the node before reversing
for(int i = 0; i<m-1; i++) pre = pre.next;
ListNode curr = pre.next; // a pointer to the beginning of a sub-list that will be reversed
ListNode next = null; // a pointer to a node that will be reversed
// 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, then = 3
// dummy-> 1 -> 2 -> 3 -> 4 -> 5
for(int i=0; i<n-m; I++)
{
next = curr.next;
curr.next = next.next;
next.next = pre.next;
pre.next = next;
}
// first reversing : dummy->1 - 3 - 2 - 4 - 5; pre = 1, start = 2, then = 4
// second reversing: dummy->1 - 4 - 3 - 2 - 5; pre = 1, start = 2, then = 5 (finish)
return dummy.next;
}
203 移除链表元素
image.png
public ListNode removeElements(ListNode head, int val) {
//创建一个虚拟头结点
ListNode dummyNode=new ListNode(val-1);
dummyNode.next=head;
ListNode prev=dummyNode;
//确保当前结点后还有结点
while(prev.next!=null){
if(prev.next.val==val){
prev.next=prev.next.next;
}else{
prev=prev.next;
}
}
return dummyNode.next;
}
递归写法
public ListNode removeElements(ListNode head, int val) {
if(head == null) return head;
head.next = removeElements(head.next,val);
return head.val == val ? head.next : head;
}
83
public ListNode deleteDuplicates(ListNode head) {
ListNode curr = head;
while(curr != null && curr.next != null){
if(curr.val == curr.next.val){
curr.next = curr.next.next;
}else{
curr = curr.next;
}
}
return head;
}
递归写法：
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
head.next = deleteDuplicates(head.next);
return head.val == head.next.val ? head.next:head;
}
82
【思路】新建链表头结点指针 dummy， 如果当前节点cur的值与下一个节点的值相同，两个节点都需要被删除。为了保证删除链表之后的链表仍然是相连的，当前节点的前一个节点pre 和后边比cur值大的节点相连。
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy, curr = head;
while(curr != null){
while(curr.next != null && curr.val == curr.next.val){
curr = curr.next;
}
if(prev.next == curr){
prev = prev.next;
}else{
prev.next = curr.next;
}
curr = curr.next;
}
return dummy.next;
}
递归解法：
public ListNode deleteDuplicates (ListNode head){
if (head == null || head.next == null) return head;
if (head.val != head.next.val) {
head.next = deleteDuplicates(head.next);
return head;
} else {
while (head.next != null && head.val == head.next.val)
head = head.next;
return deleteDuplicates(head.next);
}
}
}
86
We have given a list and a value x, we have to partion the list in such that smaller value then x comes to left & greater or equals to right.
解题思路：
将所有小于给定值的节点取出组成一个新的链表，此时原链表中剩余的节点的值都大于或等于给定值，只要将原链表直接接在新链表后即可
public ListNode partition(ListNode head, int x) {
ListNode left = new ListNode(0);
ListNode right = new ListNode(0);
ListNode leftTail = left;
ListNode rightTail = right;
while(head != null){
if(head.val < x){
leftTail.next = head;
leftTail = leftTail.next;
}
else{
rightTail.next = head;
rightTail = rightTail.next;
}
head = head.next;
}
leftTail.next = right.next;
rightTail.next = null;
return left.next;
}
328
根据节点编号的奇偶性，我们可以将奇数节点和偶数节点分离成奇数链表和偶数链表，然后将偶数链表连接在奇数链表之后，合并后的链表即为结果链表。
具体过程如下：
1、从前往后遍历整个链表，遍历时维护四个指针：奇数链表头结点，奇数链表尾节点，偶数链表头结点，偶数链表尾节点。
2、遍历时将位置编号是奇数的节点插在奇数链表尾节点后面，将位置编号是偶数的节点插在偶数链表尾节点后面。
3、遍历完整个链表后，将偶数链表头结点插在奇数链表尾节点后面即可。
public ListNode oddEvenList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode oddHead = head, evenHead = head.next;
ListNode oddTail = oddHead, evenTail = evenHead;
while(evenTail != null && evenTail.next != null){
oddTail.next = oddTail.next.next;
evenTail.next = evenTail.next.next;
oddTail = oddTail.next;
evenTail = evenTail.next;
}
oddTail.next = evenHead;
return oddHead;
}
更简洁的版本：
public ListNode oddEvenList(ListNode head) {
if (head != null) {
ListNode odd = head, even = head.next, evenHead = even;
while (even != null && even.next != null) {
odd.next = odd.next.next;
even.next = even.next.next;
odd = odd.next;
even = even.next;
}
odd.next = evenHead;
}
return head;
}
2
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
第一步
第二步
第三步
第四步
第五步
第六步
第七步
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pre = new ListNode(0);
ListNode cur = pre;
int carry = 0;
while(l1 != null || l2 != null) {
int x = l1 == null ? 0 : l1.val;
int y = l2 == null ? 0 : l2.val;
int sum = x + y + carry;
carry = sum / 10;
sum = sum % 10;
cur.next = new ListNode(sum);
cur = cur.next;
if(l1 != null)
l1 = l1.next;
if(l2 != null)
l2 = l2.next;
}
if(carry == 1) {
cur.next = new ListNode(carry);
}
return pre.next;
}
445
image.png
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
while (l1 != null) {
stack1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode head = null;
while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) {
int sum = carry;
sum += stack1.isEmpty()? 0: stack1.pop();
sum += stack2.isEmpty()? 0: stack2.pop();
// 头插法
ListNode node = new ListNode(sum % 10);
node.next = head;
head = node;
carry = sum / 10;
}
return head;
}
}
21 合并两个有序链表
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(-1);
ListNode prev = dummyHead;
while(l1 != null && l2 != null){
if(l1.val <= l2.val){
prev.next = l1;
l1 = l1.next;
}else{
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
prev.next = l1 == null ? l2 : l1;
return dummyHead.next;
}
递归思路
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
else if (l2 == null) {
return l1;
}
else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
24 两两交换链表中的节点
解题思路：
返回值：交换完成的子链表
调用单元：设需要交换的两个点为 head 和 next，head 连接后面交换完成的子链表，next 连接 head，完成交换
终止条件：head 为空指针或者 next 为空指针，也就是当前无节点或者只有一个节点，无法进行交换
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode next = head.next;
head.next = swapPairs(next.next);
next.next = head;
return next;
}
非递归写法：
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy;
while(prev.next != null && prev.next.next != null){
ListNode curr = prev.next;
ListNode next = curr.next;
prev.next = next;
curr.next = next.next;
next.next = curr;
prev = curr;
}
return dummy.next;
}
25 k个一组翻转链表
19 删除链表的倒数第N个节点
解题思路：
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy,tail = dummy;
for (int i =0; i<n+1; i++){
tail = tail.next;
}
while (tail != null){
tail = tail.next;
prev = prev.next;
}
prev.next = prev.next.next;
return dummy.next;
}
第二种思路 暴力求解，遍历链表获取长度
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
int length = getLength(head);
ListNode cur = dummy;
//为了与题目中的 n 保持一致，节点的编号从 1 开始，头节点为编号 1 的节点。
for (int i = 1; i < length - n + 1; ++i) {
cur = cur.next;
}
cur.next = cur.next.next;
ListNode ans = dummy.next;
return ans;
}
public int getLength(ListNode head) {
int length = 0;
while (head != null) {
length++;
head = head.next;
}
return length;
}
我们也可以在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则，我们弹出栈的第 n 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。这样一来，删除操作就变得十分方便了。
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
Deque<ListNode> stack = new LinkedList<ListNode>();
ListNode cur = dummy;
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
for (int i = 0; i < n; ++i) {
stack.pop();
}
ListNode prev = stack.peek();
prev.next = prev.next.next;
return dummy.next;
}
