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

人魔七七 2019-04-09 11:10:34 337

题目描述

给一个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

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

灵感示意图

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

QQ截图20190409104615.png

第二步 把目录元素入栈

QQ图片20190409111451.gif

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

QQ截图20190409104653.png

主要代码

  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


转载自公众号:人魔七七