前言
本文是题主准备面试时记录下的笔记整理而来，稍显粗陋，还请各位撸友勿喷哈！
Topic
-
目录
-
目标
- 熟练使用常用数据结构的基本操作
- 加深对常用算法与技巧的理解
- 面试
-
参考
- 《程序员面试金典》
- 《剑指offer》
- Leetcode
- 《结构之法 --July》
数组篇
左旋字符串/数组
1.问题描述
- 给定一字符串
- 将串的前若干个元素移到串的尾部
2.例子
- "abcdefg",2 ==> "cdefgab"
3.Coding感想
- 关于三步反转法
- 对每段都做了两次反转，因此每段仍然有序
- 段与段之间反转了顺序
4.解决方案
(1) 暴力移位（By一个字符）
A. A[0]存入临时变量tmp
B. 数组其余元素放到数组后面
C. 旋转几位，就执行几次A,B
(2) 三步反转法
A. 要旋转的位置将串分为两段
B. 将这两段分别进行反转
C. 对整个字符串反转
Remove Duplicates
1.问题描述
- 定一个已排序数组
- 删除重复元素
- 返回删除后数组的长度
- 不能使用额外空间
2.例子
A = [1, 1, 2] ==> len = 2, A = [1, 2]
3.解决方案
-
两个游标遍历数组
- 两个游标指向的值不等
- 游标相邻，则两个游标向前移动一位
- 游标不相邻，快游标值赋给慢游标的下一位后，快游标进一位
- 相等则快游标前进一位
- 两个游标指向的值不等
-
STL-distance()-unique()
- distance(A, unique(A, A + n))
- 注意引入#include<algorithm>
- unique()
- 作用
- 删除所有相邻的重复元素
- 不是真的删除，而是放后面
- 先排序后才能用unique（）
- 原型：unique（begin，end）
- 返回去重后最后一个元素的地址
- 作用
- distance()
- 原型distance（begin, end）
- 返回两参数间的间隔长度
-
STL-泛型模板-upper_bound()
- upper_bound()
- 定义
- 返回的在前闭后开区间查找的关键字的上界
- 返回一个迭代器，指向键值> key的第一个元素
- 原型：upper_bound(first, last, value)
- 定义
- lower_bound()
- 返回一个迭代器，指向键值>= key的第一个元素
- upper_bound()
4.Coding遇到的问题
gdb display 可否同时设置多个变量？
-
使用string的append方法
- 原型：append(const value_type ptr)
- append( string s )
- append( "hello" )
- append(const char* c)
- 与 “strA + strB”的对比
- append更加灵活
- append效率相对较低
- 相关链接
- c++拼接字符串效率比较
- 原型：append(const value_type ptr)
-
char* c =new char(10); c = "hello";
- 如此赋值会有隐患: hello是常量，但c指向的是变量
- 应定义为const char*
- 相关链接
- warning：deprecated conversion from string constant to 'char *'
常量指针 vs 指针常量
参见《effective c++》思维导图笔记-
获取数组的长度
- sizeof(array) / sizeof(array[0])
- 无法判断数组是否为空，因为数组一旦定义，里面便有随机值
5.代码示例：
/*************************************************************************
> File Name: 1_1.rm_duplicates_from_sorted_Array.cpp
> Description:
（1）给一个已排序数组
（2）删除重复元素
（3）返回删除后数组的长度
（4）不能使用额外空间，必须用常量内存
（5）A = [1,1,2] ==> len = 2, A = [1, 2]
> Conclusion:
（1）注重代码优化
（2）简化判定条件
（3）快慢游标遍历数组
> Author: rh_Jameson
> Created Time: 2014年12月02日 星期二 12时03分26秒
************************************************************************/
#include<iostream>
#include<algorithm>
using namespace std;
//-------------------------------------原始版本：Acceped--------------------------------//
int removeDuplicatesOrigin(int A[],int n)
{
int p = 0,q = 1; //游标p，q
if(n <= 0) //判空 & 非法
{
return 0;
}
if(n == 1) //数组只有一个元素的情况
{
return 1;
}
while(q != n)
{
if(A[p] != A[q] && p == q - 1) //A[p]和A[q]不等且p，q相邻时，p，q向前移动一位
{
p++;
q++;
}
else if(A[p] != A[q] && p != q - 1) //A[p]和A[q]不等且p,q不相邻时
{
p++; //p向前移动一位
A[p] = A[q]; //将数组A下标q的值赋给下标p的值
q++; //q向前移动一位
}
else if(A[p] == A[q]) //A[p]和A[q]相等时，q向前移动一位
{
q++;
}
}
return p + 1; //返回处理后数组的长度
}
//-------------------------------------优化版本：Acceped--------------------------------//
int removeDuplicatesOptimize(int A[],int n)
{
int p = 0,q = 1; //游标p，q
if(n <= 0) //判空 & 非法
{
return 0;
}
while(q != n)
{
if(A[p] != A[q]) //A[p]和A[q]不等时，p，q向前移动一位
{
A[++p] = A[q]; //巧妙优化，p，q相邻，A[q] = A[q],p,q不相邻，A[p] = A[q]
q++;
}
else if(A[p] == A[q]) //A[p]和A[q]相等时，q向前移动一位
{
q++;
}
}
return p + 1; //返回处理后数组的长度
}
//-------------------------------------优化版本2：Acceped--------------------------------//
int removeDuplicatesOptimize(int A[],int n)
{
int p = 0,q = 1; //游标p，q
if(n <= 0) //判空 & 非法
{
return 0;
}
while(q != n)
{
if(A[p] != A[q]) //A[p]和A[q]不等时，p，q向前移动一位
{
A[++p] = A[q]; //巧妙优化，p，q相邻，A[q] = A[q],p,q不相邻，A[p] = A[q]
}
q++;
}
return p + 1; //返回处理后数组的长度
}
//==================================参考代码1：Accepted==================================//
/*
* 该参考代码与上面优化版本的代码思路一直，不再赘释
*/
int removeDuplicatesLeetcode1(int A[],int n)
{
if(n <= 0)
{
return 0;
}
int index = 0;
for(int i = 1; i < n; ++i)
{
if( A[index] != A[i] )
{
A[++index] = A[i];
}
}
return index + 1;
}
//==================================参考代码2：Accepted==================================//
/*
* 使用STL distance(),unique()方法
*/
int removeDuplicatesLeetcode2(int A[],int n)
{
return distance(A, unique(A, A + n) );
}
int main()
{
//removeDuplicates
int A[3] = {1,1,2};
cout << removeDuplicatesLeetcode2(A, 3) << endl;
}
Remove Duplicates II
1.问题描述
- 给一个已排序数组
- 删除重复次数大于2的元素
- 返回删除后数组的长度
- 不能使用额外空间
2.例子
A = [1,1,1,2,2,3] ==> A.len = 5, A = [1,1,2,2,3]
3.Coding感想
- 条件语句优化技能有待提高
4.解决方案
- 思路与上一道差不多，区别是引入计数变量
- 在第一次出现重复时，做相应处理
- 多次重复，只移动快游标
- A[p] != A[q]时，注意将count重置为1
5.代码实例：
/*************************************************************************
> File Name: 1_2.remove_duplicatesII.cpp
> Description:
（1）给一个已排序数组
（2）删除重复次数大于2的元素
（3）返回删除后数组的长度
（4）不能使用额外空间
（5）A = [1,1,1,2,2,3] ==> A.len = 5,A = [1,1,2,2,3]
> Conclusion:
（1）条件语句优化技能有待提高
（2）策略：
A.思路与上一道差不多，区别是引入计数变量
B.在第一次出现重复时，做相应处理
C.多次重复，只移动快游标
D.A[p] != A[q]时，注意将count重置为1
> Author: rh_Jameson
> Created Time: 2014年12月03日 星期三 13时23分00秒
************************************************************************/
#include<iostream>
using namespace std;
//============================原始版本：Accepted,88 ms==================================//
int removeDuplicates(int A[],int n)
{
int count = 1; //计数变量
int index = 0; //慢游标
if(n <= 0) //判空，非法
{
return 0;
}
for(int i = 1; i < n; ++i)
{
/*慢游标指向值不等于快游标指向值时*/
if(A[index] != A[i])
{
A[++index] = A[i]; //慢游标前进一位，将快游标指向值赋给慢游标指向值
if(count != 1) //重置count
{
count = 1;
}
}
/*慢游标指向值等于快游标指向值时*/
else if(count == 1) //第一次出现重复的处理
{
count++;
A[++index] = A[i];
}
else //多次重复的处理
{
count++;
}
}
return index + 1;
}
//============================优化条件语句版本：Accepted,116 ms==================================//
int removeDuplicatesOpt(int A[],int n)
{
int count = 1; //计数变量
int index = 0; //慢游标
if(n <= 0) //判空，非法
{
return 0;
}
for(int i = 1; i < n; ++i)
{
if(A[index] == A[i])
{
count++;
if(count == 2)
{
A[++index] = A[i];
}
}
else
{
A[++index] = A[i];
count = 1;
}
}
return index + 1;
}
//============================参考版本：Accepted,68ms===============================//
int removeDuplicates(int A[], int n) {
if(n <= 2) //小于2直接返回n
{
return n;
}
//直接从下标2开始遍历
int index = 2;
for(int i = 2; i < n; ++i)
{
if(A[index - 2] != A[i])
{
A[index++] = A[i];
}
}
return index;
}
int main()
{
int A[4] ={1,1,1,1};
// int A[6] = {1,1,1,2,2,3};
cout << removeDuplicatesOpt(A, 4);
return 0;
}
Search In Rotated Sorted Array
1.问题描述
- 给定一旋转数组（数组分两段，各段均已排序）
- 段边界点不确定
- 给一关键字，查询数组中是否有该关键字
- 有则返回下标，无则返回-1
- 假设数组中无重复元素
- A = [4,5,6,7,0,1,2]
2.例子
A = [4,5,6,7,0,1,2], 搜索关键字：0 ==> return 4
3.解决方案
- 两次折半策略
- 折半获取边界最大值
- 判断关键字在哪一段顺序序列上
- 在目标顺序序列上折半查找关键字
- 一次折半策略
- 折半mid,比较A[mid]和target
- mid将数组分两段，判断target是在哪一段
- target没找到或first与last未交错，循环A,B
4.Coding遇到的问题与感想
- 折半查找算法实现需注意的细节及优化
- 两种情况[0,n),[0,n]
- right=n-1 => while(left <= right) => right=middle-1
- right=n => while(left < right) => right=middle;
- 注意（min + max）/ 2溢出问题
- 折半改变min或max时，防止出现死循环
- 两种情况[0,n),[0,n]
- 我想的策略复杂度为logn，但要两次折半来实现，非最优解法
5.代码示例：
/*************************************************************************
> File Name: 1_3.search_in_rotated_sorted_array.cpp
> Description:
（1）给定一旋转数组（数组分两段，各段均已排序）
（2）段边界点不确定
（3）给一关键字，查询数组中是否有该关键字
（4）有则返回下标，无则返回-1
（5）假设数组中无重复元素
（6）A = [4,5,6,7,0,1,2]
> Conclusion:
（1）策略：
A.折半获取边界最大值
B.判断关键字在哪一段顺序序列上
C.在目标顺序序列上折半查找关键字
（2）折半查找算法实现需注意的细节及优化
A.两种情况[0,n),[0,n]
B.注意（min + max）/ 2溢出问题
C.折半改变min或max时，防止出现死循环
（3）该策略复杂度为logn，但要两次折半来
实现，非最优解法
（4）一次折半优化策略：
A.折半mid,比较A[mid]和target
B.mid将数组分两段，判断target是在哪一段
C.target没找到或first与last未交错，循环A,B
> Author: rh_Jameson
> Created Time: 2014年12月03日 星期三 16时16分33秒
************************************************************************/
#include<iostream>
using namespace std;
//====================两次折半版本：Accepted，16 ms=========================//
//折半查找关键字
int binary_search(int A[], int &max, int &min, int target)
{
int mid;
while(min <= max)
{
//mid = (min + max) / 2; //常规折半
mid = min + (max - min) / 2; //防止（min + max）溢出
if(target > A[mid])
{
min = mid + 1;
}
else if(target < A[mid])
{
max = mid - 1;
}
else
{
return mid;
}
}
return -1;
}
//折半获取边界最大值leftMax
int binary_getMax(int A[], int &front, int &rear)
{
int mid;
while(front <= rear)
{
//mid = (front + rear) / 2;
mid = front + (rear - front) / 2; //防止溢出
//找到最大值，直接跳出循环
if( A[mid] > A[mid - 1] && A[mid] > A[mid + 1] ||
front == rear - 1 && A[mid] > A[mid + 1] ||
front == mid && rear == mid )
{
break;
}
//mid非最大值，进行折半
if(A[mid] >= A[front])
{
front = mid + 1;
}
else
{
rear = mid - 1;
}
}
return mid;
}
int search(int A[],int n,int target)
{
if(n <= 0) //处理非法
{
return -1;
}
int front = 0;
int rear = n - 1;
//初始化边界值
int leftMin = 0, leftMax, rightMin, rightMax = n-1;
leftMax = binary_getMax(A, front, rear); //折半获取边界最大值
rightMin = leftMax + 1;
//判断目标值在哪一段顺序序列上
if(target > A[leftMin]) //折半查找需封装
{
return binary_search(A, leftMax,leftMin,target); //折半查找左侧顺序序列
}
else if(target == A[leftMin])
{
return leftMin;
}
else
{
return binary_search(A, rightMax, rightMin, target); //折半查找右侧顺序序列
}
}
//==========================一次折半版本：Accepted,40ms===============================//
//折半mid,比较target，A[mid]
int searchOnce(int A[], int n, int target)
{
int first = 0, mid, last = n - 1;
while(first <= last) //first，last未交错，继续循环
{
mid = first + (last - first) / 2;
if(target == A[mid])
{
return mid;
}
if(target == A[first])
{
return first;
}
else if(A[mid] >= A[first])
{
if(target > A[first] && target < A[mid])
{
last = mid - 1;
}
else
{
first = mid + 1;
}
}
else
{
if(target < A[first] && target > A[mid])
{
first = mid + 1;
}
else
{
last = mid - 1;
}
}
}
return -1;
}
int main()
{
//int A[7] = {4,5,6,7,0,1,2};
int A[2] = {3,1};
cout << searchOnce(A, 2, 1) << endl;
return 0;
}
1_6.matrix_rotate
1.问题描述
- N * N矩阵表示图像
- 每像素4字节
- 实现图像旋转90度
- 不用额外空间
2.策略一：四点轮换法
- 遍历行数N/2
- 将行中每个结点旋转到相应位置
- 通过tmp变量进行轮换
- 时间复杂度O（N^2）
3.策略二：对角线替换
- 交换对角线两边元素
- 对每一列元素进行逆置
- 逆时针旋转绕横轴
- 顺时针旋转绕纵轴
4.生成随机数
- srand((int)time(NULL));
- r = rand() % 10
5.传递二维数组参数
- int a[10][10]
- int a[][10]
- 不可以用二级指针
- int** a;
- 相关网址：http://www.wutianqi.com/?p=1822
6.代码示例：
/*************************************************************************
> File Name: Solution.h
> Description:
（1）问题描述
A.N * N矩阵表示图像
B.每像素4字节
C.实现图像旋转90度
D.不用额外空间
> Conclusion:
（1）策略一：四点轮换法
A.遍历行数N/2
B.将行中每个结点旋转到相应位置
C.通过tmp变量进行轮换
D.时间复杂度O（N^2）
（2）策略二：对角线替换
A.交换对角线两边元素
B.对每一列元素进行逆置
a.逆时针旋转绕横轴
b.顺时针旋转绕纵轴
（3）生成随机数
A.srand((int)time(NULL));
B.r = rand() % 10
（4）传递二维数组参数
A.int a[10][10]
B.int a[][10]
C.不可以用二级指针
a.int** a;
b.相关网址：
http://www.wutianqi.com/?p=1822
> Author: rh_Jameson
> Created Time: 2014年12月14日 星期日 12时17分44秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
class Solution {
public:
void printMatrix(const int n,int a[][7]){
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
cout << a[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
//=======================矩阵旋转：四点轮换法,Accepted=======================//
//逆时针旋转90度
void matrix_rotate_reverse(const int n, int a[][7]){
if(n == 0){
cout << "空矩阵" << endl;
}
int col = n, len = n;
int midline = n / 2, tmp;
for(int i = 0; i < midline; ++i){
for(int j = i; j < col - 1 - i; ++j){
tmp = a[j][i];
a[j][i] = a[i][len - 1 - j];
a[i][len -1 -j] = a[len - 1 - j][len - 1 - i];
a[len - 1 - j][len - 1 - i] = a[len - 1 - i][j];
a[len - 1 - i][j] = tmp;
}
}
printMatrix(n, a);
}
//顺时针旋转90度
void matrix_rotateByExchg(const int n, int a[][7]){
if(n == 0){
cout << "空矩阵" << endl;
}
int col = n, len = n;
int midline = n / 2, tmp;
for(int i = 0; i < midline; ++i){
for(int j = i; j < col - 1 - i; ++j){
tmp = a[i][j];
a[i][j] = a[len - 1 - j][i];
a[len - 1- j][i] = a[len - 1 - i][len - 1 - j];
a[len - 1 - i][len - 1 - j] = a[j][len - 1 - i];
a[j][len - 1 - i] = tmp;
}
}
printMatrix(n, a);
}
//=====================矩阵旋转：对角线替换,Accepted======================//
void swap(int &a, int &b){
int tmp;
tmp = a;
a = b;
b = tmp;
}
void matrix_rotate(const int n, int a[][7]){
int len = n;
//对角线两侧元素互换
for(int i = 0; i < len; ++i){
for(int j = i; j < len; ++j){
swap(a[i][j],a[j][i]);
}
}
//根据纵轴逆置元素
for(int line = 0; line < len; ++line){
for(int first = 0,last = len - 1; first < last; ++first, --last){
swap(a[line][first],a[line][last]);
}
}
printMatrix(n, a);
}
};
#endif
1_7.matrix_clear_zero
1.问题描述：
- M * N矩阵
- 若某个元素为0，所在行与列均清零
2.解决策略
- 策略一：哈希表保存清零的行与列
- 遍历矩阵
- 用map记录元素为0的行, 列
- 对相应行清零
- 相应列清零
- 策略二：复用0行0列记录要清零的行，列
- 不用额外空间，直接复用0行0列的空间
- 判断0行跟0列是否存在0，bool标志真/假
- 遍历其余行跟列
- 元素为0的行列，存到0行0列的相应位置
- 遍历清零
- 检测bool标志，判断0行0列是否存在0
- 存在，则对0行 / 0列清零
3.Coding遇到的问题
- vector<vector<int> > m：
- 相当于二维数组 m[i][j]
- 行数：m.size()
- 列数：m[0].size()
- m[i][j]形式，通过2个for循环可生成随机矩阵
- vector形式不能生成
- 相关链接
- map & hashtable：
- C++ STL严格来说没有实现哈希表结构
- map底层是红黑树，访问复杂度为logN
- 哈希表一般是常数时间访问
- 性能：unordered_map > hash_map > map
- 需要有序关联容器的话要用map
- 相关链接
- STL---hash_map
- c++ hash_map 详细介绍
- map / hash_map / unordered_map 性能测试
- C++ STL中哈希表 hash_map介绍
4.代码示例：
/*************************************************************************
> File Name: Solution.h
> Description:
（1）问题描述：
A.M * N矩阵
B.若某个元素为0，所在行与列均清零
> Conclusion:
（1）策略一：哈希表保存清零的行与列
A.遍历矩阵
B.用map记录元素为0的行, 列
C.对相应行清零
D.相应列清零
（2）策略二：复用0行0列记录要清零的行，列
A.不用额外空间，直接复用0行0列的空间
B.判断0行跟0列是否存在0，bool标志真/假
C.遍历其余行跟列
D.元素为0的行列，存到0行0列的相应位置
E.遍历清零
F.检测bool标志，判断0行0列是否存在0
G.存在，则对0行 / 0列清零
（3）vector<vector<int> > m：
A.相当于二维数组 m[i][j]
B.行数：m.size()
C.列数：m[0].size()
D.m[i][j]形式，通过2个for循环可生成随机矩阵
E.vector形式不能生成
F.http://blog.csdn.net/qingdujun/article/details/17499871
（4）map & hashtable：
A.C++ STL严格来说没有实现哈希表结构
B.map底层是红黑树，访问复杂度为logN
C.哈希表一般是常数时间访问
D.性能：unordered_map > hash_map > map
E.需要有序关联容器的话要用map
F.http://blog.chinaunix.net/uid-20384806-id-3055333.html
G.http://yiluohuanghun.blog.51cto.com/3407300/1086355
H.http://blog.csdn.net/peter_teng/article/details/8433395
I.http://www.cnblogs.com/waytofall/archive/2012/06/04/2534386.html
> Author: rh_Jameson
> Created Time: 2014年12月14日 星期日 22时24分29秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
//#include<hash_map>
using namespace std;
class Solution {
public:
void printMatrix(int matrix[1][2]){
int col_num = 2;
int line_num = 1;
for(int i = 0; i < line_num; ++i){
for(int j = 0; j < col_num; ++j){
cout << matrix[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
//=====================map保存要清0的行与列：Accepted=====================//‘
void setZeroesByHash(int matrix[5][4]) {
int col_num = 4;
int line_num = 5;
map<int, int> col_map, line_map; //记录清零的行与列
int col_zero = 0, line_zero = 0; //清零行，列的个数
//遍历记录清零的行与列
for(int i = 0; i < line_num; ++i){
for(int j = 0; j < col_num; ++j){
if(matrix[i][j] == 0){
line_map[++line_zero] = i;
col_map[++col_zero] = j;
}
}
}
int tmp;
//所在行清零
while(line_zero > 0){
tmp = line_map[line_zero];
for(int i = 0; i < col_num; ++i){
matrix[tmp][i] = 0;
}
--line_zero;
}
printMatrix(matrix);
//所在列清零
while(col_zero > 0){
tmp = col_map[col_zero];
for(int i = 0; i < line_num; ++i){
matrix[i][tmp] = 0;
}
--col_zero;
}
printMatrix(matrix);
}
//=====================不用额外空间实现：Accepted=====================//
void setZeroes(int matrix[1][2]) {
int col_num = 2;
int line_num = 1;
bool flag_line = false,flag_col = false;
//判断第零行是否有0
for(int i = 0; i < col_num; ++i){
if(matrix[0][i] == 0){
flag_line = true;
break;
}
}
//判断第零列是否有0
for(int i = 0; i < line_num; ++i){
if(matrix[i][0] == 0){
flag_col = true;
break;
}
}
//将出现0的行，列记录到第0行和第零列上
for(int i = 1; i < line_num; ++i){
for(int j = 1; j < col_num; ++j){
if(matrix[i][j] == 0){
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
//清零
for(int i = 1; i < line_num; ++i){
for(int j = 1; j < col_num; ++j){
if(matrix[i][0] == 0 || matrix[0][j] == 0){
matrix[i][j] = 0;
}
}
}
//判断第零行,第零列是否要清零
if(flag_line){
for(int i = 0; i < col_num; ++i){
matrix[0][i] = 0;
}
}
if(flag_col){
for(int i = 0; i < line_num; ++i){
matrix[i][0] = 0;
}
}
printMatrix(matrix);
}
};
#endif
