Bytedance Flashcards
Add two number https://leetcode.com/problems/add-two-numbers Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.
def addTwoNumbers(self, l1, l2):
dummy = cur = ListNode(0)
carry = 0
while l1 or l2 or carry:
if l1:
carry += l1.val
l1 = l1.next
if l2:
carry += l2.val
l2 = l2.next
cur.next = ListNode(carry%10)
cur = cur.next
carry //= 10
return dummy3 Sum
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is: [ [-1, 0, 1], [-1, -1, 2] ] https://leetcode.com/problems/3sum
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
ret = []
seen = set()
nums.sort()
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]:
continue
l = i + 1
r = len(nums) - 1
while l < r:
total = nums[i] + nums[l] + nums[r]
if total == 0:
newRet = [nums[i], nums[l], nums[r]]
key = ",".join([str(i) for i in newRet])
if key not in seen:
seen.add(key)
ret.append(newRet)
l += 1
r -= 1
elif total < 0:
l += 1
else:
r -= 1
return ret
This is the answer from @caikehe and all the comments below
The main idea is to iterate every number innums.
We use the number as a target to find two other numbers which make total zero.
For those two other numbers, we move pointers,landr, to try them.
lstart from left to right.
rstart from right to left.
First, we sort the array, so we can easily moveiaround and know how to adjustlandr.
If the number is the same as the number before, we have used it as target already, continue. [1]
We always start the left pointer fromi+1because the combination of 0~ihas already been tried. [2]
Now we calculate the total:
If the total is less than zero, we need it to be larger, so we move the left pointer. [3]
If the total is greater than zero, we need it to be smaller, so we move the right pointer. [4]
If the total is zero, bingo! [5]
We need to move the left and right pointers to the next different numbers, so we do not get repeating result. [6]
We do not need to consideriafternums[i]>0, since sum of 3 positive will be always greater than zero. [7]
We do not need to try the last two, since there are no rooms forlandrpointers.
You can think of it as The last two have been tried by all others. [8]
For time complexity
Sorting takesO(NlogN)
Now, we need to think as if thenumsis really really big
We iterate through thenumsonce, and each time we iterate the whole array again by a while loop
So it isO(NlogN+N^2)~=O(N^2)
For space complexity
We didn’t use extra space except theres
So it isO(1).
Top K frequent
https://leetcode.com/problems/top-k-frequent-elements/
Given a non-empty array of integers, return the k most frequent elements.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
It’s guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
You can return the answer in any order.
class Solution(object):
def topKFrequent(self, nums, k):
hs = {}
frq = {}
for i in xrange(0, len(nums)):
if nums[i] not in hs:
hs[nums[i]] = 1
else:
hs[nums[i]] += 1
for z,v in hs.iteritems():
if v not in frq:
frq[v] = [z]
else:
frq[v].append(z)
arr = []
for x in xrange(len(nums), 0, -1):
if x in frq:
for i in frq[x]:
arr.append(i) return [arr[x] for x in xrange(0, k)]
Smallest string with swaps
https://leetcode.com/problems/smallest-string-with-swaps/
You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.
You can swap the characters at any pair of indices in the given pairs any number of times.
Return the lexicographically smallest string that s can be changed to after using the swaps.
Example 1:
Input: s = "dcab", pairs = [[0,3],[1,2]] Output: "bacd" Explaination: Swap s[0] and s[3], s = "bcad" Swap s[1] and s[2], s = "bacd"
import collections
class Solution:
def smallestStringWithSwaps(self, word: str, pairs: List[List[int]]) -> str:
jointPairs = []
tree = {}
for start, end in pairs:
if start in tree:
tree[start].append(end)
else:
tree[start] = [end]
if end in tree:
tree[end].append(start)
else:
tree[end] = [start]
visited = set()
for start in tree:
connected = set()
if start not in visited:
queue = collections.deque()
queue.append(start)
while queue:
cur = queue.popleft()
connected.add(cur)
for neighbor in tree[cur]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
jointPairs.append(connected)
print(jointPairs)
tmp = [c for c in word]
for jPair in jointPairs:
jPair = list(jPair)
jPair.sort()
chars = [tmp[i] for i in jPair]
chars.sort()
for i in range(len(jPair)):
tmp[jPair[i]] = chars[i]
return ''.join(tmp)
Swap adjacent in LR strings
https://leetcode.com/problems/swap-adjacent-in-lr-string/
In a string composed of ‘L’, ‘R’, and ‘X’ characters, like “RXXLRXRXL”, a move consists of either replacing one occurrence of “XL” with “LX”, or replacing one occurrence of “RX” with “XR”. Given the starting string start and the ending string end, return True if and only if there exists a sequence of moves to transform one string to the other.
Example:
Input: start = "RXXLRXRXL", end = "XRLXXRRLX" Output: True Explanation: We can transform start to end following these steps: RXXLRXRXL -> XRXLRXRXL -> XRLXRXRXL -> XRLXXRRXL -> XRLXXRRLX
class Solution {
public boolean canTransform(String start, String end) {
if (!start.replace("X", "").equals(end.replace("X", "")))
return false;
int p1 = 0;
int p2 = 0;
while(p1 < start.length() && p2 < end.length()){
// get the non-X positions of 2 strings
while(p1 < start.length() && start.charAt(p1) == 'X'){
p1++;
}
while(p2 < end.length() && end.charAt(p2) == 'X'){
p2++;
}
//if both of the pointers reach the end the strings are transformable
if(p1 == start.length() && p2 == end.length()){
return true;
}
// if only one of the pointer reach the end they are not transformable
if(p1 == start.length() || p2 == end.length()){
return false;
}
if(start.charAt(p1) != end.charAt(p2)){
return false;
}
// if the character is 'L', it can only be moved to the left. p1 should be greater or equal to p2.
if(start.charAt(p1) == 'L' && p2 > p1){
return false;
}
// if the character is 'R', it can only be moved to the right. p2 should be greater or equal to p1.
if(start.charAt(p1) == 'R' && p1 > p2){
return false;
}
p1++;
p2++;
}
return true;
}
}
Add 2 numbers recursive
https://leetcode.com/problems/add-two-numbers-ii
You are given twonon-emptylinked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
Example:
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
def addTwoNumbers(self, l1, l2):
len1, len2 = self.getLength(l1), self.getLength(l2)
l1 = self.addLeadingZeros(len2-len1, l1)
l2 = self.addLeadingZeros(len1-len2, l2)
c, ans = self.combineList(l1, l2)
if c>0:
l3 = ListNode(c)
l3.next = ans
ans = l3
return ans
def getLength(self, node):
l = 0
while node:
l += 1
node = node.next
return l
def addLeadingZeros(self, n, node):
for i in range(n):
new = ListNode(0)
new.next = node
node = new
return node
def combineList(self, l1, l2):
if (not l1 and not l2):
return (0, None)
c, new = self.combineList(l1.next, l2.next)
s = l1.val+l2.val+c
ans = ListNode(s%10)
ans.next = new
return (s/10, ans)
Skyline problem
https://leetcode.com/problems/the-skyline-problem/
import heapq
class Solution(object):
def getSkyline(self, buildings):
pos = sorted(set([b[0] for b in buildings] + [b[1] for b in buildings]))
alive, ret = [], []
curH, preH = 0, 0
ptr = 0
for p in pos:
while alive and alive[0][1] <= p:
heapq.heappop(alive)
while ptr < len(buildings) and buildings[ptr][0] <= p:
heapq.heappush(alive, (-buildings[ptr][2], buildings[ptr][1]))
ptr += 1
if alive:
curH = -alive[0][0]
if curH != preH:
ret.append([p, curH])
preH = curH
else:
ret.append([p, 0])
A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you aregiven the locations and height of all the buildingsas shown on a cityscape photo (Figure A), write a program tooutput the skylineformed by these buildings collectively (Figure B).
Search in rotated array
https://leetcode.com/problems/search-in-rotated-sorted-array/submissions/
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
class Solution:
def search(self, nums: List[int], target: int) -> int:
ret = -1
if not nums:
return ret
low = 0
high = len(nums)-1
l = len(nums)
mid = 0
while low <= high:
mid=(low+high)//2
if nums[mid] == target:
return mid
if nums[mid] >= nums[low]:
if nums[low] <= target <= nums[mid]:
high = mid - 1
else:
low = mid + 1
else:
if nums[mid] <= target <= nums[high]:
low = mid + 1
else:
high = mid - 1
return -1Next permutation
https://leetcode.com/problems/next-permutation
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
def nextPermutation(self, nums):
i = j = len(nums)-1
while i > 0 and nums[i-1] >= nums[i]:
i -= 1
if i == 0: # nums are in descending order
nums.reverse()
return
k = i - 1 # find the last “ascending” position
while nums[j] <= nums[k]:
j -= 1
nums[k], nums[j] = nums[j], nums[k]
l, r = k+1, len(nums)-1 # reverse the second part
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l +=1 ; r -= 1
Reverse LinkedList II
https://leetcode.com/problems/reverse-linked-list-ii/
Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL
# Definition for singly-linked list.
# class ListNode:
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
if not head:
return head
if m >= n:
return head
dummy = ListNode(None)
dummy.next = head
start = dummy
for i in range(m-1):
start = start.next
end = start.next
for i in range(n - m):
tmp = start.next
start.next = end.next
end.next = end.next.next
start.next.next = tmp
return dummy.next
Maximum product sub-array
https://leetcode.com/problems/maximum-product-subarray
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
int maxProduct(int A[], int n) {
// store the result that is the max we have found so far
int r = A[0];
// imax/imin stores the max/min product of
// subarray that ends with the current number A[i]
for (int i = 1, imax = r, imin = r; i < n; i++) {
// multiplied by a negative makes big number smaller, small number bigger
// so we redefine the extremums by swapping them
if (A[i] < 0)
swap(imax, imin);
// max/min product for the current number is either the current number itself
// or the max/min by the previous number times the current one
imax = max(A[i], imax * A[i]);
imin = min(A[i], imin * A[i]);
// the newly computed max value is a candidate for our global result
r = max(r, imax);
}
return r;
}Permutation in String
https://leetcode.com/problems/permutation-in-string/
Given two stringss1ands2, write a function to return true ifs2contains the permutation ofs1. In other words, one of the first string’s permutations is thesubstringof the second string.
For eachwindowrepresenting a substring ofs2of lengthlen(s1), we want to check if the count of the window is equal to the count ofs1. Here, the count of a string is the list of: [the number ofa’s it has, the number ofb’s,… , the number ofz’s.]
We can maintain the window by deleting the value of s2[i - len(s1)] when it gets larger thanlen(s1). After, we only need to check if it is equal to the target. Working with list values of [0, 1,…, 25] instead of ‘a’-‘z’ makes it easier to count later.
def checkInclusion(self, s1, s2):
A = [ord(x) - ord(‘a’) for x in s1]
B = [ord(x) - ord(‘a’) for x in s2]
target = [0] * 26
for x in A:
target[x] += 1
window = [0] * 26
for i, x in enumerate(B):
window[x] += 1
if i >= len(A):
window[B[i - len(A)]] -= 1
if window == target:
return True
return False
Restore IP addresses
https://leetcode.com/problems/restore-ip-addresses/
Input: “25525511135”
Output: [“255.255.11.135”, “255.255.111.35”]
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
self.ret = []
self.findIP(s, [], 0, 0)
return self.ret
def findIP(self, s, ip, i, count):
if i == len(s):
if count == 4:
self.ret.append(".".join(ip))
else:
return
if count == 4:
return
for ii in range(1, 5):
if i+ii <= len(s):
num = int(s[i:i+ii])
if 0 <= num <= 255:
if num == 0 and ii > 1:
continue
if num != 0 and s[i] == '0':
continue
self.findIP(s, ip+[s[i:i+ii]], i+ii, count+1)
Longest increasing path in matrix
https://leetcode.com/problems/longest-increasing-path-in-a-matrix/submissions/
import collections
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
self.M = matrix
length = [[-1 for i in range(len(matrix[0]))] for ii in range(len(matrix))]
ret = 0
for i in range(len(matrix)):
for ii in range(len(matrix[0])):
l = self.findLength(i, ii)
ret = max(ret, l)
return ret
@lru_cache(None)
def findLength(self, i, ii):
ret = 1
if i-1 >= 0:
if self.M[i][ii] < self.M[i-1][ii]:
ret = max(ret, 1 + self.findLength(i-1, ii))
if ii-1 >= 0:
if self.M[i][ii] < self.M[i][ii-1]:
ret = max(ret, 1 + self.findLength(i, ii-1))
if i+1 < len(self.M):
if self.M[i][ii] < self.M[i+1][ii]:
ret = max(ret, 1 + self.findLength(i+1, ii))
if ii+1 < len(self.M[0]):
if self.M[i][ii] < self.M[i][ii+1]:
ret = max(ret, 1 + self.findLength(i, ii+1))
return ret
Kth smallest in lexicographical order
https://leetcode.com/problems/k-th-smallest-in-lexicographical-order
Given integers n and k, find the lexicographically k-th smallest integer in the range from 1 to n.
Note: 1 ≤ k ≤ n ≤ 109.
Example:
Input:
n: 13 k: 2
Output:
10
Explanation:
The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.
public int findKthNumber(int n, int k) {
int curr = 1;
k = k - 1;
while (k > 0) {
int steps = calSteps(n, curr, curr + 1);
if (steps <= k) {
curr += 1;
k -= steps;
} else {
curr *= 10;
k -= 1;
}
}
return curr;
}
//use long in case of overflow
public int calSteps(int n, long n1, long n2) {
int steps = 0;
while (n1 <= n) {
steps += Math.min(n + 1, n2) - n1;
n1 *= 10;
n2 *= 10;
}
return steps;
}
