共计 6363 个字符，预计需要花费 16 分钟才能阅读完成。
10-1 斐波那契数列
int Fibonacci(int n){
int a1,a2;
int t;
a1 = a2 =1;
if(n == 0){return 0;}
if(n == 1|| n==2){return 1;}
for(int i=3;i <= n;i++){
t = a1;
a1 += a2;
a2 = t;
}
return a1;
}10-2 矩形覆盖
int rectCover(int number) {
int a1,a2;
int t;
a1 = 2;
a2 = 1;
if(number == 0){return 0;}
if(number == 1){return 1;}else if(number == 2){return 2;}
for(int i=3;i <= number;i++){
t = a1;
a1 += a2;
a2 = t;
}
return a1;
}10-3 跳台阶
int jumpFloor(int number) {
int a1,a2;
int t;
a1 = 2;
a2 = 1;
if(number == 0){return 0;}
if(number == 1){return 1;}else if(number == 2){return 2;}
for(int i=3;i <= number;i++){
t = a1;
a1 += a2;
a2 = t;
}
return a1;
}10-4 变态跳台阶
int jumpFloorII(int number) {
int a1,a2;
int t;
a1 = 1;
if(number == 0){return 0;}
if(number == 1){return 1;}
for(int i=2;i <= number;i++){a1 = a1*2;}
return a1;
}11 旋转数组的最小数字 *
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组 {3,4,5,1,2} 为{1,2,3,4,5}的一个旋转，该数组的最小值为 1。
NOTE：给出的所有元素都大于 0，若数组大小为 0，请返回 0。
int minNumberInRotateArray(vector<int> rotateArray) {
int st,end,mid;
end = rotateArray.size()-1;
st = 0;
mid = (st+end)/2;
while(st < end-1){if(rotateArray[st] <= rotateArray[mid]){st = mid;}else{end = mid;}
mid = (st+end)/2;
}
return rotateArray[st] > rotateArray[end]?rotateArray[end]:rotateArray[st];
}12 矩阵中的路径 *
判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向上下左右移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
例如下面的矩阵包含了一条 bfce 路径
使用回溯法
int x[4]{1,0,-1,0};
int y[4]{0,1,0,-1};
int map[10000]={0};
bool find(char* matrix,int pos,int rows,int cols,char* str,int strpos){if(strlen(str) == strpos){return true;}
for(int i=0; i<4;i++){if(x[i] + pos/cols < 0
|| x[i] + pos/cols >= rows
|| y[i]+pos%cols >= cols
|| y[i]+pos%cols < 0){continue;}
if (map[pos+cols*x[i]+y[i]] == 0
&& matrix[pos+cols*x[i]+y[i]] == str[strpos]){map[pos+cols*x[i]+y[i]] = 1;
if(find(matrix,pos+cols*x[i]+y[i],rows,cols,str,strpos+1)){return true;}
map[pos+cols*x[i]+y[i]] = 0;
}
}
return false;
}
bool hasPath(char* matrix, int rows, int cols, char* str)
{for(int i = 0;i < rows;i++){for(int j =0;j < cols;j++){if (matrix[i*cols+j] == str[0]){map[i*cols+j] = 1;
if(find(matrix,i*cols+j,rows,cols,str,1)){return true;}
map[i*cols+j] = 0;
}
}
}
return false;
}
13 机器人运动范围 *
BFS, 宽度优先搜索
int map[1000][1000]={0};
int x[4]{1,0,-1,0};
int y[4]{0,1,0,-1};
stack<pair<int,int>> st;
bool IsCanIn(pair<int,int> pos, int threshold){
int temp;
int res = 0;
temp = pos.first;
while(temp){
res = res+temp%10;
temp /= 10;
}
temp = pos.second;
while(temp){
res = res+temp%10;
temp /= 10;
}
return threshold >= res ? true:false;
}
int movingCount(int threshold, int rows, int cols)
{
pair<int,int> pos;
int i;
int res = 0;
res ++;
if(threshold < 0){return 0;}
st.push(make_pair(0,0));
map[0][0] = 1;
while(!st.empty()){pos = st.top();
st.pop();
// cout << pos.first << "," << pos.second << endl;
for(i = 0;i < 4;i++){if(pos.first + x[i] >= rows ||
pos.first + x[i] < 0 ||
pos.second + y[i] >= cols ||
pos.second + y[i] < 0){continue;}
if(map[pos.first + x[i]][pos.second + y[i]] == 0&&
IsCanIn(make_pair(pos.first + x[i],pos.second + y[i]),threshold)){// 如果还没访问过, 且符合要求
map[pos.first + x[i]][pos.second + y[i]] = 1;
st.push(make_pair(pos.first + x[i], pos.second + y[i]));// 入栈
res++;
}
}
}
return res;
}14 剪绳子 **
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。- 当 n=1, 这是不可能的。
- 当 n=2, 分为 1,1，结果：1；
- 当 n=3, 分为 1,2，结果：2；
- 当 n=4, 分为 2,2，结果：4；
- 当 n>=5 时，我们可以证明 2(n-2)>n 并且 3(n-3)>n。当 n >= 5 的时候，2(n-2) > 3(n-3).
从以上可以知道，我们只需要尽可能的分配更多的 3 的绳子。还有一点就是为什么是 2 和 3，我不能是 4,5,6…. 这样分，这样分你怎么保证不会比分成 3 或 2 小呢。
注意，假如分成 4,5,6…，我们可以继续将其分成 2 或 3. 更具第 5 条可以知道，会比 n 更大，也就是说 n =5, 分成 2,3. 2*3 >5; 所以和不一开始就将其分成 2,3 呢。
贪心算法
int integerBreak(int n) {
int res = 1;
int temp = n;
if(n == 2){return 1;}else if(n == 3){return 2;}else if(n == 4){return 4;}
while(temp > 4){
temp -= 3;
res *= 3;
}
if(temp == 2){return res * 2;}else if(temp == 3){return res * 3;}else if(temp == 4){return res * 4;}
}https://rongxuanhong.github.i…
DP 动态规划
如果所求问题是求最优解，而且问题能够分解为若干个子问题，并且子问题之间还有重叠的更小的子问题，那么应该考虑应用动态规划思想求解。
在应用动态规划之前要分析能否把大问题分解成小问题，分解的每个小问题也存在最优解。如果把小问题的最优解组合起来能够得到这个问题的最优解，那么我们就可以应用动态规划解决这个问题。
总之，动态规划存在以下几个特点：
- 目标问题是求最优解；
- 整体的最优解可以由子问题的最优解参与或组合得到；
- 大问题可以分成若干个子问题，且子问题之间还有相互重叠的更小的子问题；
- 为避免重复求解子问题(后面求大问题的时候可能多次用到)，采用自下而上的顺序先计算小问题的最优解并记录到一维或二维数组中，再根据已经解出的小问题来求出大问题的最优解。简而言之，就是自上而下分析问题，自下而上求解问题。
首先定义函数 f(n) 为把长度为 n 的绳子剪成若干段后的最大乘积值。
剪绳子求的是最大乘积值满足特点 1；
如果在绳子的 i 处剪一刀，那么 f(n) 要达到乘积最大，则 f(i)与 f(n-i) 也要达到乘积最大，满足特点 2；
假设 n=6，那么 f(2) 和 f(4) 都是问题的子问题，但其实 f(2) 也是 f(4) 的子问题，那么就出现了重叠的更小的子问题，满足特点 3；所以，我们为了求解目标问题，都是先从小问题开始求解，即自下而上求解，并将每个子问题的乘积最大值记录到数组中备查，满足特点 4。
因此，本题的确适合采用动态规划求解。
当绳子长度为 2 的时候，只能剪成两段长度为 1，所以 f(2)=1；当绳子长度为 3 的时候，有两种剪法，其中最大的 f(3)=2。
那么当 n>4 的时候，我们要求出把长度为 i 的绳子剪成若干段之后各段长度乘积的最大值，即求 f(i)，而 4 <=i<=n，即要求出所有子问题的最优解。那么对于每个子问题 f(i)，由于可以有 i/2 种切法，所以我们应该遍历每种切法，并计算出乘积最大的那种切法。当切点在 j(1<=j<=i/2) 处时，子问题 f(i)=max(f(j)xf(i-j)), 其中 f(j),f(i-j)，都可以从备忘数组中查询得到。
int integerBreak(int n) {
// 1 显然不成立
// 在分配中也不能分配 1, 没意义.
int* dp = new int[n+1]{0};
if (n == 2){return 1;}else if(n == 3){return 2;}
// 如果可以不剪, 其最大就是本身.
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
for(int i = 4;i <= n;i++){for(int j = 1;j <= i/2;j++){dp[i] = max(dp[i],dp[i-j]*dp[j]);
}
}
return dp[n];
}15 二进制中 1 的个数
输入一个整数，输出该数二进制表示中 1 的个数。
int NumberOf1(int n) {
int res = 0;
int flag = 1;
while(flag){if(n & flag){res++;}
flag <<=1;
}
return res;
}16 数值的整数次方
给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent，求 base 的 exponent 次方。
注意 exponent 为负
double Power(double base, int exponent) {
double res = 1;
if (exponent < 0){
exponent = -exponent;
base = 1/base;
}
while(exponent){if(exponent&1 == 1){res = res * base;}
base = base * base;
exponent/=2;
}
return res;
}17 打印从 1 到最大的 n 位数
void print(int n,string pre){if(n == 0){if(pre == "0"){return;}
cout << pre << " ";
return;
}
for(int i =0;i <=9;i++){if(pre == "" && i == 0&&n!=1) {print(n - 1, pre);
}else {print(n - 1, pre + char('0' + i));
}
}
}18.2 删除链表中重复的结点 **
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {}};
ListNode* deleteDuplication(ListNode* pHead)
{
map<int,ListNode*> m1;
ListNode myHead(0);
ListNode* t,*pre;
t = pHead;
// 使头节点一般化
myHead.next = pHead;
pre = &myHead;
while(t!=NULL){if(m1.find(t->val) == m1.end()){
// 如果还没出现过
m1[t->val] = pre;
pre = t;
t = t->next;
}else{m1[t->val]->next = t->next;
// 下一个节点的前继改为第一次出现该数时的前继
pre = m1[t->val];
t = t->next;
}
}
return myHead.next;
}
int main(){ListNode ln1{1};
ListNode ln2{2};
ListNode ln3{3};
ListNode ln4{3};
ListNode ln5{4};
ListNode ln6{4};
ln1.next = &ln2;
ln2.next = &ln3;
ln3.next = &ln4;
ln4.next = &ln5;
ln5.next = &ln6;
deleteDuplication(&ln1);
ListNode* head = &ln1;
while(head != NULL){
cout << head->val;
head = head->next;
}
return 0;
}19 正则表达式匹配 **
请实现一个函数用来匹配包括 ‘.’ 和 ‘‘ 的正则表达式。模式中的字符 ‘.’ 表示任意一个字符，而 ‘‘ 表示它前面的字符可以出现任意次（包含 0 次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串 “aaa” 与模式 “a.a” 和 “abaca” 匹配，但是与 “aa.a” 和 “ab*a” 均不匹配。
bool match(char* str, char* pattern)
{if (*str == '\0' && *pattern == '\0')
return true;
if (*str != '\0' && *pattern == '\0')
return false;
//if the next character in pattern is not '*'
if (*(pattern+1) != '*')
{if (*str == *pattern || (*str != '\0' && *pattern == '.'))
return match(str+1, pattern+1);
else
return false;
}
//if the next character is '*'
else
{if (*str == *pattern || (*str != '\0' && *pattern == '.'))
return match(str, pattern+2) || match(str+1, pattern);
else
return match(str, pattern+2);
}
}
