7.13号刷题

第一题 503. Next Greater Element II

题目描述

在一个有圈的数组中，找到每个数对应的下一个最大的数

算法

利用Stack 存储每个数的index，如果是降序，那么下一个最大的数是之前小于这个数的下一个最大数。

遍历两遍数组，找到答案

public class nextGreaterElements503 {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        if (n == 0) return res;
        Arrays.fill(res, -1);
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < nums.length * 2; i++) {
            int num = nums[i % n];
            while (!stack.isEmpty() && nums[stack.peek()] < num)
                res[stack.pop()] = num;
            if (i < n) stack.push(i);
        }
        return res;
    }
}

第二题 556. Next Greater Element III

题目描述

给定一个32位正整数n，寻找大于n，并且所含数字与n中各位数字相等的最小32位正整数。若不存在，返回-1。

算法

链接

public class nextGreaterElement556 {
    public int nextGreaterElement(int n) {
        char[] numbers = (n + "").toCharArray();

        int changeIndex = -1;
        for (int i = numbers.length - 2; i >= 0; i--) {
            if (numbers[i] < numbers[i + 1]) {
                changeIndex = i;
                break;
            }
        }
        if (changeIndex == -1) return -1;

        int nextTochange = 0, min = Integer.MAX_VALUE;
        for (int i = changeIndex + 1; i < numbers.length; i++) {
            if (numbers[i] > numbers[changeIndex] && numbers[i] - numbers[changeIndex] < min) {
                min = numbers[i] - numbers[changeIndex];
                nextTochange = i;
            }
        }

        char temp = numbers[changeIndex];
        numbers[changeIndex] = numbers[nextTochange];
        numbers[nextTochange] = temp;

        Arrays.sort(numbers, changeIndex + 1, numbers.length);
        long val = Long.valueOf(new String(numbers));
        return val <= Integer.MAX_VALUE ? (int) val : -1;
    }
}

第三题 439. Ternary Expression Parser

题目描述

给定一个字符串表示一个任意嵌套的三目表达式，计算表达式的结果。你可以假设表达式一定有效，并且只包含数字0-9,?, :, T 和 F (T 和 F 分别表示 True 和 False)

算法

DFS

public class Solution {
    public String parseTernary(String expression) {
        if (expression.isEmpty()) return "";
        
        char[] chars = expression.toCharArray();
        return String.valueOf(helper(chars, 0, chars.length - 1));
    }
    
    public char helper(char[] exp, int start, int end) {
        if (start == end) return exp[start];
        
        int i = start, count = 0;
        while (i <= end) {
            if (exp[i] == '?') {
                count++;
            }
            if (exp[i] == ':') {
                count--;
                if (count == 0) break;
            }
            i++;
        }
        return exp[start] == 'T' ? helper(exp, start + 2, i - 1) : helper(exp, i + 1, end);
    }
}

Substring

public class parseTernary439 {
    public String parseTernary3(String expression) {

        while (expression.length() != 1) {
            int index = expression.lastIndexOf("?");
            char temp;
            if (expression.charAt(index - 1) == 'T') {
                temp = expression.charAt(index + 1);
            } else {
                temp = expression.charAt(index + 3);
            }
            expression = expression.substring(0, index - 1) + temp + expression.substring(index + 4);
        }
        return expression;
    }
}

Stack

public class parseTernary439 {
    public String parseTernary2(String expression) {
        if (expression.isEmpty()) return "";
        Stack<Character> stack = new Stack<>();

        for (int i = expression.length() - 1; i >= 0; i--) {
            char c = expression.charAt(i);
            if (!stack.isEmpty() && stack.peek() == '?') {
                stack.pop();
                char first = stack.pop();
                stack.pop();
                char second = stack.pop();
                if (c == 'T') stack.push(first);
                else stack.push(second);
            } else {
                stack.push(c);
            }
        }
        return stack.pop().toString();
    }
}

第四题 385. Mini Parser

题目描述

给定一个以字符串表示的嵌套整数列表，实现一个反序列化的解析器。

每一个元素或者是一个整数，或者是一个列表 – 其元素也可能是一个整数，或者又是一个列表。

注意：你可以假设字符串是格式良好的。

• 字符串非空
• 字符串不包含空白字符。
• 字符串只包含数字0-9, [, - ,, ]

算法

利用stack，将每一个NestInter依次加入

public class deserialize385 {
    public NestedInteger deserialize(String s) {
        if (s.charAt(0) != '[') return new NestedInteger(Integer.valueOf(s));

        Stack<NestedInteger> stack = new Stack<>();
        NestedInteger cur = null;
        int l = 0;
        for (int r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            if (c == '[') {
                if (cur != null) {
                    stack.push(cur);
                }
                cur = new NestedInteger();
                l = r + 1;
            } else if (c == ']') {
                String n = s.substring(l, r);
                if (!n.isEmpty()) {
                    int num = Integer.valueOf(n);
                    cur.add(new NestedInteger(num));
                }
                if (!stack.isEmpty()) {
                    NestedInteger last = stack.pop();
                    last.add(cur);
                    cur = last;
                }
                l = r + 1;
            } else if (c == ',') {
                if (s.charAt(r - 1) != ']') {
                    String n = s.substring(l, r);
                    if (!n.isEmpty()) {
                        int num = Integer.valueOf(n);
                        cur.add(new NestedInteger(num));
                    }
                }
                l = r + 1;
            }
        }
        return cur;
    }
}

第五题 341. Flatten Nested List Iterator

题目描述

给定一个嵌套的整数列表，实现一个迭代器将其展开。

每一个元素或者是一个整数，或者是一个列表 – 其元素也是一个整数或者其他列表。

测试用例如题目描述。

算法

用两个stack,一个NestedInteger, 另一个存Integer的结果

public class NestedIterator implements Iterator<Integer> {

    Stack<NestedInteger> stacklist = new Stack<>();
    Stack<Integer> res = new Stack<>();

    public NestedIterator(List<NestedInteger> nestedList) {
        if (nestedList.isEmpty()) return;
        int n = nestedList.size();
        for (int i = n - 1; i >= 0; i--) {
            NestedInteger cur = nestedList.get(i);
            if (cur.isInteger()) {
                res.push(cur.getInteger());
            } else {
                stacklist.push(cur);
                helper();
            }
        }
    }
    public void helper() {
        while (!stacklist.isEmpty()) {
            NestedInteger cur = stacklist.pop();
            List<NestedInteger> list = cur.getList();
            int size = list.size();
            for (int i = size - 1; i >= 0; i--) {
                if (list.get(i).isInteger()) {
                    res.push(list.get(i).getInteger());
                } else {
                    stacklist.push(list.get(i));
                    helper();
                }
            }
        }
    }

    @Override
    public Integer next() {
        return res.pop();
    }

    @Override
    public boolean hasNext() {
        return !res.isEmpty();
    }
}

第六题 364. Nested List Weight Sum II

题目描述

求一个Nested List中，所有值的和的大小

算法

如果检测到是List则将他们全部推入下一层的List中。如果不是，则相加获得当前层的值

public class depthSumInverse364 {
    public int depthSumInverse(List<NestedInteger> nestedList) {
        List<Integer> res = new ArrayList<>();

        while (!nestedList.isEmpty()) {
            List<NestedInteger> next = new ArrayList<>();
            int layerSum = 0;
            for (NestedInteger nest : nestedList) {
                if (nest.isInteger()) {
                    layerSum += nest.getInteger();
                } else {
                    next.addAll(nest.getList());
                }
            }
            nestedList = next;
            res.add(0, layerSum);
        }
        int count = 1, sum = 0;
        for (Integer num : res) {
            sum += num * (count++);
        }
        return sum;
    }
}

第七题 394. Decode String

题目描述

给定一个经过编码的字符串，返回其解码字符串。

编码规则为：k[encoded_string]，其中中括号内的encoded_string被重复k次。注意k一定是正整数。

你可以假设输入字符串总是有效的；没有额外的空白字符，中括号也是格式良好的，等等。

另外，你可以假设原始数据不包含数字，并且数字只用来表示重复的次数，k。例如，输入不会出现3a或者2[4]等等。

算法

利用两个stack进行存储，一个存储所有需要重复的数字，一个存储之前的String。

之后循环向后，对每一种情况做出if的情况判断

public class Solution {
    public String decodeString(String s) {
        Stack<Integer> countStack = new Stack<>();
        Stack<String> stack = new Stack<>();

        char[] chars = s.toCharArray();
        int index = 0;
        String res = "";
        while (index < s.length()) {
            char c = chars[index];
            if (Character.isDigit(c)) {
                int count = 0;
                while (Character.isDigit(chars[index])) {
                    count = count * 10 + chars[index++] - '0';
                }
                index--;
                countStack.push(count);
            }
            else if (c == '[') {
                stack.push(res);
                res = "";
            }
            else if (c == ']') {
                int times = countStack.pop();
                StringBuilder sb = new StringBuilder(stack.pop());
                for (int i = 0; i < times; i++) sb.append(res);
                res = sb.toString();
            }
            else {
                res += c;
            }
            index++;
        }
        return res;        
    }
}

第八题 136. Single Number

题目描述

给定一个整数数组，除一个元素只出现一次外，其余各元素均出现两次。找出那个只出现一次的元素。

注意：

你的算法应该满足线性时间复杂度。可以不使用额外的空间完成此题吗？

算法

public class singleNumber136 {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int num : nums) res ^= num;
        return res;
    }
}

第九题 137. Single Number II

题目描述

在一个数组中，某个数字出现了1次，其余数字都是出现了3次。找出那个只出现1次的数字

算法

对于每一位，我们使用一个计数器进行计数。那么，对于这一位，当其个数到达k（本题中为3）的时候，我们需要将其清0,其余时候保持不变。

对于到达k清0的运算，我们用!(y1 & y2 … & yn)来表示。如果x1 = 1,那么y1 = 1。x1 = 0, y1 = ~x1

通过这样对每一位进行计数，即可得到答案。非常巧妙，建议看下链接中的图解

public class singleNumber137 {
    public int singleNumber(int[] nums) {
        int x1 = 0, x2 = 0, mask = 0;

        for (int i : nums) {
            x2 ^= x1 & i;
            x1 ^= i;
            mask = ~(x1 & x2);
            x1 &= mask;
            x2 &= mask;
        }
        return x1;
    }
}