LeetCode 794. Valid Tic-Tac-Toe State - Weekly Contest 74

https://leetcode.com/contest/weekly-contest-74/problems/valid-tic-tac-toe-state/




It's a simulation, just be patient and careful.

think of all the possibilities. Classified them. use | stand for the column strike, use - for the row strike.

use the \ and / for the diagonals.

LeetCode 791. Custom Sort String - Weekly Contest 73

https://leetcode.com/contest/weekly-contest-73/problems/custom-sort-string/


First I tried to use lambda for Arrays.sort(T[]), but it doesn't work that way.

So I come up with 3 arrays of the length of 27 which covers all the chars.

the
count: char -> occurrence
map:   char -> i index
seq:     index i -> char

this way, you can easily assemble the answer.

From their sorted sequence, with given char and the respective occurrence. all within your reach in O(1).

That's crazily fast! So let's do it!

LeetCode 789. Escape The Ghosts - Weekly Contest 73

https://leetcode.com/contest/weekly-contest-73/problems/escape-the-ghosts/


Come to think of it, I realize no matter which location they are locating, the distance to the target is what really matters.

So naturally we come up with a helper function to getDistance,

then, naturally we will compare the distances and see if any ghosts are dangerously close.

That's it.

LeetCode 788. Rotated Digits - Weekly Contest 73

https://leetcode.com/contest/weekly-contest-73/problems/rotated-digits/

Quite Straight Forward,
in case of 25, 69 they change to something beautiful.
in case of 0, 1, 8, they just don't mean anything,
in case of the 3, 4, 7 they are pretty much deal breaker.

the conditions are messy so I speed them up with an array.

LeetCode 780. Reaching Points - Weekly Contest 71

https://leetcode.com/contest/weekly-contest-71/problems/reaching-points/

A move consists of taking a point (x, y) and transforming it to either (x, x+y) or (x+y, y).

Given a starting point (sx, sy) and a target point (tx, ty), return True if and only if a sequence of moves exists to transform the point (sx, sy) to (tx, ty). Otherwise, return False.

LeetCode 781. Rabbits in Forest - Weekly Contest 71

https://leetcode.com/contest/weekly-contest-71/problems/rabbits-in-forest/

In a forest, each rabbit has some color. Some subset of rabbits (possibly all of them) tell you how many other rabbits have the same color as them. Those answers are placed in an array.

Return the minimum number of rabbits that could be in the forest.

LeetCode 783. Minimum Distance Between BST Nodes - Weekly Contest 71

https://leetcode.com/contest/weekly-contest-71/problems/minimum-distance-between-bst-nodes/
Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.

LeetCode 779. K-th Symbol in Grammar - Weekly Contest 70

https://leetcode.com/contest/weekly-contest-70/problems/k-th-symbol-in-grammar/

LeetCode 771. Jewels and Stones - Weekly Contest 69

https://leetcode.com/contest/weekly-contest-69/problems/jewels-and-stones/

LeetCode 775. Global and Local Inversions - Weekly Contest 69

https://leetcode.com/contest/weekly-contest-69/problems/global-and-local-inversions/

LeetCode 768. Max Chunks to Make Sorted (ver. 2) - Weekly Contest 68

https://leetcode.com/contest/weekly-contest-68/problems/max-chunks-to-make-sorted-ver-2/

LeetCode 769. Max Chunks To Make Sorted (ver. 1) - Weekly Contest 68

https://leetcode.com/contest/weekly-contest-68/problems/max-chunks-to-make-sorted-ver-1/

LeetCode 766. Toeplitz Matrix - Weekly Contest 68

https://leetcode.com/contest/weekly-contest-68/problems/toeplitz-matrix/

LC 765. Couples Holding Hands - Weekly Contest 67 - LeetCode

N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.

The people and seats are represented by an integer from 0 to 2N-1, the couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2N-2, 2N-1).

The couples' initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.

Example 1:

Input: row = [0, 2, 1, 3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.
Example 2:

Input: row = [3, 2, 0, 1]
Output: 0
Explanation: All couples are already seated side by side.
Note:

len(row) is even and in the range of [4, 60].
row is guaranteed to be a permutation of 0...len(row)-1.

LC 764. Largest Plus Sign - Weekly Contest 67 - LeetCode

In a 2D grid from (0, 0) to (N-1, N-1), every cell contains a 1, except those cells in the given list mines which are 0. What is the largest axis-aligned plus sign of 1s contained in the grid? Return the order of the plus sign. If there is none, return 0.

An "axis-aligned plus sign of 1s of order k" has some center grid[x][y] = 1 along with 4 arms of length k-1 going up, down, left, and right, and made of 1s. This is demonstrated in the diagrams below. Note that there could be 0s or 1s beyond the arms of the plus sign, only the relevant area of the plus sign is checked for 1s.

Examples of Axis-Aligned Plus Signs of Order k:

Order 1:
000
010
000

Order 2:
00000
00100
01110
00100
00000

Order 3:
0000000
0001000
0001000
0111110
0001000
0001000
0000000
Example 1:

Input: N = 5, mines = [[4, 2]]
Output: 2
Explanation:
11111
11111
11111
11111
11011
In the above grid, the largest plus sign can only be order 2.  One of them is marked in bold.
Example 2:

Input: N = 2, mines = []
Output: 1
Explanation:
There is no plus sign of order 2, but there is of order 1.
Example 3:

Input: N = 1, mines = [[0, 0]]
Output: 0
Explanation:
There is no plus sign, so return 0.
Note:

N will be an integer in the range [1, 500].
mines will have length at most 5000.
mines[i] will be length 2 and consist of integers in the range [0, N-1].
(Additionally, programs submitted in C, C++, or C# will be judged with a slightly smaller time limit.)


首先是把十字架的需求分解成四个方向。
这样理解就有思路了。
接着一看可以上动归。
四个方向分别开个dp数组，动态规划，全是O(N^N)的时空复杂度。
最后扫一遍得出结果，最边缘的地方特殊情况放最后处理。

最终时空复杂度O(N^N)

LC 762. Prime Number of Set Bits in Binary Representation - Weekly Contest 67 - LeetCode

Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.

(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)

Example 1:

Input: L = 6, R = 10
Output: 4
Explanation:
6 -> 110 (2 set bits, 2 is prime)
7 -> 111 (3 set bits, 3 is prime)
9 -> 1001 (2 set bits , 2 is prime)
10->1010 (2 set bits , 2 is prime)
Example 2:

Input: L = 10, R = 15
Output: 5
Explanation:
10 -> 1010 (2 set bits, 2 is prime)
11 -> 1011 (3 set bits, 3 is prime)
12 -> 1100 (2 set bits, 2 is prime)
13 -> 1101 (3 set bits, 3 is prime)
14 -> 1110 (3 set bits, 3 is prime)
15 -> 1111 (4 set bits, 4 is not prime)
Note:

L, R will be integers L <= R in the range [1, 10^6].
R - L will be at most 10000.

LC 763. Partition Labels - Weekly Contest 67 - LeetCode

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:
Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.
Note:

S will have length in range [1, 500].
S will consist of lowercase letters ('a' to 'z') only.


这题要求最多的partition。
那么我们从左到右遍历一遍，用贪心算法。
能分马上分。除非这个字母在后边还出现而不可分离。
那么聪明的读者可能想到了，我怎么知道这个/些字符在后边还有没有，有的话在多后？
我这里采用的是先扫一遍用HashMap把每个char的起始坐标给缓存起来，
第二遍直接查缓存，进而得出结果。

时间复杂度就是O(n)