剑指offer——数组中重复的数字

/** * 题目:在一个长度为n的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。 * 请找出数组中任意一个重复的数字。 * 例如,如果输入长度为7的数组{2,3,1,0,2,5,3}, * 那么对应的输出是重复的数字 2 或者 3。 * * 【法1】:一言不合先排序,排序之后双指针往后跑,直到找到相同的数字,retur

- 阅读全文 -

面试指南——字符串的交错组成

题目: 现在有3个字符串s1,s2,s3,我们需要判断s3是否是由s1和s2交错组成的。对于三个字符串A,B,C。我们称C由A和B交错组成当且仅当C包含且仅包含A,B中所有字符,且对应的顺序不改变 例如s1="abc",s="1234d",s3="ab1234dc",那么s3是由s1和s2交错组成的,如果s3="ab1234cd",则s3不是由s1和s2交错组成的。 /* * str1长度为M,s

- 阅读全文 -

面试指南——最小编辑代价

题目描述: 给定两个字符串str1和str2,再给定三个整数ic,dc,rc,分别代表插入、删除、替换一个字符的代价,返回将str1编辑成str2的最小代价。 举例: str1="abc" str2="adc" ic=5 dc=3 rc=2,从"abc"编辑到"adc"把b替换成d代价最小,为2; str1="abc" str2="adc" ic=5 dc=3 rc

- 阅读全文 -

面试指南——最长公共子序列问题

题目 给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence)。比如字符串1:BDCABA;字符串2:ABCBDAB 则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA /* * 以下dp[0...M-1]相当于dp[0]~dp[M-1] * str1.length = M;str2.length = N ==>生成M*N大小的dp矩阵,

- 阅读全文 -

面试指南——最长公共子串问题

题目: 给定两个字符串,求出它们之间最长的相同子字符串的长度。 /* * 公共子串需要连续,公共子序列不需要连续 * dp矩阵第一列dp[0...M-1][0],如果str1[i]==str2[0],令dp[i][0]=1,否则dp[i][0]=0; * dp矩阵第一行dp[0][0...N-1],如果str1[0]==str2[j],令dp[0][j]=1,否则dp[0][j]=0;

- 阅读全文 -