规模为n的原问题的解无法直接求出,进行问题规模缩减,划分子问题(这里子问题相互独立而且和原问题解的性质是相同的,只是问题规模缩小了)。如果子问题的规模仍然不够小,再进行子问题划分,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止,最后求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解。
分治算法所能解决的问题一般具有以下几个特征:
二分查找算法
#include<iostream>
#include<vector>
using namespace std;
bool binarySearch(int arr[], int i, int j, int val)
{
if (i > j)
return false;
int m = (i + j) >> 1;
if (arr[m] == val)
{
return true;
}
else if (arr[m] < val)
{
return binarySearch(arr, m + 1, j, val);
}
else
{
return binarySearch(arr, i, m - 1, val);
}
}
int main()
{
int arr[] = {
0,5,24,34,41,58,62,64,67,69,78 };
cout << binarySearch(arr, 0, sizeof(arr) / sizeof(arr[0]), 34) << endl;
}
对一组数据{41,67,34,0,69,24,78,58,62,64,5}进行快排
#include<iostream>
#include<vector>
using namespace std;
//快排划分函数,调整基准数
int partition(vector<int>& arr, int l, int r)
{
int val = arr[l];//作为基准数
while (l < r)
{
while (l < r)
{
if (arr[r] < val)//右 - 左,找第一个比val小的
{
arr[l++] = arr[r];
break;
}
r--;
}
while (l < r)
{
if (arr[l] > val)//左 - 右,找第一个比val大的
{
arr[r--] = arr[l];
break;
}
l++;
}
}
arr[l] = val;//放置基准数
return l;//返回基准数的下标
}
void quickSort(vector<int>& arr, int l, int r)
{
if (l >= r)
{
return;
}
int pos = partition(arr, l, r);
quickSort(arr, l, pos - 1);
quickSort(arr, pos + 1, r);
}
int main()
{
vector<int> arr = {
41,67,34,0,69,24,78,58,62,64,5 };
quickSort(arr, 0, arr.size() - 1);
for (int v : arr)
{
cout << v << " ";
}
cout << endl;
}
求topk问题:
两种解法各有优缺点,各自适用于不同的场合,因此在动手做题之前要先搞清楚题目要求,包括输入的数据量有多大、能否一次性载入内存、是否允许交换输入数据中数字的顺序
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//快排划分函数,调整基准数
int partition(vector<int>& vec, int l, int r)
{
int val = vec[l];//作为基准数
while (l < r)
{
while (l < r)
{
if (vec[r] < val)//右 - 左,找第一个比val小的
{
vec[l++] = vec[r];
break;
}
r--;
}
while (l < r)
{
if (vec[l] > val)//左 - 右,找第一个比val大的
{
vec[r--] = vec[l];
break;
}
l++;
}
}
vec[l] = val;//放置基准数
return l;//返回基准数的下标
}
//找第k大的,vec.size()-k小的下标
int max_select_topk(vector<int>& vec, int i, int j, int k)
{
int pos = partition(vec, i, j);
if (pos == vec.size() - k)//基准数的位置和topk的k值相等
{
return pos;
}
if (pos > vec.size() - k)//topk应该在基准数左边
{
return max_select_topk(vec, i, pos - 1, k);
}
else//topk在基准数右边
{
return max_select_topk(vec, pos + 1, j, k);
}
}
//找第k小的,k-1小的下标
int min_select_topk(vector<int>& vec, int i, int j, int k)
{
int pos = partition(vec, i, j);
if (pos == k - 1)
{
return pos;
}
if (pos > k - 1)
{
return min_select_topk(vec, i, pos - 1, k);
}
else
{
return min_select_topk(vec, pos + 1, j, k);
}
}
int main()
{
vector<int> vec;
for (int i = 0; i < 20; i++)
{
vec.push_back(rand() % 100);
}
//求第top10大的元素
int pos = max_select_topk(vec, 0, vec.size() - 1,10);
cout << "第top10大的元素:" << vec[pos] << endl;
cout << "前top10大的元素为:";
for (int i = pos; i < vec.size(); i++)
{
cout << vec[i] << " ";
}
cout << endl;
pos = min_select_topk(vec, 0, vec.size() - 1, 4);
cout << "第top4小的元素:" << vec[pos] << endl;
cout << "前top4小的元素为:";
for (int i = 0; i <= pos; i++)
{
cout << vec[i] << " ";
}
cout << endl;
sort(vec.begin(), vec.end());
for (int v : vec)
{
cout << v << " ";
}
cout << endl;
}
快排的效率和基准数的选择有关,最差是数据已经趋于有序,基准数每次都在边上,二叉树退化为链表,时间复杂度为O(n*n),所以如果数据已经趋于有序,可以随机一个下标作为基准数
直到划分到子问题只剩一个元素了,认为已经是有序的,然后向上回溯,合并子问题的解
合并出原数组的解需要开辟额外的内存空间,写子问题合并后的解,再额外空间的这些数据找到原数组的范围,不能一边遍历一边写,要不然会把数据覆盖。
归并排序的空间复杂度是O(n),时间复杂度是O(nlogn)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void merge(vector<int>& vec, int low, int mid, int high)
{
//定义额外的辅助空间,存储合并的子问题的有序数组
vector<int> tmp;
//不能用resize
//resize()是分配容器的内存大小,而capacity()只是设置容器容量大小,但并没有真正分配内存
tmp.reserve(high - low + 1);
int i = low;//[low,mid]
int j = mid+1;//[mid+1,high]
while (i <= mid && j <= high)
{
vec[i] > vec[j] ? tmp.push_back(vec[j++]) : tmp.push_back(vec[i++]);
}
while (i <= mid)
{
tmp.push_back(vec[i++]);
}
while (j <= high)
{
tmp.push_back(vec[j++]);
}
//tmp里面的元素->vec当中
for (int t : tmp)
{
vec[low++] = t;
}
}
void mergeSort(vector<int>& vec, int i, int j)
{
//子问题划分到一个元素的时候代表子问题的解已知
if (i == j)
{
return;
}
int mid = (i + j) / 2;
//先划分子问题,降低问题规模
mergeSort(vec, i, mid);
mergeSort(vec, mid + 1, j);
//向上回溯,回溯过程中,合并子问题的解
merge(vec, i, mid, j);
}
int main()
{
vector<int> vec;
for (int i = 0; i < 10; i++)
{
vec.push_back(rand() % 100);
}
for (int v : vec)
{
cout << v << " ";
}
cout << endl;
mergeSort(vec, 0, vec.size()-1);
for (int v : vec)
{
cout << v << " ";
}
cout << endl;
}
代码中使用额外内存空间,如果使用vector.push_back的话不能用resize,因为resize会分配内存,并默认值为0,而应该用vector.reserve,设置容器容量大小,不分配内存。
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct ListNode
{
int val;
ListNode* next;
ListNode(int x):val(x),next(nullptr){
}
};
ListNode* init_link(initializer_list<int> list)
{
ListNode* head = nullptr;
ListNode* p = nullptr;
for (int v : list)
{
if (head == nullptr)
{
head = new ListNode(v);
p = head;
}
else
{
p->next = new ListNode(v);
p = p->next;
}
}
return head;
}
ListNode* mergeTwoLink(ListNode* p1, ListNode* p2)
{
ListNode* head = nullptr;
if (p1 == nullptr)
{
return p2;
}
if (p2 == nullptr)
{
return p1;
}
if (p1->val > p2->val)
{
head = p2;
p2 = p2->next;
}
else
{
head = p1;
p1 = p1->next;
}
ListNode* p = head;
while (p1 != nullptr && p2 != nullptr)
{
if (p1->val > p2->val)
{
p->next = p2;
p = p2;
p2 = p2->next;
}
else
{
p->next = p1;
p = p1;
p1 = p1->next;
}
}
p->next = p1 ? p1 : p2;
return head;
}
ListNode* mergeLink(vector<ListNode*>& vlink,int i,int j)
{
if (i >= j)
{
return vlink[i];
}
int mid = (i + j) / 2;
ListNode* left = mergeLink(vlink, i, mid);
ListNode* right = mergeLink(vlink, mid + 1, j);
return mergeTwoLink(left, right);
}
int main()
{
ListNode* p1 = init_link({
1,3,5,7 });
ListNode* p2 = init_link({
2,4,6,8 });
ListNode* p3 = init_link({
0,9 });
ListNode* p4 = init_link({
1,8 });
vector<ListNode*> vlink;
vlink.push_back(p1);
vlink.push_back(p2);
vlink.push_back(p3);
vlink.push_back(p4);
ListNode* p = mergeLink(vlink, 0, vlink.size() - 1);
for (ListNode* c = p; c != nullptr; c = c->next)
{
cout << c->val << " ";
}
cout << endl;
}
偶数个数升序序列的中位数:(n/2+n/2+1)/2
奇数个数升序序列的中位数:n/2
问题:有两个升序的数组,长度分别是m和n,求两个数组所有元素的中位数是多少?要求在O(logn)时间内完成
分析:
在两个升序数组中找中位数的话,那么就是找第topk
个元素,第k个元素就是最中间的那个数字,第k
个元素的值就是max(arr[i-1],brr[j-1])
,中位数对应的下标应该是(m+n+1)/2
。如果找到k,若总长度是偶数,则中位数为(第k个+第k+1个元素)/2 (第k+1
个元素应该是min(arr[i],brr[j])
);若总长度为奇数,则中位数为第k个元素。
所以关键就是如何在对数时间内找到i和j合适的位置:
代码实现
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
double middleValue(vector<int>& nums1, int length1, vector<int>& nums2, int length2)
{
//在短的数组中求解合适的i和j值
if (length1 > length2)
return middleValue(nums2, length2, nums1, length1);
if (length1 == 0)
{
int k = (length2 - 1) / 2;
if (length2 - 1 % 2 == 0)
{
return (nums2[k] + nums2[k + 1]) * 1.0 / 2;
}
else
{
return nums2[k];
}
}
int begin = 0;
int end = length1;
int k = (length1 + length2 + 1) / 2;
int i;
int j;
//二分搜索的算法思想,在对数时间内找到i+j=k
while (begin <= end)
{
i = (begin + end) / 2;
j = k - i;
if (j > 0 && i < length1 && nums2[j - 1] > nums1[i])
{
begin = i + 1;
}
else if (i > 0 && j<length2 && nums1[i - 1]>nums2[j])
{
end = i - 1;
}
else
{
break;
}
}
int left = 0;
//nums1特别短,而且nums1数组元素都特别大,中位数肯定在nums2数组中
if (i == 0)
{
left = nums2[j - 1];
}
//nums2特别短,中位数肯定都在nums1数组中
else if (j == 0)
{
left = nums1[i - 1];
}
else
{
left = max(nums1[i - 1], nums2[j - 1]);
}
int right = 0;
//nums1数组元素太小了,而且值都特别小,中位数肯定在nums2数组中
if (i == length1)
{
right = nums2[j];
}
//中位数肯定在nums1数组中
else if (j == length2)
{
right = nums1[i];
}
else
{
right = min(nums1[i], nums2[j]);
}
//找到了合适的i和j值
if ((length1 + length2) % 2 == 0)//偶数长度
{
return(left + right) * 1.0 / 2;
}
else//奇数长度
{
return left;
}
}
int main()
{
vector<int> vec1;
vector<int> vec2;
for (int i = 0; i < 10; i++)
{
vec1.push_back(rand() % 100);
}
for (int i = 0; i < 6; i++)
{
vec2.push_back(rand() % 100);
}
sort(vec1.begin(), vec1.end());
sort(vec2.begin(), vec2.end());
vector<int> vec = vec1;
for (int v : vec2)
{
vec.push_back(v);
}
sort(vec.begin(), vec.end());
for (int v : vec)
{
cout << v << " ";
}
cout << endl;
double midval = middleValue(vec1, vec1.size(), vec2, vec2.size());
cout << midval << endl;
}
文章浏览阅读3.2w次,点赞16次,收藏90次。对于这个问题我也是从网上找了很久,终于解决了这个问题。首先遇到这个问题,应该确认虚拟机能不能正常的上网,就需要ping 网关,如果能ping通说明能正常上网,不过首先要用命令route -n来查看自己的网关,如下图:第一行就是默认网关。现在用命令ping 192.168.1.1来看一下结果:然后可以看一下电脑上面百度的ip是多少可以在linux里面ping 这个IP,结果如下:..._linux桥接ping不通baidu
文章浏览阅读512次。小妹在这里已经卡了2-3天了,研究了很多人的文章,除了低版本api 17有成功外,其他的不是channel null 就是没反应 (channel null已解决)拜托各位大大,帮小妹一下,以下是我的程式跟 gradle, 我在这里卡好久又没有人可问(哭)![image](/img/bVcL0Qo)public class MainActivity extends AppCompatActivit..._android 权限申请弹窗 横屏
文章浏览阅读1.4k次,点赞4次,收藏6次。valid padding(有效填充):完全不使用填充。half/same padding(半填充/相同填充):保证输入和输出的feature map尺寸相同。full padding(全填充):在卷积操作过程中,每个像素在每个方向上被访问的次数相同。arbitrary padding(任意填充):人为设定填充。..._cnn “相同填充”(same padding)
文章浏览阅读790次,点赞29次,收藏28次。手绘了下图所示的kafka知识大纲流程图(xmind文件不能上传,导出图片展现),但都可提供源文件给每位爱学习的朋友一个人可以走的很快,但一群人才能走的更远。不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人,都欢迎扫码加入我们的的圈子(技术交流、学习资源、职场吐槽、大厂内推、面试辅导),让我们一起学习成长![外链图片转存中…(img-Qpoc4gOu-1712656009273)][外链图片转存中…(img-bSWbNeGN-1712656009274)]
文章浏览阅读469次。Date对象取得年份有getYear和getFullYear两种方法经 测试var d=new Date;alert(d.getYear())在IE中返回 2009,在Firefox中会返回109。经查询手册,getYear在Firefox下返回的是距1900年1月1日的年份,这是一个过时而不被推荐的方法。而alert(d.getFullYear())在IE和FF中都会返回2009。因此,无论何时都应使用getFullYear来替代getYear方法。例如:2016年用 getFullYea_getyear和getfullyear
文章浏览阅读182次。Unix传奇(上篇) 陈皓 了解过去,我们才能知其然,更知所以然。总结过去,我们才会知道我们明天该如何去规划,该如何去走。在时间的滚轮中,许许多的东西就像流星一样一闪而逝,而有些东西却能经受着时间的考验散发着经久的魅力,让人津津乐道,流传至今。要知道明天怎么去选择,怎么去做,不是盲目地跟从今天各种各样琳琅满目前沿技术,而应该是去 —— 认认真真地了解和回顾历史。 Unix是目前还在存活的操作系_unix传奇pdf
文章浏览阅读308次。哈希算法:将字符串映射为数字形式,十分巧妙,一般运用为进制数,进制据前人经验,一般为131,1331时重复率很低,由于字符串的数字和会很大,所以一般为了方便,一般定义为unsigned long long,爆掉时,即为对 2^64 取模,可以对于任意子序列的值进行映射为数字进而进行判断入门题目链接:AC代码:#include<bits/stdc++.h>using na..._ac算法 哈希
文章浏览阅读952次,点赞13次,收藏27次。由于觉得Qt的编辑界面比较丑,所以想用vs2022的编辑器写Qt加MySQL的项目。_在vs中 如何装qt5sqlmysql模块
文章浏览阅读1k次。选择题题目:下面的哪个调研内容属于经济环境调研?()题目:()的目的就是加强与客户的沟通,它是是网络媒体也是网络营销的最重要特性。题目:4Ps策略中4P是指产品、价格、顾客和促销。题目:网络市场调研是目前最为先进的市场调研手段,没有任何的缺点或不足之处。题目:市场定位的基本参数有题目:市场需求调研可以掌握()等信息。题目:在开展企业网站建设时应做好以下哪几个工作。()题目:对企业网站首页的优化中,一定要注意下面哪几个方面的优化。()题目:()的主要作用是增进顾客关系,提供顾客服务,提升企业_画中画广告之所以能有较高的点击率,主要由于它具有以下特点
文章浏览阅读1k次,点赞2次,收藏5次。以爬取CSDN为例子:第一步:导入请求库第二步:打开请求网址第三步:打印源码import urllib.requestresponse=urllib.request.urlopen("https://www.csdn.net/?spm=1011.2124.3001.5359")print(response.read().decode('utf-8'))结果大概就是这个样子:好的,继续,看看打印的是什么类型的:import urllib.requestresponse=urllib.r_urlopen the read operation timed out
文章浏览阅读304次。修正sina.com/sina.cn邮箱获取不到联系人,并精简修改了其他邮箱代码,以下就是升级版版本的介绍:完整版本,整合了包括读取邮箱通讯录、MSN好友列表的的功能,目前读取邮箱通讯录支持如下邮箱:gmail(Y)、hotmail(Y)、 live(Y)、tom(Y)、yahoo(Y)(有点慢)、 sina(Y)、163(Y)、126(Y)、yeah(Y)、sohu(Y) 读取后可以发送邮件(完..._通讯录 应用读取 邮件 的相关
文章浏览阅读213次。云计算及虚拟化教程学习云计算、虚拟化和计算机网络的基本概念。此视频教程共2.0小时,中英双语字幕,画质清晰无水印,源码附件全课程英文名:Cloud Computing and Virtualization An Introduction百度网盘地址:https://pan.baidu.com/s/1lrak60XOGEqMOI6lXYf6TQ?pwd=ns0j课程介绍:https://www.aihorizon.cn/72云计算:概念、定义、云类型和服务部署模型。虚拟化的概念使用 Type-2 Hyperv_云计算与虚拟化技术 教改