LEETCODE SOLUTIONS

191 .  Number of 1 Bits Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the  Hamming weight ). Note: Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned. In Java, the compiler represents the signed integers using  2's complement notation . Therefore, in  Example 3 , the input represents the signed integer.  -3 .   Example 1: Input: n = 00000000000000000000000000001011 Output: 3 Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits. Example 2: Input: n = 00000000000000000000000010000000 Output: 1 Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit. Example 3: Input: n = 111111111...

  190 .  Reverse Bits Reverse bits of a given 32 bits unsigned integer. Note: Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned. In Java, the compiler represents the signed integers using  2's complement notation . Therefore, in  Example 2  above, the input represents the signed integer  -3  and the output represents the signed integer  -1073741825 .   Example 1: Input: n = 00000010100101000001111010011100 Output: 964176192 (00111001011110000010100101000000) Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000 . Example 2: Input: n = 11111111111111111111...

153 .  Find Minimum in Rotated Sorted Array   Suppose an array of length  n  sorted in ascending order is  rotated  between  1  and  n  times. For example, the array  nums = [0,1,2,4,5,6,7]  might become: [4,5,6,7,0,1,2]  if it was rotated  4  times. [0,1,2,4,5,6,7]  if it was rotated  7  times. Notice that  rotating  an array  [a[0], a[1], a[2], ..., a[n-1]]  1 time results in the array  [a[n-1], a[0], a[1], a[2], ..., a[n-2]] . Given the sorted rotated array  nums  of  unique  elements, return  the minimum element of this array . You must write an algorithm that runs in  O(log n) time.   Example 1: Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array was [1,2,3,4,5] rotated 3 times. Example 2: Input: nums = [4,5,6,7,0,1,2] Output: 0 Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times. Examp...

  152 .  Maximum Product Subarray Suppose an array of length  n  sorted in ascending order is  rotated  between  1  and  n  times. For example, the array  nums = [0,1,2,4,5,6,7]  might become: [4,5,6,7,0,1,2]  if it was rotated  4  times. [0,1,2,4,5,6,7]  if it was rotated  7  times. Notice that  rotating  an array  [a[0], a[1], a[2], ..., a[n-1]]  1 time results in the array  [a[n-1], a[0], a[1], a[2], ..., a[n-2]] . Given the sorted rotated array  nums  of  unique  elements, return  the minimum element of this array . You must write an algorithm that runs in  O(log n) time.   Example 1: Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array was [1,2,3,4,5] rotated 3 times. Example 2: Input: nums = [4,5,6,7,0,1,2] Output: 0 Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times. Example 3: Input:...

  143 .  Reorder List You are given the head of a singly linked-list. The list can be represented as: L 0 → L 1 → … → L n - 1 → L n Reorder the list to be on the following form: L 0 → L n → L 1 → L n - 1 → L 2 → L n - 2 → … You may not modify the values in the list's nodes. Only nodes themselves may be changed. Solution : class Solution: def reorderList(self, head: Optional[ListNode]) -> None: # searching middle s, f = head, head.next while f and f.next: s = s.next f = f.next.next # second half reversing sec = s.next prev = s.next = None while sec: temp = sec.next sec.next = prev prev = sec sec = temp # merging both fir, sec = head, prev while sec : t1, t2 = fir.next, sec.next fir.next = sec sec.next = t1 fir, sec = t1, t2 Explai...

  141 .  Linked List Cycle Given  head , the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the  next  pointer. Internally,  pos  is used to denote the index of the node that tail's  next  pointer is connected to.  Note that  pos  is not passed as a parameter . Return  true  if there is a cycle in the linked list . Otherwise, return  false . Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed). Solution : # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: s,f = head, head while f and f.n...

139 .  Word Break G iven a string   s   and a dictionary of strings   wordDict , return   true   if   s   can be segmented into a space-separated sequence of one or more dictionary words. Note  that the same word in the dictionary may be reused multiple times in the segmentation.   Example : Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code". class Solution: def wordBreak(self, s: str, wd: List[str]) -> bool: dp = [False] * (len(s)+1) dp[len(s)] = True for i in range(len(s)-1, -1, -1): for w in wd : if i + len(w) <=len(s) and s[i: i+ len(w)] == w: dp[i] = dp[i+len(w)] if dp[i]: break return dp[0] Explaination :