Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Example 1 Input: 1->2->3->3->4->4->5 Output: 1->2->5 Example 2 Input: 1->1->1->2->3 Output: 2->3
Remove all elements from a linked list of integers that have value val. Example Input: 1->2->6->3->4->5->6, val = 6 Output: 1->2->3->4->5 Solution # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def removeElements(self, head, val): """ :type head: ListNode :type val: int :rtype: ListNode """ pre = ListNode(0) pre.next = head pos = pre while pos.next != None: if pos.
Given n, how many structurally unique BST's (binary search trees) that store values 1 … n? Example Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 Exaplanation n = 3 root: 1 left: 0 right: 2 f(0)*f(2); root: 2 left: 1 right: 1 f(1)*f(1); root: 3 left: 2 right: 0 f(2)*f(0); Solution class Solution: def numTrees(self, n): """ :type n: int :rtype: int """ res = [1] for i in range(1, n+1): for j in range(i): res.
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree [1,2,2,3,4,4,3] is symmetric: 1 / \ 2 2 / \ / \ 3 4 4 3 But the following [1,2,2,null,3,null,3] is not: 1 / \ 2 2 \ \ 3 3 Note Bonus points if you could solve it both recursively and iteratively. Solution Resursive: # Definition for a binary tree node.
Given a non-empty array of integers, return the k most frequent elements. For example, Given [1,1,1,2,2,3] and k = 2, return [1,2]. Note You may assume k is always valid, 1 ≤ k ≤ number of unique elements. Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size. Solution class Solution: def topKFrequent(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ freqMap = dict() for num in nums: if freqMap.
Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value. Example 1: Input: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] Output: true Example 2: Input: 1 1 / \ 2 2 [1,2], [1,null,2] Output: false Example 3: Input: 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2] Output: false Solution # Definition for a binary tree node.
Given an array nums and a value val, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. The order of elements can be changed. It doesn’t matter what you leave beyond the new length. Example 1 Given nums = [3,2,2,3], val = 3, Your function should return length = 2, with the first two elements of nums being 2.
Given a sorted linked list, delete all duplicates such that each element appear only once. Example 1 Input: 1->1->2 Output: 1->2 Example 2 Input: 1->1->2->3->3 Output: 1->2->3 Solution # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def deleteDuplicates(self, head): """ :type head: ListNode :rtype: ListNode """ curr = head while curr != None and curr.next != None: if curr.
Given an integer, write a function to determine if it is a power of two. Example 1 Input: 1 Output: true Explanation: 2**0 = 1 Example 2 Input: 16 Output: true Explanation: 2**4 = 16 Example 3 Input: 218 Output: false Solution class Solution: def isPowerOfTwo(self, n): """ :type n: int :rtype: bool """ if n == 0: return False if n & (n - 1) == 0: return True return False
Given a non-empty array of digits representing a non-negative integer, plus one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself. Example 1 Input: [1,2,3] Output: [1,2,4] Explanation: The array represents the integer 123.