力扣爆刷第158天之TOP100五连刷56-60（子集、最小栈、最长有效括号）

力扣爆刷第158天之TOP100五连刷56-60（子集、最小栈、最长有效括号）

一、78. 子集

题目链接：https://leetcode.cn/problems/subsets/description/
思路：对于子集问题，典型的回溯解法，搜集所有子集即每一个节点都参与收集，而且子集不要求顺序，是组合类型，需要指定回溯的起始位置。而且元素无重不需要去重。

class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> list = new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {backTracking(nums, 0);return result;}void backTracking(int[] nums, int index) {result.add(new ArrayList(list));for(int i = index; 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 = map.get(preorder[lp]);TreeNode node = new TreeNode(preorder[lp]);node.left = createTree(preorder, inorder, lp+1, lp+mid-li, li, mid-1);node.right = createTree(preorder, inorder, lp+mid-li+1, rp, mid+1, ri);return node;}
}

三、43. 字符串相乘

题目链接：https://leetcode.cn/problems/multiply-strings/description/
思路：字符串相乘，首先确定拼接方法，采用数组拼接，方便计算，长度的话，两个字符串长度相加的长度正好覆盖最大乘积，至于进位如何计算，因为每次相乘都是个位数进行相乘，结果不会超过两位，所以维护两位的窗口，后一位用来累加进位，前一位作为进位。以此往复即可。

class Solution {public String multiply(String num1, String num2) {int n = num1.length(), m = num2.length();int[] nums = new int[n + m];for(int i = n-1; i >= 0; i--) {for(int j = m-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 k = 0;while(k < nums.length) {if(nums[k] != 0) break;k++;}StringBuilder sb = new StringBuilder();for(int i = k; i < nums.length; i++) {sb.append(nums[i]);}return sb.length() == 0 ? "0" : sb.toString();}
}

四、155. 最小栈

题目链接：https://leetcode.cn/problems/min-stack/description/
思路：求最小栈，要求为就是一个正常的栈先进后出，然后可以常数时间获取最小值，其实只需要维护两个栈，一个栈正常入栈出栈，另一个栈是最小值，当前元素小于栈顶时才入栈，否则把栈顶元素重复入栈。

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();}
}

五、32. 最长有效括号

题目链接：https://leetcode.cn/problems/longest-valid-parentheses/description/
思路：用栈来做，栈内记录括号的索引，遇到左括号索引入栈，遇到右括号，栈顶出栈，然后判断栈是否为空，为空右括号索引入栈，不为空记录最大值。

class Solution {public int longestValidParentheses(String s) {LinkedList<Integer> stack = new LinkedList<>();stack.push(-1);int max = 0;for(int i = 0; i < s.length(); i++) {if(s.charAt(i) == '(') {stack.push(i);}else{stack.pop();if(stack.isEmpty()) {stack.push(i);}else{max = Math.max(max, i - stack.peek());}}}return max;}
}