LeetCode 684. Redundant Connection

We are given a “tree” in the form of a 2D-array, with distinct values for each node.

In the given 2D-array, each element pair [u, v] represents that v is a child of u in the tree.

We can remove exactly one redundant pair in this “tree” to make the result a tree.

You need to find and output such a pair. If there are multiple answers for this question, output the one appearing last in the 2D-array. There is always at least one answer.

Example 1:

1
2
3
4
5
6
Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: Original tree will be like this:
1
/ \
2 - 3

Example 2:

1
2
3
4
5
6
Input: [[1,2], [1,3], [3,1]]
Output: [3,1]
Explanation: Original tree will be like this:
1
/ \\
2 3

Note:

The size of the input 2D-array will be between 1 and 1000.

Every integer represented in the 2D-array will be between 1 and 2000.

LeetCode 683. K Empty Slots

There is a garden with N slots. In each slot, there is a flower. The N flowers will bloom one by one in N days. In each day, there will be exactly one flower blooming and it will be in the status of blooming since then.

Given an array flowers consists of number from 1 to N. Each number in the array represents the place where the flower will open in that day.

For example, flowers[i] = x means that the unique flower that blooms at day i will be at position x, where i and x will be in the range from 1 to N.

Also given an integer k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k and these flowers are not blooming.

If there isn’t such day, output -1.

Example 1:

1
2
3
4
5
Input:
flowers: [1,3,2]
k: 1
Output: 2
Explanation: In the second day, the first and the third flower have become blooming.

Example 2:

1
2
3
4
Input:
flowers: [1,2,3]
k: 1
Output: -1

Note:

  1. The given array will be in the range [1, 20000].

无题

现在离家正好四个星期,匹村的温度像过山车,还好我没有感冒。

关于舰C直连

关于直连

舰C游戏不允许非日本ip访问,然而在国内用代理访问经常会偶遇猫神。我现在即使在一个没有墙的地方,距离日本却隔了半个地球,用我的服务器也总是狂猫不止。没办法就只能琢磨琢磨直连了。

注意⚠️:由于舰C本身就是禁止非日本ip访问,使用直连方法可能会有不可预估的风险,包括但不限于封号等后果。如果担心这个问题请全程代理。

准备工作:一个可用的日本代理,如ss。不要用全局vpn。

其实也可以使用改hosts的方法来使用反向代理服务器实现直连,但是反代不是这篇文章的内容,所以请自行搜索。这篇文章的方法适合手上有代理,但是连接不是很稳定的玩家。

LeetCode 617. Merge Two Binary Trees

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
Output:
Merged tree:
3
/ \
4 5
/ \ \
5 4 7

Note: The merging process must start from the root nodes of both trees.

LeetCode 606. Construct String from Binary Tree

You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.

The null node needs to be represented by empty parenthesis pair “()”. And you need to omit all the empty parenthesis pairs that don’t affect the one-to-one mapping relationship between the string and the original binary tree.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
Input: Binary tree: [1,2,3,4]
1
/ \
2 3
/
4
Output: "1(2(4))(3)"
Explanation: Originallay it needs to be "1(2(4)())(3()())",
but you need to omit all the unnecessary empty parenthesis pairs.
And it will be "1(2(4))(3)".

Example 2:

1
2
3
4
5
6
7
8
9
10
11
Input: Binary tree: [1,2,3,null,4]
1
/ \
2 3
\
4
Output: "1(2()(4))(3)"
Explanation: Almost the same as the first example,
except we can't omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.

LeetCode 605. Can Place Flowers

Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.

Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.

Example 1:

1
2
Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

Example 2:

1
2
Input: flowerbed = [1,0,0,0,1], n = 2
Output: False

Note:

  1. The input array won’t violate no-adjacent-flowers rule.
  2. The input array size is in the range of [1, 20000].
  3. n is a non-negative integer which won’t exceed the input array size.

LeetCode 560. Subarray Sum Equals K

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

1
2
Input:nums = [1,1,1], k = 2
Output: 2

Note:

  1. The length of the array is in range [1, 20,000].
  2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

LeetCode 565. Array Nesting

A zero-indexed array A consisting of N different integers is given. The array contains all integers in the range [0, N - 1].

Sets S[K] for 0 <= K < N are defined as follows:

S[K] = { A[K], A[A[K]], A[A[A[K]]], … }.

Sets S[K] are finite for each K and should NOT contain duplicates.

Write a function that given an array A consisting of N integers, return the size of the largest set S[K] for this array.

Example 1:

1
2
3
4
5
6
7
Input: A = [5,4,0,3,1,6,2]
Output: 4
Explanation:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

Note:

  1. N is an integer within the range [1, 20,000].
  2. The elements of A are all distinct.
  3. Each element of array A is an integer within the range [0, N-1].

LeetCode 540. Single Element in a Sorted Array

Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

Example 1:

1
2
Input: [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:

1
2
Input: [3,3,7,7,10,11,11]
Output: 10

Note: Your solution should run in O(log n) time and O(1) space.