100天iOS数据结构与算法实战 Day06 - 栈的算法实战 Simplify Path

题目描述

给一个Unix风格的绝对路径，简化他。注意的是绝对路径以/开始（root 目录），（ . ）代表当前的目录，（ .. ）代表父目录。

例如：

1. "/a/./"   -->表示停留在当前'a'

2. "/a/b/.."-->表示跳转到父目录，from'b' to 'a'

3. "////"    -->连续多个'/'是有效的路径，等于单个'/'

4. Input:/home/

5. Output:/home

6. Input:/a/./b/../../c/

7. Output:/c

8. Input:/a/..

9. Output:/

10. Input:/a/../

11. Ouput:/

12. Input:/../../../../../a

13. Ouput:/a

14. Input:/a/./b/./c/./d/

15. Ouput:/a/b/c/d

16. Input:/a/../.././../../.

17. Ouput:/

18. Input:/a//b//c//////d

19. Ouput:/a/b/c/d

注意：大家可以在自己的终端试试,就很容易理解这道题意了。

灵感示意图

第一步 先把字符串拆分成数组根据（ / ）

第二步 把目录元素入栈

第三步 把原始栈reverse，最后把reverse的栈元素一一出栈并拼接

主要代码

1. -(NSString*)simplifyPath:(NSString*)inputStr

2. {

3.    NSMutableString*dirStr =[@"" mutableCopy];

4.    //1

5.    [dirStr appendString:@"/"];

6.     //2

7.    NSMutableArray*dirArray =[[inputStr componentsSeparatedByString:@"/"] mutableCopy];

8. //3

9.    DSStack*newStack =[[DSStack alloc] initWithSize:20];

10.    for(int i =0; i < dirArray.count; i++)

11.    {

12.     //4

13.        while([dirArray[i] isEqualToString:@""])

14.        {

15.            i++;

16.        }

17.         //5

18.        while(i < dirArray.count &&![dirArray[i] isEqualToString:@""])

19.        {

20.            if([dirArray[i] isEqualToString:@"."])

21.            {

22.            }

23.            elseif([dirArray[i] isEqualToString:@".."])

24.            {

25.                if(![newStack isEmpty]){

26.                    [newStack popLastObject];

27.                }

28.            }

29.            else

30.            {

31.                [newStack push:dirArray[i]];

32.            }

33.            i++;

34.        }

35.    }

36.     //6

37.    DSStack*newStack1 =[[DSStack alloc] initWithSize:20];

38.    while(![newStack isEmpty])

39.    {

40.        [newStack1 push:[newStack popLastObject]];

41.    }

42.     //7

43.    while(![newStack1 isEmpty])

44.    {

45.        if([newStack1 sizeOfStack]!=1)

46.            {

47.                [dirStr appendFormat:@"%@/",[newStack1 popLastObject]];

48.            }

49.        else

50.        {

51.            [dirStr appendFormat:@"%@",[newStack1 popLastObject]];

52.        }

53.    }

54.    return dirStr;

55. }

思路描述

1. 根路径是必须有一个（ / ）

2. 根据（ / ）拆分字符串，目的为了后面把多个（ / ）变成单个（ / ）

3. 创建一个栈结构

4. 循环遍历数组如果元素是空字符串，index向后移动

5. 把非空的元素目录比如a,b入栈。当碰到（ . ）不做操作，如果遇到（ .. ）如果栈不为空则出栈

6. 创建一个辅助栈，reverse刚开始的那个栈，便于拼接字符串

7. 拼接栈内的元素，但第一个不需要后缀（ / ）

GitHubDemo地址

GitHubDemo链接 [1]  

References

[1] GithubDemo: 

https://github.com/renmoqiqi/100-Days-Of-iOS-DataStructure-Algorithm/tree/master/Day06

转载自公众号：人魔七七

• 100天iOS数据结构与算法实战 Day01

• 100天iOS数据结构与算法实战 Day02 - 栈

• 100天iOS数据结构与算法实战 Day03 - 栈的算法实战 Valid Parentheses

• 100天iOS数据结构与算法实战 Day04 - 栈的算法实战 逆波兰表示法

• 100天iOS数据结构与算法实战 Day05 - 栈的算法实战 Evaluate Reverse Polish Nota