每日算法题：Day 21
Day 21, 数据机构知识点走起~
1
编程题
【剑指Offer】和为S的两个数
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。 输出描述: 对应每个测试案例，输出两个数，小的先输出。
思路： 这里我们还是使用双指针的思想，一个指向开头，另一个指向末尾，那为什么和连续正数序列不同呢？这是由于题目要输出两个数乘积最小的那组，有一个定理是：当两个数的总和相同时，两个数相差越多，那么它的乘积就越小！反之相差越小，乘积越大，因此从两头遍历得到的第一组数一定是乘积最小的！
class Solution {
public:
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
int begin = , end = array.size()-1;
vector<int> res;
while(begin < end){
if(array[begin] + array[end] == sum){
res.push_back(array[begin]);
res.push_back(array[end]);
break;
}
while(begin < end && array[begin] + array[end] > sum) --end;
while(begin < end && array[begin] + array[end] < sum) ++begin;
}
return res;
}
};
另外一个思路直接使用STL中的库函数equal_range来获取与某一个值相等的上下边界，十分好用的！
【剑指Offer】左旋转字符串
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
思路： STL中substr的用法！注意参数n有可能大于整个字符串的长度，所以要进行取余操作！
class Solution {
public:
string LeftRotateString(string str, int n) {
int len = str.length();
if(len == ) return "";
n %= len;
str += str;
return str.substr(n, len);
}
};
另外一种方法就是不使用库函数的！对字符串进行三次的翻转，首先是0到n-1，再者是n到len-1，最后是0到len-1.
class Solution {
public:
string LeftRotateString(string str, int n) {
int len = str.length();
if(len == || n == ) return str;
reverse(str, , n-1);
reverse(str, n, len-1);
reverse(str, , len-1);
return str;
}
private:
void reverse(string& s, int begin, int end){
while(begin < end){
swap(s[begin++], s[end--]);
}
}
};2
概念题
【数据结构】m阶B树的定义为什么？
m阶B-树定义如下:
- 定义任意非叶子结点最多只有 M 个儿子；且M > 2；
- 根结点的儿子数为[2, M]；
- 除根结点以外的非叶子结点的儿子数为[M/2, M]；
- 每个结点存放至少 M/2-1 （取上整）和至多 M-1 个关键字；
因此一个有15个关键字的4阶B数最多节点数为15，因为4阶B数的每个节点的关键字范围为[M/2-1, M-1]，即[1,3].
【数据结构】假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？
当使用线性探测法时，我们假定除了该位置其他位置空间均空闲，则：
由于K个关键字互为同义词，则可假设K个关键字均为1，即有K个1 对于第一个1，散列表为空，探测一次，直接填入。 对于第二个1，这个1的位置被前一个1给占用了，所以要进行线性探测再散列，探测次数至少为2 对于第三个1，同理，探测次数至少为3。 …… 对于第K个1，探测次数至少为K。 则总的探测次数至少为为1+2+……+K=k（k+1）/2
【数据结构】最小生成树的相关概念
最小代价生成树：
- 最小生成树对应的边的权值之和是最小的，权值和是唯一的。
- 当图的各边权值都不同时，最小生成树是唯一的，但权重不同时，最小生成树可能有多个
- 最小生成树不能存在环结构，且必须连接到所有的节点
- 最小生成树实质是用n-1条边去连接n个顶点