题目都是来自牛客网在线刷题中的剑指offer。刷题记录，顺便从考察知识点的角度分类整理。主要分成以下四大类：
- 字符串、数组
- 链表、树
- 递归、回溯、动态规划
- 其他, 比如位运算、正则匹配等
这是剑指offer 系列四部曲中的第一部。第一部关于字符串和数组，第二部是栈、队列、链表和树，第三部递归、回溯和动态规划， 最后一部分在这里。
（1）二维数组中的查找
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
列的递增不是基于上一行中最大的（最右边）进行的递增，而是基于上一行对应的列的递增。所以不是左上角是最小，右下角是最大的。
双指针问题，对于任意的一点，下面的都是比其大，左面的都是比其小，这就决定了做好的出发点是从右上角出发。这样可以不断的进行if … else 的判断，然后找到 target。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
if not array: return True
n, m =len(array), len(array[0])
i , j =0, m-1
while i<n and j>=0:
if(target ==array[i][j]):
return True
elif (target > array[i][j]):
i+=1
else:
j-=1
return False
|
c++ 版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public:
// 时间 O(m+n), 空间O(1)
bool Find(int target, vector<vector<int> > array) {
if(array.empty()) return false;
int n =array.size(), m =array[0].size();
for(int i =0, j =m-1; i<n &&j>=0 ; )
{
if(target == array[i][j]) return true;
else if(target > array[i][j]) i+=1;
else j-=1;
}
return false;
}
};
|
（2）替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
Tips： 字符串的遍历对于 python 而言是比较简单的。
考察的就是字符串的遍历。如果发现了空格，那么替换成 “%20”，否则就是原字符。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
# -*- coding:utf-8 -*-
class Solution:
# s 源字符串
# 时间 O(n), 空间 O(n), n =len(s)
def replaceSpace(self, s):
# write code here
if not s: return ""
res =""
for ch in s:
if ch ==" ":
res +="%20"
else: res += ch
return res
|
在 c++ 读入和读出 sring，不能使用 cin，因为cin 读入是以空格分割的。但是读入的一个字符串不能这样。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include<iostream>
#include<string>
using namespace std;
const int N =10010;
string replaceSpace(string str)
{
string res;
for(auto x: str)
{
if (x ==' ') res += "%20";
else res += x;
}
return res;
}
int main()
{
char str[N];
gets(str);
cout<< str<<endl;
string res =replaceSpace(str);
cout<< res<<endl;
return 0;
}
|
（3）旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
时间复杂度最坏是$0(N)$， 但是对于一般情况下，是可以优化的。因为这个数据特点是存在重复的元素。本题中的比较对象是 arr[0]。
1
2
3
4
5
6
7
8
9
10
11
|
# 注意python 中判断条件是需要有 :, 而在c++中需要有 {}
def minNumber(arr):
n =len(arr)-1
if n <0: return 0
while(n and arr[0] ==arr[n]): n -=1
l, r =0, n
while(l <r):
mid = l+r >>1
if(arr[0] > arr[mid]): r =mid
else: l =mid +1
return arr[l]
|
c++ 版本。时间复杂度最坏是 $O(n)$, 但是一般的时间复杂度是 $O(logn)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include<iostream>
#include<vector>
using namespace std;
const int MAX =1010;
int n;
vector<int> arr(MAX);
int minNumber(vector<int> arr)
{
while(n && arr[n] ==arr[0]) n--;
int l =0, r =n;
while(l <r)
{
int mid = l+r >>1;
if(arr[0] > arr[mid]) r =mid;
else l =mid +1;
}
return arr[l];
}
int main()
{
cin>>n;
for(int i =0; i<n;i++)
cin >> arr[i];
cout<< minNumber(arr)<< endl;
return 0;
}
|
（4）调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
快排是根据阈值分别左右挑选了大于和小于阈值的数组。这道题是可以分别左右分别挑选偶数和奇数，然后交换位置，思路是一样的。双指针问题，使用 while语句查找，如果找到，使用 swap() 函数交换。代码格式和快排很像。快排的实现和双指针基本上是等号的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#include<iostream>
#include<vector>
using namespace std;
const int N =1000;
// 奇数在前 偶数在后
void reOrder(vector<int> &arr)
{
int i =0, j =arr.size() -1;
while( i<=j)
{
while(i <=j && arr[j] %2 ==0) j-=1;
while(i <=j && arr[i] %2 ==1) i+=1;
if(i <=j) swap(arr[i], arr[j]); // 在上面的执行过程中，有可能i 和j 已经不满足相对的关系，所以是需要进行判断
}
}
int main()
{
vector<int> arr(N);
int n;
cin >>n;
for(int i =0; i<n; i++) cin>> arr[i];
reOrder(arr);
for(int i=0; i<n; i++) cout<< arr[i] << " ";
cout<<endl;
return 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
def partition(arr):
if not arr or len(arr) ==0:
return
left, right =0, len(arr)-1
while left < right:
print(arr[left])
while arr[left] %2 ==0:# 奇偶判断的时候，尽量不要使用整除，python2 python3 的语法环境是不一样的
left +=1
while arr[right] % 2 ==1:
right -=1
if (left< right): arr[left], arr[right] =arr[right], arr[left]
if __name__ =="__main__":
arr =[1,2, 3, 4, 5]
partition(arr)
print(arr)
|
上面版本保留了原始数字相对的顺序，下面这个没有保留相对的顺序。前者的空间复杂度是 $O(N)$, 后者的空间复杂度是 $O(1)$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution:
def reOrderArray(self, array):
if len(array) ==0:
return []
left =0
right =len(array)-1
while left < right:
# 如果是奇数
key =array[left]
while left < right and array[right] & 1 == 0:
right -= 1
array[left] = array[right]
# 如果是偶数
while left < right and array[left] & 1 == 1:
left += 1
array[right] = key
return array
|
（5）字符串的全排列
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
N 表示字符串的长度。时间复杂度$ O(N * N!)$ 空间复杂度 $O(N *N!)$
python 具有更加简单的写法。实现过程中主要是用到python 的字符串的切片。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
# -*- coding:utf-8 -*-
class Solution:
def dfs(self, ss, path, res):
if not ss:
res.append(path)
for i in range(len(ss)):
self.dfs(ss[:i] +ss[i+1:], path+ss[i], res)
def Permutation(self, ss):
# write code here
if not ss: return ss
res =[]
self.dfs(ss, "", res)
return sorted(list(set(res)))
|
c++ 实现的时候是通过 swap() 函数形成不同的组合，需要注意的是如果没有返回值的话，那么 res是引用，而不是每次调用的时候都重新申请一个栈空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public:
void dfs(string str, int u, vector<string>& res)
{
if(u == str.size())
res.emplace_back(str);
for(int i =u; i< str.size(); i++)
{
if (i != u && str[u] ==str[i]) continue;
swap(str[i], str[u]);
dfs(str, u +1, res);
swap(str[i], str[u]);
}
}
vector<string> Permutation(string str) {
vector<string> res;
if (str.empty()) return res;
dfs(str, 0,res);
sort(res.begin(), res.end());
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include<iostream>
#include<vector>
using namespace std;
/*
每一个递归都是对应着一个递归树，所以好好思考这个过程。
有两种思路，一种是枚举每个位置上放哪些数字；一种是枚举每个数字放到哪些位置上。差别在于同一层中数字的不同的摆放形式。
*/
vector<int> arr;
int n;
vector<vector<int>> ans;
vector<int> path;
vector<bool> st;
// u 表示底基层, 这个代码是枚举位置（每个位置可以放什么数字）状态就是位置
void dfs(vector<int> arr, int u)
{
if(u ==n)
{
ans.push_back(path);
return;
}
for(int i =0;i< n; i++ )
{
if(!st[i])
{
st[i] =true;
path.push_back(arr[i]);
dfs(arr, u+1);
st[i] =false;
path.pop_back();
}
}
}
int main()
{
cin>>n;
arr =vector<int>(n);
for(int i =0; i<n; i++) cin>>arr[i];
st =vector<bool>(n);
dfs(arr, 0);
for(auto u: ans)
{
for(auto v: u)
cout<< v<<" ";
cout<<endl;
}
return 0;
}
|
（7）数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
Tips： 如果某个数字出现的次数多于一半，那么其他所有非该数字的出现的频数是小于该数字的，所以形成一个二分类。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
# 如果存在这样的数字，那么这个数字的频数一定是大于其他所有的频数
def MoreThanHalfNum_Solution(self, numbers):
# write code here
if not numbers:
return 0
target = numbers[0]
nums = 0
# 统计出现次数最多的数字
for i in numbers:
if target == i:
nums += 1
elif nums == 0:
target = i
nums = 1
else:
nums -= 1
res = target if numbers.count(target) > len(numbers) // 2 else 0
return res
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
int target =numbers[0];
int counts =1;
for(int i =1; i< numbers.size(); i++)
{
if(target == numbers[i]) counts +=1;
else counts -=1;
if(counts ==0)
{
target =numbers[i];
counts =1;
}
}
int c =0;
for(auto num : numbers)
{
if(num ==target)
c ++;
}
if(c > numbers.size() >>1) return target;
return 0;
}
};
|
（8）连续子数组的最大和
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
连续子数组的最大和和数组中超过一半的数字，这种问题都是属于数组的遍历问题。 最笨的方法先是枚举子数组，然后计算；但是问题是不要求求解 该子数组，只是要求最大和。时间复杂度 $O(N) $, 空间 $O(1) $
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
int max_v =array[0];
int val =0;
for(auto num : array)
{
if (val <0) val =0;
val += num; // 这个操作是无脑加上，后面的max 进行判断
max_v =max(max_v, val);
}
return max_v;
}
};
|
（9）第一个只出现一次的字符
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.
如果使用了 dictionary，那么这个只是数据结构上的问题，不存在算法上的问题了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
class Solution:
"""
Three ways to get dictionary of string s
"""
def FirstNotRepeatingChar(self, s):
if not s:
return -1
# get dictionary
from collections import defaultdict
dict1 =defaultdict(int)
for string in s:
dict1[string] += 1
# or this way
# from collections import Counter
# dict1 =Counter(s)
# or do it yourself
#dict1 =self.Counter_self(s)
for index, val in enumerate(s):
if dict1[val] == 1:
return -1
def Counter_self(self, s):
dict1 = {}
for val in s:
if val not in dict1:
dict1[val] = 1
else:
dict1[val] = dict1[val] + 1
return dict1
|
C++ 实现。本质上还是dictionary 的思想，统计每个字母出现的个数，然后遍历，时间复杂度是$O(n)$，空间是$O(n)$。当字符串比较长的时候，可以进一步优化，辅助的数组记录字符出现的最小的index。这要求在预处理的时候，进行判断一下。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
int firstUniqChar(string s) {
vector<int> arr(26, 0);
for(int i =0; i< s.size(); i++)
{
arr[s[i] -'a'] ++;
}
for(int i =0; i< s.size(); i++)
if(arr[s[i] -'a'] ==1) return i;
return -1;
}
};
|
（10）数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
# -*- coding:utf-8 -*-
class Solution:
def InversePairs(self, data):
# write code here
if not data:
return 0
temp = [i for i in data]
return self.mergeSort(temp, data, 0, len(data ) -1) % 1000000007
def mergeSort(self, temp, data, low, high):
if low >= high:
temp[low] = data[low]
return 0
mid = (low + high) / 2
left = self.mergeSort(data, temp, low, mid)
right = self.mergeSort(data, temp, mid +1, high)
count = 0
i = low
j = mid +1
index = low
while i <= mid and j <= high:
if data[i] <= data[j]:
temp[index] = data[i]
i += 1
else:
temp[index] = data[j]
count += mid - i +1
j += 1
index += 1
while i <= mid:
temp[index] = data[i]
i += 1
index += 1
while j <= high:
temp[index] = data[j]
j += 1
index += 1
return count + left + right
|
c++ 写法。逆序对的个数等于左边的逆序对个数、右边逆序对的个数和交叉（一个在左边一个在右边）逆序对的个数，对于前两种是可以通过递归求解，对于第三种在递归的过程中是可解的。时间复杂度是$O(nlogn)$ 空间复杂度是$O(n)$。$log n $的时间复杂度和 $n$ 是有很大区别的， 当 $n=10^6 $时候，$logn =20$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
class Solution {
public:
int merge(vector<int> & nums, int l, int r)
{
if(l >= r) return 0;
int mid =(l +r) >>1;
int res = merge(nums, l, mid) +merge(nums, mid+1, r);
int i =l, j =mid+1; // 别归并排序都不会写了
vector<int> temp;
while(i <= mid && j<= r)
{
if(nums[i] <= nums[j]) temp.push_back(nums[i++]); // 这个写的是非常的简洁的
else
{
temp.push_back(nums[j++]);
res += mid -i +1;
}
}
while(i <=mid) temp.push_back(nums[i++]);
while(j <= r) temp.push_back(nums[j++]);
// 下面将 temp 数组返回到nums中, temp 是已经排好序的
i =l;
for(auto x : temp) nums[i++] =x;
return res;
}
int InversePairs(vector<int> data) {
return merge(data, 0, data.size() -1);
}
};
|
（11）数字在排序数组中出现的次数
统计一个数字在排序数组中出现的次数。
对于有序数组的查找，统计某个数字的次数，所以就找到其左右边界left 和right，最后次数就是 right- left +1。那么时间复杂度是 $O(logn)$。注意处理边界问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution {
public:
int GetNumberOfK(vector<int> data ,int k) {
if( data.empty()) return 0;
int l =0, r =data.size() -1;
while( l<r)
{
int mid = (l+r )>>1;
if(data[mid] >= k) r =mid ;
else l =mid +1;
}
if (data[l] != k) return 0;
int left =l;
l =0, r =data.size() -1;
while(l<r)
{
int mid = (l +r +1) >>1;
if(data[mid] > k) r =mid-1;
else l =mid;
}
return l -left +1;
}
};
|
（12）只有一个数字出现了一次，其他的数字都是出现了偶次，那么一遍遍历数（进行异或）就可以得到这个数字。现在是由两个单独的数字。
思路一：最常规的做法是使用dictionary 统计数字出现的次数，key 是数字，vaue 是数字的个数。时间复杂度是$O(n)$，空间复杂度是$O(n)$。
思路二：除了字典思路外，对于数字而言，还可以使用异或的操作。根据异或的性质，两两异或最后剩下的数字一定是出现一次的数字。时间复杂度是$O(n)$，空间复杂度是$O(1)$。
2^4 # 4
3^4 # 7
40^42 # 2
（12）数组中只出现一次的数字
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
使用index 得到两个不同的数字二进制形式下的位置，然后从该位置将原来的数组分成两类，那么每类中只含有一个出现一次的数字，接着使用异或操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
# 使用异或的性质，如果只有一个不同，其他的偶次出现，那么全部异或的结果
# 就是那个单一的数字
def FindNumsAppearOnce(self, array):
# write code here
remain, index =0, 1
for num in array:
remain = remain ^ num
# 找出第一个是1 的位置
# index 都是
while (remain & index) ==0:
index = index <<1
res1, res2 =0,0
for num in array:
# 这个条件必须是0, 表示两个在这个位数是相同的，
# 234 ^0 =234 ,
if num & index ==0:
res1 =res1 ^ num
else:
res2 =res2 ^ num
return [res1, res2]
|
这个是基于 c++ 的实现。很简洁
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
// 思路：找到位置为1 的位置，然后从该位置分开，分别处理得到两个单独的数字
vector<int> findNumsAppearOnce(vector<int>& nums) {
int x =0;
for(auto num : nums)
x ^= num;
int i =0;
while((x >>i & 1) ==0) i ++;
int a=0;
int b =0;
for(auto num : nums)
if(num >> i & 1)
a ^= num;
else
b ^= num;
return vector<int>{a, b};
}
};
|
（13）和为S的连续正数序列
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?
这个是数学问题，使用等差数列求和。还有一种解法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
def FindContinuousSequence(self, tsum):
# write code here
if tsum < 2:
return []
left = 1
right = left + 1
res = []
while left < tsum // 2 + 1:
if sum(range(left, right)) == tsum:
res.append(range(left, right))
left += 1
elif sum(range(left, right)) < tsum:
right += 1
else:
left += 1
return res
|
双指针问题，可以在 O(n) 时间内解决。 如果是条件判断，那么最好从定义出发使用 while 进行判断。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
vector<vector<int> > findContinuousSequence(int sum) {
vector<vector<int>> res;
int i =1, j =1, s =1;
while (i < sum) // 注意这个条件
{
while(s < sum ) s += ++j; // 这个操作也是比较骚
if(s ==sum && j -i >0)
{
vector<int> tmp;
for(int k =i; k<=j ; k++) tmp.push_back(k);
res.push_back(tmp);
}
s -= i;
i ++;
}
return res;
}
};
|
（14）和为S的两个数字
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
有序序列，查找两个数字，可以使用二分。二分查找和双指针算法有比较大的相关性。如果使用二分，那么二分的跳出条件和二分的判断条件是重点需要关注的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
if len(array) < 2:
return []
left = 0
right = len(array) - 1
while left < right:
if array[left] + array[right] == tsum:
return [array[left], array[right]]
elif array[left] + array[right] < tsum:
left += 1
else:
right -= 1
return []
|
时间复杂度是$O(N)$, 但是空间复杂度是 $O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
// 使用二分的思想去做， O(logn)
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
int l =0, r =array.size()-1;
while( l<r)
{
int tmp =array[l] + array[r];
if(tmp == sum) return vector<int>{array[l], array[r]};
else if( tmp > sum) r -=1;
else l +=1;
}
return vector<int>();
}
};
|
还有一种思路使用hash 表。这种时间复杂度也是 $O(n)$，但是空间上使用了 hash 表的操作。（这里使用的set ，因为只是判断是否存在）
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
unordered_set<int> hash;
for(auto a : array)
{
if (hash.count(sum -a)) return vector<int>{a, sum -a};
hash.insert(a);
}
return vector<int>();
}
};
|
所以总结来说，使用二分（双指针）思路，那么时间复杂度是$O(n)$，空间复杂度是$O(1)$； 使用hash表（unordered_set），时间复杂度是$O(n)$，空间复杂度是$O(n)$。所以hash 表这种预处理是一种可行解，不是最优解。
（15）左旋转字符串
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
python 中直接可以使用切片的思想。
1
2
3
4
5
6
|
class Solution:
def LeftRotateString(self, s, n):
# write code here
if len(s) < n:
return ''
return s[n:] + s[:n]
|
C++ 中时间复杂度是 $O(1)$ 空间复杂度是 $O(N)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#include<iostream>
#include<string>
using namespace std;
string reversek(string str, int k)
{
reverse(str.begin(), str.end());
reverse(str.begin(), str.begin() +str.size() -k);
reverse(str.begin() +str.size() -k, str.end());
return str;
}
// 这个getline() 不能同时输入 int 和 string 两个变量
int main()
{
int k =3 ;
//cin >>k;
string str;
getline(cin, str);
string res = reversek(str, 3);
cout<< res<< endl;
return 0;
}
|
（16）翻转单词顺序
牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
这个是通过两次翻转就可以解决，第一次是字符串的完全翻转，第二次是单词的完全翻转。start, end 分别标记一个单词的开始和结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution:
def Reverse(self, s, left, right):
while left <right:
s[left], s[right] = s[right], s[left]
left +=1
right -=1
def ReverseSentence(self, s):
# write code here
if not s:
return s
# from immutable string to mutable list
# s =list(s)
self.Reverse(s, 0, len(s) - 1)
start, end = 0, 0
# 这个小于号 是python 中特有的坑，真正能够访问的区间是 [0, len(s)-1] 这样的区间
while start < len(s):
if s[start] == " ":
start += 1
end += 1
elif end == len(s) or s[end] == " ":
self.Reverse(s, start, end - 1)
# update 操作
end += 1
start = end
else:
end += 1
return "".join(s)
|
其中 string 的判断操作是非常经典的， i 和j 的操作，这个就是一个模板。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
// 整个字符串翻转，然后每个单词进行翻转 时间O(1) 空间是 o(N)
string ReverseSentence(string str) {
reverse(str.begin(), str.end());
for(int i =0; i< str.size(); i++)
{
int j =i;
while( j< str.size() && str[j] != ' ') j++;
reverse(str.begin() +i, str.begin() +j);
i =j;
}
return str;
}
};
|
（17）扑克牌顺子
LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大/小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。
模拟题
分成三步骤
- 删去所有的0
- 如果存在重复的元素，那么一定不是顺子
- 如果最大值和最小值之间的差距大于4 那么不是；如果小于4 那么就是。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
bool IsContinuous( vector<int> numbers ) {
if (!numbers.size() ) return false;
// 首先是要sort()
sort(numbers.begin(), numbers.end());
// 统计0 的个数
int i =0;
while (!numbers[i] ) i++;
// 如果有重复的，那么一定不能构成顺子
for(int j =i+1; j< numbers.size(); j++)
if(numbers[j] ==numbers[j-1]) return false;
// 只有最大的数字和最小的数字之间的间隔小于4，那么才有可能构成顺子
return numbers.back() -numbers[i] <=4;
}
};
|
（18）孩子们的游戏(圆圈中最后剩下的数)
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
Tips: 约瑟夫环的问题， 要求求解的是最后胜利者的编号，所以应用数学技巧就可以了。 $ f(x) = (f( x-1) + m ) % (x) $ , 共有 m 个编号，n 个人
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
# mod 求余 的操作， a mod b ==c ,说明 a除以b 之后余数是c
# https://blog.csdn.net/gatieme/article/details/51435055， 从做题思路上讲解的比较好
# n 个小朋友，然后是m 个编号
def LastRemaining_Solution(self, n, m):
# write code here
if n< 1 or m<1:
return -1
last =0
for i in range(2, n+1):
# 这个相当于 是一个 “挑选人” 的逆过程， 因为使用的 mod 操作就是取余的操作
last =(last +m) %i
return last
|
约瑟夫问题
使用递推的方式来做。相邻两项之间的关系，推导足够简单，那么就可以之间计算了。当去掉第m 个人之后，重新进行编号。需要寻找的是新旧编号之间的关系。
$f(n, m) = (f(n-1, m) +m ) % n$ 就是新旧编码中递推关系式。 其中 n 表示总共有n 个人，m 表示去掉m （m 表示数到的数字）个人。当n ==1 的时候（剩下一个人），那么可以跳出了。
（19）求1+2+3+…+n 之和
求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
有一种思路使用位运算， 然后结合递归进行求解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
# 如果你想使用全局变量，那么放在 __init__ 中就是一个很好的方式
def __init__(self):
self.ans =0
def Sum_Solution(self, n):
# write code here
self.recur(n)
return self.ans
# n>0 就是一个短路条件，这个直接决定了后面递归会不会继续执行下去，也就是跳出的条件
# 至于会不会回到原来最初的状态，这个是不重要的，最后的结果是 self.ans ，false之后直接使用这个就行了
def recur(self, n):
self.ans += n
n -= 1
return n > 0 and self.Sum_Solution(n)
|
（19）不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
对于两个数字（带有正负号），可以有四种组合同号（同为正数，同为负数）异号（正大负小，正小负大），可以归结为两个函数，fun1处理同号，fun2处理异号（正大负小）。
在二进制表示中，都是一样的（原码，反码和补码），不用分成正负数进行处理。使用异或和与操作分成三步进行
- 进行二进制加法（没有进位）
- 计算进位，如果进位不为0，那么继续
- 返回的是num1
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution{
public:
int Add(int num1, int num2)
{
while (num2 !=0)
{
int tmp =num1 ^ num2;
num2 = num1 & num2 <<1;
num1 =tmp;
}
return num1;
}
};
|
（20）把字符串转换成整数
将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。
Tips：还是python 中处理 string， 使用 dictionary 处理字符串和 数字的匹配。这个有好多个版本，是需要问清题目要求，然后根据进行作答。比如说这个是整数比较简单，如果加上小数，该如何处理。如果是中文，的该如何处理。
使用python 处理字符串问题。其实就是分情况一个个进行处理。
- 正负号
- 非整数类型字符
- 最后的边界问题 （python 中使用
sys.maxint判断）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
# -*- coding:utf-8 -*-
class Solution:
def StrToInt(self, s):
required =['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '+', '-']
n =len(s)
flag =1
res =0
for i in range(n):
if s[i] not in required:
return 0
elif s[i] =='-':
flag =-1
elif s[i] =='+':
continue
else:
res =res *10 + required.index(s[i])
res =res *flag
if res >=2147483648 or res <= -2147483649:
return 0
return res
|
c++ 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include<iostream>
#include<vector>
#include<string>
using namespace std;
// 处理空格，处理正负号，处理数字字母
int str2int(string str)
{
int k =0;
while(k < str.size() && str[k] ==' ') k++;
long long number =0;
// 这种对于 bool值的名称的定义
bool is_minus =false;
if(str[k] =='+') k ++;
else if(str[k] =='-') k++, is_minus =true;
for(; k< str.size() && str[k] >'0' && str[k] < '9'; k++)
{
number = number *10 + (str[k] -'0');
}
if(is_minus) number *= -1;
if(number > INT_MAX) return INT_MAX;
else if(number < INT_MIN) return INT_MIN;
return (int)number;
}
int main()
{
string str;
// 这个语句处理一个 string 的输入还是ok 的
getline(cin, str);
cout<<str2int(str)<<endl;
return 0;
}
|
（21）数组中重复的数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
(注意有的平台上的题目要求是不一样的，所以注意审题；当数字不在 [0, n-1] 的时候，题目要求是返回 -1)
解法一：使用dictionary 存储，key 表示数字，value 表示频数，时间复杂度是$O(n)$，空间复杂度是$O(n)$。
解法二：因为数组中存储的是 $[0, n-1]$的数字，和index 是相对应的。所以如果不相同，那么修改其相等为止，如果发现 numbers[i] 和 numbers[numbers[i]] 相等了，那么就找到了重复的数字；最后返回false。
如果有 [0, n-1]这种限制，那么是可以使用 for while 等结构，经常使用的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
# -*- coding:utf-8 -*-
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
len_ =len(numbers)
for i in range(len_):
while i != numbers[i]:
if numbers[numbers[i]] ==numbers[i]:
duplication[0] =numbers[i]
return True
else:
numbers[numbers[i]], numbers[i] =numbers[i], numbers[numbers[i]]
return False
|
（22）构建乘积数组
给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0] *A[1] *…*A[i-1] *A[i+1] *… *A[n-1]。不能使用除法。
Tips: 分成上下三角形进行计算，不能每个B[i] 都进行单独重复计算。下三角形是从上往下遍历，上三角形是从下往上遍历。ans 存储各个不同的结果。时间复杂度是$O(n)$，空间复杂度是$O(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution:
# A 是一个list ，只是自己构建的是一个矩阵
def multiply(self, A):
# write code here
ans =[]
tmp =1
length =len(A) # 值得是 rows
# 首先是下三角形 各个部分的数值的相乘， 从上往下遍历
for i in range(length):
ans.append(tmp)
tmp *= A[i]
tmp =1
# 上三角形 从下往上进行遍历
for i in range(length-1, -1, -1):
ans[i] *= tmp
tmp *= A[i]
return ans
|
这个题目的限制条件。
- 只能开辟一个数组空间的长度
- 不能使用除法
仔细观察两个for 循环，好的代码可读性也是很强的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include<iostream>
#include<string>
#include<vector>
using namespace std;
// 处理空格， 处理正负号，处理string 类型的数字
const int N =100;
vector<int> multiply(vector<int> arr, int n)
{
vector<int> res(n);
for(int i =0, p =1; i< n; i++)
{
res[i] =p;
p *= arr[i];
}
for(int i =n-1, p =1; i>=0; i--)
{
res[i] =p * res[i];
p *= arr[i];
}
return res;
}
int main()
{
int n;
vector<int> arr(N);
cin>>n;
for(int i =0; i<n;i++) cin>> arr[i];
vector<int> res =multiply(arr, n);
for(auto u: res) cout<< u<< " ";
cout<< endl;
return 0;
}
|
加深 对于 “~” 运算的理解 和对于 if 判断的理解。当 if 中条件是0 （对应bool 中的false）的时候，那么才会不执行，如果是 -1 那么也是可以执行的。但是这里没有必要写的那么简洁深邃，可以简单点写。
1
2
3
4
5
6
7
8
9
10
11
|
int main()
{
cout<< ~-1<< endl;
cout<< ~0 <<endl;
cout<< ~2 <<endl;
if( -3) cout<< "niubi "<< endl;
return 0;
}
|
（23）表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100",“5e2”,"-123",“3.1416"和”-1E-16"都表示数值。 但是"12e",“1a3.14”,“1.2.3”,"+-5"和"12e+4.3"都不是。
这个是一道判别题而不是 string to int 的题目。考察的是细节，从正负号，小数点， Ee和数字进行分类讨论。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
# -*- coding:utf-8 -*-
class Solution:
# s字符串
def isNumeric(self, s):
s =s.strip()
dots =e =digit =False # 这个都是flag
for i, char in enumerate(s):
if char in '+-':
if i > 0 and s[i-1] not in 'eE':
return False
elif char =='.':
if dots or e: return False
dots =True
elif char in 'eE':
if e or not digit:
return False
e, digit =True, False
elif char.isdigit():
digit =True
else:
return False
return digit
|
（24）字符流中第一个不重复的字符
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
流操作一般在笔试中不会考察。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
# 返回对应char
# 这个没有了dict 那么依赖于 count 函数
# 主要差别在于有了一个 字符流，是动态的，所以需要有一个大的存储的list
def __init__(self):
self.list1 =[]
def FirstAppearingOnce(self):
# write code here
for string in self.list1:
if self.list1.count(string) == 1:
return string
return "#"
def Insert(self, char):
# write code here
self.list1.append(char)
|
对于 $O(n^2)$ 算法复杂度，优化成 $O(n)$， 一般在面试的过程中，有两种优化算法，一种是双指针算法，一种是单调队列算法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
class Solution
{
public:
//Insert one char from stringstream
// 双指针算法，但在实现的时候不一定适用双指针
// 使用队列，可以节省内存
unordered_map<char, int> dic; // 这个维护的是一个dictionary
queue<char> q; // 这个维持的是一个 first appearing once 的队列
void Insert(char ch)
{
if( ++dic[ch] >1)
{
while(q.size() && dic[q.front()] >1) q.pop();
}
else
q.push(ch);
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
if(q.empty()) return '#';
return q.front();
}
};
|