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.            else if ([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