Implement a Queue using two Stacks – C# Solution
This problem is the opposite of implementing stacks using two queues. Aim is to construct a queue data structure using only the two stacks in C#.
Implement a Queue using two Stacks – Python Solution
This problem is the opposite of implementing stacks using two queues. Aim is to construct a queue data structure using only the two stacks in Python
Implement a Queue using two Stacks – Java Solution
This problem is the opposite of implementing stacks using two queues. Aim is to construct a queue data structure using only the two stacks.
Convert a Singly Linked List to Circular Linked List – Python Solution
To convert a singly linked list to circular linked list, we will set next pointer of tail node to head pointer. Create a copy of head pointer (temp). Traverse the […]
Longest Continuous Increasing Subsequence – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Longest Continuous Increasing Subsequence - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution {
public int findLengthOfLCIS(int[] nums) {
if (nums.length == 0) return 0;
int curr = 1, ans = 1;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] < nums[i + 1]) {
curr ++;
if (curr >= ans) ans = curr;
} else {
curr = 1;
}
}
return ans;
}
}
Convert BST to Greater Tree – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Convert BST to Greater Tree - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# https://leetcode.com/problems/convert-bst-to-greater-tree/solution/
# def __init__(self):
# self.total = 0
# def convertBST(self, root):
# if root is not None:
# self.convertBST(root.right)
# self.total += root.val
# root.val = self.total
# self.convertBST(root.left)
# return root
def convertBST(self, root):
total = 0
node = root
stack = []
while stack or node is not None:
# push all nodes up to (and including) this subtree's maximum on
# the stack.
while node is not None:
stack.append(node)
node = node.right
node = stack.pop()
total += node.val
node.val = total
# all nodes with values between the current and its parent lie in
# the left subtree.
node = node.left
return root
Transpose Matrix – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Transpose Matrix - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def transpose(self, A):
"""
:type A: List[List[int]]
:rtype: List[List[int]]
"""
R, C = len(A), len(A[0])
ans = [[None] * R for _ in xrange(C)]
for r, row in enumerate(A):
for c, val in enumerate(row):
ans[c][r] = val
return ans
# Alternative Solution:
# return zip(*A)
# def transpose(self, A):
# res = []
# for i in range(len(A[0])):
# temp = []
# for j in range(len(A)):
# temp.append(A[j][i])
# res.append(temp)
# return res
Fibonacci Number – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Fibonacci Number - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution {
/*public int fib(int N) {
// Recursively, O(n)
if (N == 0) return 0;
if (N == 1) return 1;
return fib(N - 1) + fib(N - 2);
}*/
private List memo;
public Solution() {
memo = new ArrayList();
memo.add(0);
memo.add(1);
}
public int fib(int N) {
// Dp with memo, O(n)
if (N < memo.size()) return memo.get(N);
for (int i = memo.size(); i <= N; i++) {
memo.add(memo.get(i - 1) + memo.get(i - 2));
}
return memo.get(N);
}
}
Path Sum III – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Path Sum III - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# https://leetcode.com/problems/path-sum-iii/discuss/91892/Python-solution-with-detailed-explanation
class Solution(object):
# def find_paths(self, root, target):
# if root:
# return int(root.val == target)
# + self.find_paths(root.left, target - root.val)
# + self.find_paths(root.right, target - root.val)
# return 0
# def pathSum(self, root, sum):
# """
# :type root: TreeNode
# :type sum: int
# :rtype: int
# """
# if root:
# return self.find_paths(root, sum)
# + self.pathSum(root.left, sum)
# + self.pathSum(root.right, sum)
# return 0
def pathSumHelper(self, root, target, so_far, cache):
if root:
# complement == 1, root->curr path
complement = so_far + root.val - target
if complement in cache:
# S->E path, sum(root->S)-sum(root->E) = target
self.result += cache[complement]
cache[so_far + root.val] = cache.get(so_far + root.val, 0) + 1
self.pathSumHelper(root.left, target, so_far + root.val, cache)
self.pathSumHelper(root.right, target, so_far + root.val, cache)
cache[so_far + root.val] -= 1
return
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
self.result = 0
self.pathSumHelper(root, sum, 0, {0: 1})
return self.result
Longest Substring with At Most K Distinct Characters – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Longest Substring with At Most K Distinct Characters - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def lengthOfLongestSubstringKDistinct(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
count = [0] * 256
i, numDistinct, maxLen = 0, 0, 0
for j in range(len(s)):
# udpate j
if count[ord(s[j])] == 0:
numDistinct += 1
count[ord(s[j])] += 1
# udpate i
while numDistinct > k:
count[ord(s[i])] -= 1
if count[ord(s[i])] == 0:
numDistinct -= 1
i += 1
maxLen = max(j - i + 1, maxLen)
return maxLen
Diameter of Binary Tree – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Diameter of Binary Tree - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution {
// https://leetcode.com/problems/diameter-of-binary-tree/solution/
int ans;
public int diameterOfBinaryTree(TreeNode root) {
ans = 1;
depth(root);
return ans - 1;
}
public int depth(TreeNode node) {
if (node == null) return 0;
int L = depth(node.left);
int R = depth(node.right);
ans = Math.max(ans, L+R+1);
return Math.max(L, R) + 1;
}
}
Convert a Number to Hexadecimal – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Convert a Number to Hexadecimal - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def toHex(self, num):
"""
:type num: int
:rtype: str
"""
if num == 0:
return '0'
# letter map
mp = '0123456789abcdef'
ans = ''
for _ in range(8):
# get last 4 digits
# num & 1111b
n = num & 15
# hex letter for current 1111
c = mp[n]
ans = c + ans
# num = num / 16
num = num >> 4
#strip leading zeroes
return ans.lstrip('0')
# def toHex(self, num):
# def tohex(val, nbits):
# return hex((val + (1 << nbits)) % (1 << nbits))
# return tohex(num, 32)[2:]
# def toHex(self, num, h=''):
# return (not num or h[7:]) and h or self.toHex(num / 16, '0123456789abcdef'[num % 16] + h)
Unique Email Addresses – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Unique Email Addresses - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def numUniqueEmails(self, emails):
"""
:type emails: List[str]
:rtype: int
"""
email_set = set()
for email in emails:
elements = email.split('@')
email_set.add(elements[0].split('+')[0].replace('.', '') + elements[1])
return len(email_set)
N-Repeated Element in Size 2N Array – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - N-Repeated Element in Size 2N Array - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution {
public int repeatedNTimes(int[] A) {
HashMap hash = new HashMap<>();
int ans = A[0];
for (int n: A) {
int count = hash.getOrDefault(n, 0) + 1;
hash.put(n, count);
if (count >= hash.get(ans)) ans = n;
}
return ans;
}
}
Add Strings – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Add Strings - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# def addStrings(self, num1, num2):
# """
# :type num1: str
# :type num2: str
# :rtype: str
# """
# if num1 is None:
# num1 = '0'
# if num2 is None:
# num2 = '0'
# res = []
# carry = 0
# ls = min(len(num1), len(num2))
# pos = -1
# while pos + ls >= 0:
# curr = int(num1[pos]) + int(num2[pos]) + carry
# res.insert(0, str(curr % 10))
# carry = curr / 10
# pos -= 1
# while pos + len(num1) >= 0:
# curr = int(num1[pos]) + carry
# res.insert(0, str(curr % 10))
# carry = curr / 10
# pos -= 1
# while pos + len(num2) >= 0:
# curr = int(num2[pos]) + carry
# res.insert(0, str(curr % 10))
# carry = curr / 10
# pos -= 1
# if carry != 0:
# res.insert(0, str(carry))
# return ''.join(res)
def addStrings(self, num1, num2):
res = []
pos1 = len(num1) - 1
pos2 = len(num2) - 1
carry = 0
# This conditon is great
# https://leetcode.com/problems/add-strings/discuss/90436/Straightforward-Java-8-main-lines-25ms
while pos1 >= 0 or pos2 >= 0 or carry == 1:
digit1 = digit2 = 0
if pos1 >= 0:
digit1 = ord(num1[pos1]) - ord('0')
if pos2 >= 0:
digit2 = ord(num2[pos2]) - ord('0')
res.append(str((digit1 + digit2 + carry) % 10))
carry = (digit1 + digit2 + carry) / 10
pos1 -= 1
pos2 -= 1
# reverse res
return ''.join(res[::-1])
Friend Circles – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Friend Circles - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def findCircleNum(self, M):
"""
:type M: List[List[int]]
:rtype: int
"""
# because
visited = [0] * len(M)
count = 0
for i in range(len(M)):
if visited[i] == 0:
self.dfs(M, visited, i)
count += 1
return count
def dfs(self, M, visited, i):
for j in range(len(M)):
if M[i][j] == 1 and visited[j] == 0:
visited[j] = 1
self.dfs(M, visited, j)
# def findCircleNum(self, M):
# # BFS
# visited = [0] * len(M)
# count = 0
# queue = []
# for i in range(len(M)):
# if visited[i] == 0:
# queue.append(i)
# while queue:
# curr = queue.pop(0)
# visited[curr] = 1
# for j in range(len(M)):
# if M[curr][j] == 1 and visited[j] == 0:
# queue.append(j)
# count += 1
# return count
# def findCircleNum(self, M):
# # Union Find
# union = Union()
# for i in range(len(M)):
# union.add(i)
# for i in range(len(M)):
# for j in range(i + 1, len(M)):
# if M[i][j] == 1:
# union.union(i, j)
# return union.count
# class Union(object):
# """
# weighted quick union find
# """
# def __init__(self):
# # both dic and list is fine
# self.id = {}
# self.sz = {}
# self.count = 0
# def count(self):
# return self.count
# def connected(self, p, q):
# return self.find(p) == self.find(q)
# def add(self, p):
# # init
# self.id[p] = p
# self.sz[p] = 1
# self.count += 1
# def find(self, p):
# """
# find root of p, and compress path
# """
# while p != self.id[p]:
# self.id[p] = self.id[self.id[p]]
# p = self.id[p]
# return p
# def union(self, p, q):
# """
# connect p and q
# """
# i, j = self.find(p), self.find(q)
# if i == j:
# return
# if self.sz[i] > self.sz[j]:
# i, j = j, i
# self.id[i] = j
# self.sz[j] += self.sz[i]
# self.count -= 1
Maximum Product of Three Numbers – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Maximum Product of Three Numbers - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# def maximumProduct(self, nums):
# """
# :type nums: List[int]
# :rtype: int
# """
# nums.sort()
# # Check min1*min2*max1 and max1*max2*max3
# return max(reduce(lambda x, y: x * y, nums[:2]) * nums[-1],
# reduce(lambda x, y: x * y, nums[-3:]))
def maximumProduct(self, nums):
min1 = min2 = float('inf')
max1 = max2 = max3 = float('-inf')
for num in nums:
if num <= min1:
min2 = min1
min1 = num
elif num <= min2:
min2 = num
if num >= max1:
max3 = max2
max2 = max1
max1 = num
elif num >= max2:
max3 = max2
max2 = num
elif num >= max3:
max3 = num
return max(min1 * min2 * max1, max1 * max2 * max3)
Find All Anagrams in a String – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Find All Anagrams in a String - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
res = []
if s is None or p is None or len(s) == 0 or len(p) == 0:
return res
char_map = [0] * 256
for c in p:
char_map[ord(c)] += 1
left, right, count = 0, 0, len(p)
while right < len(s):
if char_map[ord(s[right])] >= 1:
count -= 1
char_map[ord(s[right])] -= 1
right += 1
if count == 0:
res.append(left)
if right - left == len(p):
if char_map[ord(s[left])] >= 0:
count += 1
char_map[ord(s[left])] += 1
left += 1
return res
# def findAnagrams(self, s, p):
# if len(s) < len(p):
# return []
# res = []
# p_len = len(p)
# bit_map = []
# for _ in range(26):
# bit_map.append(0)
# for c in p:
# bit_map[ord(c) - ord('a')] += 1
# s_p = str(bit_map)
# for i in range(26):
# bit_map[i] = 0
# for i in range(p_len - 1):
# bit_map[ord(s[i]) - ord('a')] += 1
# for i in range(p_len - 1, len(s)):
# bit_map[ord(s[i]) - ord('a')] += 1
# if i - p_len >= 0:
# bit_map[ord(s[i - p_len]) - ord('a')] -= 1
# if str(bit_map) == s_p:
# res.append(i - p_len + 1)
# return res
# def findAnagrams(self, s, p):
# """
# :type s: str
# :type p: str
# :rtype: List[int]
# """
# res = []
# pCounter = collections.Counter(p)
# sCounter = collections.Counter(s[:len(p)-1])
# for i in range(len(p)-1,len(s)):
# sCounter[s[i]] += 1 # include a new char in the char_map
# if sCounter == pCounter: # This step is O(1), since there are at most 26 English letters
# res.append(i-len(p)+1) # append the starting index
# sCounter[s[i-len(p)+1]] -= 1 # decrease the count of oldest char in the window
# if sCounter[s[i-len(p)+1]] == 0:
# del sCounter[s[i-len(p)+1]] # remove the count if it is 0
# return res
Find Pivot Index – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Find Pivot Index - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def pivotIndex(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
totalsum = sum(nums)
leftsum = 0
for i, v in enumerate(nums):
# leftsum == rightsum
if leftsum == totalsum - leftsum - v:
return i
leftsum += v
return -1
Reorder Log Files – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Reorder Log Files - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
import java.util.List;
class Solution {
public String[] reorderLogFiles(String[] logs) {
Arrays.sort(logs, (log1, log2) -> {
String[] split1 = log1.split(" ", 2);
String[] split2 = log2.split(" ", 2);
boolean isDigit1 = Character.isDigit(split1[1].charAt(0));
boolean isDigit2 = Character.isDigit(split2[1].charAt(0));
if (!isDigit1 && !isDigit2) {
int cmp = split1[1].compareTo(split2[1]);
if (cmp != 0) return cmp;
return split1[0].compareTo(split2[0]);
}
return isDigit1 ? (isDigit2 ? 0 : 1) : -1;
});
return logs;
}
}
K Closest Points to Origin – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - K Closest Points to Origin - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# def kClosest(self, points, K):
# """
# :type points: List[List[int]]
# :type K: int
# :rtype: List[List[int]]
# """
# # Sort
# return sorted(points, key=lambda x: x[0] ** 2 + x[1] ** 2)[:K]
def kClosest(self, points, K):
# K smallest heaq
return heapq.nsmallest(K, points, key=lambda x: x[0] ** 2 + x[1] ** 2)
Reverse Words in a String III – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Reverse Words in a String III - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
public class Solution {
public String reverseWords(String s) {
String words[] = s.split(" ");
StringBuilder ans = new StringBuilder();
for (String word: words)
ans.append(new StringBuffer(word).reverse().toString() + " ");
return ans.toString().trim();
}
}
Find All Numbers Disappeared in an Array – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Find All Numbers Disappeared in an Array - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def findDisappearedNumbers(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
# https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/discuss/92956/Java-accepted-simple-solution
res = []
if nums:
n = len(nums)
for i in range(n):
val = abs(nums[i]) - 1
if nums[val] > 0:
nums[val] = -nums[val]
for i in range(n):
if nums[i] > 0:
res.append(i + 1)
return res
Backspace String Compare – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Backspace String Compare - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution {
/*public boolean backspaceCompare(String S, String T) {
// https://leetcode.com/problems/backspace-string-compare/discuss/135603/C%2B%2BJavaPython-O(N)-time-and-O(1)-space
int i = S.length() - 1, j = T.length() - 1;
while (true) {
for (int back = 0; i >= 0 && (back > 0 || S.charAt(i) == '#'); --i)
back += S.charAt(i) == '#' ? 1 : -1;
for (int back = 0; j >= 0 && (back > 0 || T.charAt(j) == '#'); --j)
back += T.charAt(j) == '#' ? 1 : -1;
if (i >= 0 && j >= 0 && S.charAt(i) == T.charAt(j)) {
i--; j--;
} else
return i == -1 && j == -1;
}
}*/
public boolean backspaceCompare(String S, String T) {
return trans(S).equals(trans(T));
}
private String trans(String str) {
StringBuilder sb = new StringBuilder();
for (char c : str.toCharArray()) {
if (c != '#') { sb.append(c); } // if not '#', append it at the end of sb.
else if (sb.length() > 0) { sb.deleteCharAt(sb.length() - 1); } // remove last char in sb, if sb is not empty.
}
return sb.toString();
}
}
Count Primes – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Count Primes - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
# https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity
isPrime = [True] * n
for i in xrange(2, n):
if i * i >= n:
break
if not isPrime[i]:
continue
for j in xrange(i * i, n, i):
isPrime[j] = False
count = 0
for i in xrange(2, n):
if isPrime[i]:
count += 1
return count
Search Insert Position – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Search Insert Position - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution:
# def searchInsert(self, nums, target):
# """
# :type nums: List[int]
# :type target: int
# :rtype: int
# """
# min, pos = 0, 0
# max = len(nums) - 1
# while min <= max:
# # binary search
# pos = (max + min) / 2
# if nums[pos] == target:
# return pos
# elif nums[pos] > target:
# max = pos - 1
# else:
# min = pos + 1
# if min > pos:
# # this means that target is great than pos, and target
# # is not in nums
# return pos + 1
# return pos
def searchInsert(self, nums, target):
l, r = int(0), len(nums) - 1
while l < r:
mid = int((l + r) / 2)
if nums[mid] < target:
l = mid + 1
else:
r = mid
if nums[l] < target:
return l + 1
return l
if __name__ == '__main__':
# begin
s = Solution()
print (s.searchInsert([1,3,5,6],5))
Convert a Number to Hexadecimal – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Convert a Number to Hexadecimal - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
import com.sun.corba.se.spi.orbutil.fsm.Guard.Result;
class Solution {
public String toHex(int num) {
String hex_map = "0123456789abcdef";
if (num == 0) return "0";
String res = "";
// To avoid infinite loop caused by negative num
while (num != 0 && res.length() < 8) {
res = hex_map.charAt(num & 15) + res;
num = num >> 4;
}
return res;
}
/* public String toHex(int num) {
String hex = Integer.toHexString(num);
return hex;
} */
}
Valid Palindrome – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Valid Palindrome - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
alnum_s = [t.lower() for t in s if t.isalnum()]
ls = len(alnum_s)
if ls <= 1:
return True
mid = ls / 2
for i in range(mid):
if alnum_s[i] != alnum_s[ls - 1 - i]:
return False
return True
Poor Pigs – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Poor Pigs - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution {
public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
int n = minutesToTest / minutesToDie + 1;
int pigs = 0;
while (Math.pow(n, pigs) < buckets) pigs++;
return pigs;
}
}
Unique Paths II – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Unique Paths II - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# def uniquePathsWithObstacles(self, obstacleGrid):
# """
# :type obstacleGrid: List[List[int]]
# :rtype: int
# """
# m, n = len(obstacleGrid), len(obstacleGrid[0])
# dmap = [[0] * n for _ in range(m)]
# for i in range(m):
# if obstacleGrid[i][0] != 1:
# dmap[i][0] = 1
# else:
# break
# for j in range(n):
# if obstacleGrid[0][j] != 1:
# dmap[0][j] = 1
# else:
# break
# for i in range(1, m):
# for j in range(1, n):
# if obstacleGrid[i][j] == 1:
# continue
# l = u = 0
# if i - 1 >= 0:
# u = dmap[i - 1][j]
# if j - 1 >= 0:
# l = dmap[i][j - 1]
# dmap[i][j] = l + u
# return dmap[m - 1][n - 1]
def uniquePathsWithObstacles(self, obstacleGrid):
m, n = len(obstacleGrid), len(obstacleGrid[0])
if m == 0:
return 0
dmap = [[0] * (n + 1) for _ in range(m + 1)]
dmap[m - 1][n] = 1
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
if obstacleGrid[i][j] == 1:
dmap[i][j] = 0
else:
dmap[i][j] = dmap[i][j + 1] + dmap[i + 1][j]
return dmap[0][0]
Min Stack – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Min Stack - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
import java.util.ArrayList;
import java.util.List;
/* class MinStack {
private Stack stack;
private Stack minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int x) {
stack.push(x);
if (minStack.size() == 0 || x <= minStack.peek()) minStack.push(x);
}
public void pop() {
if (stack.size() > 0) {
int curr = stack.pop();
if (minStack.size() > 0 && curr == minStack.peek()) minStack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
if (minStack.size() > 0)
return minStack.peek();
else
return stack.peek();
}
} */
class MinStack {
private Stack stack;
private Stack minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int x) {
stack.push(x);
if (minStack.size() == 0 || x <= minStack.peek()) minStack.push(x);
else minStack.push(minStack.peek());
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
Min Stack – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Min Stack - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
# class MinStack(object):
# def __init__(self):
# """
# initialize your data structure here.
# """
# self.stack = []
# self.min_stack = []
# def push(self, x):
# """
# :type x: int
# :rtype: nothing
# """
# self.stack.append(x)
# if len(self.min_stack) == 0 or x <= self.min_stack[-1]:
# self.min_stack.append(x)
# def pop(self):
# """
# :rtype: nothing
# """
# if len(self.stack) > 0:
# last = self.stack[-1]
# # Need to check whether pop minStack
# if len(self.min_stack) > 0 and last == self.min_stack[-1]:
# self.min_stack.pop()
# self.stack.pop()
# def top(self):
# """
# :rtype: int
# """
# if len(self.stack) > 0:
# return self.stack[-1]
# return None
# def getMin(self):
# """
# :rtype: int
# """
# if len(self.min_stack) > 0:
# return self.min_stack[-1]
# else:
# if len(self.stack) > 0:
# return self.stack[-1]
# return None
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.min_stack = []
def push(self, x):
"""
:type x: int
:rtype: nothing
"""
self.stack.append(x)
if len(self.min_stack) == 0:
self.min_stack.append(x)
return
if x <= self.min_stack[-1]:
self.min_stack.append(x)
else:
# Push top of min stack again
self.min_stack.append(self.min_stack[-1])
def pop(self):
"""
:rtype: nothing
"""
if len(self.stack) > 0:
# Much simple than solution 1
# But use more space
self.min_stack.pop()
self.stack.pop()
def top(self):
"""
:rtype: int
"""
if len(self.stack) > 0:
return self.stack[-1]
return None
def getMin(self):
"""
:rtype: int
"""
if len(self.min_stack) > 0:
return self.min_stack[-1]
return None
Linked List Cycle – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Linked List Cycle - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
# def hasCycle(self, head):
# """
# :type head: ListNode
# :rtype: bool
# """
# # Add max and check if reach max
# if head is None:
# return False
# count = 0
# max = 100000
# pos = head
# while pos is not None:
# count += 1
# pos = pos.next
# if count > max:
# return True
# return False
# def hasCycle(self, head):
# # Hash or set
# dic = {}
# pos = head
# while pos is not None:
# try:
# dic[pos]
# return True
# except KeyError:
# dic[pos] = pos
# pos = pos.next
# return False
def hasCycle(self, head):
# Two points
try:
fast = head.next.next
slow = head.next
while fast != slow:
fast = fast.next.next
slow = slow.next
return True
except:
return False
Binary Gap – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Binary Gap - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution:
# def binaryGap(self, n: int) -> int:
# # Store index
# A = [i for i in xrange(32) if (N >> i) & 1]
# if len(A) < 2: return 0
# return max(A[i+1] - A[i] for i in xrange(len(A) - 1))
def binaryGap(self, n: int) -> int:
# one pass and store max
current = 1
last1 = -1
out = 0
while n > 0:
if n % 2 == 1:
if last1 >= 1:
out = max(out, current - last1)
last1 = current
current += 1
n = n // 2
return out
# def binaryGap(self, n: int) -> int:
# # one pass and store max
# res = 0
# last = -1
# # Get binary encoding with bin
# for i, curr in enumerate(bin(n)[2:]):
# if curr == '1':
# if last >= 0:
# res = max(res, i - last)
# last = i
# return res
Evaluate Reverse Polish Notation – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Evaluate Reverse Polish Notation - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def evalRPN(self, tokens):
"""
:type tokens: List[str]
:rtype: int
"""
stack = []
for t in tokens:
try:
temp = int(t)
stack.append(temp)
except:
b = stack.pop()
a = stack.pop()
if t == "+":
a += b
elif t == "-":
a -= b
elif t == "*":
a *= b
else:
a = int(a * 1.0 / b)
stack.append(a)
return stack[-1]
Maximum 69 Number – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Maximum 69 Number - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution {
public int maximum69Number (int num) {
// Replace first 6 with 9 if exists
return Integer.valueOf(String.valueOf(num).replaceFirst("6", "9"));
}
/*
public int maximum69Number (int num) {
char[] chars = Integer.toString(num).toCharArray();
// Replace first 6 with 9 if exists
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '6') {
chars[i] = '9';
break;
}
}
return Integer.parseInt(new String(chars));
}*/
}
Top K Frequent Words – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Top K Frequent Words - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# def topKFrequent(self, words, k):
# """
# :type words: List[str]
# :type k: int
# :rtype: List[str]
# """
# counter = collections.Counter(words)
# res = sorted(counter.items(), cmp=cmp_frequency, reverse=True)
# return [k for k, _ in res[:k]]
# def cmp_frequency(x, y):
# if x[1] != y[1]:
# return cmp(x[1], y[1])
# return cmp(y[0], x[0])
# def topKFrequent(self, words, k):
# count = collections.Counter(words)
# candidates = count.keys()
# candidates.sort(key = lambda w: (-count[w], w))
# return candidates[:k]
def topKFrequent(self, words, k):
count = collections.Counter(words)
# Note that python heapq only support min heap
# So, we can make the value negative to create a max heap
heap = [(-freq, word) for word, freq in count.items()]
heapq.heapify(heap)
return [heapq.heappop(heap)[1] for _ in xrange(k)]
Edit Distance – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Edit Distance - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# https://discuss.leetcode.com/topic/17639/20ms-detailed-explained-c-solutions-o-n-space/2
# def minDistance(self, word1, word2):
# """
# :type word1: str
# :type word2: str
# :rtype: int
# """
# ls_1, ls_2 = len(word1), len(word2)
# dp = [[0] * (ls_2 + 1) for _ in range(ls_1 + 1)]
# for i in range(1, ls_1 + 1):
# dp[i][0] = i
# for j in range(1, ls_2 + 1):
# dp[0][j] = j
# for i in range(1, ls_1 + 1):
# for j in range(1, ls_2 + 1):
# if word1[i - 1] == word2[j - 1]:
# dp[i][j] = dp[i - 1][j - 1]
# else:
# dp[i][j] = min(dp[i - 1][j - 1] + 1,
# dp[i][j - 1] + 1,
# dp[i - 1][j] + 1)
# return dp[ls_1][ls_2]
def minDistance(self, word1, word2):
ls_1, ls_2 = len(word1), len(word2)
dp = list(range(ls_1 + 1))
for j in range(1, ls_2 + 1):
pre = dp[0]
dp[0] = j
for i in range(1, ls_1 + 1):
temp = dp[i]
if word1[i - 1] == word2[j - 1]:
dp[i] = pre
else:
dp[i] = min(pre + 1, dp[i] + 1, dp[i - 1] + 1)
pre = temp
return dp[ls_1]
if __name__ == '__main__':
# begin
s = Solution()
print (s.minDistance("horse","ros"))
print (s.minDistance("intention","execution"))
Logger Rate Limiter – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Logger Rate Limiter - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
# class Logger(object):
# def __init__(self):
# """
# Initialize your data structure here.
# """
# self.timestamps = {}
# def shouldPrintMessage(self, timestamp, message):
# """
# Returns true if the message should be printed in the given timestamp, otherwise returns false.
# If this method returns false, the message will not be printed.
# The timestamp is in seconds granularity.
# :type timestamp: int
# :type message: str
# :rtype: bool
# """
# if timestamp < self.timestamps.get(message, 0):
# return False
# self.timestamps[message] = timestamp + 10
# return True
import heapq
class Logger(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.heap = []
self.cache = {}
def shouldPrintMessage(self, timestamp, message):
"""
Returns true if the message should be printed in the given timestamp, otherwise returns false.
If this method returns false, the message will not be printed.
The timestamp is in seconds granularity.
:type timestamp: int
:type message: str
:rtype: bool
"""
while len(self.heap):
if self.heap[0][0] <= timestamp:
temp = heapq.heappop(self.heap)
self.cache.pop(temp[1])
else:
break
if timestamp < self.cache.get(message, 0):
return False
self.cache[message] = timestamp + 10
heapq.heappush(self.heap, (timestamp + 10, message))
return True
# Your Logger object will be instantiated and called as such:
# obj = Logger()
# param_1 = obj.shouldPrintMessage(timestamp,message)
Longest Consecutive Sequence – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Longest Consecutive Sequence - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def longestConsecutive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
def longestConsecutive(self, num):
# Pop adjacency O(n) and O(n)
num = set(num)
maxLen = 0
while num:
n = num.pop()
i = n + 1
l1 = 0
l2 = 0
while i in num:
num.remove(i)
i += 1
l1 += 1
i = n - 1
while i in num:
num.remove(i)
i -= 1
l2 += 1
maxLen = max(maxLen, l1 + l2 + 1)
return maxLen
Convert Sorted Array to Binary Search Tree – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Convert Sorted Array to Binary Search Tree - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
# def sortedArrayToBST(self, nums):
# """
# :type nums: List[int]
# :rtype: TreeNode
# """
# # Recursion with slicing
# if not nums:
# return None
# mid = len(nums) / 2
# root = TreeNode(nums[mid])
# root.left = self.sortedArrayToBST(nums[:mid])
# root.right = self.sortedArrayToBST(nums[mid + 1:])
# return root
def sortedArrayToBST(self, nums):
# Recursion with index
return self.getHelper(nums, 0, len(nums) - 1)
def getHelper(self, nums, start, end):
if start > end:
return None
mid = (start + end) / 2
node = TreeNode(nums[mid])
node.left = self.getHelper(nums, start, mid - 1)
node.right = self.getHelper(nums, mid + 1, end)
return node
Two Sum II – Input array is sorted – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Two Sum II - Input array is sorted - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
# Two Points
begin, end = 0, len(numbers) - 1
while begin < end:
curr = numbers[begin] + numbers[end]
if curr == target:
return [begin + 1, end + 1]
elif curr < target:
begin += 1
else:
end -= 1
Product of Array Except Self – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Product of Array Except Self - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
public class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] res = new int[n];
res[0] = 1;
for (int i = 1; i < n; i++) {
// left part
res[i] = res[i - 1] * nums[i - 1];
}
int right = 1;
for (int i = n - 1; i >= 0; i--) {
res[i] *= right;
// right part
right *= nums[i];
}
return res;
}
}
Missing Number – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Missing Number - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution {
/* public int missingNumber(int[] nums) {
int n = nums.length;
int total = n * (n + 1) / 2;
for (int i = 0; i < nums.length; i++) {
total -= nums[i];
}
return total;
} */
public int missingNumber(int[] nums) {
int res = nums.length;
for (int i = 0; i < nums.length; i++) {
res ^= i;
res ^= nums[i];
}
return res;
}
/* public int missingNumber(int[] nums) {
Arrays.sort(nums);
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] > mid) right = mid - 1;
else left = mid + 1;
}
return left;
} */
}
Paint Fence – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Paint Fence - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# def numWays(self, n, k):
# """
# :type n: int
# :type k: int
# :rtype: int
# """
# w = [0, k, k*k]
# while len(w) <= n:
# w += sum(w[-2:]) * (k-1),
# return w[n]
def numWays(self, n, k):
if n == 0:
return 0
elif n == 1:
return k
# two step dp
# ways[1] = k
# ways[2] = k * k
# ways[i>2] = (ways[i-1] + ways[i-2]) * (k - 1)
dp = [0] * 2
dp[0] = k
dp[1] = k * k
for i in range(2, n):
temp = dp[1]
dp[1] = sum(dp) * (k - 1)
dp[0] = temp
return dp[1]
Hamming Distance – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Hamming Distance - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution {
public int hammingDistance(int x, int y) {
return Integer.bitCount(x ^ y);
}
}
Walls and Gates – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Walls and Gates - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def wallsAndGates(self, rooms):
"""
:type rooms: List[List[int]]
:rtype: void Do not return anything, modify rooms in-place instead.
"""
# BFS with queue
direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]
m = len(rooms)
if m == 0:
return
n = len(rooms[0])
q = []
for row in range(m):
for col in range(n):
# gate
if rooms[row][col] == 0:
q.append((row, col))
while len(q) > 0:
point = q.pop(0)
row, col = point[0], point[1]
for d in direction:
r = row + d[0]
c = col + d[1]
# wall or out of rooms
if r < 0 or c < 0 or r >= m or c >= n or rooms[r][c] != 2147483647:
continue
rooms[r][c] = rooms[row][col] + 1
q.append((r, c))
Combination Sum III – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Combination Sum III - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
import itertools as it
class Solution(object):
def combinationSum3(self, k, n):
"""
:type k: int
:type n: int
:rtype: List[List[int]]
"""
return list(it.ifilter(lambda x: sum(x) == n, list(it.combinations(range(1, 10), k))))
Max Consecutive Ones – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Max Consecutive Ones - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def findMaxConsecutiveOnes(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ans = 0
curr = 0
for n in nums:
if n == 1:
# Add 1 to curr when encounter 1
curr += 1
if curr > ans:
ans = curr
else:
# Add 1 to curr when encounter 1
curr = 0
return ans
Subarray Sum Equals K – Leetcode Challenge – Java Solution
This is the java solution for the Leetcode problem - Subarray Sum Equals K - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
public class Solution {
/*public int subarraySum(int[] nums, int k) {
int count = 0;
for (int start = 0; start < nums.length; start++) {
int sum = 0;
for (int end = start; end < nums.length; end++) {
sum += nums[end];
if (sum == k)
count++;
}
}
return count;
}*/
public int subarraySum(int[] nums, int k) {
int count = 0, sum = 0;
HashMap < Integer, Integer > map = new HashMap < > ();
map.put(0, 1);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
// check if sum - k in hash
if (map.containsKey(sum - k))
count += map.get(sum - k);
// push sum into hash
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
}
Diameter of Binary Tree – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Diameter of Binary Tree - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
# https://leetcode.com/problems/diameter-of-binary-tree/solution/
def diameterOfBinaryTree(self, root):
self.ans = 1
def depth(node):
if not node: return 0
L = depth(node.left)
R = depth(node.right)
self.ans = max(self.ans, L+R+1)
return max(L, R) + 1
depth(root)
# number of nodes - 1 = length
return self.ans - 1
Two Sum III – Data structure design – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Two Sum III - Data structure design - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class TwoSum(object):
def __init__(self):
"""
initialize your data structure here
"""
self.internal = []
self.dic = {}
def add(self, number):
"""
Add the number to an internal data structure.
:rtype: nothing
"""
self.internal.append(number)
if number in self.dic:
# more than once
self.dic[number] = True
return
# once
self.dic[number] = False
def find(self, value):
"""
Find if there exists any pair of numbers which sum is equal to the value.
:type value: int
:rtype: bool
"""
for v in self.internal:
if value - v in self.dic:
if v << 1 == value and not self.dic[v]:
continue
return True
return False
# Your TwoSum object will be instantiated and called as such:
# twoSum = TwoSum()
# twoSum.add(number)
# twoSum.find(value)
Maximum Subarray – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Maximum Subarray - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# def maxSubArray(self, nums):
# return self.maxSubArrayHelper(nums, 0, len(nums) - 1)
#
# def maxSubArrayHelper(self, nums, l, r):
# if l > r:
# return -2147483647
# mid = (l + r) / 2
# leftAns = self.maxSubArrayHelper(nums, l, mid - 1)
# rightAns = self.maxSubArrayHelper(nums, mid + 1, r)
# lMaxSum = res = 0
# for i in range(mid - 1, l -1, -1):
# res += nums[i]
# lMaxSum = max(res, lMaxSum)
# rMaxSum = res = 0
# for i in range(mid + 1, r + 1):
# res += nums[i]
# rMaxSum = max(res, rMaxSum)
# return max(lMaxSum + nums[mid] + rMaxSum, max(leftAns, rightAns))
# def maxSubArray(self, nums):
# """
# :type nums: List[int]
# :rtype: int
# """
# ls = len(nums)
# start = [0] * ls
# all = [0] * ls
# start[-1], all[-1] = nums[-1], nums[-1]
# for i in reversed(range(ls - 1)):
# start[i] = max(nums[i], nums[i] + start[i + 1])
# all[i] = max(start[i], all[i + 1])
# return all[0]
# def maxSubArray(self, nums):
# ls = len(nums)
# start, all = nums[-1], nums[-1]
# for i in reversed(range(ls - 1)):
# start = max(nums[i], nums[i] + start)
# all = max(start, all)
# return all
def maxSubArray(self, nums):
maxEndingHere = maxSofFar = nums[0]
for i in range(1, len(nums)):
maxEndingHere = max(maxEndingHere + nums[i], nums[i])
maxSofFar = max(maxEndingHere, maxSofFar)
return maxSofFar
Copy List with Random Pointer – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Copy List with Random Pointer - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution(object):
# def copyRandomList(self, head):
# """
# :type head: RandomListNode
# :rtype: RandomListNode
# """
# # hash O(n) and O(n)
# dic = collections.defaultdict(lambda: RandomListNode(0))
# dic[None] = None
# n = head
# while n:
# dic[n].label = n.label
# dic[n].next = dic[n.next]
# dic[n].random = dic[n.random]
# n = n.next
# return dic[head]
# def copyRandomList(self, head):
# # hash O(n) and O(n)
# dic = {}
# dic[None] = None
# dummyHead = RandomListNode(0)
# p, q = head, dummyHead
# while p is not None:
# q.next = RandomListNode(p.label)
# dic[p] = q.next
# p = p.next
# q = q.next
# p, q = head, dummyHead
# while p is not None:
# q.next.random = dic[p.random]
# p = p.next
# q = q.next
# return dummyHead.next
def copyRandomList(self, head):
# Modify original structure: Original->Copy->Original->Copy
# node.next.random = node.random.next
# O(n) and O(1)
p = head
while p is not None:
next = p.next
copy = RandomListNode(p.label)
p.next = copy
copy.next = next
p = next
p = head
while p is not None:
if p.random is not None:
p.next.random = p.random.next
p = p.next.next
p = head
if p is not None:
headCopy = p.next
else:
headCopy = None
while p is not None:
copy = p.next
p.next = copy.next
p = p.next
if p is not None:
copy.next = p.next
return headCopy
Single Number – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Single Number - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# def singleNumber(self, nums):
# """
# :type nums: List[int]
# :rtype: int
# """
# # hash
# dic = {}
# for num in nums:
# try:
# dic[num] += 1
# except KeyError:
# dic[num] = 1
# for num in nums:
# if dic[num] == 1:
# return num
# def singleNumber(self, nums):
# # set
# s = set()
# for num in nums:
# if num in s:
# s.remove(num)
# else:
# s.add(num)
# return s.pop()
def singleNumber(self, nums):
# xor
res = 0
for num in nums:
res ^= num
return res
Find Minimum in Rotated Sorted Array II – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Find Minimum in Rotated Sorted Array II - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# def findMin(self, nums):
# """
# :type nums: List[int]
# :rtype: int
# """
# return self.get_min(nums, 0, len(nums) - 1)
# def get_min(self, nums, start, end):
# mid = (start + end) / 2
# if start == end:
# # one element
# return nums[start]
# if mid == start or mid == end:
# # two element
# return min(nums[start], nums[end])
# if nums[mid] < nums[end]:
# # right side sorted
# if nums[mid] > nums[start]:
# # not rotated
# return nums[start]
# return self.get_min(nums, start, mid)
# elif nums[mid] > nums[end]:
# # left side sorted
# return self.get_min(nums, mid, end)
# else:
# # cannot judge which direction is sorted
# return min(self.get_min(nums, start, mid), self.get_min(nums, mid, end))
# def findMin(self, nums):
# start, end = 0, len(nums) - 1
# while start < end:
# mid = (start + end) / 2
# if nums[mid] > nums[end]:
# start = mid + 1
# elif nums[mid] < nums[end]:
# end = mid
# else:
# end -= 1
# return nums[start]
def findMin(self, nums):
l, r = 0, len(nums) - 1
while l < r and nums[l] >= nums[r]:
mid = (l + r) / 2
if nums[mid] > nums[r]:
l = mid + 1
elif nums[mid] < nums[l]:
r = mid
else:
# nums[l] = nums[r] = nums[mid]
l += 1
return nums[l]
Count Primes – Leetcode Challenge – C++ Solution
This is the c++ solution for the Leetcode problem - Count Primes - Leetcode Challenge - C++ Solution.
Source - qiyuangong's repository.
// Source : https://leetcode.com/problems/count-primes/
/**********************************************************************************
*
* Description:
* Count the number of prime numbers less than a non-negative number, n.
*
* Credits:Special thanks to @mithmatt for adding this problem and creating all test cases.
*
* Let's start with a isPrime function. To determine if a number is prime, we need to check if
* it is not divisible by any number less than n. The runtime complexity of isPrime function
* would be O(n) and hence counting the total prime numbers up to n would be O(n2). Could we do better?
*
* As we know the number must not be divisible by any number > n / 2, we can immediately cut the total
* iterations half by dividing only up to n / 2. Could we still do better?
*
* Let's write down all of 12's factors:
*
* 2 × 6 = 12
* 3 × 4 = 12
* 4 × 3 = 12
* 6 × 2 = 12
*
* As you can see, calculations of 4 × 3 and 6 × 2 are not necessary. Therefore, we only need to consider
* factors up to √n because, if n is divisible by some number p, then n = p × q and since p ≤ q, we could derive that p ≤ √n.
*
* Our total runtime has now improved to O(n1.5), which is slightly better. Is there a faster approach?
*
* public int countPrimes(int n) {
* int count = 0;
* for (int i = 1; i < n; i++) {
* if (isPrime(i)) count++;
* }
* return count;
* }
*
* private boolean isPrime(int num) {
* if (num <= 1) return false;
* // Loop's ending condition is i * i <= num instead of i <= sqrt(num)
* // to avoid repeatedly calling an expensive function sqrt().
* for (int i = 2; i * i <= num; i++) {
* if (num % i == 0) return false;
* }
* return true;
* }
*
* The Sieve of Eratosthenes is one of the most efficient ways to find all prime numbers up to n.
* But don't let that name scare you, I promise that the concept is surprisingly simple.
*
* [Sieve of Eratosthenes](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)
*
* [https://leetcode.com/static/images/solutions/Sieve_of_Eratosthenes_animation.gif]
* [http://commons.wikimedia.org/wiki/File:Sieve_of_Eratosthenes_animation.gif]
*
* Sieve of Eratosthenes: algorithm steps for primes below 121. "Sieve of Eratosthenes Animation"()
* by SKopp is licensed under CC BY 2.0.
*
* * [Skoop](http://de.wikipedia.org/wiki/Benutzer:SKopp)
* * [CC BY 2.0](http://creativecommons.org/licenses/by/2.0/)
*
* We start off with a table of n numbers. Let's look at the first number, 2. We know all multiples of 2
* must not be primes, so we mark them off as non-primes. Then we look at the next number, 3. Similarly,
* all multiples of 3 such as 3 × 2 = 6, 3 × 3 = 9, ... must not be primes, so we mark them off as well.
* Now we look at the next number, 4, which was already marked off. What does this tell you? Should you
* mark off all multiples of 4 as well?
*
* 4 is not a prime because it is divisible by 2, which means all multiples of 4 must also be divisible
* by 2 and were already marked off. So we can skip 4 immediately and go to the next number, 5. Now,
* all multiples of 5 such as 5 × 2 = 10, 5 × 3 = 15, 5 × 4 = 20, 5 × 5 = 25, ... can be marked off.
* There is a slight optimization here, we do not need to start from 5 × 2 = 10. Where should we start marking off?
*
* In fact, we can mark off multiples of 5 starting at 5 × 5 = 25, because 5 × 2 = 10 was already marked off
* by multiple of 2, similarly 5 × 3 = 15 was already marked off by multiple of 3. Therefore, if the current
* number is p, we can always mark off multiples of p starting at p2, then in increments of p: p2 + p, p2 + 2p, ...
* Now what should be the terminating loop condition?
*
* It is easy to say that the terminating loop condition is p n, which is certainly correct but not efficient.
* Do you still remember Hint #3?
*
* Yes, the terminating loop condition can be p n, as all non-primes ≥ √n must have already been marked off.
* When the loop terminates, all the numbers in the table that are non-marked are prime.
*
* The Sieve of Eratosthenes uses an extra O(n) memory and its runtime complexity is O(n log log n).
* For the more mathematically inclined readers, you can read more about its algorithm complexity on
* [Wikipedia](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity).
*
* public int countPrimes(int n) {
* boolean[] isPrime = new boolean[n];
* for (int i = 2; i < n; i++) {
* isPrime[i] = true;
* }
* // Loop's ending condition is i * i < n instead of i < sqrt(n)
* // to avoid repeatedly calling an expensive function sqrt().
* for (int i = 2; i * i < n; i++) {
* if (!isPrime[i]) continue;
* for (int j = i * i; j < n; j += i) {
* isPrime[j] = false;
* }
* }
* int count = 0;
* for (int i = 2; i < n; i++) {
* if (isPrime[i]) count++;
* }
* return count;
* }
*
*
**********************************************************************************/
#include
#include
#include
using namespace std;
int countPrimes(int n)
{
vector isPrimer(n, true);
for (int i = 2; i * i < n; i++)
{
if (isPrimer[i])
{
for (int j = i * i; j < n; j += i)
{
isPrimer[j] = false;
}
}
}
int cnt = 0;
for (int i = 2; i < n; i++)
{
if (isPrimer[i])
{
//cout << i << ", ";
cnt++;
}
}
return cnt;
}
int main(int argc, char **argv)
{
int n = 100;
if (argc > 1)
{
n = atoi(argv[1]);
}
cout << endl
<< n << " : " << countPrimes(n) << endl;
return 0;
}
XOR Queries of a Subarray – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - XOR Queries of a Subarray - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution:
def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
pref = [0]
# Compute accumulated xor from head
for e in arr:
pref.append(e ^ pref[-1])
ans = []
# query result equal to xor[0, l] xor x[0, r]
for [l, r] in queries:
ans.append(pref[r+1] ^ pref[l])
return ans
# def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
# for i in range(len(arr) - 1):
# arr[i + 1] ^= arr[i]
# return [arr[j] ^ arr[i - 1] if i else arr[j] for i, j in queries]
Fizz Buzz – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem - Fizz Buzz - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# def fizzBuzz(self, n):
# """
# :type n: int
# :rtype: List[str]
# """
# res = []
# for i in range(1, n + 1):
# if i % 3 == 0:
# if i % 5 == 0:
# res.append('FizzBuzz')
# else:
# res.append('Fizz')
# elif i % 5 == 0:
# res.append('Buzz')
# else:
# res.append(str(i))
# return res
# def fizzBuzz(self, n):
# """
# :type n: int
# :rtype: List[str]
# """
# res = []
# for i in range(1, n + 1):
# curr = ''
# if i % 3 == 0:
# curr += 'Fizz'
# if i % 5 == 0:
# curr += 'Buzz'
# if not len(curr):
# curr += str(i)
# res.append(curr)
# return res
def fizzBuzz(self, n):
return [str(i) * (i % 3 != 0 and i % 5 != 0) + "Fizz" * (i % 3 == 0) + "Buzz" * (i % 5 == 0)
for i in range(1, n + 1)]
# def fizzBuzz(self, n):
# return ['Fizz' * (not i % 3) + 'Buzz' * (not i % 5) or str(i) for i in range(1, n+1)]