数据结构与算法--练习题（一）

括号匹配

题目：

假设表达式中允许包含两种括号:圆括号与⽅括号,其嵌套顺序随意,即() 或者[([][])]都是正 确的.⽽这[(]或者(()])或者([()) 都是不正确的格式. 检验括号是否匹配的⽅法可⽤”期待的急迫 程度"这个概念来描述.例如,考虑以下括号的判断: [ ( [ ] [ ] ) ]

解题思路：

对于上述问题我们可以考虑使用栈来解决，每当遇到左括号时，将符号入栈，当遇到右括号时，取栈顶的符号与之匹配，如果能够匹配，将括号出栈。如果不能匹配，结束循环，说明格式不正确。遍历结束，如果栈中的元素不为0，则说明还有没有匹配成功的元素，返回匹配失败。

代码：

int checkMatchingBrackets(char * S){

    // 获取字符串长度
    unsigned long length = strlen(S);
    
    // 初始化栈
    Stack stack;
    InitStack(&stack);
    
    PushStack(&stack, S[0]);
    // 1.如果是左括号 入栈
    // 2.如果是右括号, 取栈顶元素, 如果括号可以匹配, 将栈顶元素出栈, 继续循环. 如果不配直接return.
   
    for (int i = 1; i < length; i++) {
        char c = S[i];
        switch (c) {
            case ']':
            {
                char top;
                GetTop(stack, &top);
                if (top == '[') {
                    PopStack(&stack, &top);
                    break;
                } else {
                    return -1;
                }
            }
            case '}':
            {
                char top;
                GetTop(stack, &top);
                if (top == '{') {
                    PopStack(&stack, &top);
                    break;
                } else {
                    return -1;
                }
            }
            case ')':
            {
                char top;
                GetTop(stack, &top);
                if (top == '(') {
                    PopStack(&stack, &top);
                    break;
                } else {
                    return -1;
                }
            }
            default:
                PushStack(&stack, c);
                break;
        }
    }
    
    if (StackLength(stack) == 0) {
        DestoryStack(&stack);
        return 0;
    } else {
        DestoryStack(&stack);
        return -1;
    }
}

返回0说明匹配成功，-1表示匹配失败。栈的实现可以参考之前的文章：

时间复杂度： O(n)

空间复杂度： O(n)

每日气温

题目：

根据每日 气温 列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]

解法一: 暴力法

思路： 如果数组的长度为n, 当遍历到第i个元素（0 <= i < n）时, 从[j, n-1] （i + 1 <= j < n）开始遍历，如果遇到比第i个元素大的值，那么result[i] = j - i。

代码：

int* dailyTemperatures(int* T, int TSize, int* returnSize){

    int *res = (int *)malloc(sizeof(int) * TSize);
    *returnSize = TSize;

    for (int i = 0; i < TSize; i++) {
        int x = T[i];
        int diff = 0;
        for (int j = i + 1; j < TSize; j++) {
            int y = T[j];
            if (y > x) {
                diff = j - i;
                break;
            }
        }
        res[i] = diff;
    }
    return res;
}

时间复杂度： O(n^2)

空间复杂度： O(1)

解法二： 跳跃对比

思路：

这个思路和解法一的思路类似都是使用两次嵌套循环进行查找，不同的是，此解法是外层遍历是从后往前开始遍历的。这样能够利用已知的信息减少第二次循环的次数。

1. 最后一天的值一定是0，因为最后一天后面一定不会有比他温度更高的。
2. 外层循环从[TSize - 2, 0]遍历数组， 元素索引为i。
3. 内存循环从[i + 1, TSize - 1]， 元素索引为j。
   • 如果T[j] > T[i],那么res[i] = j - i
   • 如果T[j] <= T[i]
     • 如果res[j] == 0 则res[i] = 0. 第j天之后没有比它温度更高的，那么一定不会楚天比第i天更高的。
     • 如果res[j] != 0,则j+=res[j]。第j天之后还有比它更高的，直接跳跃到这一天进行对比。

代码：

int* dailyTemperatures2(int* T, int TSize, int* returnSize){

    int *res = (int *)malloc(sizeof(int) * TSize);
    *returnSize = TSize;
    // 最后一个元素,一定没有比他温度跟高的,所以等于0
    res[TSize - 1] = 0;

    // 从 TSize - 1 开始往前遍历
    for (int i = TSize - 2; i >= 0; i--) {
        int x = T[i];
        int diff = 0;
        for (int j = i + 1; j < TSize; ) {
            int y = T[j];
            if (y > x) {
                diff = j - i;
                break;
            } else {
                // 利用已知信息进行跳跃对比
                if (res[j] == 0) {
                    // 第j天的温度, 比第i天更低, 第j天后面没有比他温度更高的,那么一定不会出现比第i天更高的,
                    diff = 0;
                    break;
                } else {
                    // 第j天后面还有比他更高的,那么直接跳到这天进行对比
                    j+=res[j];
                }
            }
        }
        
        res[i] = diff;
    }
    return res;
}

解法三：栈

思路：

1. 初始化一个栈indexStack用来存放索引，和结果数组result
2. 遍历数组
   • 如果当前温度大于栈顶的温度，那么栈顶元素，应该在当前温度的索引和栈顶温度索引的差天后遇到比它温度高的。将栈顶元素出栈。
   • 将当前索引入栈
3. 遍历结束，将栈中剩余的元素，在结果数组result对应的索引位置的值设置为0。

代码：

int* dailyTemperatures(int* T, int TSize, int* returnSize){
    int *stack = (int *)malloc(sizeof(int) * TSize);
    int top = -1;
    int *result = malloc(sizeof(int) * TSize);
    *returnSize = TSize;
    
    top++;
    stack[top] = 0;
    
    for (int i = 1; i < TSize; i++) {
        int temp = T[i];
        int topIndex = stack[top];
        int topTemp = T[topIndex];
        while (topTemp < temp) {
            result[topIndex] = i - topIndex;
            top--;
            if (top == -1) break;
            topIndex = stack[top];
            topTemp = T[topIndex];
        }
        top++;
        stack[top] = i;
    }
    while (top != -1) {
        result[stack[top]] = 0;
        top--;
    }
    return result;
}

时间复杂度：O(n)

爬楼梯

题目：

爬楼梯问题:(LeetCode-中等) 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不 同的⽅法可以爬到楼顶呢？注意：给定 n 是⼀个正整数。

解法一：递归法

思路：： 如果要爬n阶楼梯，是爬n-1阶楼梯的方法与爬n-2阶楼梯的和。f(n) = f(n-1) + f(n-2).

代码：

int climbStairs1(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return climbStairs1(n - 1) + climbStairs1(n - 2);
}

时间复杂度： O(2^n).这种时间复杂度，执行效率太低。

解法二：动态规划

不难发现，这个问题可以被分解为一些包含最优子结构的子问题，即它的最优解可以从其子问题的最优解来有效地构建，我们可以使用动态规划来解决这一问题。

在第i阶可以又以下两种方法达到：

1. 在第i-1阶后爬一阶
2. 在第i-2阶后爬两阶

到达第i阶的方法总数，就是(i - i)阶和（i - 2）的方法数之和。

代码：

int climbStairs2(int n) {
    
    if (n < 3) {
        return n;
    }
    int arr[n];
    arr[0] = 1;
    arr[1] = 2;
    for (int i = 2; i < n; i++) {
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    return arr[n - 1];
}

时间复杂度： O(n).

字符串编码

问题：

字符串编码(LeetCode-中等) 给定⼀个经过编码的字符串，返回它解码后的字符串。 编码规则为: k[encoded_string]，表示其中⽅括号内部的 encoded_string 正好重复 k 次。 注意 k 保证为正整数。你可以认为输⼊字符串总是有效的；输⼊字符串中没有额外的空格， 且输⼊的⽅括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只 表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输⼊。 例如: s = "12[a]2[bc]", 返回 "aaabcbc". s = "3[a2[c]]", 返回 "accaccacc". s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

思路： 编码的字符串存在层级关系，所以需要进行一层一层的解码，联想到之前的括号匹配问题，可以使用栈结构解决问题。一次将字符串进行解码。根据题目可以得到三个关键点：

1. 遍历时第一次出现数字字符，到[符号之间，表示此层字符重复的次数。
2. 遇到[符号是，创建一个栈元素入栈，栈元素保存了此层[]之间的字符，和重复的次数。
3. 每当遇到]时，需要将此层字符进行展开，然后出栈元素，将展开的字符，添加到此时栈顶元素的内容后面。

代码：

Swift实现版本

public struct Stack<T> {
    
  /// Datastructure consisting of a generic item.
  fileprivate var array = [T]()

  /// The number of items in the stack.
  public var count: Int {
    return array.count
  }

  /// Verifies if the stack is empty.
  public var isEmpty: Bool {
    return array.isEmpty
  }

  /**
     Pushes an item to the top of the stack.
     
     - Parameter element: The item being pushed.
  */
  public mutating func push(_ element: T) {
    array.append(element)
  }

  /**
     Removes and returns the item at the top of the sack.
     
     - Returns: The item at the top of the stack.
  */
  public mutating func pop() -> T? {
    return array.popLast()
  }

  /// Returns the item at the top of the stack.
  public var top: T? {
    return array.last
  }
}

class StackElem {
    var repeatCount: Int = 1
    var content: String = ""
    
    var result: String {
        return String(repeating: content, count: repeatCount)
    }
}

func stringDecode(_ str: String) -> String {
    
    var repeatCountStr: String = ""
    
    var stack = Stack<StackElem>()
    
    stack.push(StackElem())
    
    for c in str {
        switch c {
        case "a"..."z":
            let top = stack.top!
            top.content.append(c)
            break
        case "0"..."9":
            repeatCountStr.append(c)
            break
        case "[" :
            // 创建一个栈元素 入栈
            let elem = StackElem()
            elem.repeatCount = Int(repeatCountStr)!
            repeatCountStr = ""
            stack.push(elem)
            break
        case "]":
            // 将栈顶元素出栈
            let elem = stack.pop()!
            if let top = stack.top {
                // 栈中还有元素
                top.content.append(elem.result)
            }
            break
        default:
            break
        }
    }
    
    return stack.top?.content ?? ""
}

时间复杂度：O(n)

字符串去重

题目：

给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

思路： 使用两次遍历的方式，第一次遍历记录每个字符出现的次数。第二次遍历将每个字符和栈顶字符进行比较，如果栈顶字符较小，且后面出现的次数大于0，将栈元素出栈，此栈顶元素出现次数-1.继续对比下个栈顶元素，如果栈顶元素在后面不会出现，将当前元素入栈。

1. 创建数组letterAppearCount来储存字符出现的个数，将他的每个元素设置为0。用字符当索引时要字符的索引应该为 letters - ’a‘,这时索引值才是从0开始的
2. 创建seen数组储存字符是否在栈中0不在，1在栈中。
3. 第一次遍历，如果当前的字符为c， 那么 letterAppearCount[c - 'a'] = letterAppearCount[c - 'a'] + 1.
4. 第二次遍历， 创建一个栈stack，用来进行字典序排序。
   • 如果字符在栈中，更新letterAppearCount数量
   • 如果当前字符c字典序大于栈顶字符，将字符c入栈。
   • 如果当前字符c字典序小于栈顶字符，有两种情况：
     • 如果栈顶字符在letterAppearCount数组中的值大于0时，将此元素出栈。同时更新letterAppearCount数组中的值-1, seen数组中置为0,继续和栈顶元素进行比较
     • 如果栈顶字符在letterAppearCount数组中的值为0，说明后面不会出现了，就不能将这个字符出栈了。
   • 将当前字符c入栈, 更新seen数组中置为1
5. 最后得到栈中的从栈底到栈顶组成的字符串就是字典序最小的字符串了。

代码：

char * removeDuplicateLetters(char * s){
    
    // 记录字符出现次数的数组
    int *letterAppearCount = (int *)malloc(sizeof(int) * 26);
    memset(letterAppearCount, 0, sizeof(int) * 26);
    // 记录字符是否在栈中的数组
    int *seen = (int *)malloc(sizeof(int) * 26);
    memset(seen, 0, 26 * sizeof(char));
    
    unsigned long length = strlen(s);
    
    for (int i = 0; i < length; i++) {
        letterAppearCount[s[i] - 'a']++;
        // printf("字符%c出现次数: %d\n", s[i], letterAppearCount[s[i] - 'a']);
    }
    
    char *stack = malloc(sizeof(char) * 27);
    int top = -1;
    
    for (int i = 0; i < length; i++) {
        char c = s[i];
        
        // 字符已经在栈中
        if (seen[c - 'a'] == 1) {
            // 当初字符的出现次数-1
            letterAppearCount[c - 'a']--;
            continue;
        }
        
        while (top != -1 &&
               stack[top] > c &&
               letterAppearCount[stack[top] - 'a'] > 1) {
            seen[stack[top] - 'a'] = 0;
            letterAppearCount[stack[top] - 'a']--;
            //printf("out %c, 剩余次数: %d\n", stack[top], letterAppearCount[stack[top] - 'a']);
            top--;
        }
        top++;
        stack[top] = c;
        seen[c - 'a'] = 1;
        //printf("in %c\n", c);
    }
    top++;
    stack[top] = '\0';
    //printf("result: %s\n", stack);
    return stack;
}

杨辉三角

代码

int** generate(int numRows, int* returnSize, int** returnColumnSizes){
    
    int **res = malloc(sizeof(int *) * numRows);
    *returnSize = numRows;
    *returnColumnSizes = malloc(sizeof(int) * numRows);
    
    for (int i = 0; i < numRows; i++) {
        int *row = (int *)malloc(sizeof(int) * (i + 1));
        res[i] = row;
        // 填入行首
        res[i][0] = 1;
        // 填入行尾
        res[i][i] = 1;
        (*returnColumnSizes)[i] = i + 1;
        if (i < 2) continue;
        for (int j = 1; j < i; j++) {
            res[i][j] = res[i - 1][j] + res[i - 1][j - 1];
        }
    }
    return res;
}