Find All Anagrams in a String Grumpy Bookstore Owner Add Two Numbers II Longest Consecutive Sequence Prison Cells After N Days
String to Integer (atoi) Contiguous Array Minimum Size Subarray Sum Consecutive Numbers Sum Sliding Puzzle
Beta
EQ-1 *
Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s. Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100. Input: s: "cbaebabacd" p: "abc" Output: [0, 6]
p_count,s_count = [0] * 26, [0] * 26 # build reference array using string p forch in p: p_count[ord(ch)- ord('a')] += 1
output = [] # sliding window on the string s fori in range(ns): # add one more letter # on the right side of the window s_count[ord(s[i])- ord('a')] += 1 # remove one letter # from the left side of the window ifi >= np: s_count[ord(s[i- np]) - ord('a')] -= 1 # compare array in the sliding window # with the reference array ifp_count == s_count: output.append(i- np + 1)
output = [] # sliding window on the string s fori in range(ns): # add one more letter # on the right side of the window s_count[s[i]]+= 1 # remove one letter # from the left side of the window ifi >= np: ifs_count[s[i - np]] == 1: dels_count[s[i - np]] else: s_count[s[i- np]] -= 1 # compare array in the sliding window # with the reference array ifp_count == s_count: output.append(i- np + 1)
returnoutput # sliding window on the string s # add one more letter on the right side of the window # remove one letter from the left side of the window # compare array in the sliding window with the reference array
EQ-2
Today, the bookstore owner has a store open for customers.length minutes. Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute. On some minutes, the bookstore owner is grumpy. If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0. When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied. The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once. Return the maximum number of customers that can be satisfied throughout the day. Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3 Output: 16
# 1052. Grumpy Bookstore Owner classSolution: def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int: n = len(customers) if not n: return 0
pre_sum1, pre_sum2 = [0], [0] for gru, cust in zip(grumpy, customers): if gru: pre_sum1.append(pre_sum1[-1]) pre_sum2.append(pre_sum2[-1] + cust) else: pre_sum1.append(pre_sum1[-1] + cust) pre_sum2.append(pre_sum2[-1])
max_sat, add_sat = -1, -1 for i in range(X, n+1): # print(i, i-X, pre_sum2[i], pre_sum2[i-X]) if pre_sum2[i] - pre_sum2[i-X] > max_sat: max_sat = pre_sum2[i] - pre_sum2[i-X] add_sat = i
return pre_sum1[-1] + max_sat
EQ-3
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 8 -> 0 -> 7
for c in str(total): prev.next = ListNode(int(c)) prev = prev.next
return dummy.next
defget_list_sum(self, head): sum = 0 current = head
whilecurrent: sum *= 10 sum += current.val current = current.next
return sum
EQ-4
Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Your algorithm should run in O(n) complexity. Input: [100, 4, 200, 1, 3, 2] Output: 4
There are 8 prison cells in a row, and each cell is either occupied or vacant. Each day, whether the cell is occupied or vacant changes according to the following rules:
If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
Otherwise, it becomes vacant. (Note that because the prison is a row, the first and the last cells in the row can’t have two adjacent neighbors.)
We describe the current state of the prison in the following way: cells[i] == 1 if the i-th cell is occupied, else cells[i] == 0. Given the initial state of the prison, return the state of the prison after N days (and N such changes described above.)
class Solution: defprisonAfterNDays(self,cells:List[int],N:int)->List[int]: N=(N-1)%14# It's a repeating pattern for every 14 days fordayinrange(N+1):# +1 to make sure it runs for atleast 1 cycle temp=[]# temp = [0]*8 temp.append(0)
class Solution1: defprisonAfterNDays(self,cells:List[int],N:int)->List[int]: seen={str(cells):N} while N: seen.setdefault(str(cells),N) N-=1 cells=[0]+[cells[i-1]^cells[i+1]^1foriinrange(1,7)]+[0] ifstr(cells)in seen: N%=seen[str(cells)]-N returncells
EQ-6
Implement atoi which converts a string to an integer. The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value. The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function. If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed. If no valid conversion could be performed, a zero value is returned.
Note: Only the space character ‘ ‘ is considered as whitespace character. Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead. Input: s = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: the subarray [4,3] has the minimal length under the problem constraint.
1 2 3 4 5 6 7 8 9 10 11 12 13
# 209. Minimum Size Subarray Sum
class Solution1: def minSubArrayLen(self, s:int, nums: List[int]) -> int: total = left = 0 result = len(nums) + 1 forright, n in enumerate(nums): total += n while total >= s: result = min(result, right - left + 1) total -= nums[left] left += 1 return result if result <= len(nums) else0
EQ-9
Given a positive integer N, how many ways can we write it as a sum of consecutive positive integers? Input: 15 Output: 4 Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
On a 2x3 board, there are 5 tiles represented by the integers 1 through 5, and an empty square represented by 0. A move consists of choosing 0 and a 4-directionally adjacent number and swapping it. The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]]. Given a puzzle board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.
classSolution: defslidingPuzzle(self, board: List[List[int]]) -> int: moves, used, cnt = {0: {1, 3}, 1:{0, 2, 4}, 2:{1, 5}, 3:{0, 4}, 4:{1, 3, 5}, 5:{2, 4}}, set(), 0 s = "".join(str(c) for row in board for c in row) q = [(s, s.index("0"))] while q: new = [] for s, i in q: used.add(s) if s == "123450": return cnt arr = [c for c in s] for move in moves[i]: new_arr = arr[:] new_arr[i], new_arr[move] = new_arr[move], new_arr[i] new_s = "".join(new_arr) ifnew_s not in used: new.append((new_s, move)) cnt += 1 q = new return-1