Ens

Given a string containing only three types of characters: ‘(’, ‘)’ and ‘*’, write a function to check whether this string is valid. We define the validity of a string by these rules: Any left parenthesis ‘(’ must have a corresponding right parenthesis ‘)’. Any right parenthesis ‘)’ must have a corresponding left parenthesis ‘(’. Left parenthesis ‘(’ must go before the corresponding right parenthesis ‘)’. ‘*’ could be treated as a single right parenthesis ‘)’ or a single left parenthesis ‘(’ or an empty string. An empty string is also valid. Example 1: ...

You are given a string s containing lowercase English letters, and a matrix shift, where shift[i] = [direction, amount]: direction can be 0 (for left shift) or 1 (for right shift). amount is the amount by which string s is to be shifted. A left shift by 1 means remove the first character of s and append it to the end. Similarly, a right shift by 1 means remove the last character of s and add it to the beginning. Return the final string after all operations. ...

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1. Example 1: 1 2 3 4 5 6 7 8 9 Input: [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1. Example 2: ```txt Input: [0,1,0] Output: 2 Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1. Note: The length of the given binary array will not exceed 50,000. ...

We have a collection of stones, each stone has a positive integer weight. Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is: If x == y, both stones are totally destroyed; If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x. At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.) ...

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. Example: Given a binary tree 1 2 3 4 5 1 / \ 2 3 / \ 4 5 Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3]. ...

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. 1 2 3 4 5 6 7 8 9 10 Example: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 class MinStack { private LinkedList<Node> stack = new LinkedList<>(); /* value, min -3, -3 0, -2 -2, -2 */ /** initialize your data structure here. */ public MinStack() { } public void push(int x) { Node node; if (stack.isEmpty()) { node = new Node(x, x); } else { int min = Math.min(x, stack.peekFirst().min); node = new Node(x, min); } stack.push(node); System.out.printf("val %d min %d\n", node.value, node.min); } public void pop() { Node pop = stack.pop(); System.out.printf("pop val %d min %d\n", pop.value, pop.min); } public int top() { return stack.peekFirst().value; } public int getMin() { Node first = stack.peekFirst(); System.out.printf("getMin val %d min %d\n", first.value, first.min); return first.min; } class Node { Node(int value, int min) { this.value= value; this.min = min; } int value; int min; } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character. 1 2 3 4 5 Example 1: Input: S = "ab#c", T = "ad#c" Output: true Explanation: Both S and T become "ac". 1 2 3 4 5 Example 2: Input: S = "ab##", T = "c#d#" Output: true Explanation: Both S and T become "". 1 2 3 4 5 Example 3: Input: S = "a##c", T = "#a#c" Output: true Explanation: Both S and T become "c". 1 2 3 4 5 Example 4: Input: S = "a#c", T = "b" Output: false Explanation: S becomes "c" while T becomes "b". Note: ...

Middle of the Linked List

Given a non-empty, singly linked list with head node head, return a middle node of linked list. If there are two middle nodes, return the second middle node. 1 2 3 4 5 6 7 Example 1: Input: [1,2,3,4,5] Output: Node 3 from this list (Serialization: [3,4,5]) The returned node has value 3. (The judge's serialization of this node is [3,4,5]). Note that we returned a ListNode object ans, such that: ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL. 1 2 3 4 5 Example 2: Input: [1,2,3,4,5,6] Output: Node 4 from this list (Serialization: [4,5,6]) Since the list has two middle nodes with values 3 and 4, we return the second one. Note: ...

archives