Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1. Example 1 Input: [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1. Example 2 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.
Implement a basic calculator to evaluate a simple expression string. The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero. Example 1 Input: "3+2*2" Output: 7 Example 2 Input: " 3/2 " Output: 1 Example 3 Input: " 3+5 / 2 " Output: 5 Note You may assume that the given expression is always valid. Do not use the eval built-in library function.
Implement a basic calculator to evaluate a simple expression string. The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces . Example 1 Input: "1 + 1" Output: 2 Example 2 Input: " 2-1 + 2 " Output: 3 Example 3 Input: "(1+(4+5+2)-3)+(6+8)" Output: 23 Note You may assume that the given expression is always valid.
Solution (build string ❌) Time: O(N) Space: O(N) class Solution: def backspaceCompare(self, S: str, T: str) -> bool: res_1 = self.helper(S) res_2 = self.helper(T) return len(res_1) == len(res_2) and res_1 == res_2 def helper(self, s): stack = [] for c in s: if c != "#": stack.append(c) else: if len(stack) > 0: stack.pop() return "".join(stack) s Solution (two pointers 👍🏼) Time: O(N) Space: O(1) from itertools import zip_longest class Solution: def backspaceCompare(self, S: str, T: str) -> bool: return all( a == b for a, b in zip_longest(self.
Algorithm of Insertion Sort Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain. Example 1 Input: 4->2->1->3 Output: 1->2->3->4 Example 2 Input: -1->5->3->4->0 Output: -1->0->3->4->5 Solution # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.
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. 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.
Sort a linked list in O(n log n) time using constant space complexity. Example 1 Input: 4->2->1->3 Output: 1->2->3->4 Example 2 Input: -1->5->3->4->0 Output: -1->0->3->4->5 Solution (merge sort - top down) Time: O(NlogN) Space: O(logN) Doesn’t satisfy the requirement # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def sortList(self, head: ListNode) -> ListNode: if not head or not head.
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. Example 1 Input: [[1,1],[2,2],[3,3]] Output: 3 Explanation: ^ | | o | o | o +-------------> 0 1 2 3 4 Example 2 Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4 Explanation: ^ | | o | o o | o | o o +-------------------> 0 1 2 3 4 5 6 NOTE: input types have been changed on April 15, 2019.
Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed). Example 1 Input: nums = [ [9,9,4], [6,6,8], [2,1,1] ] Output: 4 Explanation: The longest increasing path is [1, 2, 6, 9]. Example 2 Input: nums = [ [3,4,5], [3,2,6], [2,2,1] ] Output: 4 Explanation: The longest increasing path is [3, 4, 5, 6].