剑指offer算法题(11-20)
剑指offer算法题(03-10)
旋转数组中的最小值-11
排序算法
我的排序算法总结
旋转数组最小值
原有序数组:1,2,3,4,5,6,7,旋转一下,把一部分放到后面去:4,5,6,7, 1,2,3。
求:在\(O(logn)\) 内找到数组中最小的元素
leetcode旋转数组
思路
特点:左边序列全部大于等于右边序列。
最小的值在中间 ,顺序查找肯定不行,那就只能二分查找
了。
设两个指针,left
从左边 向中间靠拢,right
从右边 向中间靠拢。
循环条件 :a[l] >= a[r]
直到l+1==r
为止,那么a[r]
就是我们要的最小值。
计算中间值 a[m]
a[m] >= a[l]
:m在左边序列,l = m
, l向右走
a[m] <= a[r]
: m在右边序列,r == m
, r向左走
陷阱
可能一个数字都不旋转,即a为有序序列,直接返回a[0]
有重复的数字,a[l]==a[m] && a[m]==[r]
, 则只能顺序查找 了
关键代码
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 int minum_rotate_array (const vector <int >& a) { if (a.size() == 0 ) { return 0 ; } int l = 0 ; int r = a.size() - 1 ; if (a[l] < a[r]) { return a[l]; } int res = -1 ; while (a[l] >= a[r]) { if (l + 1 == r) { res = a[r]; break ; } int m = (l + r) / 2 ; if (a[l] == a[m] && a[m] == a[r]) { res = get_min(a, l, r); break ; } if (a[m] >= a[l]) { l = m; } else if (a[m] <= a[r]) { r = m; } } return res; } int get_min (const vector <int >&a, int start, int end) { int min = a[start]; for (int i = start + 1 ; i <= end; i++) if (a[i] < min) { min = a[i]; } return min; }
矩阵中的路径-12
给一个字符数组,手动给行和列进行分割。再给一个字符串,判断该字符串是否在该字符矩阵中。使用回溯法 进行搜索。
其实就是遍历所有的点开始,然后依次进行上下左右继续查找。用visited
去记录点是否已经走过,用pathlen
记录目标字符串的遍历长度。
[关键代码]
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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 bool has_path (const char * matrix, int rows, int cols, const char * str) { if (matrix== nullptr || rows < 1 || cols < 1 || str == nullptr ) { return false ; } bool *visited = new bool [rows * cols]; memset (visited, 0 , rows * cols); int pathlen = 0 ; for (int row = 0 ; row < rows; row++) { for (int col = 0 ; col < cols; col++) { bool has = go_find(matrix, rows, cols, row, col, str, pathlen, visited); if (has) { delete [] visited; return true ; } } } delete [] visited; return false ; } bool go_find (const char * matrix, int rows, int cols, int row, int col, const char * str, int &pathlen, bool *visited) { if (str[pathlen] == '\0' ) { return true ; } bool ok = false ; int cur = row * cols + col; if (row >= 0 && row < rows && col >= 0 && col < cols && matrix[cur] == str[pathlen] && visited[cur] == false ) { ++pathlen; visited[cur] = true ; bool left = go_find(matrix, rows, cols, row, col - 1 , str, pathlen, visited); bool right = go_find(matrix, rows, cols, row, col + 1 , str, pathlen, visited); bool down = go_find(matrix, rows, cols, row + 1 , col, str, pathlen, visited); bool up = go_find(matrix, rows, cols, row - 1 , col, str, pathlen, visited); ok = left || right || down || up; if (!ok) { --pathlen; visited[cur] = false ; } } return ok; }
机器人的运动范围-13
给一个\(\rm{rows \times cols}\) 的矩阵,和一个阈值\(k\) 。 机器人从\((0, 0)\) 出发,进入矩阵的格子。
能进入格子:(35, 38),因为3+5+3+8k
思路
回溯法
, \(\rm{count = 1 + left + right + up + down}\)
[关键代码]
定义Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { private : int threshold; int rows; int cols; bool *visited; public : int movingCount (int threshold, int rows, int cols) ; int dfs (int row, int col) ; bool check_point (int row, int col) ; static int resolve_num (int n) ; };
movingcount
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 int Solution::movingCount(int threshold, int rows, int cols) { if (threshold < 0 || rows < 1 || cols < 1 ) { return 0 ; } this ->threshold = threshold; this ->rows = rows; this ->cols = cols; this ->visited = new bool [rows * cols]; memset (this ->visited, 0 , rows * cols); int count = dfs(0 , 0 ); delete [] this ->visited; return count; }
回溯法上下左右格子累加
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 int Solution::dfs(int row, int col) { if (check_point(row, col) == false ) { return 0 ; } int cur = row * cols + col; visited[cur] = true ; int left = dfs(row, col - 1 ); int right = dfs(row, col + 1 ); int up = dfs(row - 1 , col); int down = dfs(row + 1 , col); int count = 1 + left + right + up + down; return count; }
检查点是否可进入和分解数
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 int Solution::resolve_num(int n) { int sum = 0 ; while (n > 0 ) { sum += n % 10 ; n = n / 10 ; } return sum; } bool Solution::check_point(int row, int col) { int cur = row * cols + col; if (row < 0 || row >= rows || col < 0 || col >= cols || visited[cur] == true ) { return false ; } if (resolve_num(row) + resolve_num(col) > threshold) { return false ; } return true ; }
剪绳子-14
动态规划
求最优解(最大值or最小值),大问题分解成若干个小问题。使用动态规划四个特点,如下
求最优解
整体问题的最优解依赖于各个子问题的最优解
若干个子问题,之间有相互重叠的更小的子问题。如f(2)是f(4)和f(6)共同的子问题
从上往下分析问题,从下网上求解问题。用数组存下小问题的解嘛。
贪心算法
每一步做一个贪婪的选择,基于这个选择,可以得到最优解。需要数学证明。
剪绳子-动态规划
条件
长度为\(n\) 的绳子,把绳子剪成\(m, \; (m \ge 2)\) 段, 每段长度为\(k[0], k[1], \cdots, k[m]\) 。 m和n都是整数,都大于1。
问题
长度连乘积最大是多少?
思路
定义: \(f(n)\) 为把绳子切成若干段后,各段长度乘积的最大值
第一刀的时候,在长度为\(i\) 的地方剪,分成\(i\) 和\(n-i\) 两段。 递推公式如下: \[
f(n) = \max (f(i) \cdot f(n-i)), \quad 0 < i < n
\]
1 2 3 4 5 6 7 8 9 10 11 int max = 0 ;for (int j = 1 ; j <= i / 2 ; j++) { int t = f[j] * f[i - j]; if (t > max) { max = t; } } f[i] = max;
关键代码
长度在3以内的特殊返回
构建f[i],f[0,1,2,3]手动赋值处理,意义不同
自下而上计算f[4, ..., length]
单独计算f[i],找到\(\max(f_j \cdot f_{i-j})\) , 其中\(j \in \{1, \cdots, i/2\}\)
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 int max_product_dp (int length) { if (length <= 1 ) { return 0 ; } else if (length == 2 ) { return 1 ; } else if (length == 3 ) { return 2 ; } int * f = new int [length + 1 ]; f[0 ] = 0 ; f[1 ] = 1 ; f[2 ] = 2 ; f[3 ] = 3 ; int max = 0 ; for (int i = 4 ; i <= length; i++) { max = 0 ; for (int j = 1 ; j <= i / 2 ; j++) { int t = f[j] * f[i - j]; if (t > max) { max = t; } } f[i] = max; } max = f[length]; delete [] f; return max; }
剪绳子-贪心
贪心策略
当\(n \ge 5\) 时, 尽可能多地剪成长度为3的绳子
当剩余长度为4的时候,要剪成2*2的绳子
关键代码
特殊处理,长度在3以内,自动返回
计算3的个数
计算2的个数
计算最终结果 pow(3, t3)*pow(2,t2)
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 int max_product_greedy (int length) { if (length <= 1 ) { return 0 ; } else if (length == 2 ) { return 1 ; } else if (length == 3 ) { return 2 ; } else if (length == 4 ) { return 4 ; } int t3 = length / 3 ; if (length - t3*3 == 1 ) { t3--; } int t2 = (length - t3*3 ) / 2 ; return (int ) pow (3 , t3) * (int ) (pow (2 , t2)); }
二进制中1的个数-15
基础知识
位运算
与&
都为1,才为1
或|
有一个为1,就为1
异或^
不同为1,相同为0
移位
左移n位
丢弃左边n位,右边n位补0
右移n位
无符号数&正数:右移n位,左边补n个0
负数:右移n位,左边补n个1
重要结论
n & (n-1)
把n的二进制中,最右边的1变成0
n & 1
检测n的二进制,末尾位是否是1
n & 2
检测n的二进制,倒数第二位是否是1
二进制中1的个数
问题:给一个整数,判断它的二进制中,有多少个1
正数思路
n & 1,n不停右移。每次判断 n & 1,即最末尾位是否是1。
但是负数有问题,负数右移,左边会补1,陷入死循环。
正数负数思路
n不变,n & flag,flag每次向左移。即从右到左依次判断n的各个位是否是1。一共循环n的二进制位数次。
最优思路
n = n & (n - 1),每次把n的最右边的1变成0。看看能执行多少次这样的操作,就有多少个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 int count_1_by_flag (int n) { int count = 0 ; unsigned int flag = 1 ; while (flag != 0 ) { if (n & flag) { count++; } flag = flag << 1 ; } return count; } int count_1 (int n) { int count = 0 ; while (n) { n = n & (n - 1 ); count++; } return count; }
数值的整数次方-16
代码风格
代码的规范性:清晰的书写、清晰的布局、合理的命名
代码的完整性:功能测试、边界测试、负面测试
处理错误的方法
返回值
和系统API一致
不能方便使用计算结果
全局变量
能够方便使用计算结果
用户可能会忘记检查全局变量
异常
不同错误,抛出不同异常,可自定义。逻辑清晰
有的语言不支持;对性能负面影响
数值的整数次方
要求实现
1 double power (double base, int exponent) ;
注意特殊情况条件
指数为0
指数为负数
指数为负数,底数不能为0或者约等于0。用fabs(a-b) < theta
思路1
条件考虑全面,一个一个乘
思路2递归
使用这个公式 \[
a^n = \begin{cases}
& a^{n/2} \cdot a^{n/2} &\text{n为偶数} \\
& a^{(n-1)/2} \cdot a^{(n-1)/2} & \text{n为奇数} \\
\end{cases}
\] 思路3位运算
例如\(a^{13}\) , 13的二进制是1101
。
从右向左,依次读1,flag & 1
, b = b >> 1
遇到1就累乘, res *= a
每读一位,倍数增加, a *= a
关键代码
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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 double power_normal_binary (double base, int exponent) { if (exponent == 0 ) { return 1 ; } else if (exponent == 1 ) { return base; } double res = 1 ; while (exponent != 0 ) { if ((exponent & 1 ) == 1 ) { res *= base; } base *= base; exponent = exponent >> 1 ; } return res; } double power_normal_recur (double base, int exponent) { if (exponent == 0 ) { return 1 ; } else if (exponent == 1 ) { return base; } double res = power_normal_recur(base, exponent >> 1 ); res *= res; if ((exponent & 1 ) == 1 ) { res *= base; } return res; } double power_normal (double base, int exponent) { double res = 1 ; for (int i = 0 ; i < exponent; i++) { res *= base; } return res; } double power (double base, int exponent) { if (exponent == 0 ) { return 1 ; } if (exponent < 0 && equal(base, 0.0 )) { cout << "error. exponent < 0, base should != 0" << endl ; return 0 ; } double res = 1 ; if (exponent > 0 ) { res = power_normal_binary(base, exponent); } else { res = power_normal_binary(base, -exponent); res = 1.0 / res; } return res; }
打印1到最大的N位数-17
问题:输出打印1-999。但是n不确定,非常大,要注意溢出的问题 。
思路
开辟n+1位的字符串,来存储数字。末尾位是''
字符串模拟数字的自增、进位和溢出
长度超过n+1,或者第0位产生进位,则溢出
输出的时候,要人性化点。比如0087,要打印87
关键代码
开始的时候,个位加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 void Solution::increment() { int now = -1 ; int take = 0 ; int i = -1 ; for (i = n - 1 ; i >= n - real_len; i--) { int now = num[i] - '0' + take; if (i == n - 1 ) { now = now + 1 ; } if (now >= 10 ) { num[i] = '0' + (now - 10 ); take = 1 ; } else { num[i] = '0' + now; take = 0 ; break ; } } if (take > 0 ) { if (i < 0 ) { cout << "num char* over flow" << endl ; this ->over_flow = true ; delete this ->num; return ; } num[i] = '0' + 1 ; real_len++; } return ; }
删除链表中的元素-18
删除一个节点
给一个链表和一个节点,删除这个节点i,要求\(O(1)\)
思路
从头到尾遍历找到i的前驱节点,时间复杂度为\(O(n)\) , 显然不行。
把i的后继节点的值拷贝到i上,然后删除i的后继节点 。
但,要注意:头结点、中间节点、末尾节点(顺序遍历)。
关键代码
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 void delete_node (ListNode ** phead, ListNode* pdeleted) { if (!phead || !pdeleted) { return ; } if (*phead == pdeleted && pdeleted->next == nullptr ) { delete pdeleted; pdeleted = nullptr ; *phead = nullptr ; } else if (pdeleted->next == nullptr ) { ListNode* p = *phead; while (p->next != pdeleted) { p = p->next; } p->next = nullptr ; delete pdeleted; pdeleted = nullptr ; } else { ListNode* pnext = pdeleted->next; pdeleted->val = pnext->val; pdeleted->next = pnext->next; delete pnext; pnext = nullptr ; } }
删除有序链表中的重复元素
Remove Duplicates from Sorted List 有序的链表。
留下一个
每个重复的元素,留下一个。
思路
从head开始循环,遍历每一个节点。
对于当前节点c,再进行遍历,直到下一个节点不等于它或者为空。中间删除掉重复的节点。
全部删除
把所有重复的元素,都删除,有序链表。
思路
当前节点cur
, 需要保留前一个元素的指针pre
。
我的思路
循环遍历到cur,head应该为第一个pre。
cur无重复cur!=next || next==null
pre为空,则pre=cur
; pre不为空, 则pre.next=cur
,pre=pre.next
。实际上pre.next指向下一轮的cur
cur重复 cur=next
遍历删除所有与cur相同的元素
删除cur
但由于原本pre.next指向当前cur,cur又被删除。所以pre.next=nullptr
其实最重要是:当前不重复,则续接到pre后面,pre后移;当前重复,则删除,pre后面设为空 。
关键代码
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 ListNode* del_dups_nosave (ListNode* head) { if (head == nullptr ) { return head; } ListNode* cur = head; ListNode* pre = nullptr ; ListNode* next = nullptr ; while (cur) { if (cur->next == nullptr || cur->val != cur->next->val) { if (pre == nullptr ) { pre = cur; head = pre; } else { pre->next = cur; pre = cur; } cur = cur->next; } else { next = cur->next; while (next && cur->val == next->val) { cur->next = next->next; delete next; next = cur->next; } delete cur; cur = next; if (pre != nullptr ) pre->next = nullptr ; } } if (pre == nullptr ) { head = nullptr ; } return head; }
正则表达式匹配-19
问题
正则表达式:普通字符、.
任意字符 、*
前面的字符出现0次或多次。
给定字符串,去判断该字符串是否符合正则表达式。
例如:aaa
与a.a
和ab*ac*a
匹配, 与aa.a
和ab*a
不匹配。
思路
递归 去判断。用\(s_1\) 和\(p_1\) 去 代表第一个字符和第一个模式。
\(s_1\) 与\(p_1\) 匹配成功: s1==p1 || (p1 == '.' && s1 != '\0')
必须先判断\(p2\) 是否是 *
如果,第二个模式\(p_2\) 是*
\(s_1\) 与\(p_1\) 匹配成功
*代表出现1次,go(s2, p3)
*代表出现0次,go(s1, p3)
*代表出现多次,go(s2, p1)
\(s_1\) 与\(p_1\) 匹配失败
*只能代表出现0次,go(s1, p3)
如果\(s_1\) 与\(p_1\) 匹配成功
总结
p结束,s结束。返回true
p结束,s还有。 返回false
p未结束,\(p_2\) == *。\(s_1\) 与\(p_1\) 匹配成功, p2作为0、1、多次,合并返回 。匹配失败,作为0次,返回。
p未结束,\(p_2\) != *,单独match成功。go(s2, p2)
p未结束,\(p_2\) != *,单独match失败。返回false
关键代码
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 52 53 54 55 56 57 58 59 60 61 bool single_char_match (const string &str, int s, const string &pattern, int p) { if (s >= str.size() || p >= pattern.size()) { return false ; } if (str[s] == pattern[p] || (pattern[p] == '.' && s < str.size())) { return true ; } return false ; } bool match_core (const string &str, int snow, const string &pattern, int pnow) { if (pnow >= pattern.size() && snow >= str.size()) { return true ; } if (pnow >= pattern.size() && snow < str.size()) { return false ; } int p2 = pnow + 1 ; if (p2 < pattern.size() && pattern[p2] == '*' ) { if (single_char_match(str, snow, pattern, pnow) == true ) { bool t0 = match_core(str, snow, pattern, pnow + 2 ); bool t1 = match_core(str, snow+1 , pattern, pnow + 2 ); bool t_many = match_core(str, snow+1 , pattern, pnow); return t0 || t1 || t_many; } else { return match_core(str, snow, pattern, pnow + 2 ); } } if (single_char_match(str, snow, pattern, pnow) == true ) { return match_core(str, snow+1 , pattern, pnow+1 ); } return false ; }
表示数值的字符串-20
数值:+100、5e2、-123、3.1416、-1E-16 、1.5e2
非数值:12e、1a3.14、1.2.3、+-5、12e+5.4
判断字符串是否是一个正确的数值。A[.[B]][e|EC]
或者.B[e|EC]
(符号)、整数、小数点、(整数)、e、整数
小数点前后,必须有一个整数
e前面是一个数,后面是一个整数
关键代码
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 bool Solution::isNumeric(const string &str) { int start = 0 ; bool pre_int = scan_integer(str, start); bool numeric = pre_int; if (start < str.size() && str[start] == '.' ) { start++; bool dot_int = scan_unsigned_integer(str, start); numeric = pre_int || dot_int; } if (start < str.size() && (str[start] == 'E' ||str[start] == 'e' )) { start++; bool e_int = scan_integer(str, start); numeric = numeric && e_int; } if (start < str.size()) { return false ; } return numeric; }