Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i]. Solve it without division and in O(n). For example, given [1,2,3,4], return [24,12,8,6]. Solution 1 Time: O(n) Space: O(n) class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: left, right = [nums[0]], [nums[-1]] N = len(nums) if N <= 1: return 0 res = [] for i in range(1, N-1): left.
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements. For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0]. Note You must do this in-place without making a copy of the array. Minimize the total number of operations. Credit Special thanks to @jianchao.
The count-and-say sequence is the sequence of integers with the first five terms as following: 1 11 21 1211 111221 1 is read off as "one 1" or 11. 11 is read off as "two 1s" or 21. 21 is read off as "one 2, then one 1" or 1211. Given an integer n where 1 ≤ n ≤ 30, generate the nthterm of the count-and-say sequence. Note: Each term of the sequence of integers will be represented as a string.
Implement strstr(). Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Example 1 Input: haystack = "hello", needle = "ll" Output: 2 Example 2 Input: haystack = "aaaaa", needle = "bba" Output: -1 Clarification What should we return when needle is an empty string? This is a great question to ask during an interview. For the purpose of this problem, we will return 0 when needle is an empty string.
Given a string containing just the characters ‘(', ‘)', ‘{', ‘}', ‘[’ and ‘]', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Note that an empty string is also considered valid. Example 1 Input: "()" Output: true Example 2 Input: "()[]{}" Output: true Example 3 Input: "(]" Output: false Example 4 Input: "([)]" Output: false Example 5 Input: "{[]}" Output: true Solution: class Solution { public boolean isValid(String s) { HashMap<Character, Character> charMap = new HashMap<>(); charMap.
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area. Example Input: 1 0 1 0 0 1 0 **1** **1** 1 1 1 **1** **1** 1 1 0 0 1 0 Output: 4 Solution class Solution: def maximalSquare(self, matrix): """ :type matrix: List[List[str]] :rtype: int """ area = 0 if not matrix: return area # Edge case: single col matrix for i in range(len(matrix)): if matrix[i][0] == "1": matrix[i][0] = 1 area = 1 # Edge case: single row matrix for i in range(len(matrix[0])): if matrix[0][i] == "1": matrix[0][i] = 1 area = 1 for i in range(1, len(matrix)): for j in range(1, len(matrix[0])): if matrix[i][j] == "0": matrix[i][j] = 0 continue localMin = min( int(matrix[i-1][j]), int(matrix[i-1][j-1]), int(matrix[i][j-1]) ) print(int(matrix[i-1][j]), int(matrix[i-1][j-1]), int(matrix[i][j-1])) matrix[i][j] = localMin + 1 if matrix[i][j] > area: area = matrix[i][j] return area**2 Java
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. Note: For the purpose of this problem, we define empty string as valid palindrome. Example 1 Input: "A man, a plan, a canal: Panama" Output: true Example 2 Input: "race a car" Output: false Solution class Solution: def isPalindrome(self, s): """ :type s: str :rtype: bool """ if not s: return True head = 0 tail = len(s) - 1 while head <= tail: cHead, cTail = s[head], s[tail] if not cHead.
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).” Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the : “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).” Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4] _______3______ / \ ___5__ ___1__ / \ / 6 _2 0 8 / 7 4
Given a sorted integer array without duplicates, return the summary of its ranges. Example 1 Input: [0,1,2,4,5,7] Output: ["0->2","4->5","7"] Explanation: 0,1,2 form a continuous range; 4,5 form a continuous range. Example 2 Input: [0,2,3,4,6,8,9] Output: ["0","2->4","6","8->9"] Explanation: 2,3,4 form a continuous range; 8,9 form a continuous range. Solution class Solution: def summaryRanges(self, nums): """ :type nums: List[int] :rtype: List[str] """ if not nums: return [] ranges = [str(nums[0])] for i in range(len(nums)-1): if nums[i+1] == nums[i] + 1: print(ranges) ranges[len(ranges)-1] = ranges[len(ranges)-1].