KK's blog

Karat 004 Ads Conversion

Posted on 2022-02-12 Edited on 2022-02-21 Disqus:

A list of user ids + IPs, a list of user ids who have made purchases, a list of advertisement
clicks with user IPs.
Each user id has at most 1 IP.

Output: for each ad, output the number of clicks and the number of purchases.

completed_purchase_user_ids = ["123"]

ad_clicks = [
    #"IP_Address,Time,Ad_Text",
    "127.0.0.1,2011-01-03 09:21:22,black pen"]

all_user_ips = [
    #"User_ID,IP_Address",
        "123,127.0.0.1"]

输出:
black pen, 1 click, 1 purchase

题目大意：

给定购买记录，click记录，ip地址。求每个产品点击数和购买次数

解题思路：

此题比较直观，点击数直接可以从click记录中获得，购买次数就是将三个表格join一起获得

解题步骤：

N/A

注意事项：

Python代码：

def get_ad_clicks_purchases(self, completed_purchase_user_ids, ad_clicks, all_user_ips):
	# get clicks
	product_to_clicks = collections.defaultdict(int)
	for ad_click in ad_clicks:
		parts = ad_click.split(',')
		product_to_clicks[parts[2]] += 1

	# get purchases
	userid_to_ip = collections.defaultdict(str)
	for all_user_ip in all_user_ips:
		parts = all_user_ip.split(',')
		userid_to_ip[parts[0]] = parts[1]

	ip_to_product = collections.defaultdict(str)
	for ad_click in ad_clicks:
		parts = ad_click.split(',')
		ip_to_product[parts[0]] = parts[2]

	product_to_purchase = collections.defaultdict(int)
	for user_id in completed_purchase_user_ids:
		ip = userid_to_ip[user_id]
		product = ip_to_product[ip]
		product_to_purchase[product] += 1

	res = []
	for product, click in product_to_clicks.items():
		res.append((product, click, product_to_purchase[product]))
	return res

算法分析：

时间复杂度为O(n + m + p)，空间复杂度O(n + m + p), n, m, p分别每个表的大小

LeetCode 498 Diagonal Traverse

Posted on 2022-02-12 Edited on 2022-02-28 Disqus:

LeetCode

Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]

Example 2:

Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]

Constraints:

m == mat.length n == mat[i].length
1 <= m, n <= 104 1 <= m * n <= 104
* -105 <= mat[i][j] <= 105

题目大意：

按类对角线梅花间竹地遍历每个元素，输出最后结果

找规律解题思路：

边界条件很难找，而且每一层的结束点也和矩阵的长度或宽度有关。先找规律，可以看出

1	每层的所有元素下标和相等

正常从左到右从上到下遍历矩阵，用一个dict来每层的每一个数，可以看出这些数的顺序都是按题目要求的，只不过是正序或逆序，所以最后按照奇偶决定是否正序或逆序加入到结果

解题步骤：

从左到右从上到下遍历矩阵，dict[i + j]来加入每层的每一个数
dict的key的范围容易得知，按照奇偶决定是否正序或逆序加入到结果

注意事项：

dict[i + j]来加入每层的每一个数
dict的key的最大值为len(mat) + len(mat[0]) - 1

Python代码：

def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
	groups = collections.defaultdict(list)
	for i in range(len(mat)):
		for j in range(len(mat[0])):
			groups[i + j].append(mat[i][j])
	res = []
	for i in range(len(mat) + len(mat[0]) - 1):
		if i % 2 == 1:
			res.extend(groups[i])
		else:
			res.extend(groups[i][::-1])
	return res

算法分析：

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

按题意II解题思路：

Python代码：

def print_diagnals(matrix):
    if not matrix or not matrix[0]:
        return []
    res = []
    is_reversed = True
    # all diagnal starting from top row
    for col in range(len(matrix[0])):
        diag_row, diag_col = 0, col
        one_print = []
        while diag_row < len(matrix) and diag_col >= 0:
            one_print.append(matrix[diag_row][diag_col])
            diag_row += 1
            diag_col -= 1
        if is_reversed:
            res.extend(one_print[::-1])
        else:
            res.extend(one_print)
        is_reversed = not is_reversed
    # diagnal start rightmost columns
    for row in range(1, len(matrix)):
        diag_row, diag_col = row, len(matrix[0]) - 1
        one_print = []
        while diag_row < len(matrix) and diag_col >= 0:
            one_print.append(matrix[diag_row][diag_col])
            diag_row += 1
            diag_col -= 1
        if is_reversed:
            res.extend(one_print[::-1])
        else:
            res.extend(one_print)
        is_reversed = not is_reversed
    return res

算法分析：

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

LeetCode 1779 Find Nearest Point That Has the Same X or Y Coordinate

Posted on 2022-02-08 Disqus:

LeetCode

You are given two integers, x and y, which represent your current location on a Cartesian grid: (x, y). You are also given an array points where each points[i] = [ai, bi] represents that a point exists at (ai, bi). A point is valid if it shares the same x-coordinate or the same y-coordinate as your location.

Return the index (0-indexed) of the valid point with the smallest Manhattan distance from your current location. If there are multiple, return the valid point with the smallest index. If there are no valid points, return -1.

The Manhattan distance between two points (x1, y1) and (x2, y2) is abs(x1 - x2) + abs(y1 - y2).

Example 1:

Input: x = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]]
Output: 2
Explanation: Of all the points, only [3,1], [2,4] and [4,4] are valid. Of the valid points, [2,4] and [4,4] have the smallest Manhattan distance from your current location, with a distance of 1. [2,4] has the smallest index, so return 2.

Example 2:

Input: x = 3, y = 4, points = [[3,4]]
Output: 0
Explanation: The answer is allowed to be on the same location as your current location.

Example 3:

Input: x = 3, y = 4, points = [[2,3]]
Output: -1
Explanation: There are no valid points.

Constraints:

1 <= points.length <= 104 points[i].length == 2
* 1 <= x, y, ai, bi <= 104

题目大意：

给定一个坐标和一堆坐标，这个坐标与某个点在同一条y轴或x轴上叫合法点，求它到这些点的最小曼哈顿距离对应的点的下标，若有多个结果，返回最小的数组下标。

解题思路：

Easy题，根据题意求

解题步骤：

N/A

注意事项：

Python代码：

def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:
	min_dis = float('inf')
	res = -1
	for i, (_x, _y) in enumerate(points):
		if x == _x or y == _y:
			if abs(x - _x) + abs(y - _y) < min_dis:
				min_dis = abs(x - _x) + abs(y - _y)
				res = i
			elif abs(x - _x) + abs(y - _y) == min_dis and i < res:
				res = i
	return res

算法分析：

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

LeetCode 1761 Minimum Degree of a Connected Trio in a Graph

Posted on 2022-02-08 Disqus:

LeetCode

You are given an undirected graph. You are given an integer n which is the number of nodes in the graph and an array edges, where each edges[i] = [ui, vi] indicates that there is an undirected edge between ui and vi.

A connected trio is a set of three nodes where there is an edge between every pair of them.

The degree of a connected trio is the number of edges where one endpoint is in the trio, and the other is not.

Return the minimum degree of a connected trio in the graph, or -1 if the graph has no connected trios.

Example 1:

Input: n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]
Output: 3
Explanation: There is exactly one trio, which is [1,2,3]. The edges that form its degree are bolded in the figure above.

Example 2:

Input: n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]
Output: 0
Explanation: There are exactly three trios:
1) [1,4,3] with degree 0.
2) [2,5,6] with degree 2.
3) [5,6,7] with degree 2.

Constraints:

2 <= n <= 400 edges[i].length == 2
`1 <= edges.length <= n (n-1) / 2*1 <= u_i, v_i <= n*u_i != v_i`
* There are no repeated edges.

题目大意：

给定一个图，trio是三个节点直接互相相连，而度数表示连着trio的边的个数

解题思路：

根据定义，找出所有三个节点的组合，判断是否trio，然后根据trio的每个节点的度数总和 - 6即为所求
遍历所有三个节点组合时，会重复了两次。所以一个优化是，先按度数排序节点，若节点度数大于等于最小度数除以3，跳出循环。因为这个最小度数的节点已经大于等于3，trio里其他两个度数比它大的节点的度数更加会大于最小度数除以3，这样总度数肯定大于此时的最小度数

解题步骤：

N/A

注意事项：

根据定义，找出所有三个节点的组合u -> v, v -> w, w是否在u中，判断是否trio。先按度数排序节点，若节点度数大于等于最小度数除以3，跳出循环
邻接图用set，因为Line 13查找w是否在u中可以提高效率
min_degree / 3不是// 3

Python代码：

def minTrioDegree(self, n: int, edges: List[List[int]]) -> int:
	graph = collections.defaultdict(set) # use set coz if w in graph[u]
	for u, v in edges:
		graph[u].add(v)
		graph[v].add(u)

	min_degree = float('inf')
	for u in sorted(range(1, n + 1), key=lambda x: len(graph[x])):
		if len(graph[u]) >= min_degree / 3: # remember / 3 not // 3
			break
		for v in graph[u]:
			for w in graph[v]:
				if w in graph[u]:
					min_degree = min(min_degree, len(graph[u]) + len(graph[v]) + len(graph[w]))
	return min_degree - 6 if min_degree != float('inf') else -1

算法分析：

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

LeetCode 979 Distribute Coins in Binary Tree

Posted on 2022-02-08 Disqus:

LeetCode

You are given the root of a binary tree with n nodes where each node in the tree has node.val coins. There are n coins in total throughout the whole tree.

In one move, we may choose two adjacent nodes and move one coin from one node to another. A move may be from parent to child, or from child to parent.

Return the minimum number of moves required to make every node have exactly one coin.

Example 1:

Input: root = [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.

Example 2:

Input: root = [0,3,0]
Output: 3
Explanation: From the left child of the root, we move two coins to the root [taking two moves]. Then, we move one coin from the root of the tree to the right child.

Constraints:

The number of nodes in the tree is n. 1 <= n <= 100
0 <= Node.val <= n The sum of all Node.val is n.

题目大意：

二叉树某些节点含有硬币，求将这些硬币推向其他节点，使得所有节点都有一个硬币，求总移动次数

解题思路：

先思考，若硬币都在root，也就是求所有节点的路径和。可以用每个节点的路径和求和，也可以定义dfs返回节点数，用全局变量加左右数，每轮递归都加一次，所以每个节点被加了其路径长度的次数。本算法采用后者
下面思考若硬币不在root，由于硬币可以从儿子给父亲，这是双向的，所以dfs定义为儿子给父亲的硬币数，若节点没有硬币，返回值会是负数，也就是父亲给儿子硬币，此时这个负数正是以此节点为root的数的总的节点数，所以与上述定义一致。
所以返回root.val + left + right - 1，left和right都是负数，left + right - 1是树的大小的负数，此结果为剩余硬币推给父亲的硬币数
res += abs(left) + abs(right)左子树和右子树所有节点一起走一条边的路径和

解题步骤：

N/A

注意事项：

dfs定义为儿子给父亲的硬币数(若有硬币)，同时是子树的节点数的负数(若无硬币)

Python代码：

def distributeCoins(self, root: TreeNode) -> int:
	res = 0

	def dfs(root):
		if not root:
			return 0
		nonlocal res
		left = dfs(root.left)
		right = dfs(root.right)
		res += abs(left) + abs(right)
		return root.val + left + right - 1

	dfs(root)
	return res

算法分析：

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