流下了不学无术的泪水——今天你刷题了吗(三)

点击上方“

程序人生

”,选择“置顶公众号”

第一时间关注程序猿(媛)身边的故事

流下了不学无术的泪水——今天你刷题了吗(三)

插图作者:maxwellthebeech



编者按:《今天你刷题了吗》是小班克发起的一场做算法题的活动,该活动会尽量保持在一周一期,喜欢刷题的、或者对刷题有需要的同僚,可以跟着小班克我一起,每周一道算法题。当然,能力较强或者时间较多的朋友也可以自己去LeetCode上注册一个账号,按照自己的速度刷题。那么闲话不多说,我们一起来看看

上期

留下的问题的解决方案吧!

在讲题目之前先啰嗦一句,由于小班克平时 Unity 3D 游戏引擎使用的比较多,因此小班克解题使用的均是 C-Sharp 语言(Unity 3D 游戏引擎使用的语言是 C-Sharp)。但是其他的官方解就不一定了,有可能是 Java,也有可能是 C,总之小班克以后会在前面标注出来(对啊,我就是懒不愿意帮你翻译成统一的语言~)

题目如下:



流下了不学无术的泪水——今天你刷题了吗(三)

翻译过来就是:

给你一个字符串,找出最长的没有重复字符的子字符串的长度。

 

接下来,就让大家见识见识小班克的穷举法吧!哈哈哈

解题过程(C-Sharp):

解题思路如下:这个应该算是目前来说遇到的一个比较难的题目了,在

LeetCode

上显示的也是属于中等难度一类的。我的做法比较粗暴,我首先定义了两个链表,分别用来存储当前子字符串和当前最大字符串(使用

Hash Tab

应该会更快)。然后使用嵌套的循环将所有的可能都测试一遍。当然这种暴力的穷举法,小班克是不推荐的

~





public

 

class

 

Solution

 {



  

public

 

int

 

LengthOfLongestSubstring

(

string

 s)



       

{

           List<

char

> maxSubString = 

new

 List<

char

>();

           List<

char

> curSubString = 

new

 List<

char

>();



           

for

 (

int

 i = 

0

; i < s.Length; i++)

           {

               curSubString.Clear();



               

for

 (

int

 j = i; j < s.Length; j++)

               {

                   

if

 (!curSubString.Contains(s[j]))

                       curSubString.Add(s[j]);

                   

else



                       

break

;

               }



               

if

 (curSubString.Count > maxSubString.Count)

               {

                   maxSubString = 

new

 List<

char

>(curSubString);

               }

           }

       

           

return

 maxSubString.Count;

       }

}

时间复杂度:O(n^2)。两个嵌套的循环,最大运行的次数是n + (n-1) + (n-2) + (n-3) + …… + 1。算一下就是n(n+1)/2,去掉系数取最高次幂,因此时间复杂度为O(n^2)。

空间复杂度:

O(1)。只会在一开始创建两个链表(这个小班克自己也不确定,希望有大牛给出正确的答案,期待在评论中看到正确的答案)。

 

附加解题方案一

(Java)

public

 

class

 

Solution

 

{

public

 

int

 

lengthOfLongestSubstring

(

String s



{

       

int

 n = s.length();

       

int

 ans = 

0

;

       

for

 (

int

 i = 

0

; i < n; i++)

           

for

 (

int

 j = i + 

1

; j <= n; j++)

               

if

 (allUnique(s, i, j)) ans = Math.max(ans, j - i);

       

return

 ans;

   }



public

 boolean 

allUnique

(

String s, 

int

 start, 

int

 end



{

       Set<Character> 

set

 = 

new

 HashSet<>();

       

for

 (

int

 i = start; i < end; i++) 

{

           Character ch = s.charAt(i);

           

if

 (

set

.contains(ch)) 

return

 

false

;

           

set

.

add

(ch);

       }

       

return

 

true

;

}

}

解题思路:

这个解题思路和我的很像,只不过他单独写了一个函数allUnique来判断这个子字符串是不是没有重复的字符,而我使用了C-Sharp语言库中List自带的函数Contains函数来判断重复。

时间复杂度:

O(n^3)。同学们,考验你们高数成绩的时候到了。

    首先我们可以非常简单的算出,函数allUnique的时间复杂度是O(end-start),即O(j-i);

    然后对于一个给定的i,消耗的时间为

流下了不学无术的泪水——今天你刷题了吗(三)

   

 最后所有的时间复杂度为

流下了不学无术的泪水——今天你刷题了吗(三)

空间复杂度:

O(min(m, n))。官方给出的解释是,每次检查子集重复性的时候,我们都需要花费O(k)的空间来创建一个集合,来判断子字符串是否重复,而k就是这个集合的长度。k的长度为给定字符串的长度和子字符串的长度的下界。(我是感觉不太对的,因为每次循环都会创建一个新的集合)。

附加解题方案二(Java):

public

 

class

 

Solution

 

{

public

 

int

 

lengthOfLongestSubstring

(

String s



{

       

int

 n = s.length();

       Set<Character> 

set

 = 

new

 HashSet<>();

       

int

 ans = 

0

, i = 

0

, j = 

0

;

       

while

 (i < n && j < n) 

{

           

// try to extend the range [i, j]



           

if

 (!

set

.contains(s.charAt(j)))

    {

               

set

.

add

(s.charAt(j++));

               ans = Math.max(ans, j - i);

           }

           

else

 

    {

               

set

.

remove

(s.charAt(i++));

           }

       }

       

return

 ans;

}

}

解题思路:

这个方案明显要比前两个方案高明很多。

    1. 首先创建一个集合 set,用于存储当前的子字符串,然后创建三个变量,分别为最大无重复子字符串的长度 ans、子字符串起点在给定的字符串的指针位置 i,子字符串终点的指针 j。

    2. 使用一个 While 循环,当子字符串中没有字符 s[j] 时,将字符 s[j] 压入子字符串,并将字符串的长度和 ans 做对比,取最大值。并将 j++。

    3. 当子字符串中含有字符 s[j],将 s[i] 从子字符串中移除,并将起点向前移动一格,即 i++。

    4. 最后,当 i 或者 j 其中某一个大于 s 的长度时,退出循环。



时间复杂度:

O(n)。比较简单,就不解释了。



空间复杂度:

O(n)。和第一题一样,小编也不是很确定这个空间复杂度算是 o(n) 还是其它。

小编保证,在下一期之前一定好好学习空间复杂度的知识,把这个问题解决了~

流下了不学无术的泪水——今天你刷题了吗(三)

插图作者:maxwellthebeech



下期题目:

这期题目是我们做到现在为止,第一个难度为 Hard 的题目:

流下了不学无术的泪水——今天你刷题了吗(三)

流下了不学无术的泪水——今天你刷题了吗(三)

翻译过来就是:

给你两个排好序的数组,找出该数组的中间值(如果两个数组的长度和是偶数的话,如示例二,则中间值为中间两个数的平均值)。需要注意的是,这题要求时间复杂度不得高于 O(log(m+n))。



点击图片get往期内容

流下了不学无术的泪水——今天你刷题了吗(三)

流下了不学无术的泪水——今天你刷题了吗(三)

流下了不学无术的泪水——今天你刷题了吗(三)

流下了不学无术的泪水——今天你刷题了吗(三)