力扣爆刷第114天之CodeTop100五连刷56-60

一、78. 子集

题目链接：https://leetcode.cn/problems/subsets/description/
思路：求组合，元素无重，求全部子集，那么每一个节点都搜集，且组合需要起始位置，结束。

class Solution {
    List<Integer> list = new ArrayList<>();
    List<List<Integer>> resList = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backTracking(nums, 0);
        return resList;
    }
    
    void backTracking(int[] nums, int start) {
        resList.add(new ArrayList(list));

        for(int i = start; i < nums.length; i++) {
            list.add(nums[i]);
            backTracking(nums, i+1);
            list.remove(list.size()-1);
        }
    }
}

二、105. 从前序与中序遍历序列构造二叉树

题目链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
思路：很典型的题目，递归构造二叉树，为了节省时间，先用一个map记录下来根节点在中序的索引，通过这个索引，可以确定左右子树各有多少元素，由此可以敲定边界条件，把握住这个思路就可以。

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return createTree(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
    }
    
    TreeNode createTree(int[] preorder, int[] inorder, int lp, int rp, int li, int ri) {
        if(lp > rp) return null;
        int mid = preorder[lp];
        int in = map.get(mid);
        TreeNode root = new TreeNode(mid);
        root.left = createTree(preorder, inorder, lp+1, lp+in-li, li, in-1);
        root.right = createTree(preorder, inorder, lp+in-li+1, rp, in+1, ri);
        return root;
    }
}

三、43. 字符串相乘

题目链接 ：https://leetcode.cn/problems/multiply-strings/description/
思路：两数相乘的结果要存入的位置分别为i+j和i+j+1，把握住这个然后控制好边界条件即可。

class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length(), n = num2.length();
        int[] nums = new int[m+n];
        for(int i = m-1; i >= 0; i--) {
            for(int j = n-1; j >= 0; j--) {
                int x = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int p1 = i+j, p2 = i+j+1;
                int sum = x + nums[p2];
                
                nums[p2] = sum % 10;
                nums[p1] += sum / 10;
            }
        }
        int i = 0;
        while(i < nums.length) {
            if(nums[i] != 0) break;
            i++;
        }
        StringBuilder builder = new StringBuilder();
        while(i < nums.length) {
            builder.append(nums[i++]);
        }
        String s = builder.toString();
        return s.length() == 0 ? "0" : s;
    }
}

四、155. 最小栈

题目链接：https://leetcode.cn/problems/min-stack/description/
思路：使用两个栈，一个栈正常当栈用，另一个栈，只有元素小于栈顶元素才放入，否则重复放入栈顶元素，这样可以简化pop操作。

class MinStack {
    LinkedList<Integer> stack1 = new LinkedList<>();
    LinkedList<Integer> stack2 = new LinkedList<>();
    public MinStack() {
        
    }
    
    public void push(int val) {
        stack1.push(val);
        stack2.push(Math.min(val, stack2.isEmpty() ? val : stack2.peek()));
    }
    
    public void pop() {
        stack1.pop();
        stack2.pop();
    }
    
    public int top(){
        return stack1.peek();
    }
    
    public int getMin() {
        return stack2.peek();
    }
}

五、151. 反转字符串中的单词

题目链接：https://leetcode.cn/problems/reverse-words-in-a-string/description/
思路：经典题目，先逐个翻转单词，然后再整体翻转。

class Solution {
    public String reverseWords(String s) {
        char[] clist = s.toCharArray();
        StringBuilder b1 = new StringBuilder();
        StringBuilder b2 = new StringBuilder();
        for(int i = 0; i < clist.length; i++) {
            if(clist[i] != ' ') {
                b2.append(clist[i]);
            }else if(b2.length() != 0) {
                b1.append(b2.reverse()).append(' ');
                b2 = new StringBuilder();
            }
        }
        if(clist[clist.length-1] != ' ') b1.append(b2.reverse());
        if(b1.charAt(b1.length()-1) == ' ') b1.deleteCharAt(b1.length()-1);
        return b1.reverse().toString();
    }
   
}