每日算法题：Day 21

算法工程师之路

发布于 2019-08-23 14:27:35

3110

发布于 2019-08-23 14:27:35

文章被收录于专栏：算法工程师之路

Day 21, 数据机构知识点走起~

编程题

【剑指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--]);
        }
    }
};

概念题

【数据结构】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

【数据结构】最小生成树的相关概念

最小代价生成树：