自己实现的字符串分割操作
vector<string> split(string str){
vector<string> ret;
if(str.empty())
return ret;
int start=0;
for(int i=0;i<=str.size();i++){
if(i==str.size()||str[i]==' '){
ret.push_back(str.substr(start,i-start));
start=i+1;
}
}
return ret;
}
功能：把s按照空格进行分割，返回一个vector集合。
说明：
0.重要的定义：start是当前分割的起始位置，i是将要讨论的字符。
1.当i达到字符串末尾【s.size()】处，不管是不是分隔符都要进行分割 或者 遇到分割字符时，进行分割操作；分割完后，要维护好start和i，start应该指向i+1，因为i是分割字符，所以分割后的起点是i的下一个位置。i则指向start，开始讨论.
2.不满足分割条件，i++
3.str.substr(int startIndex,int count)---截取str[startIndex,startIndex+count)
字符串翻转
string reverse(string &str){
int n=str.size();
for(int i=0;i<n/2;i++){
swap(str[i],str[n-1-i]);
}
return str;
}
查找最长公共字串
思路：
暴力搜索
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
string getStr(string &a, string &b){
int alen = a.size(), blen = b.size(), num = 0, retlen = 0, start = 0;
for (int i = 0; i < alen; i++){
for (int j = 0; j < blen; j++){
int start1 = i, start2 = j;
while (start1 < alen && start2 < blen && a[start1++] == b[start2++])
num++;
if (num>retlen){
retlen = num;
start = i;
}
num = 0;
}
}
string ret;
for (int i = start; i < start + retlen; i++)
ret.push_back(a[i]);
return ret;
};
int main(){
string a = "abccade", b = "dgcadde";
string ret = getStr(a, b);
cout << ret << endl;
system("pause");
return 0;
}
代码解释：
- 首先先定义好需要记录的变量，比如我们要找出最长公共字串部分，那么首先我们要知道公共字串在原字符串的起始位置，以及长度（结束位置）
- 明确以上部分后，开始设计算法，采用暴力搜索（n方时间复杂度，从第一个字符串的第一个字符开始，与第二个字符串的所有进行比较），从2个字符串的起点开始比较，成立就后续继续，不成立就先移动第2个字符串。
上机大数乘法、大数加法
取巧的做法是直接用Java中的BigInteger
例如求阶乘（1000以内）
import java.math.BigInteger;
import java.util.Scanner;
public class Solution {
public static void main(String[] args){
Scanner sca=new Scanner(System.in);
int n=sca.nextInt();
int result=1;
String s=String.valueOf(result);
BigInteger ans=new BigInteger(s);
for(int i=1;i<=n;i++){
String x=String.valueOf(i);
BigInteger v=new BigInteger(x);
ans=ans.multiply(v);
}
System.out.println(ans);
sca.close();
}
}
使用cpp实现大数加法、大数乘法，还以求1000的阶乘为例
思路：
先定义好数组，加法比较简单，逐位相加即可，乘法的话，逐位相乘，再处理进位符
const int maxn = 20000 + 10;
int a[maxn];
int main(){
int n;
while (scanf("%d", &n) == 1){
a[0] = 1;
int digit = 1, temp = 0;
for (int i = 2; i <= n; i++){
for (int j = 0; j<digit; j++){
a[j] = a[j] * i + temp;
temp = a[j] / 10;
a[j] = a[j] % 10;
}
while (temp != 0){
a[digit++] = temp % 10;
temp /= 10;
}
}
for (int i = digit - 1; i >= 0; i--){
printf("%d", a[i]);
}
printf("\n");
}
return 0;
}
经验：
机试的时候时间宝贵，怎么节省时间怎么来，用int作数组可以避免char的运算处理。Java的biginteger更是连大数加减乘除的实现都节省掉了。
广度优先搜索的思想
应用：
遍历 、寻找最短路径
设计思路：
首先需要借助队列这个数据结构。
其次要清楚什么时候入队，什么时候出队;入队的是哪些元素，出队的元素又是哪些，该如何处理。
入队元素可以进行筛选（剪枝操作）来优化算法 ，有时候这个优化需要借助集合或者数组进行状态标记和管理
代码模板
java伪代码（找最短路径）
/**
* Return the length of the shortest path between root and target node.
*/
int BFS(Node root, Node target) {
Queue<Node> queue; // store all nodes which are waiting to be processed
int step = 0; // number of steps neeeded from root to current node
// initialize
add root to queue;
// BFS
while (queue is not empty) {
step = step + 1;
// iterate the nodes which are already in the queue
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = the first node in queue;
return step if cur is target;
for (Node next : the neighbors of cur) {
add next to queue;
}
remove the first node from queue;
}
}
return -1; // there is no path from root to target
}
如代码所示，在每一轮中，队列中的结点是等待处理的结点。
在每个更外一层的 while 循环之后，我们距离根结点更远一步。变量 step 指示从根结点到我们正在访问的当前结点的距离。
评论：从leetcode上找的模板跟我的思路有些出入，我的while循环是每次循环只处理一个出队元素，然后根据处理的出队元素判断哪些元素入队。
而leetcode模板每次while循环是处理完当前队列中的所有元素（通过size来标记处理个数），相当于一次迭代处理完了一层元素，并根据每个处理掉的元素判断哪些元素入队（新入队元素并不会在本次while循环中被处理）
java伪代码（要求避免重复访问）
/**
* Return the length of the shortest path between root and target node.
*/
int BFS(Node root, Node target) {
Queue<Node> queue; // store all nodes which are waiting to be processed
Set<Node> used; // store all the used nodes
int step = 0; // number of steps neeeded from root to current node
// initialize
add root to queue;
add root to used;
// BFS
while (queue is not empty) {
step = step + 1;
// iterate the nodes which are already in the queue
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = the first node in queue;
return step if cur is target;
for (Node next : the neighbors of cur) {
if (next is not in used) {
add next to queue;
add next to used;
}
}
remove the first node from queue;
}
}
return -1; // there is no path from root to target
}
有两种情况你不需要使用哈希集：
你完全确定没有循环，例如，在树遍历中；
你确实希望多次将结点添加到队列中。
递归思路设计
递归的要素：
- 先搞定主逻辑 f(n-1) el(n) --> f(n)
- 在主逻辑梳理清楚的基础上，再去确认递归终止条件
- 判断非法情况
- 保证递归每次迭代1
二分搜索树：
插入、删除、查找
最大值、最小值、上界、下界、某个元素的排名、寻找第k大元素
回溯法应用：
回溯法其实可以看作是一种搜索算法，暴力搜索每一种可能情况，类似于深度搜索。
回溯一般来说是通过递归实现的，但是比递归的设计要复杂，可以认为是升级版的递归，因为一般来说回溯算法涉及到了各种约束条件以及剪枝操作。
通过画树形图可以帮助我们从整体结构上查看回溯算法的递归调用链
回溯的要点就是抓住访问当前的节点后，要对哪些邻近点进行递归操作，递归前后的状态遍历怎么维护和变动，递归的约束有哪些，考虑清楚这些，回溯算法基本也就设计出来了
联系：
链表的递归 相当于当前点只有1个后继节点
二叉树的递归 相当于当前点有2个临近点的递归
图的递归 相当于当前点有多个临近点递归，且点与点间有可能重复，所以需要状态变量去维护，限制
许多回溯算法的题目 相当于是多叉树的问题
链表排序
解答一：归并排序（递归法）
题目要求时间空间复杂度分别为O(nlogn)O(nlogn)O(nlogn)和O(1)O(1)O(1)，根据时间复杂度我们自然想到二分法，从而联想到归并排序；
对数组做归并排序的空间复杂度为 O(n)O(n)O(n)，分别由新开辟数组O(n)O(n)O(n)和递归函数调用O(logn)O(logn)O(logn)组成，而根据链表特性：
数组额外空间：链表可以通过修改引用来更改节点顺序，无需像数组一样开辟额外空间；
递归额外空间：递归调用函数将带来O(logn)O(logn)O(logn)的空间复杂度，因此若希望达到O(1)O(1)O(1)空间复杂度，则不能使用递归。
通过递归实现链表归并排序，有以下两个环节：
分割 cut 环节： 找到当前链表中点，并从中点将链表断开（以便在下次递归 cut 时，链表片段拥有正确边界）；
我们使用 fast,slow 快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。
找到中点 slow 后，执行 slow.next = None 将链表切断。
递归分割时，输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp(因为链表是从 slow 切断的)。
cut 递归终止条件： 当head.next == None时，说明只有一个节点了，直接返回此节点。
合并 merge 环节： 将两个排序链表合并，转化为一个排序链表。
双指针法合并，建立辅助ListNode h 作为头部。
设置两指针 left, right 分别指向两链表头部，比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表。
返回辅助ListNode h 作为头部的下个节点 h.next。
时间复杂度 O(l + r)，l, r 分别代表两个链表长度。
当题目输入的 head == None 时，直接返回None。
作者：jyd
链接：https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
网友评论