算法学习笔记

排序

  • 三路快排
    语言标准库中快排的基本实现
  • 插入排序
    近乎有序的数据排序
  • 计数排序
    数据范围有限

    排序要求

    存储结构

    链表:归并
    数组:快排

    存储位置

    大量数据存储在硬盘中:外部排序

    链接

    www.hackerrank.com

回答思路

  • 注意问题条件和范围,数据规模
  • 简单测试用例,暴力解法
  • 不要说没有思路
  • 遍历常见的数据结构和算法思路
  • 优化方法
    • 空间和时间的交换(哈希表)
    • 预处理数据(排序)
    • 在瓶颈处寻找优化

递归和回溯

树形问题

Letter Combinations of a Phone Number

https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/

题目描述

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

1
2
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

分析

给出一个数字字符串,返回这个数字字符串能表示的所有字母组合

  • 字符串的合法性
  • 空字符串
  • 多解的顺序
    数字和字符的对应关系
1
2
3
4
5
6
7
8
9
10
11
12
const string letterMap[10] = {
" ", //0
"", //1
"abc", //2
"def", //3
"ghi", //4
"jkl", //5
"mno", //6
"pqrs", //7
"tuv", //8
"wxyz" //9
};

当输入的数据为 digits = "23"时,生成的字符串可以通过树形结构进行遍历🏪。

1
2
3
4
递推公式
s(digits[0...n-1])
= letter(digits[0]) + s(digits[1...n-1])
= letter(digits[0]) + letter(digits[1]) + s(digits[2...n-1])

递归中的return是回到上一层,变量加 1 后继续进行。

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
class Solution {
private:
const string letterMap[10] = {
" ", //0
"", //1
"abc", //2
"def", //3
"ghi", //4
"jkl", //5
"mno", //6
"pqrs", //7
"tuv", //8
"wxyz" //9
};
vector<string> res;
void findCombination(const string &digits, int index, const string &s){
if(index == digits.size()){
res.push_back(s);
return;
}
char c = digits[index];
assert(c >= '0' && c <= '9' && c !='1');
string letters = letterMap[c-'0'];
for(int i = 0 ; i < letters.size() ; i++){
//递归
findCombination(digits,index+1,s + letters[i]);
}
return;
}
public:
vector<string> letterCombinations(string digits) {
res.clear();
if( digits == "")
return res;
findCombination(digits, 0 , "");
return res;
}
};
int main() {
vector<string> res = Solution().letterCombinations("234");
for( int i = 0 ; i < res.size() ; i ++ )
cout<<res[i]<<endl;
return 0;
}

回溯
递归调用的性质是 递归调用结束之后需要返回到上一层继续调用,直到根节点。