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.
Given a linked list, swap every two adjacent nodes and return its head. Example Given 1->2->3->4, you should return the list as 2->1->4->3. Note Your algorithm should use only constant extra space. You may not modify the values in the list’s nodes, only nodes itself may be changed. Solution # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def swapPairs(self, head): """ :type head: ListNode :rtype: ListNode """ # https://www.
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). How many possible unique paths are there? Above is a 7 x 3 grid. How many possible unique paths are there?
Given two strings s and t , write a function to determine if t is an anagram of s. Example 1: Input: s = "anagram", t = "nagaram" Output: true Example 2: Input: s = "rat", t = "car" Output: false Note You may assume the string contains only lowercase alphabets. Follow-up What if the inputs contain unicode characters? How would you adapt your solution to such case? Solution (using prime numbers) this approach is elegant but noted that if the strings are too long, the total sums maybe too big (overflow)
Write a program to check whether a given number is an ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. Example 1 Input: 6 Output: true Explanation: 6 = 2 × 3 Example 2 Input: 8 Output: true Explanation: 8 = 2 × 2 × 2 Example 3 Input: 14 Output: false Explanation: 14 is not ugly since it includes another prime factor 7. Note 1 is typically treated as an ugly number.
Given a set of distinct integers, nums, return all possible subsets (the power set). Note The solution set must not contain duplicate subsets. Example Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] Solution Time: O(n * 2^n) Space: O(n * 2^n) keep all the subsets of length N, since each of N elements could be present or absent. class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: results = [] subset = [] # Edge case 1 if nums == None: return results # Edge case 2 if len(nums) == 0: results.
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. For example: Given nums = [1, 2, 1, 3, 2, 5], return [3, 5]. Note The order of the result is not important. So in the above example, [5, 3] is also correct. Your algorithm should run in linear runtime complexity.
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one. Note Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? Example 1 Input: [2,2,3,2] Output: 3 Example 2 Input: [0,1,0,1,0,1,99] Output: 99 Solution class Solution: def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ # https://www.cnblogs.com/ganganloveu/p/4110996.html # https://blog.csdn.net/karen0310/article/details/78226261 ones, twos = 0, 0 for _, num in enumerate(nums): ones = (ones ^ num) & ~twos twos = (twos ^ num) & ~ones print(bin(num), "ones: ", bin(ones), "twos: ", bin(twos)) return ones