Unpivot or melt with pandas and SQLAlchemy
Here’s the script to melt data with pandas and SQLAlchemy.
Find unique values in a JavaScript array by property
To return the whole object of unique values, try the following code snippet.
Get min and max value from array of objects in JavaScript
This is very similar to finding min/max value from an array of primitive data.
How to truncate table with foreign key constraint in MySQL?
SET FOREIGN_KEY_CHECKS = 0; TRUNCATE table1;
Force / turn off garbage collection in python
Force garbage collection Turn off garbage collection
Get indexes of all matches from Array.filter in JavaScript
For simple arrays For Array of Objects
Export JSON to XLSX using Sheet.js
This code snippet exports a JSON / JSON Array to a XLSX formatted file. I used Sheet.js version 0.14.0.
Pad a number to two digits with Javascript
Similar to padding a number with leading zeros, we can pad a number into two digits in JavaScript.
Get the URL port number of a web page using JavaScript
To get the URL port number of a web page in JavaScript we can use the window.location object in Location API. This method will return a USVString containing the port number of the URL, […]
Remove decimal part from a number in JavaScript
In JavaScript, we can use the parseInt() or Math.trunc() function to remove the decimal parts from a number.
How to generate random numbers in Java within range?
Using java.util.Random Using ThreadLocalRandom
Implement a Queue using two Stacks – JavaScript 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 JavaScript.
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.
Implement Stack using Two Queues – Java Solution
Convert a queue with their standard operations (enqueue, dequeue, isempty, size) to a stack with its standard operations (pop, push, isempty, size).
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