算法
什么是大O
n表示数据规模
O(f(n))表示运行算法所需要执行的指令数，和f(n)成正比
二分查找法O(logn) 所需执行指令数：alogn
寻找数组中的最大/最小值 所需执行指令数：bn
归并排序算法O(nlogn) 所需指令数：cnlogn
选择排序法O(n^2) 所需指令数：dn^2
算法A： O(n) 所需指令数：10000n
算法B： O(n^2) 所需指令数: 10n^2
在学术界，严格来讲，O(f(n))表示算法执行的上界
归并排序算法的时间复杂度是O(nlogn)的，同时也是O(n^2)
在业界，我们使用O来表示算法执行的最低上界
对邻接表实现的图进行遍历：
时间复杂度： O(V+E)
！在这里V是图中顶点个数，E是图中边的个数 V和E没有关系 不能替换
插入排序算法 O(n^2) 快速排序算法O(nlogn)
最差情况： O(n^2) 最差情况O(n^2)
最好情况： O(n) 最好情况：O(nlogn)
平均情况： O(n^2) 平均情况：O(nlogn)
例题1
一个时间复杂度的问题
有一个字符串数组，将数组中的每一个字符串按照字母序进行排序；之后再将整个字符串数组按照字典序排序。整个操作的时间复杂度？
假设最长的字符串长度为s；数组中有n个字符串
对每个字符串排序：O(slogs)
将数组中的每一个字符串按照字母序: O(nslog(s)+)
将整个字符串数组按照字典序排序： O(snlog(n))
O(nslog(s)) + O(snlog(n)) = O(nslog(s)+snlog(n))
数据规模的概念
如果想要在1s内解决问题：
O(n^2)的算法可以处理大约10^4级别的数据
O(n)的算法可以处理大约10^8级别的数据
O(nlogn)的算法可以处理大约10^7级别的数据
空间复杂度
多开一个辅助的数组： O(n)
多开一个辅助的二维数组： O(n^2)
多开常数空间： O(1)
递归调用是有空间代价的
复杂度
O(1)
void swapTwoInts(int &a,int &b){
int temp = a;
a = b;
b = temp
}O(n)
int sum(int n){
int ret = 0;
for(int i = 0;i<=n;i++)
ret +=i;
return ret;
}O(n)
void reverse(string &s){
int n = s.size();
for(int i = 0;i<n/2;i++)
swap(s[i],s[n-1-i]);
}1/2* n次swap操作： O(n)
O(n^2)
void selectionSort(int arr[],int n){
for (int i =0;i<n;i++){
int minIndex = i;
for (int j =i+1;j<n;k++)
if (arr[j] <arr[minIndex])
minIndex = j;
swap(arr[i],arr[minIndex])
}
}(n-1)+(n-2)+…+0
1/2* n^2 -1/2* n =O(n^2)
O(n^2)?
void printInformation(int n){
for(int i =1;i<=n;i++)
for(int j =1;j<=30;j++)
cout<<"class"<<i<<"-"<<"NO."<<j<<endl;
return;
}30n次基本操作：O(n)
O(logn)
int binarySearch(int arr[],int n;int target){
int l =0,r = n-1;
while(l<=r){
int mid = l+(r-l)/2;
if(arr[mid] == target)
return mid;
if(arr[mid] > target)
r = mid - 1;
else
l = mid + 1;
}
return -1;
}n
n/2
n/4
.
.
.
1
n经过几次除以2操作后，等于1
log2 n = O(logn)
O(logn)
string inToString(int sum){
string s = " ";
while(num){
s += '0'+num%10; //int类型变成char类型，就需要加上一个’0’了
num /=10;
}
reverse(s);
return s;
}n经过几次除以10操作后，等于0
?num为负数的情况下？
O(n^2)
void hello(int n){
for(int sz = 1;sz < n;sz += sz)
for(int i =1;i<n;i++)
cout<<"Hello,Algorithm"<<endl;
} 第一层循环中 ，实际上sz每次增加为2* sz
换种理解方式第一层循环执行的次数 = n经过几次除以2之后等于1
所以执行数为O(logn)
总执行数为O(nlogn)
O(sqrt(n))
判断一个数是否为素数
bool isPrime(int n){
for(int x =2;x*x<=n;x++)
if(n%x == 0)
return false;
return true;
}递归算法的复杂度分析
double pow(double x,int n){
assert(n >=0 );
if (n == 0)
return 1.0;
double t = pow(x,n/2);
if(n%2) //判断是否能被2整除
return x*t*t;
return t*t;
}如果一个一个相乘计算，时间复杂度为O(n)
这里通过递归调用 降低了时间复杂度
递归深度： logn
时间复杂度: O(logn)
递归中进行多次递归调用
int f(int n){
assert(n>=0);
if(n==0)
return 1;
return f(n-1)+f(n-1);
}多次递归调用，实际上是算树的有多少节点
时间复杂度O(2^n)
指数级算法计算效果非常差
主定理？
均摊复杂度分析 Amortized Time
动态数组(vector)
#include<iostream>
using namespace std;
template<typename T>
class Myvector{
private:
T *data;
int capacity;
int size;
void resize(int newCapacity){
T *newData = new T[newCapacity];
for(int i =0;i<size;i++)
newData[i] = data[i];
delete[]data;
data = newData;
capacity = newCapacity;
}
public:
Myvector(){
data = new T[10];
capacity = 10;
size = 0;
}
~Myvector(){
delete[] data;
}
//average : O(1)
void push_back(T e){
if(size==capacity)
resize(2*capacity);
data[size++] = e;
}
//O(1)
T pop_back(){
assert(size>0);
T ret = data[size-1];
size--; //没有真正的把最后一个元素删除，而是把整个元素放在合法范围外
if(size == capacity/4) //这里在某一临界值，程序处于连续增大内存空间与删除内存空间的操作，所以为了避免时间复杂度的震荡，在这里把临界值改为1/4 capacity
resize (capacity/2);
return ret;
}
};
动态数组
动态栈
动态队列
数组算法问题
如何写出正确的程序
明确变量的含义
循环不变量
小数据量调试
大数据量调试
二分查找法
对于有序数列，才能使用二分查找法（排序的作用）
#include<iostream>
#include<cmath>
#include<cassert>
#include<ctime>
using namespace std;
template<typename T>
int binarySearch(T arr[],int n,T target){
int l = 0,r = n-1; //在[l,r]范围 里寻找target
while(l<=r){ //当l==r时，区间[l.....r]依然是有效的
int mid = (l+r)/2; //为了防止整型溢出 mid = l + (r-l)/2
if (arr[mid] == target)
return mid;
if(target>arr[mid])
l = mid +1; //target在[mid+1...r]中
else
r = mid -1;//targer在[l...mid-1]中
}
return -1;
}
int main(){
return 0;
}真实面试问题
问题283：
给定一个数组nums,写一个函数，将数组中的所有的0挪到数组的末尾，而维持其他所有非0元素的相对位置。
举例：
nums = [0,1,0,3,12]，函数运行后的结果为[1,3,12,0,0]
class Solution{
public:
//时间复杂度：O(n)
//空间复杂度：O(n)
void moveZeroes(vector <int>& nums){
vector <int> nonZeroElements;
for(i =0;i<nums.size();i++)
if(nums[i]) //判断数组是否非0
nonZeroElements.push_back(num[i]);//pushback压入非零数组
for(int i =0;i<nonZeroElements.size();i++) //遍历一边非零数组 将其再赋值给原数组
num[i] = nonZeroElements[i];
for(int i = nonZeroElements.size();i<num.size();i++) //在数组后面空余位置补充0
num[i] = 0;
}
}
int main(){
int arr[0,1,0,3,12];
vector<int> vec(arr,arr+sizeof(arr)/sizeof(int));
Solution().moveZeroes(vec);
for(int i=0;i<vec.size();i++)
cout<<vec[i]<<" ";
cout<<endl;
}优化:不用辅助空间
class Solution{
public:
//时间复杂度：O(n)
//空间复杂度 :O(1)
void moveZeroes(vector <int>& nums){
int k =0; //索引k nums中,[0,k)的元素均为非0元素
//遍历到第i个元素后，保证[0...i]中所有非0元素
//都按照顺序排列在[0..k]中
for(i =0;i<nums.size();i++)
if(nums[i]) //判断数组是否非0
nums[k++] = nums[i];
for(int i =0;i<num.size();i++)
num[i] = 0;
}
}
继续优化：
交换排序比一个个赋值香
class Solution{
public:
//时间复杂度：O(n)
//空间复杂度 :O(1)
void moveZeroes(vector <int>& nums){
int k =0; //索引k nums中,[0,k)的元素均为非0元素
//遍历到第i个元素后，保证[0...i]中所有非0元素
//都按照顺序排列在[0..k]中
//同时[k...i]为0
for(i =0;i<nums.size();i++)
if(nums[i]) //判断数组是否非0
swap(nums[k++],nums[i]);
}
}
我TM再优化:
当元素都为0的时候交换消耗时间
再增加一个条件语句
class Solution{
public:
//时间复杂度：O(n)
//空间复杂度 :O(1)
void moveZeroes(vector <int>& nums){
int k =0; //索引k nums中,[0,k)的元素均为非0元素
//遍历到第i个元素后，保证[0...i]中所有非0元素
//都按照顺序排列在[0..k]中
//同时[k...i]为0
for(i =0;i<nums.size();i++)
if(nums[i]) //判断数组是否非0
if(i!=k)
swap(nums[k++],nums[i]);
else //i==k
k++;
}
}
Remove Element
问题27：
给定一个数组nums和一个数值val,将数组中所有等于val的元素删除，并返回剩余的元素个数
如何定义删除？从数组中删除？还是放在数组末尾？
剩余元素的排列是否要保证原有的相对顺序？
是否有空间复杂度的要求？
问题26：
给定一个有序数组，对数组中的元素去重，使得原数组的每个元素只有一个，并返回去重后数组的长度值
问题80：
给定一个有序数组，对数组中的元素去重，使得原数组的每个元素最多保留两个。返回去重后的长度值
如nums = [1,1,1,2,2,3]
结果返回应为5，返回的元素1,1,2,2,3
基础算法思路的应用
问题75：
给定一个有n个元素的数组，数组中元素的取值只有0，1，2三种可能，为这个数组排序
-可以使用任意一种排序算法
-没有使用上题目中给出的特殊条件
#include<iostream>
#include<cassert>
#include<vector>
using namespace std;
class Solution{
public:
void SortColors(vector <int> &nums){
int count[3] = {0}; //存放0，1，2的频率
for (int i = 0; i < nums.size();i++)
assert(num[i] >= 0 && num[i] <= 2);
count[nums[i]]++; //计算频率
}
int index = 0;
for (int i = 0;i<count[0],i++)
nums[index++] = 0;
for (int i = 0; i < count[1];i++)
nums[index++] = 1;
for (int i = 0; i < count[2];i++)
nums[i] = 2;
}前者多次遍历数组，进行优化
class Solution{
//时间复杂度O(n)
//空间复杂度O(1)
//只遍历一遍
public:
void SortColors(vector <int> &nums){
int zero = -1;//nums[0...zero] == 0 前后闭区间，这样当zero等于-1的时候区间无效不会算为0
int two = nums.size() //nums[two...n-1] == 2
for (int i = 0; i < two;) {
if (nums[i] == 1)
i++;
else if (nums[i] == 2)
swap(nums[i], nums[--two]);
else if(nums[i]==0)
zero++;
swap(nums[zero], nums[i]);//swap(nums[++zero],nums[i++])简写
i++;
}
}
}
问题88：
给定两个有序整型数组nums1,nums2,将nums2的元素归并到nums1
问题215:
在一个整数序列中寻找第k大的元素
-如给定数组[3,2,1,5,6,4],k=2,结果为5
利用快排partition,将pivot放置在了其正确的位置上的性质
问题167:
给定一个有序整型数组和一个整数target，在其中寻找两个元素，使其和为target,返回这两个数的索引。
如numbers = [2,7,11,15],target = 9;
返回数字2，7的索引1，2 （索引从1开始计算）
-如果没有解的情况下？
-如果有多个解的情况？返回任意解
class Solution{
public:
vector <int> twoSum(vector &numbers,int target){
int l =0;,r=number.size()-1;
while(l<r){
if(numbers[r]==target){
int res[2] = {l +1 ,r+ 1};
return vector<int> (res,res+2);
}
else if(numbers[l]+numbers[r]<target)
l++;
else
r--;
}
throw invalid_argument("The input has no solution.")
}
}问题125：
给定一个字符串，只看其中的数字和字母，忽略大小写，判断这个字符串是否为回文串？
-空字符串如何看
-字符的定义
-大小写问题
问题344：
给定一个字符串，返回这个字符串的倒序字符串
如hello，返回olleh
类似：翻转一个数组
问题345:
给定一个字符串，将该字符串中的元音字母翻转
如hello，返回holle
原因不包含y
问题11：
给出一个非负整数数组a1…an;每一个整数表示一个竖立在坐标轴x位置的一堵高度为ai的墙，选择两堵墙，和x轴构成的容器容纳最多的水
问题：209
双索引技术 Facebook
给定一个数组和一个数字s，找到数组中最短的一个连续子数组，使得连续子数组的数字和sum>=s,返回这个最短的连续子数组的长度值
- 如 给定数组[2,3,1,2,4,3]，s=7
- 答案为[4,3] 返回2
什么叫子数组
子数组可以不连续，此题中强调连续子数组
如果没有解怎么办 返回0？
暴力解：遍历所有的连续子数组[i…j]
计算其和sum 验证sum>=s
时间复杂度为O(n^3)
优化暴力解 O(n^2)？
class Solution{
//时间复杂度O(n)
//空间复杂度O(1)
public:
int minSubArrayLen(int s,vector<int> &nums){
int l =0,r=-1; //这里的关键是设置滑动窗口，初始范围为nums[l,r] r=-1初始值无效
int sum = 0;
int res = nums.size()+1;
while(l<nums.size()){
if(r+1<nums.size()&&sum<s){
r++;
sum+=nums[r];
else
sum-=nums[l++];
if(sum==s)
res = min(res,l-r+1);//闭区间
}
if(res = nums.size()+1) //当遍历一遍之后没有解，则返回0
return 0;
return res;
}
}
}例题3：
在一个字符串中寻找没有重复字母的最长子串
如“abcccaa” abc
字符集，只有字母？数字+字母？ASCII？
大小写是否敏感？
class Solution(){
public:
int lengthOfLongestSubstring(string s){
int freq[256] = {0};
int l =0,r=-1; //滑动窗口为s[l...r]
int res = 0;
while(l<s.size()){
if (r+1<s.size()&&freq[s[r+1]] == 0)
freq[s[++r]]++；
else
freq[s[l++]]--;//如果重复了，这里将频率-1，左边界右移
res = max(res,r-l+1);
}
return res;
}
}例题438：
给定一个字符串s和一个非空字符串p,找出p中所有是s的anagrams字符串的子串，返回这些字串的起始索引。
如s=”cbaebabacd” p=”abc” 索引[0,6]
字符集范围？英文小写字母
返回解的顺序？任意
例题 76:
给定一个字符串S和T，在S中寻找最短的子串，包含T中的所有字符
如S=”ADOBECODEBANC” T=”ABC”
结果为”BANC”
