|
文档：知识点-3-字符串.note
链接：http://note.youdao.com/noteshare?id=8e67c3fc06c54922d0c2e067047f8033&sub=BF87BC64EB1B4019A872B403E7F9D148
--------------------------------------------------------------------------------------------------------------------------------
1. NC20：数字字符串转化成IP地址
? ? ? ? ?解法：三个循环，注意每个循环的终止条件
2.NC31：第一个只出现一次的字符
? ? ? ? ?解法1：数组
? ? ? ? ?解法2：哈希
3.①NC17：最长回文子串
? ? ? ? ?解法1：暴力解法
? ? ? ? ?解法2：动态规划
? ? ? ? ?解法3：中心扩散法(先找到回文的中心，然后向两端扩散)
3.②NC28：最小覆盖子串（*难*）
? ? ? ? ?解法：双指针之 滑动可变窗口
3.③NC41：最长无重复子串
? ? ? ? ?解法1：滑动窗口+HashMap
3.④NC55：最长公共前缀
? ? ? ? ?解法1:对字符串数组进行排序，然后只要比较首尾两个字符串即可
? ? ? ? ?解法2：水平扫描法：在线处理，不断调整公共前缀的长度
? ? ? ? ?解法3：垂直扫描法：按列扫描，先验证所有字符串的第一个元素
? ? ? ? ?解法4：分治
? ? ? ? ?解法5：二分查找算法
3.⑤NC49：最长括号子串
? ? ? ? ?解法一：动态规划
? ? ? ? ?解法二：栈
? ? ? ? ?解法三：不需要额外的空间
3.⑥NC142：最长重复子串
? ? ? ? ?解法：滑动窗口
4.① NC1：大数加法：
? ? ? ? ?解法：单链表加法
4. ② NC10：大数乘法
? ? ? ? ?解法：分治（按位相乘）
4. ③ 单链表的大数加法
? ? ? ? ?解法1：链表逆序后转成数字，加完后还原成链表
? ? ? ? ?解法2：链表处理
5.NC41：找到字符串的最长无重复字符子串
? ? ? ? ?解法1： 滑动窗口法：
? ? ? ? ?解法2：双指针+回头遍历：
6.NC85：拼接所有的字符串产生字典序最小的字符串
? ? ? ? ?解法：比较器
NC63：扑克牌顺子
? ? ? ? ?解法1：排序+遍历
? ? ? ? ?解法2：最大值与最小值的差值应该小于5-count0；
NC89：字符串变形
? ? ? ? ?解法1：空格划分+栈+大小写互转
? ? ? ? ?解法2：空格划分+从右向左扫描+大小写互转
? ? ? ? ?解法3：两次翻转+大小写互转
NC111：最大数
? ? ? ? ?思路1：字符串数组+比较器
? ? ? ? ?思路2：链表+比较器
NC104:比较版本号
NC113:验证IP
NC114：旋转字符串
? ? ? ? ?解法1：暴力求解
? ? ? ? ?解法2：(A+A).contains(B);
? ? ? ? ?解法3：B中是否同时包含 head和tail 两部分
NC121：字符串的排列
? ? ? ? ?解法1：递归回溯法
NC141：判断回文
? ? ? ? ?解法1： 𝑠𝑡𝑟[𝑖] != 𝑠𝑡𝑟[𝑙𝑒𝑛?1?𝑖]
? ? ? ? ?解法2：双指针
? ? ? ? ?解法3：栈+比较
|