算法题-第三周

1.计算器

给定一个包含正整数、加(+)、减(-)、乘()、除(/)的算数表达式(括号除外)，计算其结果。
表达式仅包含非负整数，+， - ，，/ 四种运算符和空格  。 整数除法仅保留整数部分。

• 示例 1:
  输入: “3+2*2”
  输出: 7
• 示例 2:
  输入: " 3/2 "
  输出: 1
• 示例 3:
  输入: " 3+5 / 2 "
  输出: 5

说明：你可以假设所给定的表达式都是有效的。请不要使用内置的库函数 eval。

/**
*模拟栈结构
*/
public static int calculate(String s) {
    Stack<Integer> stack = new Stack<>();
    char opt = '+';
    int currentNum = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c > '0' && c < '9') {
            currentNum = currentNum * 10 + (c - '0');
        }
        if ((!(c > '0' && c < '9') && c != ' ') || i == s.length() - 1) {
            if (opt == '+') {
                stack.push(currentNum);
            } else if (opt == '-') {
                stack.push(-currentNum);
            } else if (opt == '*') {
                stack.push(stack.pop() * currentNum);
            } else if (opt == '/') {
                stack.push(stack.pop() / currentNum);
            }
            opt = c;
            currentNum = 0;
        }
    }
    int result = 0;
    while (!stack.isEmpty()) {
        result += stack.pop();
    }
    return result;
}

2.每日温度

请根据每日气温列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

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

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

解题思路

暴力解，双循环遍历

public int[] dailyTemperatures(int[] T) {
    int[] waitDays = new int[T.length];
    int index = 0;
    while (index < T.length) {
        int currentTemp = T[index];
        for (int i = index + 1; i < T.length; i++) {
            if (currentTemp < T[i]) {
                waitDays[index] = i - index;
                break;
            }
        }
        ++index;
    }
    return waitDays;
}

解法2，倒序
从最后一天开始计算，最后一天的等待天数肯定为 0，往前遍历,直到遍历到最后一天,i 与 i+1 对比:
开始从 i+1 步进 waitDay[i+1]
T[i] < T[i+1]: waitDay = 1
T[i] > T[i+1]: i+1+(waitDay[i+1])*n - i

public static int[] dailyTemperaturesDES(int[] T) {
    int[] waitDays = new int[T.length];
    int index = T.length - 2;
    waitDays[T.length - 1] = 0;
    while (index >= 0) {
        int currentTemp = T[index];
        int nextTemp = T[index + 1];
        for (int i = index + 1; i < T.length; i += waitDays[i]) {
            if (nextTemp > currentTemp) {
                waitDays[index] = 1;
                break;
            } else {
                if (currentTemp < T[i]) {
                    waitDays[index] = i - index;
                    break;
                } else if (waitDays[i] == 0) {
                    waitDays[index] = 0;
                    break;
                }
            }
        }
        index -= 1;
    }
    return waitDays;
}