栈递归算法应用实现

2022-08-10 本文已影响0人 erlich

文章的算法实例阅读需要一定的c基础，在涉及算法之前会先实现栈的顺序结构与链式结构，希望能帮到你复习栈的知识

文中几个问题的解决，依赖最基础的数据结构，所以，最好的方式是自己实现一遍最基础的栈结构，最好能调试栈的本质方法

至少保障最基本的栈结构能独立实现，这不是一件很难的事情

如果不动手操作一番，这些算法往往就是过眼烟云尔

我自己不是那类聪明人，能传达的经验就是，正儿八经的自己多敲几遍，然后再以这些基础分析涉及到的几个算法问题

慢慢的你会习惯，习惯着用计算机的思维方式去考虑遇到的问题，但是又会在计算机思维的基础上，发挥我们人脑特有的抽象演化跟想象力，最终得出解决问题的方案

栈的顺序结构实现

// 初始化顺序结构SeqStack
bool initSeqStack(struct SeqStack *sStack) {
    sStack->top = -1;
    return true;
}

bool seqStackEmpty(struct SeqStack *sStack) {
    return sStack->top <= -1;
}

void configSeqStackData(struct SeqStack *sStack, int *array, int n) {
    if (n > INIT_SEQSTACK_CAPACITY) {
        n = INIT_SEQSTACK_CAPACITY;
    }
    for (int i = 0; i < n; i++) {
        union SeqStackNode mStackNode;
        mStackNode.data = array[i];
        sStack->nodes[++(sStack->top)] = mStackNode;
    }
}
void configSeqStackCh(struct SeqStack *sStack, char *array, int n) {
    if (n > INIT_SEQSTACK_CAPACITY) {
        n = INIT_SEQSTACK_CAPACITY;
    }
    for (int i = 0; i < n; i++) {
        union SeqStackNode mStackNode;
        mStackNode.ch = array[i];
        sStack->nodes[++(sStack->top)] = mStackNode;
    }
}

// 栈顶元素
union SeqStackNode *topSeqStack(struct SeqStack *sStack) {
    if (sStack->top < 0) {
        return NULL;
    }
    
    return &sStack->nodes[sStack->top];
}

// 栈长度
int lengthSeqStack(struct SeqStack *sStack) {
    return sStack->top + 1;
}


// 压栈
bool pushSeqStack(struct SeqStack *sStack, union SeqStackNode *node) {
    if (sStack->top >= INIT_SEQSTACK_CAPACITY - 1) {
        printf("栈已满，请pop栈.....\n");
        return false;
    }
    
    sStack->top = sStack->top + 1;
    sStack->nodes[sStack->top] = *node;
    
    return true;
}

// 出栈
union SeqStackNode *popSeqStack(struct SeqStack *sStack) {
    if (sStack->top < 0) {
        return NULL;
    }
    sStack->top = sStack->top - 1;
    return &sStack->nodes[sStack->top + 1];
}

// 遍历
void traverseSeqStack1(struct SeqStack *sStack) {
    if (sStack->top < 0) {
        return;
    }
    printf("\n========== stack - s ========== \n");
    for (int i = 0; i < sStack->top + 1; i++) {
        printf(" <<< %i", sStack->nodes[i].data);
    }
    printf("\n========== stack - e ========== \n");
}
void traverseSeqStack2(struct SeqStack *sStack) {
    if (sStack->top < 0) {
        return;
    }
    printf("\n========== stack - s ========== \n");
    for (int i = 0; i < sStack->top + 1; i++) {
        printf(" <<< %c)", sStack->nodes[i].ch);
    }
    printf("\n========== stack - e ========== \n");
}


// 测试 顺序结构 stack 基本功能
void testSeqStack(void) {
    struct SeqStack sStack;
    
    initSeqStack(&sStack);
    
    int array[10] = {1, 2, 3, 5, 7, 9, 6, 4, 2, 0};
    configSeqStackData(&sStack, array, 10);
    
    union SeqStackNode node1;
    node1.data = 30;
    printf("--- 压栈: %i---\n", node1.data);
    pushSeqStack(&sStack, &node1);
    
    traverseSeqStack1(&sStack);
    printf("seq stack 长度: %i\n", lengthSeqStack(&sStack));
    
    printf("--- 出栈---\n");
    union SeqStackNode *node2 = popSeqStack(&sStack);
    printf("出栈节点 : %i\n", node2->data);
    
    traverseSeqStack1(&sStack);
    
    printf("seq stack 长度: %i\n", lengthSeqStack(&sStack));
}

    --- 压栈: 30---

    ========== stack - s ========== 
     <<< 1 <<< 2 <<< 3 <<< 5 <<< 7 <<< 9 <<< 6 <<< 4 <<< 2 <<< 0 <<< 30
    ========== stack - e ========== 
    seq stack 长度: 11
    --- 出栈---
    出栈节点 : 30

    ========== stack - s ========== 
     <<< 1 <<< 2 <<< 3 <<< 5 <<< 7 <<< 9 <<< 6 <<< 4 <<< 2 <<< 0
    ========== stack - e ========== 
    --- 出栈---
    出栈节点 : 0

    ========== stack - s ========== 
     <<< 1 <<< 2 <<< 3 <<< 5 <<< 7 <<< 9 <<< 6 <<< 4 <<< 2
    ========== stack - e ========== 
    seq stack 长度: 9

栈的链式结构实现

// 初始化 链式结构SeqStack
bool initLinkStack(struct LinkStack *lStack) {
    lStack->count = 0;
    lStack->top = NULL; // top 指向头节点
    
    return NULL;
}

void configLinkStackData(struct LinkStack *lStack, int *array, int n) {
    for (int i = 0; i < n; i++) {
        union SeqStackNode mStackNode;
        mStackNode.data = array[i];
        
        struct LinkStackNode *lStackNode = (struct LinkStackNode *)malloc(sizeof(struct LinkStackNode *));
        lStackNode->item = mStackNode;
        lStackNode->next = NULL;
        
        if (lStack->top == NULL) {
            lStack->top = lStackNode;
        } else {
            lStackNode->next = lStack->top;
            lStack->top = lStackNode;
        }
        
        lStack->count = lStack->count + 1;
    }
}
void configLinkStackCh(struct LinkStack *lStack, char *array, int n) {
    for (int i = 0; i < n; i++) {
        union SeqStackNode mStackNode;
        mStackNode.data = array[i];
        
        struct LinkStackNode *lStackNode = (struct LinkStackNode *)malloc(sizeof(struct LinkStackNode *));
        lStackNode->item = mStackNode;
        lStackNode->next = NULL;
        
        if (lStack->top == NULL) {
            lStack->top = lStackNode;
        } else {
            lStackNode->next = lStack->top;
            lStack->top = lStackNode;
        }
        
        lStack->count = lStack->count + 1;
    }
}

// 栈顶元素
union SeqStackNode topLinkStack(struct LinkStack *lStack) {
    return lStack->top->item;
}

// 栈长度
int lengthLinkStack(struct LinkStack *lStack) {
    return lStack->count;
}


// 压栈
bool pushLinkStack(struct LinkStack *lStack, union SeqStackNode *item) {
    
    struct LinkStackNode *lStackNode = (struct LinkStackNode *)malloc(sizeof(struct LinkStackNode *));
    lStackNode->item = *item;
    lStackNode->next = NULL;
    
    if (lStack->top == NULL) {
        lStack->top = lStackNode;
    } else {
        lStackNode->next = lStack->top;
        lStack->top = lStackNode;
    }
    
    lStack->count = lStack->count + 1;
    return true;
}

// 出栈
union SeqStackNode popLinkStack(struct LinkStack *lStack) {
    struct LinkStackNode *q = lStack->top;
    lStack->top = q->next;
    lStack->count = lStack->count - 1;
    
    union SeqStackNode mStackNode = q->item;
    
    free(q);
    
    return mStackNode;
}

// 遍历
void traverseLinkStack1(struct LinkStack *lStack) {
    struct LinkStackNode *q = lStack->top;
    printf("\n========== link stack - s ========== \n");
    while (q != NULL) {
        printf(" <<< %i", q->item.data);
        q = q->next;
    }
    printf("\n========== link stack - e ========== \n");
}

void traverseLinkStack2(struct LinkStack *lStack) {
    struct LinkStackNode *q = lStack->top;
    printf("\n========== link stack - s ========== \n");
    while (q != NULL) {
        printf(" <<< %c", q->item.ch);
        q = q->next;
    }
    printf("\n========== link stack - e ========== \n");
}


void testLinkStack(void) {
    struct LinkStack lStack;
    
    initLinkStack(&lStack);
    
    int array[10] = {1, 2, 3, 5, 7, 9, 6, 4, 2, 0};
    configLinkStackData(&lStack, array, 10);
    
    union SeqStackNode node1;
    node1.data = 30;
    printf("--- 压栈: %i---\n", node1.data);
    pushLinkStack(&lStack, &node1);
    
    traverseLinkStack1(&lStack);
    printf("link stack 长度: %i\n", lengthLinkStack(&lStack));
    
    printf("--- 出栈---\n");
    union SeqStackNode node2 = popLinkStack(&lStack);
    printf("出栈节点 : %i\n", node2.data);
    
    traverseLinkStack1(&lStack);
    
    printf("link stack 长度: %i\n", lengthLinkStack(&lStack));
    
    
    
    printf("--- 出栈---\n");
    union SeqStackNode node3 = popLinkStack(&lStack);
    printf("出栈节点 : %i\n", node3.data);
    
    traverseLinkStack1(&lStack);
    
    printf("link stack 长度: %i\n", lengthLinkStack(&lStack));
}

    --- 压栈: 30---

    ========== link stack - s ========== 
     <<< 30 <<< 0 <<< 2 <<< 4 <<< 6 <<< 9 <<< 7 <<< 5 <<< 3 <<< 2 <<< 1
    ========== link stack - e ========== 
    link stack 长度: 11
    --- 出栈---
    出栈节点 : 30

    ========== link stack - s ========== 
     <<< 0 <<< 2 <<< 4 <<< 6 <<< 9 <<< 7 <<< 5 <<< 3 <<< 2 <<< 1
    ========== link stack - e ========== 
    link stack 长度: 10
    --- 出栈---
    出栈节点 : 0

    ========== link stack - s ========== 
     <<< 2 <<< 4 <<< 6 <<< 9 <<< 7 <<< 5 <<< 3 <<< 2 <<< 1
    ========== link stack - e ========== 
    link stack 长度: 9

有了两种栈结构的视线，接下来就可以考虑以下几个算法问题了

进制转换问题

由于转换需要重复取模运算，而前面取模的结果往往在低位，后取模的结果在高位，输出按从左到右，由高位到低位，正好可以借助栈的后进先出来解决这个问题

// 十进制 转 二进制
void decimal_to_binary(int n) {
    struct SeqStack sStack;
    initSeqStack(&sStack);
    
    while (n > 0) {
        union SeqStackNode node;
        node.ch = n % 2 + 48;
        pushSeqStack(&sStack, &node);
        n = n / 2;
    }
    
    int len = lengthSeqStack(&sStack);
    union SeqStackNode *node1 = popSeqStack(&sStack);
    printf("二进制:  0b");
    for (int i = 0; i < 32 - len; i++) {
        printf("0");
    }
    
    while (node1 != NULL) {
        printf("%c", node1->ch);
        node1 = popSeqStack(&sStack);
    }
    printf("\n");
}

// 十进制 转 八进制
void decimal_to_octal(int n) {
    struct SeqStack sStack;
    initSeqStack(&sStack);
    
    while (n > 0) {
        union SeqStackNode node;
        node.ch = n % 8 + 48;
        pushSeqStack(&sStack, &node);
        n = n / 8;
    }
    
//    int len = lengthSeqStack(&sStack);
    union SeqStackNode *node1 = popSeqStack(&sStack);
    printf("八进制:  0");
    
    while (node1 != NULL) {
        printf("%c", node1->ch);
        node1 = popSeqStack(&sStack);
    }
    printf("\n");
}

// 十进制 转 十六进制
void decimal_to_hex(int n) {
    struct SeqStack sStack;
    initSeqStack(&sStack);
    
    while (n > 0) {
        union SeqStackNode node;
        int h = n % 16;
        if (h > 9) {
            node.ch = h - 9 + 97 - 1;
        } else {
            node.ch = h + 48;
        }
        pushSeqStack(&sStack, &node);
        n = n / 16;
    }
    
    int len = lengthSeqStack(&sStack);
    union SeqStackNode *node1 = popSeqStack(&sStack);
    printf("十六进制: 0x");
    
    for (int i = 0; i < 8 - len; i++) {
        printf("0");
    }
    
    while (node1 != NULL) {
        printf("%c", node1->ch);
        node1 = popSeqStack(&sStack);
    }
    printf("\n");
}

爬楼梯问题

题目

需要爬n阶楼梯达到楼顶
每次可以选择爬1或2个台阶

有多少种不同的方法可以爬到楼顶?

分析

在分析这个问题之前，我想到以前有人玩过的一种游戏，比这个题目更生动, 就当个小插曲

A跟B两个人比策略,谁能先加到20就赢
回合制，就是每人在每个回合里选择 +1 还是 +2，然后对方执行，紧接着又自己...
你有没有碰到过有人玩这个游戏，总赢，百分百，不管先手还是后手

如果是你，你能保障不管先手还是后手永远赢对方么?

如果你能肯定，那么你一定是个聪明人，而且一定是个善于顶层设计的高手

秘密其实就在于稳赢的一方总是先把自己置于赢的低位上，然后一步步分析自己前一步应该达到一个什么样的条件

这就是递归思路了

如果我想一直赢下去, 那么就得保障最后加到20的操作肯定得是我来执行，不管我是不是先手
为了保障自己最后这一手，就必须设置安全机制，肯定是对手出手之后，我出手完成最后一步加到20，稳赢
我就给对方设置一个到20的距离，这个距离，对方够不到，但是我可以接着对方的出手，保障我自己能百分百够得到
- 20之前对方出手之后，要保障我到20的距离要么是1，要么是2，那么对方出手时的距离就应该是3，这样不管对方怎么出手，始终我赢
- 为了让对方保持这个3的距离，前一步我也得赢17
- 对方到17的距离就得是3，我得赢14
最终我只要抢占 2 5 8 11 14 17，就能保障从开始一直赢到最后

当然如果对方熟知这个规则，对方先手，就稳赢

忽然想到了这个例子，就当是活跃一下思路了，看看对分析此问题有没有帮助

回到爬楼梯问题

要么选择爬一阶，要么选择爬两阶
最后要么爬一阶到顶，要么爬两阶到顶
爬一阶到顶的话，前面的n-1阶就有f(n-1)种方法
爬两阶到顶的话，前面的n-2阶就有f(n-2)种方法

爬楼梯算法实现

n == 1, f(n) = 1
n == 2, f(n) = 2
n == 3, f(n) = 3 [f(3) = f(1) + f(2)]

由于另一篇博客已经专门针对fibonacci的递归以及优化做了详细阐述，此处就不再赘述了，具体实现及优化 - 从斐波那契 - 谈及动态规划 - 优化

每日气温问题

题目

根据每日气温表，重新生成一个列表，对应位置的输入为需要等待几天温度才会超过该位置对应的温度
例如给定温度列表 [33, 34, 28, 25, 15, 36, 32, 22, 10, 37]

输出列表 [1, 4, 3, 2, 1, 4, 3, 2, 1, 0]

分析一

我们跳过不需要思考就能写下的暴力遍历方法，而考虑的是怎么优化复杂度

是否可以比较的次数
每天的气温可以认为是一个随机变量，遍历到具体某一天，这天之后的气温针对于这一天都是一个全新状态
如果从前往后，后面的每一天就需要按部就班的遍历与当天比较
这样复杂度就为O(n^2)(系数忽略)

减少比较的次数

可否预先存储一定的过程比较结果
考虑从后往前遍历，这样针对于前面的某一天气温，这一天之后的气温就不再是完全空的状态了，问题在于怎么样存储这些状态，又如何运用
如果遍历到某一天，这一天之后的每一天都能存储下来气温上升需要的天数差值，也就是后一天存储了气温上升的天数
- 如果后一天气温比当天高，后面就不需要遍历了
- 那么如果后一天气温比当天低，遍历不再是后一天开始挨个往后遍历比较了，而是往后滑动一个窗口距离再次比较
- 上面的过程重复，当天之后的遍历过程变为一个个窗口遍历，窗口针对于挨个遍历，次数就少了很多
- 除非当天之后的气温是升序的，而且最后一天气温比当天高，其余的每天气温都比当天低，这样窗口就是1，当天比较遍历流程这个回合里，这跟暴力没什么区别
- 这种极端情况也不会造成多大困扰，因为也就仅仅针对当天而已，跨过当天，后续的每一天的比较复杂度都是O(1)

反向遍历方法实现

这其实也包含了动态规划的思想，因为从后往前遍历，前面的每天在进行轮询判断的时候，都依赖往后的每一天的比较结果存储

//- 根据每日气温表，重新生成一个列表，对应位置的输入为
//  需要等待几天温度才会超过该位置对应的温度
//- 例如给定温度列表 [33, 34, 28, 25, 15, 36, 32, 22, 10, 37]
//
//    输出列表 [1, 4, 3, 2, 1, 4, 3, 2, 1, 0]
void day_weather(int array[], int n, int days[]) {
    // 从后往前遍历
    for (int i = n - 2; i >= 0; i--) {
        for (int j = i + 1; j < n; j += days[j]) {
            // 如果判断紧 第i天之后的一天 比当天气温高，就把天数差值存储下来
            if (array[i] < array[j]) {
                days[i] = j - i;
                break;
            } else if (days[j] == 0) {
                // 第i天之后的 第j天 不存在比第j天气温更高的 日子，
                // 那么 第i天 之后 也不存在比 第i天气温更高的 日子
                // 因为 第i天 已经比 第j天 气温高
                days[i] = 0;
            }
        }
    }
}

分析二

上面的分析一策略并没有最终把复杂度完全降解到一个线性的维度

如果我们靠空间换时间策略是否可以做到

通过额外空间缓存之前的每一步过程及状态信息，如何做到呢？

之前的每一步记录都会缓存，为的是当前的节点与记录比较
并不是缓存之前所有的每一步记录
重点在于回溯过程

可能描述还是比较抽象，直接操作一遍流程，就比较清晰了

image.png
image.png
image.png

结合上面的流程

遍历过程中，事先并不知道后续还有没有比当天气温高的天
栈的作用就是让之前的比较过程能有机会先把index缓存起来
碰到日气温高的一天，当天index跟 pop栈index 差值存放在结果数组，位置就放在pop栈index处

最后结果就是 1 4 3 2 1 4 3 2 1 0

栈方式有没有降低时间复杂度呢，并没有，但是在处理复杂问题的时候，借助栈可以解决

栈方式实现

void day_weather1(int array[], int n, int days[]) {
    struct SeqStack indexStack;
    initSeqStack(&indexStack);
    
    for (int i = 0; i < n; i++) {
        if (seqStackEmpty(&indexStack)) {
            union SeqStackNode sStackNode;
            sStackNode.data = i;
            pushSeqStack(&indexStack, &sStackNode);
            continue;
        }
        
        union SeqStackNode *topNode = topSeqStack(&indexStack);
        
        while (!seqStackEmpty(&indexStack) && array[topNode->data] < array[i]) {
            popSeqStack(&indexStack);
            days[topNode->data] = i - topNode->data;
            topNode = topSeqStack(&indexStack);
        }
        
        union SeqStackNode mNode;
        mNode.data = i;
        pushSeqStack(&indexStack, &mNode);
    }
}

去除重复字母，保持字典序最小

题目

给定一个字符串，仅包含小写字母
需要除去字符串中的重复字母，使得每个字母仅出现一次
要求返回的结果字符串字典序列最小
不打乱其他字符的相对位置
给定 bccbbcadbaec, adbec 就比 bcade 字典序小

分析

去重问题不大，就是实现简单与复杂的问题
去重，去哪些，留哪个，由字典序结果而定
如何处理选择过程
字典序 - 比较字母ascii
有先后顺序，可以用栈来控制
需要一个记录容器，记录字符出现的次数

实现

char *remove_dup_chars(char *src) {
    if (src == NULL) {
        return "";
    }
    
    int records[26] = {0};      // char - 'a' = index
    int len = (int)strlen(src);
    char *stack = malloc((len + 1) * sizeof(char));
    memset(stack, 0, (len + 1) * sizeof(char));
    if (len <= 1) {
        return src;
    }
    
    int top = -1;
    
    for (int i = 0; i < len; i++) {
        records[src[i] - 'a']++;
    }
    
    for (int i = 0; i < len; i++) {
        bool ifExist = false;
        for (int j = 0; j <= top; j++) {
            if (stack[j] == src[i]) {
                ifExist = true;
                break;
            }
        }
        
        if (ifExist) { // 如果栈已经存在字符，就不需要再压栈了 记录中出现次数--
            records[src[i] - 'a']--;
        } else {
            while (top > -1 && stack[top] > src[i] && records[stack[top] - 'a'] > 1) {
                records[stack[top] - 'a']--;
                top--;
            }
            stack[++top] = src[i];
        }
    }
    stack[++top] = '\n';
    
    return stack;
}

字符串编码

题目

给定一个经过编码的字符串，返回它解码后的字符串
k[encoded_string] -> encoded_string 重复k次
encoded_string 没有额外的空格
3[a]2[bc] -> aaabcbc
3[a2[c]] -> accaccacc
2[abc]3[cd]ef -> abcabccdcdcdef

分析

解析字符串，字符串中包含指令字符跟文本字符及控制字符需要解析的，栈是最合适的结果
[] 界定问题
如果数字是1位以上的字符处理，如13

实现

实例中栈结构用模拟方式处理

仔细揣摩判断的过程

举例 - 3[a2[c]]

碰到 3 压栈
[ 压栈
a 压栈
2 压栈
[ 压栈
c 压栈
] 解析 cc -> 3[acc
] 解析 accaccacc

char * str_decode(char *src_str) {
    int stack_size = 20;
    int append_size = 10;
    char *stack = (char *)malloc(stack_size * sizeof(char));
    int top = -1;
    
    int len = (int)strlen(src_str);
    // 字符入栈
    for (int i = 0; i < len; i++) {
        if (src_str[i] != ']') {
            if (top == stack_size - 1) {
                stack_size += append_size;
                stack = realloc(stack, stack_size * sizeof(char));
            }
            stack[++top] = src_str[i];
        } else {
            // i位置碰到了 ]
            // 定义一个 结构 pop出来的元素
            int m_size = 10;
            int m_append_size = 5;
            int m_top = -1;
            char *mstack = (char *)malloc(sizeof(char));
            while (stack[top] != '[') {
                if (m_top == m_size - 1) {
                    m_size += m_append_size;
                    mstack = realloc(mstack, m_size *sizeof(char));
                }
                mstack[++m_top] = stack[top--];
            }
            
            // '[' 出栈
            top--;
            
            // 解析数字
            char str_num[10];
            int len_str_num = 0;
            while (top > -1 && stack[top] >= '0' && stack[top] <= '9') {
                str_num[len_str_num++] = stack[top--];
            }
            
            int num = atoi(str_num);
            int temp_top = m_top;
            
            for (int i = 0; i < num; i++) {
                m_top = temp_top;
                while (m_top > -1) {
                    if (top == stack_size - 1) {
                        stack_size += append_size;
                        stack = realloc(stack, stack_size * sizeof(char));
                    }
                    stack[++top] = mstack[m_top--];
                }
            }
            
            free(mstack);
            mstack = NULL;
        }
    }
    
    stack = realloc(stack, (top + 1) * sizeof(char));
    stack[top + 1] = '\0';
    
    return stack;
}

栈递归算法应用实现

栈的顺序结构实现

栈的链式结构实现

进制转换问题

爬楼梯问题

题目

分析

爬楼梯算法实现

每日气温问题

题目

分析一

反向遍历方法实现

分析二

栈方式实现

去除重复字母，保持字典序最小

题目

分析

实现

字符串编码

题目

分析

实现

猜你喜欢

热点阅读

栈 递归 算法应用实现

栈的顺序结构实现

栈的链式结构实现

进制转换问题

爬楼梯问题

题目

分析

爬楼梯算法实现

每日气温问题

题目

分析一

反向遍历方法实现

分析二

栈方式实现

去除重复字母，保持字典序最小

题目

分析

实现

字符串编码

题目

分析

实现

猜你喜欢

热点阅读

栈递归算法应用实现