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指针所指结点的操作应为?
双向链表稍微复杂些,主要分为以下步骤:
【数据结构】STL中vector详解?
在内存中分配一块连续的内存空间进行存储。支持不指定vector大小的存储。STL内部实现时,首先分配一个非常大的内存空间预备进行存储,即capacituy()函数返回的大小,当超过此分配的空间时再整体重新放分配一块内存存储,这给人以vector可以不指定vector即一个连续内存的大小的感觉。通常此默认的内存分配能完成大部分情况下的存储。 优点:
缺点:
3
资源分享
公众号简介:分享算法工程师必备技能,谈谈那些有深度有意思的算法,主要范围:C++数据结构与算法/深度学习(CV),立志成为Offer收割机!坚持分享算法题目和解题思路(Day By Day)
号外,算法刷题群已经建立,但由于人数超出限制,无法扫码添加,可以加号主微信(Leopard7319538)说明来意,可以加入到算法刷题群,每天2道编程题3道概念题,晚9点打卡,我们一起坚持下去!!!
完