每日算法题：Day 14（数据结构）
作者：TeddyZhang，公众号：算法工程师之路
Day 14, 数据结构知识点走起~
1
编程题
【剑指Offer】字符串的排列
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
思路：
如上图所示，树状图的第一层其实质就是下一个递归子问题入口str的值，也就是0与j（0，1，2…str.length()）
交换后str的值，并且每次进入递归函数时，在i 之前字母将会被固定，其后面的数进行全排列（交换元素的位置）。然后一直递归下去，从而得到最后的全排列！一般我们写递归函数如果需要动态保存数据，如vector res, 我们可以把它当作一个参数，并使用引用传递的形式来修改res这个变量！
递归的结束条件为，索引i等于了str.length()时，递归结束！
class Solution {
public:
void process(vector<string>& res, string str, int i){
if(i == str.length()){
res.push_back(str);
}
set<char> ss;
for(int j = i;j < str.length(); j++){
if(ss.find(str[j]) == ss.end()){
ss.insert(str[j]);
swap(str[i], str[j]);
process(res, str, i+);
}
}
}
vector<string> Permutation(string str) {
vector<string> res;
if(str.length() == ) return res;
process(res, str, );
return res;
}
};
【剑指Offer】数组中超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路： 首先，第一个思路，我们不考虑空间复杂度，这种在笔试时最好用，使用一个哈希表，然后遍历，由于unordered_map中不允许重复的key，因此每遍历到相同的key，value就加一。然后判断这个值大不大于数组的一半，如果大于，直接返回即可，否则返回零。
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
unordered_map<int, int> hash_map;
if(numbers.size() == ) return ;
for(auto i: numbers){
hash_map[i]++;
if(hash_map[i] > (numbers.size() / )){
return i;
}
}
return ;
}
};
另一种思路时，先对整个序列进行排序操作，如果数组中一个数的数量超过这个数组的一半，那么对整个数组排序后，这个数一定位于数组的中间位置！那么既然要排序，我们这里使用快排对数组进行排序，O(Nlogn),虽然有人可以优化到O(n)，但是代码太多太复杂了！经过排序后，我们首先获得中间位置的值，然后遍历整个排序数组，统计这个值的个数，如果确实大于size/2，则返回这个数的个数！既然你要学算法，就尽量别调库了，老老实实自己写个快排！
class Solution {
public:
vector<int> qs_partition(vector<int>& list, int L, int R){
int more = R; // 选取最后一个数为分界点
int less = L - ;
int cur = L;
vector<int> res();
while(cur < more){
if(list[cur] < list[R]){
swap(list[++less], list[cur++]);
}else if(list[cur] > list[R]){
swap(list[--more], list[cur]);
// 交换后cur有可能小于中间值，还需要再次交换，因此cur不进行自加
}else{
cur++;
}
}
swap(list[more], list[R]);
res[] = less+;
res[] = more;
return res;
}
// 经典快排
void QuickSort(vector<int>& list, int L, int R){
if(list.size() < ) return;
if(L < R){
vector<int> p = qs_partition(list, L, R);
QuickSort(list, L, p[]-1);
QuickSort(list, p[]+, R); // 递归处理其他部分
}
}
int MoreThanHalfNum_Solution(vector<int> numbers) {
if(numbers.size() == ) return ;
int size = numbers.size();
QuickSort(numbers, , size-1);
int mid = size / ; // 获得中间位置的值
int count = ;
for(auto num: numbers){
if(num == numbers[mid]){
count++; // 统计中间位置值的数量
if(count > (size / )){
return num;
}
}
}
return ;
}
};2
概念题
【数据结构】在一个单链表中，若p所指的结点不是最后结点，在p所指结点之后插进s所指结点，则应执行操纵
首先改变s的next指针的指向：s->next = p->next; 然后改变p的next指针的指向：p->next = s;
【数据结构】对于双向循环链表，每个结点有两个指针域next和prior，分别指向前驱和后继。在p指针所指向的结点之后插入s指针所指结点的操作应为？
双向链表稍微复杂些，主要分为以下步骤：
- 对插入节点s的前驱和后继进行赋值：s->prior=p; s->next=p->next;
- 修改p->next的前驱为s: p->next->prior = s;
- 修改p->next的指向：p->next = s; 注意：最后两步不可以颠倒，如果先修改p->next，那么就找不到原来的next节点，也就无法修改其前驱指针了！
【数据结构】STL中vector详解？
在内存中分配一块连续的内存空间进行存储。支持不指定vector大小的存储。STL内部实现时，首先分配一个非常大的内存空间预备进行存储，即capacituy（）函数返回的大小，当超过此分配的空间时再整体重新放分配一块内存存储，这给人以vector可以不指定vector即一个连续内存的大小的感觉。通常此默认的内存分配能完成大部分情况下的存储。 优点：
- 不指定一块内存大小的数组的连续存储，即可以像数组一样操作，但可以对此数组进行动态操作。通常体现在push_back() pop_back()
- 随机访问方便，即支持[ ]操作符和vector.at()
缺点：
- 在内部进行插入删除操作效率低。
- 只能在vector的最后进行push和pop，不能在vector的头进行push和pop。
- 当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释放
3
资源分享
欢迎关注我的个人公众号 （算法工程师之路），公众号内有大量视频资料和电子书资料以及算法笔记，回复关键字即可获取！
公众号简介：分享算法工程师必备技能，谈谈那些有深度有意思的算法，主要范围：C++数据结构与算法/深度学习（CV），立志成为Offer收割机！坚持分享算法题目和解题思路（Day By Day)
号外，算法刷题群已经建立，但由于人数超出限制，无法扫码添加，可以加号主微信（Leopard7319538）说明来意，可以加入到算法刷题群，每天2道编程题3道概念题，晚9点打卡，我们一起坚持下去！！！
完
腾讯云开发者
