KK's blog

Mock 002 Print 5-min intervals

Posted on 2022-03-07 Edited on 2026-06-03 Disqus:

Input - (“mon 10:00 am”, mon 11:00 am)
Output - [11005, 11010, 11015…11100]
Output starts with 1 if the day is monday, 2 if tuesday and so on till 7 for sunday
Append 5 min interval times to that till the end time
So here it is 10:05 as first case, so its written as 11005
2nd is 10:10 so its written as 11010

题目大意：

DD的面经题，给定开始时间和结束时间，求5分钟的间隔时间，注意要round to 5min

解题思路：

由于非10进制，所以开一个类来计算进制

解题步骤：

N/A

注意事项：

实现lt函数
12am, 12pm要mod 12
(0 if parts[2] == ‘am’ else 12)加括号
开始时间到到5分钟端点，结束时间加1分钟，由于只实现了lt

Python代码：

DAY_DICT = {'mon': 1, 'tue': 2, 'wed': 3, 'thu': 4, 'fri': 5, 'sat': 6, 'sun': 7}
class Solution(TestCases):

    def get_intervals(self, start, end) -> List:
        start_time = Time(start)
        end_time = Time(end)
        if start_time.min % 5 > 0:
            start_time.add(5 - start_time.min % 5)
        end_time.add(1)
        res = []
        while start_time < end_time:
            res.append(start_time.get_numeric())
            start_time.add(5)
        return res


class Time:

    def __init__(self, time):
        parts = time.split(' ')
        day = DAY_DICT[parts[0]]
        time_parts = parts[1].split(':')
        hour = int(time_parts[0]) % 12 + (0 if parts[2] == 'am' else 12) # remember paren (0 ...12), and % 12
        self.day = day
        self.hour = hour
        self.min = int(time_parts[1])

    def __lt__(self, other):
        if self.day < other.day or (self.day == other.day and self.hour < other.hour) or \
                (self.day == other.day and self.hour == other.hour and self.min < other.min):
            return True
        else:
            return False

    def get_numeric(self):
        return self.day * 10000 + self.hour * 100 + self.min

    def add(self, mins):
        self.min += mins
        if self.min == 60:
            self.min = 0
            self.hour += 1
        if self.hour == 24:
            self.hour = 0
            self.day += 1
        if self.day == 7:
            self.day = 0

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

Karat 002 Longest Common Continuous Subarray

Posted on 2022-03-04 Edited on 2026-06-03 Disqus:

[
[“3234.html”, “xys.html”, “7hsaa.html”], // user1
[“3234.html”, “sdhsfjdsh.html”, “xys.html”, “7hsaa.html”] // user2
]

输出两个user的最长连续且相同的访问记录。

题目大意：

求连续最长子数组

解题思路：

类似于LeetCode 1143先求最长公共子字符串。

LeetCode 1143 Longest Common Subsequence, 求最长公共子字符串
Karat 002 Longest Common Continuous Subarray 一样的题目，结果类型不同：最长长度和结果

不同之处在于：

由于是连续，所以递归只有相同的情况，其他情况为0。
答案不是最后一位，而是全局最值

递归式为

1 2	dp[i][j] = dp[i - 1][j - 1] + 1 if text1[i - 1] == text2[j - 1] = 0

解题步骤：

N/A

注意事项：

递归只有一种情况
答案需求全局

Python代码：

# dp[i][j] = dp[i - 1][j - 1] + 1 if text1[i - 1] == text2[j - 1]
#          = 0
def longestCommonContinuous(self, text1: str, text2: str) -> int:
	dp = [[0 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]
	res = 0
	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			if text1[i - 1] == text2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
				res = max(res, dp[i][j])
	return res

优化空间：

def longestCommonContinuous(self, text1: str, text2: str) -> int:
	dp = [[0 for _ in range(len(text2) + 1)] for _ in range(2)]
	res = 0
	for i in range(1, len(text1) + 1):
		for j in range(1, len(dp[0])):
			if text1[i - 1] == text2[j - 1]:
				dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1
				res = max(res, dp[i % 2][j])
	return res

回到原题，输入是列表而不是字符串，但原理一样。还有需要输出公共结果，而不是数字

Python代码：

def longestCommonContinuousSubarray(self, history1, history2):
	dp = [[0 for _ in range(len(history2) + 1)] for _ in range(len(history1) + 1)]
	max_len, res = 0, []
	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			if history1[i - 1] == history2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
				if dp[i][j] > max_len:
					max_len = dp[i][j]
					res = history1[i - dp[i][j]:i]
	return res

算法分析：

时间复杂度为O(nm)，空间复杂度O(nm)

LeetCode 002 Add Two Numbers

Posted on 2022-03-04 Edited on 2026-06-04 Disqus:

LeetCode

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

The number of nodes in each linked list is in the range [1, 100].

0 <= Node.val <= 9

It is guaranteed that the list represents a number that does not have leading zeros.

题目大意：

数位链表(从最低位到最高位)相加

算法思路：

类似于merge sort

注意事项：

其中一个可能较长，所以主循环出来后还要继续循环较长的链表，类似于merge sort
所有链表遍历完后，carry可能还会是1，要加一个if语句特别处理

Python代码：

def addTwoNumbers(self, l1: 'ListNode', l2: 'ListNode') -> 'ListNode':
	fake_head = ListNode(0)
	carry = 0
	it, it2, it_res = l1, l2, fake_head
	while it or it2:
		value = carry
		if it:
			value += it.val
			it = it.next
		if it2:
			value += it2.val
			it2 = it2.next
		carry = 1 if value >= 10 else 0
		value %= 10
		it_res.next = ListNode(value)
		it_res = it_res.next
	if carry == 1:
		it_res.next = ListNode(1)
	return fake_head.next

算法分析：

时间复杂度为O(n + m)，空间复杂度O(1)

LeetCode 224 Basic Calculator

Posted on 2022-03-01 Edited on 2026-06-03 Disqus:

LeetCode

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = “1 + 1”
Output: 2

Example 2:

Input: s = “ 2-1 + 2 “
Output: 3

Example 3:

Input: s = “(1+(4+5+2)-3)+(6+8)”
Output: 23

Constraints:

`1 <= s.length <= 3 10⁵*sconsists of digits,‘+’,‘-‘,‘(‘,‘)’, and‘ ‘

.
*

s

represents a valid expression.
*

‘+’is **not** used as a unary operation (i.e.,“+1”and“+(2 + 3)”

is invalid).
*

‘-‘could be used as a unary operation (i.e.,“-1”and“-(2 + 3)”` is valid).
There will be no two consecutive operators in the input. Every number and running calculation will fit in a signed 32-bit integer.

题目大意：

实现字符串加减，但有括号。

算法思路：

括号题优先考虑用Stack。这里Stack不能只存数，因为括号前可以是正负，所以将这个信息以+1或-1也压入栈（栈不能混合字符和数字）
所以用一个stack，num是一个数，res是括号内的累积结果。num在处理完每一个数都要重设，res和sign在处理完每个括号都要重设。

运用模板，代码中含五种情况：空格，运算符，数字，左右括号。左括号将res和sign入栈，右括号将res和sign出栈，计算结果存在res

LeetCode 224 Basic Calculator 括号加减法, 同一层括号内求和遇括号入栈
LeetCode 227 Basic Calculator II 加减乘除, 和的每一项入栈，方便出栈计乘除
LeetCode 772 Basic Calculator III 加减乘除括号, L227的递归版

注意事项：

括号前可以是正负，所以将这个信息以+1或-1也压入栈
左括号无论前面是正负都要入栈
num在处理完每一个数都要重设，res和sign在处理完每个括号都要重设

Python代码：

# 1-(2+3)+(4+5)
# 1+2+3
def calculate(self, s: str) -> int:
	res, num, stack, sign = 0, 0, [], 1
	s += '+'
	for char in s:
		if char == ' ':
			continue
		if char.isdigit():
			num = num * 10 + int(char)
		if char == '+':
			res += sign * num
			sign = 1
			num = 0
		if char == '-':
			res += sign * num
			sign = -1
			num = 0
		if char == '(':
			stack.append(res) # [-4+]
			stack.append(sign) #
			sign = 1
			res = 0
		if char == ')':
			res += sign * num # 9
			prev_sign = stack.pop() # +
			tmp = stack.pop() # -4
			res = tmp + prev_sign * res # -4 +9
			# sign = 1 next one will be +-, so num = 0 and sign doesn't matter
			num = 0
		# else:
		 #   res += char
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

LeetCode 238 Product of Array Except Self

Posted on 2022-03-01 Edited on 2026-06-03 Disqus:

LeetCode

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

2 <= nums.length <= 10<sup>5</sup> -30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1)extra space complexity? (The output array *does not count as extra space for space complexity analysis.)

题目大意：

求每个数对应的结果：数组出自己外全部相乘

解题思路：

累计思想

解题步骤：

N/A

注意事项：

两轮计算，从左到右，再从右到左，用res数组作为临时计算结果。从左到右，计算res[i] = num[0] x nums[i - 1], 从右到左类似
res初始值为1，因为从左到右是跳过第0个值的，而从右到左中res[i] *= product，若初始为0，结果res[i] = 0

Python代码：

def productExceptSelf(self, nums: List[int]) -> List[int]:
	n = len(nums)
	res, product = [1] * n, nums[0]
	for i in range(1, n):
		res[i] = product # [1, 1]
		product *= nums[i]
	product = nums[-1] # 2
	for i in range(n - 2, -1, -1):
		res[i] *= product # [2, 1]
		product *= nums[i]
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

若可以用除法算法II解题思路：

按照定义用数学方法，但只要注意一个0和两个0的情况

Python代码：

def productExceptSelf(self, nums: List[int]) -> List[int]:
	product, zero_count = 1, 0
	for n in nums:
		if n != 0:
			product *= n
		else:
			zero_count += 1
	if zero_count > 1:
		return [0] * len(nums)
	res = []
	for i in range(len(nums)):
		if nums[i] == 0:
			res.append(product)
		elif zero_count > 0:
			res.append(0)
		else:
			res.append(int(product / nums[i]))
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(1)