Swap Nodes in Pairs

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.

by lek tin in "algorithm" access_time 1-min read

Unique Paths

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?

by lek tin in "algorithm" access_time 2-min read

Valid Anagram

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)

by lek tin in "algorithm" access_time 2-min read

Ugly Number

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.

by lek tin in "algorithm" access_time 1-min read

Subsets

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.

by lek tin in "algorithm" access_time 2-min read

Roman to Integer

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.

by lek tin in "algorithm" access_time 2-min read

Single Number III

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.

by lek tin in "algorithm" access_time 1-min read

Single Number II

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

by lek tin in "algorithm" access_time 1-min read

Single Number

Given a non-empty array of integers, every element appears twice except for one. 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,1] Output: 1 Example 2 Input: [4,1,2,1,2] Output: 4 Solution // Java class Solution { public int singleNumber(int[] nums) { int result=0; for(int num : nums) { result=result^num; } return result; } } Solution class Solution: def singleNumber(self, nums: List[int]) -> int: singleNum = nums[0] for i in range(1, len(nums)): singleNum ^= nums[i] return singleNum

by lek tin in "algorithm" access_time 1-min read

Find Peak Element

A peak element is an element that is greater than its neighbors. Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that nums[-1] = nums[n] = -∞. Example 1 Input: nums = [1,2,3,1] Output: 2 Explanation: 3 is a peak element and your function should return the index number 2.

by lek tin in "algorithm" access_time 1-min read