文章目录
前置基础知识
1、快速排序的基本思想： 快速排序使用分治的思想，通过一趟排序将待排序列分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
2、快速排序的三个步骤：
(1)选择基准：在待排序列中，按照某种方式挑出一个元素，作为 “基准”（pivot）
(2)分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大
(3)递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。
3、选择基准的方式
对于分治算法，当每次划分时，算法若都能分成两个等长的子序列时，那么分治算法效率会达到最大。也就是说，基准的选择是很重要的。选择基准的方式决定了两个分割后两个子序列的长度，进而对整个算法的效率产生决定性影响。
最理想的方法是，选择的基准恰好能把待排序序列分成两个等长的子序列
随机算法与快速排序
注意！！！
即便对于随机算法，无论是计算期望运行时间还是最坏运行时间，我们都依然考虑最坏的输入。
期望运行时间不是输入为期望输入时的运行时间！我们讨论的是算法中随机部分的期望，不是所有可能输入的期望值。
（猴子排序）
再来看快速排序
和的期望=期望的和
//快速排序c++版本 01
void quick_sort_v1(int *arr, int l, int r){
if(l >= r) return;
int x = l, y = r, base = arr[l];
while(x <= y){
while(x <= y && arr[y] > base){
y--;
}
while(x <= y && arr[x] < base){
x++;
}
if(x <= y){
swap(arr[x], arr[y]);
x++, y--;//两个箭头继续相向而行
}
}
quick_sort_v1(arr, l, y);
quick_sort_v1(arr, x, r);
return;
}
int main(){
int arr[6] = {9, 5, 1, 4, 0, 7};
quick_sort_v1(arr, 0, 5);
for(int i = 0; i < 6; i++){
cout << arr[i] << endl;
}
return 0;
}
从C++STL 学习快速排序
- 单边递归法
- 三点取中法
- 特殊数据，停止快排(具体使用的是堆排序，此时堆排序虽然不能使用好CPU一读读一段数据的特性，但是它很稳定)
- 使用插入排序进行收尾
- 无监督写法(不太重要)：泛指一种编程技巧，在函数的实现过程中，尽量少使用条件判断
算法题实战
排序数组
/**
* 排序数组
* @author: William
* @time:2022-04-23
*/publicclassNum912{publicint[]sortArray(int[] nums){quick_sort(nums,0, nums.length -1);return nums;}publicvoidquick_sort(int[] nums,int l,int r){__quick_sort(nums, l, r);final_insert_sort(nums, l, r);//插入排序优化}publicvoidswap(int[] nums,int l,int r){int t = nums[l];
nums[l]= nums[r];
nums[r]= t;}publicintmedian(int a,int b,int c){int max =Math.max(a,Math.max(b, c));int min =Math.min(a,Math.min(b, c));if(a != max && a != min)return a;if(c != max && c != min)return c;//或者这样// if(a > b) swap(a, b);// if(a > c) swap(a, c);// if(b > c) swap(b, c);return b;}publicvoid__quick_sort(int[] nums,int l,int r){while(r - l >16){int i = l, j = r;double m =median(nums[l], nums[r], nums[(l + r)/2]);//三点取中优化// do {// while(nums[i] < m) i++;// while(nums[j] > m) j--;// if(i <= j) {//此时i j没有错位// swap(nums, i, j);// i++;// j--;// }// }while(i <= j);//此时左边都小于中间值//while写法while(i <= j){while(i <= j && nums[i]< m){
i++;}while(i <= j && nums[j]> m){
j--;}if(i <= j){//此时上面循环停了，需要交换两个值swap(nums, i, j);
i++;
j--;}}__quick_sort(nums, i, r);//把右边的都排好
r = j;//再来排左边 单边递归优化}}publicvoidfinal_insert_sort(int[] nums,int l,int r){int index = l;for(int i = l +1; i <= r; i++){if(nums[i]< nums[index]){
index = i;//找到数组中最小元素}}while(index > l){swap(nums, index, index -1);//把index挪到第一个
index--;}for(int i = l +2; i <= r; i++){int j = i;while(nums[j]< nums[j -1]){//也是从后往前一个个比较 插入排序优化swap(nums, j, j -1);
j--;}}}}
排序链表
/**
* 排序链表
* @author: William
* @time:2022-04-23
*/classListNode{int val;ListNode next;ListNode(){}ListNode(int val){this.val = val;}ListNode(int val,ListNode next){this.val = val;this.next = next;}}publicclassNum148{//快排方法publicListNodesortList(ListNode head){if(head ==null)return head;int l = head.val, r = head.val;double m;ListNode h1 =null, h2 =null, p =null, q =null;//寻找基准值
p = head;while(p !=null){
l =Math.min(l, p.val);
r =Math.max(r, p.val);
p = p.next;}if(l == r)return head;//终止条件很重要
m =(l + r)/2.0;
p = head;//根据基准值分割链表while(p !=null){
q = p.next;if(p.val <= m){//小于基准值
p.next = h1;
h1 = p;}else{//大于基准值
p.next = h2;
h2 = p;}
p = q;//p去找q}//递归排序子链表
h1 =sortList(h1);
h2 =sortList(h2);
p = h1;//连接子链表while(p.next !=null){
p = p.next;}
p.next = h2;return h1;}//归并排序方法 - 递归版publicListNodesortList1(ListNode head){if(head ==null|| head.next ==null)return head;//快慢指针ListNode fast = head.next, slow = head;while(fast !=null&& fast.next !=null){
slow = slow.next;
fast = fast.next.next;}ListNode tmp = slow.next;//此时tmp位于链表中间
slow.next =null;//链表断开ListNode left =sortList(head);ListNode right =sortList(tmp);ListNode h =newListNode(0);ListNode res = h;while(left !=null&& right !=null){if(left.val < right.val){
h.next = left;
left = left.next;}else{
h.next = right;
right = right.next;}
h = h.next;}
h.next = left !=null? left : right;//左边为空h就把他们连起来return res.next;}}
盛水最多的容器
/**
* 盛水最多的容器
* @author: William
* @time:2022-04-25
*/publicclassNum11{publicintmaxArea(int[] height){//注意j的位置，别超出数组长度了int i =0, j = height.length -1, res =0;while(i < j){// res = height[i] < height[j] ?// //因为矩形的面积取决于短板// Math.max(res, (j - i) * height[i++]):// Math.max(res, (j - i) * height[j--]);//另一种写法
res =Math.max(res,(j - i)*Math.min(height[i], height[j]));if(height[i]< height[j]){
i++;}else{
j--;}}return res;}}
最小K个数
/**
* 最小K个数
* @author: William
* @time:2022-04-24
*/publicclassNum17_14{//快排的核心是分区publicint[]smallestK(int[] arr,int k){int[] ans =newint[k];if(k ==0)return ans;quick_sort(arr,0, arr.length -1, k);for(int i =0; i < k ; i++){
ans[i]= arr[i];}return ans;}privateintgetmid(int a,int b,int c){// int max = Math.max(a, Math.max(b, c));// int min = Math.min(a, Math.min(b, c));// if(a != max && a != min) return a;// if(c != max && c != min) return c;//或者这样 if(a > b)swap(a, b);if(a > c)swap(a, c);if(b > c)swap(b, c);return b;}privatevoidswap(int a,int b){int t = a;
a = b;
b = t;}privatevoidswap(int[] arr,int l,int r){int t = arr[l];
arr[l]= arr[r];
arr[r]= t;}publicvoidquick_sort(int[] arr,int l,int r,int k){if(l >= r)return;//这个三点取中优化力扣不给过 —— 栈溢出int i = l , j = r, mid =getmid(arr[l], arr[r], arr[(l + r)/2]);do{while(arr[i]< mid) i++;while(arr[j]> mid) j--;if(i <= j){swap(arr, i, j);
i++;
j--;}}while(i <= j);if(j - l == k -1)return;//左边区间刚好是k个数if(j - l >= k){//左边多了 继续筛选quick_sort(arr, l , j, k);}else{//左边少 继续填//此时i在j后面一位 i - l == j - l + 1quick_sort(arr, i, r, k - i + l);//注意}return;}//直接排序publicint[]smallestK2(int[] arr,int k){int[] vec =newint[k];Arrays.sort(arr);for(int i =0; i < k;++i){
vec[i]= arr[i];}return vec;}//堆 大根堆publicint[]smallestK3(int[] arr,int k){int[] res =newint[k];if(k ==0)return res;PriorityQueue<Integer> queue =newPriorityQueue<>((a, b)-> b - a);for(int i =0; i < k; i++){//将前k个数插入到大根堆中
queue.offer(arr[i]);}for(int i = k; i < arr.length; i++){//从k+1开始遍历if(queue.peek()> arr[i]){
queue.poll();//大了就弹出换小的
queue.offer(arr[i]);}}for(int i =0; i < k; i++){
res[i]= queue.poll();}return res;}}
剑指offer21 调整数组顺序使奇数位偶数前面
/**
* 剑指offer21 调整数组顺序使奇数位偶数前面
* @author: William
* @time:2022-04-24
*/publicclassNum21{//kkb中的dowhile版本publicint[]exchange(int[] nums){if(nums.length ==0)return nums;int l =0, r = nums.length -1;do{//注意l这个条件很重要 如果都是奇数 l < nums.length - 1程序会超出时间限制while(l < nums.length && nums[l]%2!=0) l++;while(r >=0&& nums[r]%2==0) r--;if(l <= r){int t = nums[l];
nums[l]= nums[r];
nums[r]= t;}}while(l <= r);//k神版本 x&1 位运算 等价于 x % 2 取余运算// while( l < r) {// while(l < r && (nums[l] & 1) == 1) l++;// while(l < r && (nums[r] & 1) == 0) r--;// int t = nums[l];// nums[l] = nums[r];// nums[r] = t;// }return nums;}//一端开始publicint[]exchange1(int[] nums){int slow =0, fast =0;while(fast < nums.length){if((nums[fast]&1)==1)swap(nums, slow++, fast);
fast++;}return nums;}publicvoidswap(int[] nums,int a,int b){int t = nums[a];
nums[a]= nums[b];
nums[b]= t;}}
滑动窗口的最大值
/**
* 滑动窗口的最大值
* @author: William
* @time:2022-04-25
*/publicclassNum239{publicint[]maxSlidingWindow(int[] nums,int k){//if(k == 0) return new int[0]; 或者if(nums ==null|| nums.length <2)return nums;int index =0;List<Integer> res =newArrayList<>();//双向队列保存当前窗口最大值的数组位置 从大到小排序Deque<Integer> deque =newArrayDeque<>();while(index < nums.length){//遍历数组if(!deque.isEmpty()&& deque.getFirst()+ k <= index){//此时代表这个值不属于滑窗中的部分
deque.pollFirst();//队列往前吐出}while(!deque.isEmpty()&& nums[index]> nums[deque.getLast()]){//此时说明最后那个没机会成为最大值 直接吐出
deque.pollLast();}
deque.offerLast(index);//往后滑，就是从后面新增，从前面删除
index++;if(index >= k){//滑动窗口满了//规定维护的双端队列最大值永远放在队列头部
res.add(nums[deque.getFirst()]);}}//把集合转成数组return res.stream().mapToInt(Integer::valueOf).toArray();}//左程云老师的双端队列解法publicint[]maxSlidingWindow2(int[] nums,int k){if(nums ==null|| nums.length <2)return nums;// 双向队列 保存当前窗口最大值的数组位置 保证队列中数组位置的数值按从大到小排序Deque<Integer> queue =newArrayDeque<>();// 结果数组int[] result =newint[nums.length - k +1];// 遍历nums数组for(int i =0;i < nums.length;i++){// 保证从大到小 如果前面数小则需要依次弹出，直至满足要求while(!queue.isEmpty()&& nums[queue.peekLast()]<= nums[i]){
queue.pollLast();}// 添加当前值对应的数组下标
queue.addLast(i);// 判断当前队列中队首的值是否有效if(queue.peek()<= i - k){
queue.poll();}// 当窗口长度为k时 保存当前窗口中最大值if(i +1>= k){
result[i - k +1]= nums[queue.peek()];}}return result;}//优先队列 —— 大根堆publicint[]maxSlidingWindow3(int[] nums,int k){int n = nums.length;//优先队列存放的是而二元组(num, index)//大顶堆：元素大小不同按元素排列，元素大小相同按下标进行排列//num：比较元素大小//index：判断窗口的大小是否超出范围PriorityQueue<int[]> pq =newPriorityQueue<>((pair1, pair2)->{return pair1[0]!= pair2[0]? pair2[0]- pair1[0]: pair2[1]- pair1[1];});for(int i =0; i < k ;++i){//把数组加到大根堆中去
pq.offer(newint[]{nums[i], i});}int[] ans =newint[n - k +1];
ans[0]= pq.peek()[0];//初始化res[0]：拿出堆顶元素for(int i = k; i < n;++i){//向右移动滑动窗口
pq.offer(newint[]{nums[i], i});while(pq.peek()[1]<= i - k){//将下标不再滑动窗口的元素都干掉
pq.poll();//维护：堆的大小就是滑动窗口大小}//此时堆顶元素就是滑动窗口的最大值
ans[i - k +1]= pq.peek()[0];}return ans;}}
字符串解码
/**
* 字符串解码
* @author: William
* @time:2022-04-25
*/publicclassNum394{//递归法publicStringdecodeString(String s){//1. 数字 正常读取//2. 字母 拼接//3. [ 重复k次 调用递归方法 得到子串后作拼接//4. ] 字符串处理完毕 结束递归returndecodeString(s,0)[0];}//如果长度为2： 0 右括号的位置 1 字串//1：只包含结果字串publicString[]decodeString(String s,int i){StringBuffer res =newStringBuffer();int num =0;while(i < s.length()){if(s.charAt(i)>='0'&& s.charAt(i)<='9'){//数字
num = num *10+(s.charAt(i)-'0');//字符串转数字常用工具}elseif(s.charAt(i)=='['){String[] tmp =decodeString(s, i +1);//i+1开始获取
i =Integer.parseInt(tmp[0]);//更新i的位置while(num >0){//拼接
res.append(tmp[1]);
num--;}}elseif(s.charAt(i)==']'){returnnewString[]{String.valueOf(i), res.toString()};//记录当前位置}else{
res.append(s.charAt(i));}
i++;}returnnewString[]{res.toString()};}//k神 —— 辅助栈法publicStringdecodeString1(String s){StringBuffer res =newStringBuffer();int num =0;LinkedList<Integer> stack_multi =newLinkedList<>();LinkedList<String> stack_res =newLinkedList<>();for(Character c : s.toCharArray()){if(c >='0'&& c <='9'){
num = num *10+Integer.parseInt(c +"");}elseif(c =='['){//将num和res入栈 并分别置空
stack_multi.addLast(num);
stack_res.addLast(res.toString());
num =0;
res =newStringBuffer();}elseif(c ==']'){//stack出栈 //拼接res = last_res + cur_multi * resStringBuffer tmp =newStringBuffer();int cur_multi = stack_multi.removeLast();for(int i =0; i < cur_multi; i++) tmp.append(res);
res =newStringBuffer(stack_res.removeLast()+ tmp);}else{//为字母的时候
res.append(c);}}return res.toString();}}
用Rand7()实现Rand10
/**
* 用Rand7()实现Rand10
* @author: William
* @time:2022-04-26
*//**
* The rand7() API is already defined in the parent class SolBase.
* public int rand7();
* @return a random integer in the range 1 to 7
*/publicclassNum470{/**
* 已知 rand_N() 可以等概率的生成[1, N]范围的随机数
那么：
(rand_X() - 1) × Y + rand_Y() ==> 可以等概率的生成[1, X * Y]范围的随机数
即实现了 rand_XY()
通过前面的分析我们发现：
要实现rand10()，就需要先实现rand_N()，并且保证N大于10且是10的倍数。
这样再通过rand_N() % 10 + 1 就可以得到[1,10]范围的随机数了。
(rand7()-1) × 7 + rand7() ==> rand49()
但是这样实现的N不是10的倍数，这就需要"拒绝采样"，
也就是说如果某个采样结果不在要求的范围内，则丢弃它
*/publicintrand7(){//随机生成1-7Random r =newRandom();int x = r.nextInt(7)+1;//或者//int x = (int)(Math.random()*7 + 1);return x;}publicintrand10(){int x =0;while(true){
x =(rand7()-1)*7+rand7();//R49 R10 1~40 R9 1~49if(x <=40){return x %10+1;}
x =(x -40-1)*7+rand7();//R63if(x <=60){return x %10+1;}
x =(x -60-1)*7+rand7();//R21if(x <=20){return x %10+1;}}}}
颜色分类
/**
* 颜色分类
* @author: William
* @time:2022-04-24
*//**
*for循环中++i和i++的区别
语法
for (语句1; 语句2; 语句3)
{
被执行的代码块
}
语句 1 在循环（代码块）开始前执行
语句 2 定义运行循环（代码块）的条件
语句 3 在循环（代码块）已被执行之后执行
这就是循环中的++i和i++结果一样的原因，但是性能不一样，
在大量数据的时候++i的性能要比i++的性能好原因：
i++由于是在使用当前值之后再+1，所以需要一个临时的变量来转存。
而++i则是在直接+1，省去了对内存的操作的环节，相对而言能够提高性能
*
*/publicclassNum75{//输入 0红色 1白色 2蓝色 [0, x] [ ] [y, r]publicvoidsortColors(int[] nums){three_partition(nums,0, nums.length -1);}voidthree_partition(int[] nums,intL,intR){if(L>=R)return;//x 代表红色区间 y 蓝色 i 辅助遍历int x =-1, y =R+1, i =L;//初始化while(i < y){//撞上就代表整理好之前的区间了if(nums[i]==1){//白色就不需要管
i++;}elseif(nums[i]<1){//红色
x++;swap(nums, x, i);//红色区间扩容
i++;}elseif(nums[i]>1){//蓝色
y--;swap(nums, i, y);}}}voidswap(int[] nums,int i,int j){int t = nums[i];
nums[i]= nums[j];
nums[j]= t;}}
不同的二叉搜索树
/**
* 不同的二叉搜索树
* @author: William
* @time:2022-04-25
*/classTreeNode{int val;TreeNode left;TreeNode right;TreeNode(){}TreeNode(int val){this.val = val;}TreeNode(int val,TreeNode left,TreeNode right){this.val = val;this.left = left;this.right = right;}}publicclassNum95{publicList<TreeNode>generateTrees(int n){if(n ==0)returnnewArrayList<TreeNode>();returndfs(1, n);}privateList<TreeNode>dfs(int l,int r){List<TreeNode> ans =newArrayList<>();if(l > r){
ans.add(null);return ans;}for(int i = l; i <= r; i++){//枚举每一个节点List<TreeNode> left_tree =dfs(l, i -1);List<TreeNode> right_tree =dfs(i +1, r);//分别拿出左右子树的组合for(TreeNode left : left_tree){for(TreeNode right : right_tree){TreeNode node =newTreeNode(i, left, right);
ans.add(node);}}}return ans;}}
本文转载自: https://blog.csdn.net/qq_57469718/article/details/125707534
版权归原作者 慢慢敲吧 所有， 如有侵权，请联系我们删除。
版权归原作者 慢慢敲吧 所有， 如有侵权，请联系我们删除。