Leetcode

![https://leetcode.com/problems/min-stack/] Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) – Push element x onto stack. pop() – Removes the element on top of the stack. top() – Get the top element. getMin() – Retrieve the minimum element in the stack. Example 1: Input ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] Output [null,null,null,null,-3,null,0,-2] Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2 Constraints: ...

![https://leetcode.com/problems/basic-calculator-ii/] Given a string s which represents an expression, evaluate this expression and return its value. The integer division should truncate toward zero. Example 1: Input: s = "3+2*2" Output: 7 Example 2: Input: s = " 3/2 " Output: 1 Example 3: Input: s = " 3+5 / 2 " Output: 5 Constraints: 1 <= s.length <= 3 * 105 s consists of integers and operators (’+’, ‘-’, ‘*’, ‘/’) separated by some number of spaces. s represents a valid expression. All the integers in the expression are non-negative integers in the range [0, 231 - 1]. The answer is guaranteed to fit in a 32-bit integer. class Solution { public int calculate(String s) { var values = new int[s.length()]; var signs = new char[s.length()]; int valuesSize = 0; int signsSize = 0; char[] symbols = s.toCharArray(); for (int i = 0; i < symbols.length; i++) { char c = symbols[i]; if (c == ' ') { continue; } if (Character.isDigit(c)) { int j = i; int val = 0; while (j < symbols.length && Character.isDigit(symbols[j])) { val = (val * 10) + (symbols[j] - '0'); j++; } i = j - 1; if (signsSize > 0) { char op = signs[signsSize - 1]; if (op == '*' || op == '/') { signsSize--; int prev = values[valuesSize - 1]; valuesSize--; if (op == '*') { val = val * prev; } else { val = prev / val; } } } values[valuesSize++] = val; } else { signs[signsSize++] = c; } // System.out.println("signs = " + Arrays.toString(signs)); // System.out.println("values = " + Arrays.toString(values)); } int j = 0; int res = values[0]; for (int i = 0; i < valuesSize - 1; i++) { char op = signs[j++]; int a = values[i]; int b = values[i + 1]; res = (op == '+') ? a + b : a - b; values[i + 1] = res; } return res; } }

![https://leetcode.com/problems/backspace-string-compare/] Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character. Note that after backspacing an empty text, the text will continue empty. Example 1: Input: S = "ab#c", T = "ad#c" Output: true Explanation: Both S and T become "ac". Example 2: Input: S = "ab##", T = "c#d#" Output: true Explanation: Both S and T become "". Example 3: Input: S = "a##c", T = "#a#c" Output: true Explanation: Both S and T become "c". Example 4: Input: S = "a#c", T = "b" Output: false Explanation: S becomes "c" while T becomes "b". Note: ...

ou are keeping score for a baseball game with strange rules. The game consists of several rounds, where the scores of past rounds may affect future rounds’ scores. At the beginning of the game, you start with an empty record. You are given a list of strings ops, where ops[i] is the ith operation you must apply to the record and is one of the following: An integer x - Record a new score of x. “+” - Record a new score that is the sum of the previous two scores. It is guaranteed there will always be two previous scores. “D” - Record a new score that is double the previous score. It is guaranteed there will always be a previous score. “C” - Invalidate the previous score, removing it from the record. It is guaranteed there will always be a previous score. Return the sum of all the scores on the record. ...

![https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/] Given a string s of ‘(’ , ‘)’ and lowercase English characters. Your task is to remove the minimum number of parentheses ( ‘(’ or ‘)’, in any positions ) so that the resulting parentheses string is valid and return any valid string. Formally, a parentheses string is valid if and only if: It is the empty string, contains only lowercase characters, or It can be written as AB (A concatenated with B), where A and B are valid strings, or It can be written as (A), where A is a valid string. Example 1: Input: s = "lee(t(c)o)de)" Output: "lee(t(c)o)de" Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted. Example 2: Input: s = "a)b(c)d" Output: "ab(c)d" Example 3: Input: s = "))((" Output: "" Explanation: An empty string is also valid. Example 4: Input: s = "(a(b(c)d)" Output: "a(b(c)d)" Constraints: ...

![https://leetcode.com/problems/baseball-game/] You are keeping score for a baseball game with strange rules. The game consists of several rounds, where the scores of past rounds may affect future rounds’ scores. At the beginning of the game, you start with an empty record. You are given a list of strings ops, where ops[i] is the ith operation you must apply to the record and is one of the following: An integer x - Record a new score of x. “+” - Record a new score that is the sum of the previous two scores. It is guaranteed there will always be two previous scores. “D” - Record a new score that is double the previous score. It is guaranteed there will always be a previous score. “C” - Invalidate the previous score, removing it from the record. It is guaranteed there will always be a previous score. Return the sum of all the scores on the record. ...

![https://leetcode.com/problems/longest-consecutive-sequence/] Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. Example 1: Input: nums = [100,4,200,1,3,2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4. Example 2: Input: nums = [0,3,7,2,5,8,4,6,0,1] Output: 9 Constraints: 0 <= nums.length <= 104 -109 <= nums[i] <= 109 class Solution { public int longestConsecutive(int[] nums) { Map<Integer, Integer> valueToIndex = new HashMap<>(); UF uf = new UF(nums.length); for (int i = 0; i < nums.length; i++) { int value = nums[i]; if (valueToIndex.containsKey(value)) { continue; } if (valueToIndex.containsKey(value - 1)) { uf.union(i, valueToIndex.get(value - 1)); } if (valueToIndex.containsKey(value + 1)) { uf.union(i, valueToIndex.get(value + 1)); } valueToIndex.put(value, i); } return uf.maxSize; } static class UF { private int[] a; private int[] sz; private int maxSize = 0; UF(int n) { this.a = new int[n]; this.sz = new int[n]; for (int i = 0; i < n; i++) { a[i] = i; sz[i] = 1; maxSize = 1; } } void union(int p, int q) { int pid = find(p); int qid = find(q); if (sz[pid] > sz[qid]) { a[qid] = pid; sz[pid] += sz[qid]; maxSize = Math.max(maxSize, sz[pid]); } else { a[pid] = qid; sz[qid] += sz[pid]; maxSize = Math.max(maxSize, sz[qid]); } } int find(int p) { while (p != a[p]) { p = a[p]; } return p; } } }

![https://leetcode.com/problems/accounts-merge/] Given a list accounts, each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account. Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some email that is common to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name. ...

![https://leetcode.com/problems/smallest-string-with-swaps/] You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string. You can swap the characters at any pair of indices in the given pairs any number of times. Return the lexicographically smallest string that s can be changed to after using the swaps. Example 1: Input: s = "dcab", pairs = [[0,3],[1,2]] Output: "bacd" Explaination: Swap s[0] and s[3], s = "bcad" Swap s[1] and s[2], s = "bacd" Example 2: Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]] Output: "abcd" Explaination: Swap s[0] and s[3], s = "bcad" Swap s[0] and s[2], s = "acbd" Swap s[1] and s[2], s = "abcd" Example 3: Input: s = "cba", pairs = [[0,1],[1,2]] Output: "abc" Explaination: Swap s[0] and s[1], s = "bca" Swap s[1] and s[2], s = "bac" Swap s[0] and s[1], s = "abc" Constraints: ...

![https://leetcode.com/problems/is-graph-bipartite/] Given an undirected graph, return true if and only if it is bipartite. Recall that a graph is bipartite if we can split its set of nodes into two independent subsets A and B, such that every edge in the graph has one node in A and another node in B. The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn’t contain any element twice. ...