链表review

链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。——维基百科

海量数据处理

海量数据处理,顾名思义,是指基于海量数据的存储和处理,因为数据量过大,导致要么无法短时间内解决,要么无法一次性装入内存。

字符串处理

字符串相关概念: 回文 子串 子序列 前缀树 后缀树和后缀数组 匹配 字典序 字符串操作: 1.与数组相关的操作 增删改查 2.字符的替换 3.字符串的旋转 字符串题目的常见类型 1.规则判断 判断字符串是否符合整数规则 判断字符串是否符合浮点数规则 判断字符串是否符合会问字符串规则 2.数字运算 int 和long 类型表达整数范围有限所以经常用字符串实现大整数 与大整数相关的加减乘除操作,需要模拟笔算的过程 3.与数组操作相关的类型 数组相关的调整、排序等操作需要掌握 快速排序的划分过程需要掌握和改写 4.字符计数 hash表 固定长度的数组 滑动串口问题、寻找无重复字符子串问题、计算变位词问题 5.动态规划类型 最长公共子串 最长公共子串序列 最长回文子串 最长回文子序列 6.搜索类型 宽度优先搜索 深度优先搜索 7.高级算法与数据结构 manacher算法解决最长回文子串问题 kmp算法解决字符串匹配问题 前缀树结构 后缀树和后缀数组 对于两棵彼此独立的二叉树A和B,请编写一个高效算法,检查A中是否存在一棵子树与B树的拓扑结构完全相同。给定两棵二叉树的头结点A和B,请返回一个bool值,代表A中是否存在一棵同构于B的子树。 解决办法: # -*- coding:utf-8 -*- # class TreeNode: # def __init__(self,…

排序算法复习与总结

排序算法比较 冒泡排序 时间复杂度O(N^2) 工作原理: 1.比较相邻两个元素,如果前者比后者大就交换 2.对第0个到第n-1个数重复步骤1,使得最大的数到达数组的末尾 3.重复以上步骤,直到比较完 c++版: “`c++ class BubbleSort { public: int* bubbleSort(int* A, int n) { <pre><code> for(int i=0;i <= n;i++) for(int j = n-1;j > i;j–){ if(A[j-1]>A[j]) { swap(A[j],A[j-1]); } } return A; // write code here } </code></pre> }; <pre><code class=" line-numbers">python版: “`python def bubble_sort(arry): n = len(arry) #获得数组的长度 for…

字符串高频面试题目

确定字符互异 请实现一个算法,确定一个字符串的所有字符是否全都不同。这里我们要求不允许使用额外的存储结构。 给定一个string iniString,请返回一个bool值,True代表所有字符全都不同,False代表存在相同的字符。保证字符串中的字符为ASCII字符。字符串的长度小于等于3000。 测试样例: “aeiou” 返回:True BarackObama” 返回:False 解题思路 使用集合能自动去重,然后判断set()前和set()后长度是否一样,如果一样,则没有重复的字符。 # -*- coding:utf-8 -*- class Different: def checkDifferent(self, iniString): if len(iniString) == len(set(iniString)): return True else: return False 原串翻转 请实现一个算法,在不使用额外数据结构和储存空间的情况下,翻转一个给定的字符串(可以使用单个过程变量)。 给定一个string iniString,请返回一个string,为翻转后的字符串。保证字符串的长度小于等于5000。 测试样例: “This is nowcoder” 返回:”redocwon si sihT” 解题思路 直接利用序列操作符切片来进行反向索引 # -*- coding:utf-8 -*- class Reverse: def reverseString(self, iniString): return iniString[::-1] 替换空格 请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We…