RominYue’s Blog

A lifeway of coders

Leetcode Problem 1-5

| Comments

源代码push到了github上,戳这里

Problem 1: Two sum

题目描述: 在一数组中,找到下标不同的两个数,使得两数之和等于一个给定的值.
解法1: 循环两次扫描数组,找到两个下标. 时间复杂度 O(n2), 空间复杂度 O(1).
解法2: 将数组排序,从第一个数开始扫描,在他之后的数用二分查找找出另外一个数. 时间复杂度O(nlogn), 空间复杂度O(n).

Problem 2: Longest Substring Without Repeating Characters

题目描述: 给定一字符串,找出最长的不含有重复字符的子串.
解法1: 枚举子串的起点和终点,O(n)判断是否是满足条件的子串.总的时间复杂度为O(n3), 空间复杂度O(1).
解法2: 用idx数组记录当前字符的前面离他最近的相同字符的下标,这样两个相邻相同字符之间肯定是满足条件的子串. 时间复杂度O(n), 空间复杂度O(k),常量空间

Problem 3: Add Two Numbers

题目描述: 给定两个数字,用链表表示,且是逆序表示,将两数相加,结果用链表逆序表示
输入输出样例:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

解法: Two Pointers, 两个指针在两个链表上游走逐位相加,最后要注意的是加完之后可能会多出进位的一位数字,要判断一下. 时间复杂度 O(n + m).

Problem 4: Median of Two Sorted Arrays

题目描述: 给定两个排好序的数组,找出他们的中位数.
解法1: 将两数组合并成一个数组,排序,找中位数. 时间复杂度O(n + m),空间复杂度O(n + m)
解法2: Two Pointers. 两个指针比较向前走,同时加上一个计数器,记录是否已经走到中位数处. 时间复杂度O(n + m), 空间复杂度O(1).
解法3: 泛化成在俩排序数组中寻找第K小数.在解法2的基础上,每次比较的不是1个数,而是k/2个数,这样一下子就可以丢弃一半的数.具体可以参考这里. 时间复杂度O(log(n + m))

Problem 5: Longest Palindromic Substring

题目描述: 最长回文子串 解法:经典问题

  • dp解法 时间复杂度O(n2)/空间复杂度O(n2)
  • 中心扩展法 时间复杂度O(n2)/空间复杂度O(1)
  • 马拉车算法 时间复杂度O(n)/空间复杂度O(n).具体参考这里这里.

现在来说明一下为什么马拉车算法他是O(n)的.先看代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//maxrange == mx (图中的)
int p[2200], maxrange = 0, id = 0;
memset(p,0,sizeof(p));
for(int i = 1; i < n ; i++)
{
  if(i < maxrange) p[i] = min(p[2*id - i],maxrange- i);
  else p[i] = 1;

  while(str[i + p[i]] == str[i - p[i]]) p[i] ++;

  if(p[i] + i > maxrange)
  {
     maxrange = p[i] + i;
     id = i;
  }
}

主要实在上图第一种情况下( i + p[i] <= maxrange),此时在向两边拓展,执行 while(str[i + p[i]] == str[i - p[i]]) p[i] ++ 的时候,一般情况下是失败的.为什么呢?因为如果要是成功的话,那么镜像翻转之后p[j]的值也会增加.换句话说,p[j]的值便是p[i]的值的上限.仅有一种情况除外,就是p[j]的值包含了边界,这样 p[i]向外扩展才有可能成功.因此可以认为所有符合第一种情况的时间复杂度是O(1).

其他情况的都是从maxrange以后开始向外扩展,假设向外扩展了K步,则此步花费时间O(k),那么接下来的K步都将花费O(1).(依据上述)那么相当于从下标j跳到下标 j+k+1 花费了O(2k). 所以,从下标1到下标n实际上是由几段的k组成的,总花费为O(2k1+2k2+2k3…) = O(2*n),是线性的.

Comments