This is the java solution for the Leetcode problem – Number of Recent Calls – Leetcode Challenge – Java Solution.
Source – qiyuangong’s repository.
class RecentCounter {
Queue q;
public RecentCounter() {
q = new LinkedList();
}
public int ping(int t) {
q.add(t);
while (q.peek() < t - 3000)
q.poll();
return q.size();
}
}
This is the python solution for the Leetcode problem - N-Repeated Element in Size 2N Array - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
import collections
class Solution(object):
def repeatedNTimes(self, A):
"""
:type A: List[int]
:rtype: int
"""
counter = collections.Counter(A)
return counter.most_common(1)[0][0]
if __name__ == '__main__':
s = Solution()
print s.repeatedNTimes([1, 2, 3, 3])
print s.repeatedNTimes([2, 1, 2, 5, 3, 2])
print s.repeatedNTimes([5, 1, 5, 2, 5, 3, 5, 4])
This is the python solution for the Leetcode problem - Rectangle Overlap - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def isRectangleOverlap(self, rec1, rec2):
"""
:type rec1: List[int]
:type rec2: List[int]
:rtype: bool
"""
return not (rec1[2] <= rec2[0] or # left
rec1[3] <= rec2[1] or # bottom
rec1[0] >= rec2[2] or # right
rec1[1] >= rec2[3]) # top
# def isRectangleOverlap(self, rec1, rec2):
# def intersect(p_left, p_right, q_left, q_right):
# return min(p_right, q_right) > max(p_left, q_left)
# return (intersect(rec1[0], rec1[2], rec2[0], rec2[2]) and
# intersect(rec1[1], rec1[3], rec2[1], rec2[3]))
This is the python solution for the Leetcode problem - Find Minimum in Rotated Sorted Array - 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)
def findMin(self, nums):
# A[l] > A[r]
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
else:
r = mid
return nums[l]
This is the python solution for the Leetcode problem - Running Sum of 1d Array - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution:
def runningSum(self, nums: List[int]) -> List[int]:
if nums is None or len(nums) == 0:
return nums
for i in range(1, len(nums)):
nums[i] += nums[i-1]
return nums
# def runningSum(self, nums: List[int]) -> List[int]:
# # accumulate method
# return accumulate(nums)
This is the java solution for the Leetcode problem - Find All Numbers Disappeared in an Array - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution {
// https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/discuss/92956/Java-accepted-simple-solution
public List findDisappearedNumbers(int[] nums) {
List ret = new ArrayList();
for(int i = 0; i < nums.length; i++) {
int val = Math.abs(nums[i]) - 1;
if(nums[val] > 0) {
nums[val] = -nums[val];
}
}
for(int i = 0; i < nums.length; i++) {
if(nums[i] > 0) {
ret.add(i+1);
}
}
return ret;
}
}
This is the python solution for the Leetcode problem - Single Number II - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# def singleNumber(self, nums):
# """
# :type nums: List[int]
# :rtype: int
# """
# import ctypes
# # note that if res is not c 32
# # there will be errors
# count = [0] * 32
# res = ctypes.c_int32(0)
# for i in range(32):
# for num in nums:
# if (ctypes.c_int32(num).value >> i) & 1:
# count[i] += 1
# res.value |= ((count[i] % 3) << i)
# return res.value
def singleNumber(self, nums):
# bitmask
# ones as a bitmask to represent the ith bit had appeared once.
# twos as a bitmask to represent the ith bit had appeared twice.
# threes as a bitmask to represent the ith bit had appeared three times.
ones, twos, threes = 0, 0, 0
for num in nums:
twos |= ones & num
ones ^= num
threes = ones & twos
ones &= ~threes
twos &= ~threes
return ones
This is the java solution for the Leetcode problem - Shift 2D Grid - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution {
public List> shiftGrid(int[][] grid, int k) {
int[][] newGrid = new int[grid.length][grid[0].length];
int m = grid.length;
int n = grid[0].length;
// Compute final move
int true_k = k % (m * n);
// Row move
int move_i = true_k / n;
// Column move
int move_j = true_k % n;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
int new_i = i + move_i;
int new_j = (j + move_j) % n;
// Move 1 row if (move_j + j >= n
if (move_j + j >= n) new_i ++;
new_i %= m;
newGrid[new_i][new_j] = grid[i][j];
}
}
// Copy the grid into a list for returning.
List> result = new ArrayList<>();
for (int[] row : newGrid) {
List listRow = new ArrayList<>();
result.add(listRow);
for (int v : row) listRow.add(v);
}
return result;
}
}
This is the java solution for the Leetcode problem - Sum of Left Leaves - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
import java.util.Stack;
import javax.swing.tree.TreeNode;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
/* public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
if (root.left != null
&& root.left.left == null
&& root.left.right == null)
return root.left.val + sumOfLeftLeaves(root.right);
return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
} */
public int sumOfLeftLeaves(TreeNode root) {
int res = 0;
Stack stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node != null) {
if (node.left != null
&& node.left.left == null
&& node.left.right == null)
res += node.left.val;
stack.push(node.right);
stack.push(node.left);
}
}
return res;
}
}
This is the java solution for the Leetcode problem - Validate Stack Sequences - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack inStack = new Stack<>();
int posPush = 0, posPop = 0;
while (posPush != pushed.length) {
int curr = pushed[posPush];
while (!inStack.empty() && popped.length > 0 && inStack.peek() == popped[posPop]) {
inStack.pop();
posPop++;
}
if (popped.length == 0) break;
if (curr == popped[posPop]) posPop++;
else inStack.push(curr);
posPush++;
}
while (!inStack.empty() && popped.length > 0 && inStack.peek() == popped[posPop]) {
inStack.pop();
posPop++;
}
if (inStack.empty()) return true;
return false;
}
}
This is the python solution for the Leetcode problem - Convert Binary Number in a Linked List to Integer - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
'''
Given head which is a reference node to a singly-linked list.
The value of each node in the linked list is either 0 or 1.
The linked list holds the binary representation of a number.
Return the decimal value of the number in the linked list.
Example 1:
Input: head = [1,0,1]
Output: 5
Explanation: (101) in base 2 = (5) in base 10
Example 2:
Input: head = [0]
Output: 0
Example 3:
Input: head = [1]
Output: 1
Example 4:
Input: head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
Output: 18880
Example 5:
Input: head = [0,0]
Output: 0
Constraints:
The Linked List is not empty.
Number of nodes will not exceed 30.
Each node's value is either 0 or 1.
'''
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getDecimalValue(self, head: ListNode) -> int:
binary_numbers_list = []
binary_numbers_list.append(head.val)
while(head.next is not None):
head = head.next
binary_numbers_list.append(head.val)
answer = 0
power = 0
# from len(binary_numbers_list) - 1 -> 0
for digit in range(len(binary_numbers_list) - 1, -1, -1):
if(binary_numbers_list[digit] > 0):
answer += ((2 ** power) * binary_numbers_list[digit])
power += 1
return answer
This is the java solution for the Leetcode problem - Running Sum of 1d Array - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution {
public int[] runningSum(int[] nums) {
if (nums.length <= 1) return nums;
for (int i = 1; i < nums.length; i++)
nums[i] += nums[i - 1];
return nums;
}
}
This is the python solution for the Leetcode problem - Peak Index in a Mountain Array - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# def peakIndexInMountainArray(self, A):
# """
# :type A: List[int]
# :rtype: int
# """
# i = 0
# while A[i + 1] >= A[i]:
# i += 1
# return i
def peakIndexInMountainArray(self, A):
lo, hi = 0, len(A) - 1
while lo < hi:
mid = (lo + hi) / 2
if A[mid] < A[mid + 1]:
lo = mid + 1
else:
hi = mid
return lo
This is the python solution for the Leetcode problem - Reverse Words in a String III - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
return ' '.join([word[::-1] for word in s.split(' ')])
This is the java solution for the Leetcode problem - Valid Palindrome II - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution {
public boolean isPalindromeRange(String s, int i, int j) {
for (int k = i; k <= i + (j - i) / 2; k++) {
if (s.charAt(k) != s.charAt(j - k + i)) return false;
}
return true;
}
public boolean validPalindrome(String s) {
for (int i = 0; i < s.length() / 2; i++) {
if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
// Not equal
int j = s.length() - 1 - i;
// delete left or right
return (isPalindromeRange(s, i + 1, j) ||
isPalindromeRange(s, i, j - 1));
}
}
return true;
}
}
This is the java solution for the Leetcode problem - Binary Gap - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution {
/*public int binaryGap(int n) {
// Store Indexes
int[] A = new int[32];
int t = 0;
for (int i = 0; i < 32; ++i)
if (((N >> i) & 1) != 0)
A[t++] = i;
int ans = 0;
for (int i = 0; i < t - 1; ++i)
ans = Math.max(ans, A[i+1] - A[i]);
return ans;
}*/
public int binaryGap(int N) {
int last = -1, ans = 0;
for (int i = 0; i < 32; ++i)
if (((N >> i) & 1) > 0) {
// Store max
if (last >= 0)
ans = Math.max(ans, i - last);
last = i;
}
return ans;
}
}
This is the python solution for the Leetcode problem - Strobogrammatic Number - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def isStrobogrammatic(self, num):
"""
:type num: str
:rtype: bool
"""
# hash table
dic = {'0':'0', '6':'9', '9': '6', '1' :'1', '8': '8'}
temp_s = ''
for c in num[::-1]:
if c not in dic:
return False
temp_s += dic[c]
if int(temp_s) == int(num):
return True
return False
# def isStrobogrammatic(self, num):
# # https://discuss.leetcode.com/topic/20840/1-liners-python
# return all(num[i] + num[~i] in '696 00 11 88' for i in range(len(num)/2+1))
This is the java solution for the Leetcode problem - Third Maximum Number - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
public class Solution {
public int thirdMax(int[] nums) {
PriorityQueue pq = new PriorityQueue<>(3);
Set set = new HashSet<>();
for (int i : nums) {
if (set.contains(i)) continue;
pq.offer(i);
set.add(i);
if (pq.size() > 3) set.remove(pq.poll());
}
while (pq.size() < 3 && pq.size() > 1) {
pq.poll();
}
return pq.peek();
}
}
This is the python solution for the Leetcode problem - Valid Palindrome II - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# def validPalindrome(self, s):
# """
# :type s: str
# :rtype: bool
# """
# def is_pali_range(i, j):
# return all(s[k] == s[j - k + i] for k in range(i, j))
# for i in xrange(len(s) / 2):
# if s[i] != s[~i]:
# j = len(s) - 1 - i
# return is_pali_range(i + 1, j) or is_pali_range(i, j - 1)
# return True
# Actually we can make this solution more general
def validPalindrome(self, s):
return self.validPalindromeHelper(s, 0, len(s) - 1, 1)
def validPalindromeHelper(self, s, left, right, budget):
# Note that budget can be more than 1
while left < len(s) and right >= 0 and left <= right and s[left] == s[right]:
left += 1
right -= 1
if left >= len(s) or right < 0 or left >= right:
return True
if budget == 0:
return False
budget -= 1
return self.validPalindromeHelper(s, left + 1, right, budget) or self.validPalindromeHelper(s, left, right - 1, budget)
This is the python solution for the Leetcode problem - Palindrome Permutation II - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def generatePalindromes(self, s):
"""
:type s: str
:rtype: List[str]
"""
dic = {}
half = []
res = []
for c in s:
dic[c] = dic.get(c, 0) + 1
odd, even = 0, 0
for c in dic:
if dic[c] % 2 == 0:
even += 1
else:
odd += 1
if odd > 1:
return []
# generate half
seed = []
mid = ''
for c in dic:
if dic[c] % 2 == 1:
mid = c
seed.extend([c] * (dic[c] / 2))
self.permute(half, seed, 0)
# merge half to get res
for r in half:
res.append(''.join(r) + mid + ''.join(reversed(r)))
return res
def permute(self, res, num, index):
if index == len(num):
res.append(list(num))
return
appeared = set()
for i in range(index, len(num)):
if num[i] in appeared:
continue
appeared.add(num[i])
num[i], num[index] = num[index], num[i]
self.permute(res, num, index + 1)
num[i], num[index] = num[index], num[i]
This is the python solution for the Leetcode problem - 1-bit and 2-bit Characters - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
# We have two special characters. The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11).
# Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero.
# Example 1:
# Input:
# bits = [1, 0, 0]
# Output: True
# Explanation:
# The only way to decode it is two-bit character and one-bit character. So the last character is one-bit character.
# Example 2:
# Input:
# bits = [1, 1, 1, 0]
# Output: False
# Explanation:
# The only way to decode it is two-bit character and two-bit character. So the last character is NOT one-bit character.
# Note:
# 1 <= len(bits) <= 1000.
# bits[i] is always 0 or 1.
# https://leetcode.com/problems/1-bit-and-2-bit-characters/solution/
class Solution:
def isOneBitCharacter(self, bits: List[int]) -> bool:
pos = 0
# Go through bits
while pos < len(bits) - 1:
# if 1, pos + 2; if 0, pos + 1
pos += bits[pos] + 1
return pos == len(bits) - 1
# def isOneBitCharacter(self, bits):
# # From len - 2
# pos = len(bits) - 2
# # until encounter 0
# while pos >= 0 and bits[pos] > 0:
# pos -= 1
# # check if second last zero is even
# return (len(bits) - pos) % 2 == 0
This is the java solution for the Leetcode problem - Max Stack - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class MaxStack {
TreeMap> map;
DoubleLinkedList dll;
public MaxStack() {
map = new TreeMap();
dll = new DoubleLinkedList();
}
public void push(int x) {
Node node = dll.add(x);
if(!map.containsKey(x))
map.put(x, new ArrayList());
map.get(x).add(node);
}
public int pop() {
int val = dll.pop();
List L = map.get(val);
L.remove(L.size() - 1);
if (L.isEmpty()) map.remove(val);
return val;
}
public int top() {
return dll.peek();
}
public int peekMax() {
return map.lastKey();
}
public int popMax() {
int max = peekMax();
List L = map.get(max);
Node node = L.remove(L.size() - 1);
dll.unlink(node);
if (L.isEmpty()) map.remove(max);
return max;
}
}
class DoubleLinkedList {
Node head, tail;
public DoubleLinkedList() {
head = new Node(0);
tail = new Node(0);
head.next = tail;
tail.prev = head;
}
public Node add(int val) {
Node x = new Node(val);
x.next = tail;
x.prev = tail.prev;
tail.prev = tail.prev.next = x;
return x;
}
public int pop() {
return unlink(tail.prev).val;
}
public int peek() {
return tail.prev.val;
}
public Node unlink(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
return node;
}
}
class Node {
int val;
Node prev, next;
public Node(int v) {val = v;}
}
This is the java solution for the Leetcode problem - Middle of the Linked List - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
// public ListNode middleNode(ListNode head) {
// List array = new ArrayList();
// while (head != null) {
// array.add(head);
// head = head.next;
// }
// return array.get(array.size() / 2);
// }
public ListNode middleNode(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
This is the python solution for the Leetcode problem - Read N Characters Given Read4 II - Call multiple times - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
# The read4 API is already defined for you.
# @param buf, a list of characters
# @return an integer
# def read4(buf):
class Solution(object):
def __init__(self):
self.buff = [''] * 4
self.offset = 0
self.bufsize = 0
def read(self, buf, n):
"""
:type buf: Destination buffer (List[str])
:type n: Maximum number of characters to read (int)
:rtype: The number of characters read (int)
"""
pos, eof = 0, False
while not eof and pos < n:
if self.bufsize == 0:
self.bufsize = read4(self.buff)
eof = self.bufsize < 4
byte = min(n - pos, self.bufsize)
for i in range(byte):
buf[pos + i] = self.buff[self.offset + i]
self.offset = (self.offset + byte) % 4
self.bufsize -= byte
pos += byte
return pos
This is the python solution for the Leetcode problem - Fruit Into Baskets - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# def totalFruit(self, tree):
# """
# :type tree: List[int]
# :rtype: int
# """
# basket, res, start = 2, 0, 0
# queue_map = {}
# for i, v in enumerate(tree):
# queue_map[v] = queue_map.get(v, 0) + 1
# if len(queue_map) > 2:
# queue_map[tree[start]] -= 1
# if queue_map[tree[start]] == 0:
# del queue_map[tree[start]]
# start += 1
# res = max(res, i - start + 1)
# return res
# https://leetcode.com/problems/fruit-into-baskets/solution/
# def totalFruit(self, tree):
# blocks = [(k, len(list(v)))
# for k, v in itertools.groupby(tree)]
# ans = i = 0
# while i < len(blocks):
# # We'll start our scan at block[i].
# # types : the different values of tree[i] seen
# # weight : the total number of trees represented
# # by blocks under consideration
# types, weight = set(), 0
# # For each block from i and going forward,
# for j in xrange(i, len(blocks)):
# # Add each block to consideration
# types.add(blocks[j][0])
# weight += blocks[j][1]
# # If we have 3 types, this is not a legal subarray
# if len(types) >= 3:
# i = j-1
# break
# ans = max(ans, weight)
# # If we go to the last block, then stop
# else:
# break
# return ans
def totalFruit(self, tree):
ans = i = 0
count = collections.Counter()
for j, x in enumerate(tree):
count[x] += 1
while len(count) >= 3:
count[tree[i]] -= 1
if count[tree[i]] == 0:
del count[tree[i]]
i += 1
ans = max(ans, j - i + 1)
return ans
This is the java solution for the Leetcode problem - Verifying an Alien Dictionary - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution {
HashMap orderMap = new HashMap<>();
public boolean isAlienSorted(String[] words, String order) {
// Put value index map into hashmap
for (int i = 0; i < order.length(); i++) {
orderMap.put(order.charAt(i), i);
}
for (int i = 0; i < words.length - 1; i++) {
if (cmp_alien(words[i], words[i + 1]) > 0) return false;
}
return true;
}
private int cmp_alien(String a, String b) {
int ls = a.length() < b.length() ? a.length(): b.length();
int pos = 0;
// Compare based on hashmap
while (pos < ls) {
if (orderMap.get(a.charAt(pos)) != orderMap.get(b.charAt(pos)))
return orderMap.get(a.charAt(pos)) - orderMap.get(b.charAt(pos));
pos += 1;
}
return a.length() <= b.length() ? -1: 1;
}
}
This is the python solution for the Leetcode problem - Coin Change - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# def coinChange(self, coins, amount):
# """
# :type coins: List[int]
# :type amount: int
# :rtype: int
# """
# # Top-down dp
# if amount < 1:
# return 0
# return self.coinChange_helper(coins, amount, [0] * (amount + 1))
# def coinChange_helper(self, coins, amount, count):
# if amount < 0:
# return -1
# if amount == 0:
# return 0
# if count[amount - 1] != 0:
# return count[amount - 1]
# min_count = 1000000000
# for coin in coins:
# res = self.coinChange_helper(coins, amount - coin, count)
# if res >= 0 and res < min_count:
# min_count = 1 + res
# if min_count == 1000000000:
# count[amount - 1] = -1
# else:
# count[amount - 1] = min_count
# return count[amount - 1]
def coinChange(self, coins, amount):
# bottom-up dp
if amount == 0:
return 0
if coins is None or len(coins) == 0:
return -1
coins.sort()
dp = [1000000000] * (amount + 1)
for i in range(1, amount + 1):
for coin in coins:
if i == coin:
dp[i] = 1
break
elif i > coin:
dp[i] = min(dp[i], dp[i - coin] + 1)
if dp[amount] == 1000000000:
return -1
return dp[amount]
This is the java solution for the Leetcode problem - Flipping an Image - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution {
public int[][] flipAndInvertImage(int[][] A) {
int C = A[0].length;
for (int[] row: A)
for (int i = 0; i < (C + 1) / 2; ++i) {
int tmp = row[i] ^ 1;
row[i] = row[C - 1 - i] ^ 1;
row[C - 1 - i] = tmp;
}
return A;
}
}
This is the python solution for the Leetcode problem - Sort Array By Parity - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# def sortArrayByParity(self, A):
# """
# :type A: List[int]
# :rtype: List[int]
# """
# # Bad idea, O(nlogn)
# A.sort(key=lambda x: x % 2)
# return A
# def sortArrayByParity(self, A):
# return ([x for x in A if x % 2 == 0] +
# [x for x in A if x % 2 == 1])
def sortArrayByParity(self, A):
# Quit like quick sort or quick selection
lo, hi = 0, len(A) - 1
while lo < hi:
if A[lo] % 2 > A[hi] % 2:
A[lo], A[hi] = A[hi], A[lo]
if A[lo] % 2 == 0: lo += 1
if A[hi] % 2 == 1: hi -= 1
return A
This is the python solution for the Leetcode problem - Duplicate Zeros - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution:
def duplicateZeros(self, arr: List[int]) -> None:
"""
Do not return anything, modify arr in-place instead.
"""
move_pos = 0
last_pos = len(arr) - 1
for i in range(last_pos + 1):
# Only check [0, lastPos - movePos]
if i > last_pos - move_pos:
break
if arr[i] == 0:
# Special case
if i == last_pos - move_pos:
arr[last_pos] = 0
last_pos -= 1
break
move_pos += 1
last_pos -= move_pos
for i in range(last, -1, -1):
if arr[i] == 0:
arr[i + move_pos] = 0
move_pos -= 1
arr[i + move_pos] = 0
else:
arr[i + move_pos] = arr[i]
This is the python solution for the Leetcode problem - Merge Two Binary Trees - 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 mergeTrees(self, t1, t2):
"""
:type t1: TreeNode
:type t2: TreeNode
:rtype: TreeNode
"""
if t1 is None:
return t2
if t2 is None:
return t1
t1.val += t2.val
t1.left = self.mergeTrees(t1.left, t2.left)
t1.right = self.mergeTrees(t1.right, t2.right)
return t1
# def mergeTrees(self, t1, t2):
# if t1 is None:
# return t2
# stack = [(t1, t2)]
# while len(stack) != 0:
# n1, n2 = stack.pop()
# if n1 is None or n2 is None:
# continue
# n1.val += n2.val
# if n1.left is None:
# n1.left = n2.left
# else:
# stack.insert(0, (n1.left, n2.left))
# if n1.right is None:
# n1.right = n2.right
# else:
# stack.insert(0, (n1.right, n2.right))
# return t1
This is the python solution for the Leetcode problem - Fraction to Recurring Decimal - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def fractionToDecimal(self, numerator, denominator):
"""
:type numerator: int
:type denominator: int
:rtype: str
"""
if numerator == 0:
return '0'
fraction = ''
if (numerator < 0) ^ (denominator < 0):
fraction += '-'
dividend = abs(numerator)
divisor = abs(denominator)
fraction += str(dividend / divisor)
remainder = dividend % divisor
if remainder == 0:
return fraction
fraction += '.'
dic = {}
while remainder != 0:
if remainder in dic:
fraction = fraction[:dic[remainder]] + '(' + fraction[dic[remainder]:] + ')'
break
dic[remainder] = len(fraction)
remainder *= 10
fraction += str(remainder / divisor)
remainder %= divisor
return fraction
if __name__ == '__main__':
s = Solution()
# print s.longestValidParentheses(")(((((()())()()))()(()))(")
print s.fractionToDecimal(-50, 8)
This is the python solution for the Leetcode problem - Network Delay Time - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# def networkDelayTime(self, times, N, K):
# # DFS
# graph = collections.defaultdict(list)
# for u, v, w in times:
# graph[u].append((w, v))
# dist = {node: float('inf') for node in xrange(1, N + 1)}
# def dfs(node, elapsed):
# if elapsed >= dist[node]: return
# dist[node] = elapsed
# for time, nei in sorted(graph[node]):
# dfs(nei, elapsed + time)
# dfs(K, 0)
# ans = max(dist.values())
# return ans if ans < float('inf') else -1
def networkDelayTime(self, times, N, K):
# Dijkstra
graph = collections.defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {node: float('inf') for node in xrange(1, N + 1)}
seen = [False] * (N + 1)
dist[K] = 0
while True:
cand_node = -1
cand_dist = float('inf')
for i in xrange(1, N + 1):
if not seen[i] and dist[i] < cand_dist:
cand_dist = dist[i]
cand_node = i
if cand_node < 0: break
seen[cand_node] = True
for nei, d in graph[cand_node]:
dist[nei] = min(dist[nei], dist[cand_node] + d)
ans = max(dist.values())
return ans if ans < float('inf') else -1
This is the java solution for the Leetcode problem - Can Place Flowers - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
public class Solution {
/*public boolean canPlaceFlowers(int[] flowerbed, int n) {
int i = 0, count = 0;
while (i < flowerbed.length) {
if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {
flowerbed[i++] = 1;
count++;
}
if(count >= n)
return true;
i++;
}
return false;
}*/
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int count = 0, curr;
for (int i = 0; i < flowerbed.length; i++) {
curr = flowerbed[i];
if (i - 1 >= 0) curr += flowerbed[i - 1];
if (i + 1 < flowerbed.length) curr += flowerbed[i + 1];
if (curr == 0) {
count++;
flowerbed[i] = 1;
}
if (count >= n) return true;
}
return false;
}
}
This is the java solution for the Leetcode problem - How Many Numbers Are Smaller Than the Current Number - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
import java.util.Map;
class Solution {
/* public int[] smallerNumbersThanCurrent(int[] nums) {
Map sortedIndex = new HashMap<>();
int[] sortedNums = new int[nums.length];
// sort and get position
System.arraycopy(nums, 0, sortedNums, 0, nums.length);
Arrays.sort(sortedNums);
for (int i = 0; i < nums.length; i++) {
if (sortedIndex.containsKey(sortedNums[i])) continue;
sortedIndex.put(sortedNums[i], i);
}
for (int i = 0; i < nums.length; i++)
sortedNums[i] = sortedIndex.get(nums[i]);
return sortedNums;
} */
public int[] smallerNumbersThanCurrent(int[] nums) {
int[] countList = new int[101];
int[] res = new int[nums.length];
// count numbers
for (int i = 0; i < nums.length; i++)
countList[nums[i]]++;
// compute numbers before current index
for (int i = 1; i < 101; i++)
countList[i] += countList[i-1];
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) res[i] = 0;
else res[i] = countList[nums[i]-1];
}
return res;
}
}
This is the java solution for the Leetcode problem - Network Delay Time - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution {
/*Map dist;
public int networkDelayTime(int[][] times, int N, int K) {
// DFS
Map> graph = new HashMap();
for (int[] edge: times) {
if (!graph.containsKey(edge[0]))
graph.put(edge[0], new ArrayList());
graph.get(edge[0]).add(new int[]{edge[2], edge[1]});
}
for (int node: graph.keySet()) {
Collections.sort(graph.get(node), (a, b) -> a[0] - b[0]);
}
dist = new HashMap();
for (int node = 1; node <= N; ++node)
dist.put(node, Integer.MAX_VALUE);
dfs(graph, K, 0);
int ans = 0;
for (int cand: dist.values()) {
if (cand == Integer.MAX_VALUE) return -1;
ans = Math.max(ans, cand);
}
return ans;
}
public void dfs(Map> graph, int node, int elapsed) {
if (elapsed >= dist.get(node)) return;
dist.put(node, elapsed);
if (graph.containsKey(node))
for (int[] info: graph.get(node))
dfs(graph, info[1], elapsed + info[0]);
}*/
Map dist;
public int networkDelayTime(int[][] times, int N, int K) {
// Dijkstra
Map> graph = new HashMap();
for (int[] edge: times) {
if (!graph.containsKey(edge[0]))
graph.put(edge[0], new ArrayList());
graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
}
dist = new HashMap();
for (int node = 1; node <= N; ++node)
dist.put(node, Integer.MAX_VALUE);
dist.put(K, 0);
boolean[] seen = new boolean[N+1];
while (true) {
int candNode = -1;
int candDist = Integer.MAX_VALUE;
for (int i = 1; i <= N; ++i) {
if (!seen[i] && dist.get(i) < candDist) {
candDist = dist.get(i);
candNode = i;
}
}
if (candNode < 0) break;
seen[candNode] = true;
if (graph.containsKey(candNode))
for (int[] info: graph.get(candNode))
dist.put(info[0],
Math.min(dist.get(info[0]), dist.get(candNode) + info[1]));
}
int ans = 0;
for (int cand: dist.values()) {
if (cand == Integer.MAX_VALUE) return -1;
ans = Math.max(ans, cand);
}
return ans;
}
}
This is the python solution for the Leetcode problem - H-Index - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# def hIndex(self, citations):
# """
# :type citations: List[int]
# :rtype: int
# """
# # Sort and check the max h where the number of paper with no less than h citations
# # is no less than h
# citations.sort()
# ls = len(citations)
# h = ls
# while h > 0 and citations[ls - h] < h:
# h -= 1
# return h
# def hIndex(self, citations):
# citations.sort()
# i = 0
# while i < len(citations) and citations[len(citations) - 1 - i] > i:
# i += 1
# return i
def hIndex(self, citations):
# counting sort
ls = len(citations)
papers = [0] * (ls + 1)
for c in citations:
papers[min(ls, c)] += 1
k, s = ls, papers[ls]
while k > s:
k -= 1
s += papers[k]
return k
This is the python solution for the Leetcode problem - Flood Fill - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# def floodFill(self, image, sr, sc, newColor):
# """
# :type image: List[List[int]]
# :type sr: int
# :type sc: int
# :type newColor: int
# :rtype: List[List[int]]
# """
# r_ls, c_ls = len(image), len(image[0])
# color = image[sr][sc]
# if color == newColor:
# return image
# def dfs(r, c):
# if image[r][c] == color:
# image[r][c] = newColor
# if r - 1 >= 0: dfs(r - 1, c)
# if r + 1 < r_ls: dfs(r + 1, c)
# if c - 1 >= 0: dfs(r, c - 1)
# if c + 1 < c_ls: dfs(r, c + 1)
# dfs(sr, sc)
# return image
def floodFill(self, image, sr, sc, newColor):
# BFS with queue
r_ls, c_ls = len(image), len(image[0])
color = image[sr][sc]
if color == newColor:
return image
queue = [(sr, sc)]
while len(queue) > 0:
r, c = queue.pop(0)
if image[r][c] == color:
image[r][c] = newColor
if r - 1 >= 0: queue.append((r - 1, c))
if r + 1 < r_ls: queue.append((r + 1, c))
if c - 1 >= 0: queue.append((r, c - 1))
if c + 1 < c_ls: queue.append((r, c + 1))
return image
This is the python solution for the Leetcode problem - Maximal Square - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# def maximalSquare(self, matrix):
# """
# :type matrix: List[List[str]]
# :rtype: int
# """
# # Brute force O(mn^2)
# if matrix is None or len(matrix) == 0:
# return 0
# rows, cols = len(matrix), len(matrix[0])
# res = 0
# for i in range(rows):
# for j in range(cols):
# if matrix[i][j] == '1':
# sqlen, flag = 1, True
# while sqlen + i < rows and sqlen + j < cols and flag:
# for k in range(j, sqlen + j + 1):
# if matrix[i + sqlen][k] == '0':
# flag = False
# break
# for k in range(i, sqlen + i + 1):
# if matrix[k][j + sqlen] == '0':
# flag = False
# break
# if flag:
# sqlen += 1
# if res < sqlen:
# res = sqlen
# return res * res
# def maximalSquare(self, matrix):
# # dp[i][j] = min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1
# if matrix is None or len(matrix) == 0:
# return 0
# rows, cols, res = len(matrix), len(matrix[0]), 0
# dp = [[0] * (cols + 1) for _ in range(rows + 1)]
# for i in range(1, rows + 1):
# for j in range(1, cols + 1):
# if matrix[i - 1][j - 1] == '1':
# dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
# res = max(res, dp[i][j])
# return res * res
def maximalSquare(self, matrix):
# dp[j] = min([j], dp[j-1], prev) + 1
# O(n) space
if matrix is None or len(matrix) == 0:
return 0
rows, cols, res, prev = len(matrix), len(matrix[0]), 0, 0
dp = [0] * (cols + 1)
for i in range(1, rows + 1):
for j in range(1, cols + 1):
temp = dp[j]
if matrix[i - 1][j - 1] == '1':
dp[j] = min(dp[j - 1], dp[j], prev) + 1
res = max(res, dp[j])
else:
dp[j] = 0
prev = temp
return res * res
This is the python solution for the Leetcode problem - Self Dividing Numbers - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution:
def selfDividingNumbers(self, left: int, right: int) -> List[int]:
# check every digit
return [x for x in range(left, right+1) if all([int(i) != 0 and x % int(i)==0 for i in str(x)])]
# def selfDividingNumbers(self, left: int, right: int) -> List[int]:
# return [x for x in range(left, right+1) if all((i and (x % i==0) for i in map(int, str(x))))]
This is the python solution for the Leetcode problem - Longest Palindrome - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution:
# https://leetcode.com/problems/longest-palindrome/solution/
# def longestPalindrome(self, s):
# ans = 0
# for v in collections.Counter(s).itervalues():
# ans += v / 2 * 2
# if ans % 2 == 0 and v % 2 == 1:
# ans += 1
# return ans
def longestPalindrome(self, s):
ans = 0
char_map = {}
for c in s:
char_map[c] = char_map.get(c, 0) + 1
for c in char_map.keys():
if char_map[c] % 2 == 0:
ans += char_map.pop(c)
else:
ans += char_map[c] / 2 * 2
if len(char_map) != 0:
ans += 1
return ans
This is the python solution for the Leetcode problem - Android Unlock Patterns - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def numberOfPatterns(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
used = [False] * 9
res = 0
for l in range(m, n + 1):
res += self.calc_patterns(used, -1, l)
used = [False] * 9
return res
def is_valid(self, used, index, last):
# markded
if used[index]:
return False
# first digit
if last == -1:
return True
# adjacent cells (in a row or in a column)
if (last + index) % 2 == 1:
return True
mid = (last + index) / 2
if mid == 4:
return used[mid]
# adjacent cells on diagonal
if (index % 3 != last % 3) and (index / 3 != last / 3):
return True
# all other cells which are not adjacent
return used[mid]
def calc_patterns(self, used, last, length):
if length == 0:
return 1
res = 0
for i in range(9):
if self.is_valid(used, i, last):
used[i] = True
res += self.calc_patterns(used, i, length - 1)
used[i] = False
return res
This is the java solution for the Leetcode problem - Design HashMap - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class MyHashMap {
final ListNode[] nodes = new ListNode[10000];
// https://leetcode.com/problems/design-hashmap/discuss/152746/Java-Solution
public void put(int key, int value) {
int i = idx(key);
if (nodes[i] == null)
nodes[i] = new ListNode(-1, -1);
ListNode prev = find(nodes[i], key);
if (prev.next == null)
prev.next = new ListNode(key, value);
else prev.next.val = value;
}
public int get(int key) {
int i = idx(key);
if (nodes[i] == null)
return -1;
ListNode node = find(nodes[i], key);
return node.next == null ? -1 : node.next.val;
}
public void remove(int key) {
int i = idx(key);
if (nodes[i] == null) return;
ListNode prev = find(nodes[i], key);
if (prev.next == null) return;
prev.next = prev.next.next;
}
int idx(int key) { return Integer.hashCode(key) % nodes.length;}
ListNode find(ListNode bucket, int key) {
ListNode node = bucket, prev = null;
while (node != null && node.key != key) {
prev = node;
node = node.next;
}
return prev;
}
class ListNode {
int key, val;
ListNode next;
ListNode(int key, int val) {
this.key = key;
this.val = val;
}
}
}
This is the python solution for the Leetcode problem - Verifying an Alien Dictionary - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def isAlienSorted(self, words, order):
"""
:type words: List[str]
:type order: str
:rtype: bool
"""
order_map = {}
for i, v in enumerate(order):
order_map[v] = i
def cmp_alien(x, y):
ls = min(len(x), len(y))
index = 0
while index < ls:
if x[index] != y[index]:
return order_map[x[index]] - order_map[y[index]]
index += 1
return len(x) - len(y)
pos = 0
while pos + 1 < len(words):
if cmp_alien(words[pos], words[pos + 1]) > 0:
return False
pos += 1
return True
if __name__ == '__main__':
s = Solution()
print s.isAlienSorted(["hello","leetcode"], "hlabcdefgijkmnopqrstuvwxyz")
print s.isAlienSorted(["word","world","row"], "worldabcefghijkmnpqstuvxyz")
print s.isAlienSorted(["apple","app"], "abcdefghijklmnopqrstuvwxyz")
This is the python solution for the Leetcode problem - Convert Sorted List to Binary Search Tree - 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
# 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):
# convert to list
# def __init__(self):
# self.nodelist = []
#
# def sortedListToBST(self, head):
# """
# :type head: ListNode
# :rtype: TreeNode
# """
# if head is None:
# return None
# size = 0
# pos = head
# while pos is not None:
# self.nodelist.append(pos)
# pos = pos.next
# size += 1
# return self.sortList(0, size - 1)
#
# def sortList(self, start, end):
# if start > end:
# return None
# mid = (start + end) / 2
# current = TreeNode(self.nodelist[mid].val)
# current.left = self.sortList(start, mid - 1)
# current.right = self.sortList(mid + 1, end)
# return current
# point in recursive function
def __init__(self):
self.node = None
def sortedListToBST(self, head):
# Bottom-up recursion O(n) and O(lgn)
if head is None:
return head
size = 0
pos = self.node = head
while pos is not None:
pos = pos.next
size += 1
return self.inorderHelper(0, size - 1)
def inorderHelper(self, start, end):
if start > end:
return None
mid = (start + end) / 2
# left side and move
left = self.inorderHelper(start, mid - 1)
# move and create
root = TreeNode(self.node.val)
root.left = left
self.node = self.node.next
# right side and move
root.right = self.inorderHelper(mid + 1, end)
return root
# two point
# O(nlgn) and O(n)
# def sortedListToBST(self, head):
# if head is None:
# return head
# return self.toBST(head, None)
# def toBST(self, head, tail):
# fast = slow = head
# if head == tail:
# return None
# while fast != tail and fast.next != tail:
# fast = fast.next.next
# slow = slow.next
# root = TreeNode(slow.val)
# root.left = self.toBST(head, slow)
# root.right = self.toBST(slow.next, tail)
# return root
This is the python solution for the Leetcode problem - Leaf-Similar Trees - 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 leafSimilar(self, root1, root2):
"""
:type root1: TreeNode
:type root2: TreeNode
:rtype: bool
"""
if not root1 and not root2:
return True
leaf1 = []
leaf2 = []
self.dfs(root1, leaf1)
self.dfs(root2, leaf2)
if leaf1 == leaf2:
return True
return False
def dfs(self, node, leavels):
if not node:
return
if not node.left and not node.right:
leavels.append(node.val)
self.dfs(node.left, leavels)
self.dfs(node.right, leavels)
This is the python solution for the Leetcode problem - Closest Binary Search Tree Value - 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 closestValue(self, root, target):
# """
# :type root: TreeNode
# :type target: float
# :rtype: int
# """
# # brute force, Search all
# return self.closestValue_helper(root, target, 21474483647)
# def closestValue_helper(self, root, target, curr_min):
# if root is None:
# return curr_min
# if abs(root.val - target) < abs(curr_min - target):
# curr_min = root.val
# left_min = self.closestValue_helper(root.left, target, curr_min)
# right_min = self.closestValue_helper(root.right, target, curr_min)
# if abs(left_min - target) < abs(right_min - target):
# return left_min
# else:
# return right_min
# def closestValue(self, root, target):
# # Iteratively compare root result with current kid's result (left or right)
# path = []
# while root:
# path += root.val,
# root = root.left if target < root.val else root.right
# return min(path, key=lambda x: abs(target - x))
def closestValue(self, root, target):
# compare kids' result with root
kid = root.left if target < root.val else root.right
if not kid:
return root.val
kid_min = self.closestValue(kid, target)
return min((kid_min, root.val), key=lambda x: abs(target - x))
This is the python solution for the Leetcode problem - Maximum Product Subarray - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums is None or len(nums) == 0:
return 0
max_here = min_here = max_so_far = nums[0]
for i in range(1, len(nums)):
mx, mn = max_here, min_here
max_here = max(max(mx * nums[i], nums[i]), mn * nums[i])
min_here = min(min(mx * nums[i], nums[i]), mn * nums[i])
max_so_far = max(max_here, max_so_far)
return max_so_far
This is the python solution for the Leetcode problem - Roman to Integer - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution:
# def romanToInt(self, s):
# """
# :type s: str
# :rtype: int
# """
# roman = {'I': 1, 'V': 5, 'X': 10,
# 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
# result = 0
# last = s[-1]
# for t in reversed(s):
# if t == 'C' and last in ['D', 'M']:
# result -= roman[t]
# elif t == 'X' and last in ['L', 'C']:
# result -= roman[t]
# elif t == 'I' and last in ['V', 'X']:
# result -= roman[t]
# else:
# result += roman[t]
# last = t
# return result
def romanToInt(self, s):
roman = {'I': 1, 'V': 5, 'X': 10,
'L': 50, 'C': 100, 'D': 500, 'M': 1000}
prev, total = 0, 0
for c in s:
curr = roman[c]
total += curr
# need to subtract
if curr > prev:
total -= 2 * prev
prev = curr
return total
This is the python solution for the Leetcode problem - Longest Absolute File Path - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def lengthLongestPath(self, input):
"""
:type input: str
:rtype: int
"""
if input is None or len(input) == 0:
return 0
lines = input.split('\n')
last_level_len = [0] * (len(lines) + 1); max_len = 0
for line in lines:
try:
level = line.rindex('\t') + 1
except:
level = 0
cur_len = last_level_len[level + 1] = last_level_len[level] + len(line) - level + 1
if '.' in line:
max_len = max(max_len, cur_len - 1)
return max_len
if __name__ == '__main__':
s = Solution()
print s.lengthLongestPath("dir\n file.txt")
This is the python solution for the Leetcode problem - Range Addition - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def getModifiedArray(self, length, updates):
"""
:type length: int
:type updates: List[List[int]]
:rtype: List[int]
"""
res = [0] * length
# interval problem
for t in updates:
start, end, val = t
res[start] += val
if end < length - 1:
res[end + 1] -= val
# Cumulative sums
for i in range(1, length):
res[i] = res[i] + res[i - 1]
return res
This is the java solution for the Leetcode problem - Fizz Buzz - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
import java.util.ArrayList;
import java.util.List;
class Solution {
public List fizzBuzz(int n) {
List res = new ArrayList<>();
for (int i = 1; i <= n; i++) {
String tmp = "";
if (i % 3 == 0) tmp += "Fizz";
if (i % 5 == 0) tmp += "Buzz";
if (tmp.length() == 0) tmp += String.valueOf(i);
res.add(tmp);
}
return res;
}
}
This is the java solution for the Leetcode problem - Heaters - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
public class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(heaters);
int result = Integer.MIN_VALUE;
for (int house : houses) {
// Java binarySearch return - insertPoint - 1 if not found
// This point is greater than value you want
int index = Arrays.binarySearch(heaters, house);
if (index < 0) index = -(index + 1);
int dist1 = index - 1 >= 0 ? house - heaters[index - 1] : Integer.MAX_VALUE;
int dist2 = index < heaters.length ? heaters[index] - house : Integer.MAX_VALUE;
result = Math.max(result, Math.min(dist1, dist2));
}
return result;
}
}
This is the python solution for the Leetcode problem - Minimum Increment to Make Array Unique - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def minIncrementForUnique(self, A):
"""
:type A: List[int]
:rtype: int
"""
if A is None or len(A) == 0:
return 0
res = 0
num_set = set()
duplicate = []
A.sort()
left, right = A[0], A[-1]
holes = right - left + 1
for v in A:
if v in num_set:
duplicate.append(v)
else:
num_set.add(v)
holes = holes - len(num_set)
# find a hole for these numbers
for hole in range(left + 1, right):
if holes == 0 or len(duplicate) == 0:
break
if hole not in num_set and hole > duplicate[0]:
res += hole - duplicate.pop(0)
holes -= 1
while len(duplicate) != 0:
right += 1
res += right - duplicate.pop(0)
return res
if __name__ == '__main__':
s = Solution()
# print s.minIncrementForUnique([3, 2, 1, 2, 1, 7])
# print s.minIncrementForUnique([0, 2, 2])
This is the java solution for the Leetcode problem - First Unique Character in a String - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution {
public int firstUniqChar(String s) {
int freq [] = new int[26];
for(int i = 0; i < s.length(); i ++)
freq [s.charAt(i) - 'a'] ++;
for(int i = 0; i < s.length(); i ++)
if(freq [s.charAt(i) - 'a'] == 1)
return i;
return -1;
}
}
This is the python solution for the Leetcode problem - Find Leaves 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):
# def findLeaves(self, root):
# """
# :type root: TreeNode
# :rtype: List[List[int]]
# """
# res = []
# if root is None:
# return []
# stack = [root]
# check_set = set()
# while len(stack) > 0:
# curr = stack.pop()
# check_set.add(curr)
# if curr.left:
# stack.append(curr.left)
# if curr.right:
# stack.append(curr.right)
# while len(check_set) > 0:
# curr = []
# for node in check_set:
# if (node.left is None or node.left not in check_set) and\
# (node.right is None or node.right not in check_set):
# curr.append(node)
# res.append([node.val for node in curr])
# for node in curr:
# check_set.remove(node)
# return res
def findLeaves(self, root):
res = []
self.findLeaves_helper(root, res)
return res
def findLeaves_helper(self, node, res):
if node is None:
return -1
level = 1 + max(self.findLeaves_helper(node.left, res), self.findLeaves_helper(node.right, res))
if len(res) < level + 1:
res.append([])
res[level].append(node.val)
return level
This is the python solution for the Leetcode problem - Shortest Unsorted Continuous Subarray - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
# https://leetcode.com/problems/shortest-unsorted-continuous-subarray/solution/
# def findUnsortedSubarray(self, nums):
# """
# :type nums: List[int]
# :rtype: int
# """
# snums = nums[::]
# snums.sort()
# start = len(nums)
# end = 0
# for i in range(len(nums)):
# if snums[i] != nums[i]:
# start = min(start, i)
# end = max(end, i)
# if end >= start:
# return end - start + 1
# return 0
def findUnsortedSubarray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
stack = []
l, r = len(nums), 0
for i in range(len(nums)):
while len(stack) != 0 and nums[stack[-1]] > nums[i]:
l = min(l, stack.pop())
stack.append(i)
stack = []
for i in range(len(nums) - 1, -1, -1):
while len(stack) != 0 and nums[stack[-1]] < nums[i]:
r = max(r, stack.pop())
stack.append(i)
if r > l:
return r - l + 1
return 0
# def findUnsortedSubarray(self, nums):
# smin = 2 ** 31 -1
# smax = -2 ** 31
# flag = False
# for i in range(1, len(nums)):
# if nums[i] < nums[i-1]:
# flag = True
# if flag:
# smin = min(smin, nums[i])
# flag = False
# for i in range(len(nums)-2, -1, -1):
# if nums[i] > nums[i+1]:
# flag = True
# if flag:
# smax = max(smax, nums[i])
# for l in range(len(nums)):
# if smin < nums[l]:
# break
# for r in range(len(nums)-1, -1, -1):
# if smax > nums[r]:
# break
# if r > l:
# return r - l + 1
# return 0
This is the java solution for the Leetcode problem - Transpose Matrix - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
class Solution {
public int[][] transpose(int[][] A) {
int R = A.length, C = A[0].length;
int[][] ans = new int[C][R];
for (int r = 0; r < R; ++r)
for (int c = 0; c < C; ++c) {
ans[c][r] = A[r][c];
}
return ans;
}
}
This is the java solution for the Leetcode problem - Shortest Unsorted Continuous Subarray - Leetcode Challenge - Java Solution.
Source - qiyuangong's repository.
public class Solution {
// https://leetcode.com/problems/shortest-unsorted-continuous-subarray/solution/
/* public int findUnsortedSubarray(int[] nums) {
int[] snums = nums.clone();
Arrays.sort(snums);
int start = snums.length, end = 0;
for (int i = 0; i < snums.length; i++) {
if (snums[i] != nums[i]) {
start = Math.min(start, i);
end = Math.max(end, i);
}
}
return (end - start >= 0 ? end - start + 1 : 0);
} */
public int findUnsortedSubarray(int[] nums) {
Stack < Integer > stack = new Stack < Integer > ();
int l = nums.length, r = 0;
for (int i = 0; i < nums.length; i++) {
while (!stack.isEmpty() && nums[stack.peek()] > nums[i])
l = Math.min(l, stack.pop());
stack.push(i);
}
stack.clear();
for (int i = nums.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && nums[stack.peek()] < nums[i])
r = Math.max(r, stack.pop());
stack.push(i);
}
return r - l > 0 ? r - l + 1 : 0;
}
/* public int findUnsortedSubarray(int[] nums) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
boolean flag = false;
for (int i = 1; i < nums.length; i++) {
if (nums[i] < nums[i - 1])
flag = true;
if (flag)
min = Math.min(min, nums[i]);
}
flag = false;
for (int i = nums.length - 2; i >= 0; i--) {
if (nums[i] > nums[i + 1])
flag = true;
if (flag)
max = Math.max(max, nums[i]);
}
int l, r;
for (l = 0; l < nums.length; l++) {
if (min < nums[l])
break;
}
for (r = nums.length - 1; r >= 0; r--) {
if (max > nums[r])
break;
}
return r - l < 0 ? 0 : r - l + 1;
} */
/* public int findUnsortedSubarray(int[] nums) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
boolean flag = false;
for (int i = 1; i < nums.length; i++) {
if (nums[i] < nums[i - 1])
flag = true;
if (flag)
min = Math.min(min, nums[i]);
}
flag = false;
for (int i = nums.length - 2; i >= 0; i--) {
if (nums[i] > nums[i + 1])
flag = true;
if (flag)
max = Math.max(max, nums[i]);
}
int l, r;
for (l = 0; l < nums.length; l++) {
if (min < nums[l])
break;
}
for (r = nums.length - 1; r >= 0; r--) {
if (max > nums[r])
break;
}
return r - l < 0 ? 0 : r - l + 1;
} */
}
This is the python solution for the Leetcode problem - Third Maximum Number - Leetcode Challenge - Python Solution.
Source - qiyuangong's repository.
class Solution(object):
def thirdMax(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
import Queue
pq = Queue.PriorityQueue(4)
check = set()
for n in nums:
if n in check:
continue
pq.put(n)
check.add(n)
if len(check) > 3:
check.remove(pq.get())
total = len(check)
while total < 3 and total > 1:
total -= 1
return pq.get()