Estom的博客

1 二叉树与双向链表问题分析 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 链接 1.1 二叉树与双向链表——左旋右旋 借鉴了构建二叉平衡树的内容。可以自己完成以下二叉平衡树试试。 算法设计 通过左旋右旋操作实现树的旋转。最终旋转成一个倒V树。 算法分析 时间复杂度O(n) 空间复杂度O(n) 算法实现123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384class Solution {public: Node* treeToDoublyList(Node* root) { // 类似于二叉平衡树的左旋右旋。 if(root==nullptr){ retu...

数组与滑动窗口1 最长不含重复字符的子字符串——滑动窗口问题描述 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。 问题分析问题分类算法设计 哈希表 dicdic 统计： 指针 jj 遍历字符 ss ，哈希表统计字符 s[j]s[j] 最后一次出现的索引 。 更新左指针 ii ： 根据上轮左指针 ii 和 dic[s[j]]dic[s[j]] ，每轮更新左边界 ii ，保证区间 [i + 1, j][i+1,j] 内无重复字符且最大。$$i=max(dic[s[j]],i)$$ 更新结果 res ： 取上轮 res 和本轮双指针区间 [i + 1,j][i+1,j] 的宽度（即 j - ij−i ）中的最大值 $$res=max(res,j−i)$$ 算法分析 时间复杂度 O(N)： 其中 N为字符串长度，动态规划需遍历计算 dpdp 列表。 空间复杂度 O(1) ： 字符的 ASCII 码范围为 00 ~ 127，哈希表 dic最多使用 O(128) = O(1) 大小的额外空间。 算法分析 时间复杂度 O(N...

1 把数组排成最小数问题描述 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: “102” 示例 2: 输入: [3,30,34,5,9] 输出: “3033459” 链接 问题分析问题分类 排序 算法设计 算法原理：此题求拼接起来的最小数字，本质上是一个排序问题。设数组nums 中任意两数字的字符串为 x 和 y ，则规定 排序判断规则 为： 若拼接字符串 x+y>y+x ，则 x “大于” y ； 反之，若 x+y<y+x ，则 x “小于” y ； 算法流程 初始化： 字符串列表 strsstrs ，保存各数字的字符串格式； 列表排序： 应用以上 “排序判断规则” ，对 strsstrs 执行排序； 返回值： 拼接 strsstrs 中的所有字符串，并返回。 算法分析 时间复杂度O(NlogN) ： N 为最终返回值的字符数量（ strs列表的长度 N≤N ）；使用快排或内置函数的平均时间复杂度为 O(NlogN) ，最差为 O(N^2) 空间...

字符串全排列问题描述策略选择 循环构建全排列 递归构建全排列 判断相同字符的选择 算法设计算法分析 时间复杂度O(n!) 空间复杂度O(n2) 算法实现123456789101112131415161718192021222324252627vector<string> permutation(string s) { vector<string> vec; string pre; perm(pre,s,vec); return vec;}void perm(string pre,string s,vector<string> &vec){ if(s.size()==0){ // cout<<pre<<endl; vec.push_back(pre); return; } set<char> se; for(int i=0;i<s.size();i++)&...

1 1～n 整数中 1 出现的次数问题描述 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。 链接 问题分析问题分类 数值问题 策略选择算法设计算法分析 时间复杂度 O(logn) ： 循环内的计算操作使用 O(1)时间；循环次数为数字 n 的位数，即logn ，因此循环使用O(logn)时间。 空间复杂度 O(1)O(1) ： 几个变量使用常数大小的额外空间。 算法实现1234567891011121314151617181920int countDigitOne(int n) { int i=0; int wei=0; int result=0; int end=0; while(n!=0){ wei=n%10; i++; if(wei>1){ result+=(i-1)*wei*pow(10,i-2)+pow(10,i-1); ...

反转链表1 从尾到头打印链表内容问题描述输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。 问题分类 线性数据结构 枚举法 排序问题 问题分析1.1 从尾到头打印链表内容——辅助栈策略选择 数据结构：链表、栈、数组 算法思想：枚举法 可以利用栈的先进后出特性。 算法设计 入栈： 遍历链表，将各节点值 push 入栈。（Python​ 使用 append() 方法，​Java​借助 LinkedList 的addLast()方法）。 出栈： 将各节点值 pop 出栈，存储于数组并返回。（Python​ 直接返回 stack 的倒序列表，Java ​新建一个数组，通过 popLast() 方法将各元素存入数组，实现倒序输出）。 算法分析 时间复杂度O(n) 空间复杂度O(n) 算法实现1234567891011121314vector<int> reversePrint1(ListNode* head) { stack<int> s; vector<int> v; ListNode * temp...

链表与双指针1 链表中的倒数第k个节点问题描述 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。 问题分析 典型的双指针问题 问题分类 数组与链表 双指针问题 策略选择 蛮力法 算法流程 两个一样快的指针。相距k个距离。 一个到达终点，另一个则为倒数第k个节点 算法分析 时间复杂度O(n) 空间复杂度O(1) 算法实现123456789101112ListNode* getKthFromEnd(ListNode* head, int k) { ListNode* first=head; ListNode* second=head; while(--k){ second=second->next; } while(second->next){ second = se...

正则表达式匹配问题1 正则表达式匹配问题描述 请实现一个函数用来匹配包含’.‘和’*‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’*‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但与”aa.a”和”ab*a”均不匹配。 问题分析 可以使用动态规划。将字符串的规模增长的方向，作为动态变化的方向。状态变量表示当前的正则表达式，能够与之匹配。当规模发生变化时，保证字符串-1和正则表达式-1能够匹配。其实在这里感觉规模增长的方向，确实是有两个。但是状态变量的设置比较精巧。 问题分类 字符串匹配问题 动态规划 递归 1.1 正则表达式匹配——动态规划选择策略 动态规划 算法设计 设s的长度为n ，pp 的长度为 m ；将 s 的第 i 个字符记为 s_i，p 的第 j个字符记为 p_j ，将 s 的前 i 个字符组成的子字符串记为s[:i] , 同理将 p 的前 j 个字符组成的子字符串记为 p[:j]p[:j] 。 因此，本题可转化为求s[:n] 是否能和p[:m...

表示数值的字符串1 表示数值的字符串问题描述 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”、”5e2”、”-123”、”3.1416”、”-1E-16”、”0123”都表示数值，但”12e”、”1a3.14”、”1.2.3”、”+-5”及”12e+5.4”都不是。 链接 问题分析 这题一看，明显就是有限状态自动机。词法分析过程中用来判断关键字、数值的。属于暴力破解。使用优先状态自动机。确定分类讨论的情况。找到符合规则的所有的路。 另外提供了另外一种暴力破解的思路。通过讨论违反规则的情况。找到违反规则的所有的路。 提供了两种截然不同的分类讨论的思路。在某些情况下，第二种思路反而会简单很多。 在 C++ 文档 中，描述了一个合法的数值字符串应当具有的格式。具体而言，它包含以下部分： 符号位，即 +、− 两种符号 整数部分，即由若干字符 0-9组成的字符串 小数点 小数部分，其构成与整数部分相同 指数部分，其中包含开头的字符 e（大写小写均可）、可选的符号位，和整数部分 问题分类 枚举法 正向分类讨论和反向分类讨论 1.1 表示...

和积最大1 剪绳子问题描述 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m - 1] 。请问 k[0]k[1]…*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。 链接 问题分析问题分类 贪心思想 数值问题 无数据结构 策略选择 n尽可能多的包含因子3 算法设计 如果 n == 2，返回1，如果 n == 3，返回2，两个可以合并成n小于4的时候返回n - 1 如果 n == 4，返回4 如果 n > 4，分成尽可能多的长度为3的小段，每次循环长度n减去3，乘积res乘以3；最后返回时乘以小于等于4的最后一小段；每次乘法操作后记得取余就行 以上2和3可以合并 算法分析 时间复杂度O(logn) 空间复杂度O(1)...