DartsInter-Uni Programming Contest Tasks Leaderboard Contest

字数统计: 1.6k字   |   阅读时长: 9min

Description：

Darts
https://interunia.unswcpmsoc.com/task/Darts/

Thinking：

This contest is harder than I imaged, this is the second task, and I spent a lot of time but when I checked the Leaderboard and no one has solved it yet, I feel a little bit better.
At first, I thought of simply judging whether this point is in the middle of this circle, using Euclidean distance calculation. But later I found that when there are n circles and m darts, the amount of data is surprisingly large. After the brute force cracking timed out, I had to consider a new method.

We can use the gridded Spatial Indexing, the specific steps are as follows:

1. Spatial division: Divide the entire plane into grids of equal size (Grid), and map the target and dart to the corresponding grid.

Purpose:

  • Reduce the number of targets that need to be calculated.
  • For each dart, you only need to check the targets in its grid and adjacent grids.

2. Map Targets to Grids:

  • Calculate the bounding box of each target.
    • Lower-left corner: ( (x_i - r_i, y_i - r_i) )
    • Upper-right corner: ( (x_i + r_i, y_i + r_i) )
  • Record all grid cells covered by this rectangle and add the target index to these grid cells.

3. Map Darts to Grids:

For each dart, calculate the grid coordinates where it is located.

4. Check if the Dart Hits a Target:

  • For each dart, check all targets in its grid and the adjacent 8 grids.
  • Calculate the distance from the dart to the center of each target and determine whether it is less than or equal to the square of the target’s radius, i.e., ( (dx - x_i)^2 + (dy - y_i)^2 \leq r_i^2 ).

Grid Division Parameters

Grid size (GRID_SIZE):

  • Choose an appropriate grid size, such as 500.
  • The choice of grid size requires a trade-off between space and time efficiency.
1
2
3
4
5
auto get_grid_cell = [&](long long x_n, long long y_n) {
    int gx = int((x_n - min_x) / s);
    int gy = int((y_n - min_y) / s);
    return make_pair(gx, gy);
};

Coordinate mapping function:

Maps actual coordinates to grid coordinates.

  • s is the actual length of each grid cell.
  • $min_x$ and $min_y$ are the minimum values among all target and dart coordinates, used to shift the coordinates.

Mapping Targets to Grids

  • Iterate over all targets and calculate their covered grid ranges.
  • In these grids, record the indices of the targets.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for (int idx = 0; idx < n; ++idx) {
    int x, y, r;
    tie(x, y, r) = circles[idx];
    long long x_min = x - r;
    long long x_max = x + r;
    long long y_min = y - r;
    long long y_max = y + r;
    auto [gx_min, gy_min] = get_grid_cell(x_min, y_min);
    auto [gx_max, gy_max] = get_grid_cell(x_max, y_max);
    for (int gx = gx_min; gx <= gx_max; ++gx) {
        for (int gy = gy_min; gy <= gy_max; ++gy) {
            long long key = get_grid_key(gx, gy);
            grid[key].push_back(idx); // 存储靶子索引
        }
    }
}

Mapping Darts to Grids

  • For each dart, calculate the grid cell it belongs to.
  • No need to store darts in grids; we process them directly.

Checking if Darts Hit Targets

  • For each dart, get its grid coordinates ( (gx, gy) ).
  • Check the dart’s grid cell and its 8 adjacent grid cells.
  • For each target in these grids, calculate the distance to the dart.
  • If the distance squared is less than or equal to the target’s radius squared, increment the counter.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
for (const auto& p : points) {
    int dx = p.first;
    int dy = p.second;
    auto [gx, gy] = get_grid_cell(dx, dy);
    bool found = false;
    
    // Check the grid and the 8 adjacent grids
    for (int ix = gx - 1; ix <= gx + 1; ++ix) {
        for (int iy = gy - 1; iy <= gy + 1; ++iy) {
            long long key = get_grid_key(ix, iy);
            if (grid.count(key)) {
                const auto& circle_indices = grid[key];
                for (int idx : circle_indices) {
                    int x, y, r;
                    tie(x, y, r) = circles[idx];
                    // caculate the distance
                    long long dx_sq = (long long)(dx - x) * (dx - x);
                    long long dy_sq = (long long)(dy - y) * (dy - y);
                    long long r_sq = (long long)r * r;
                    if (dx_sq + dy_sq <= r_sq) {
                        ans++;
                        found = true;
                        break; // The dart has found the target, check the next dart
                    }
                }
            }
            if (found) break;
        }
        if (found) break;
    }
}

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import math

n, m = map(int, input().split())

circles = []

min_x = min_y = float('inf')
max_x = max_y = float('-inf')

for _ in range(n):
    x, y, r = map(int, input().split())
    circles.append((x, y, r))
    min_x = min(min_x, x - r)
    max_x = max(max_x, x + r)
    min_y = min(min_y, y - r)
    max_y = max(max_y, y + r)

points = []

for _ in range(m):
    dx, dy = map(int, input().split())
    points.append((dx, dy))
    min_x = min(min_x, dx)
    max_x = max(max_x, dx)
    min_y = min(min_y, dy)
    max_y = max(max_y, dy)

GRID_SIZE = 500
delta_x = max_x - min_x
delta_y = max_y - min_y
s = max(delta_x, delta_y) / GRID_SIZE
if s == 0:
    s = 1

# Function that maps coordinates to grid indices
def get_grid_cell(x_n, y_n):
    gx = int((x_n - min_x) / s)
    gy = int((y_n - min_y) / s)
    return gx, gy

grid = {}

# Mapping the targets onto the grid
for idx, (x, y, r) in enumerate(circles):
    x_min = x - r
    x_max = x + r
    y_min = y - r
    y_max = y + r
    gx_min, gy_min = get_grid_cell(x_min, y_min)
    gx_max, gy_max = get_grid_cell(x_max, y_max)
    for gx in range(gx_min, gx_max + 1):
        for gy in range(gy_min, gy_max + 1):
            if (gx, gy) not in grid:
                grid[(gx, gy)] = []
            grid[(gx, gy)].append(idx)  # store the target index

ans = 0

# For each dart, check the target in the grid where it is located
for dx, dy in points:
    gx, gy = get_grid_cell(dx, dy)
    found = False
    if (gx, gy) in grid:
        for idx in grid[(gx, gy)]:
            x, y, r = circles[idx]
            # Determine if the dart is in the target
            if (dx - x) ** 2 + (dy - y) ** 2 <= r ** 2:
                ans += 1
                found = True
                break  # 找到后跳出循环
    # The grids do not overlap and the surrounding grids are not detected?

print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <iostream>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    // Fast input/output
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<tuple<int, int, int>> circles;
    long long min_x = LLONG_MAX, min_y = LLONG_MAX;
    long long max_x = LLONG_MIN, max_y = LLONG_MIN;

    // Read circles and update bounding box
    for (int i = 0; i < n; ++i) {
        int x, y, r;
        cin >> x >> y >> r;
        circles.emplace_back(x, y, r);
        min_x = min(min_x, (long long)x - r);
        max_x = max(max_x, (long long)x + r);
        min_y = min(min_y, (long long)y - r);
        max_y = max(max_y, (long long)y + r);
    }

    vector<pair<int, int>> points;

    // Read darts and update bounding box
    for (int i = 0; i < m; ++i) {
        int dx, dy;
        cin >> dx >> dy;
        points.emplace_back(dx, dy);
        min_x = min(min_x, (long long)dx);
        max_x = max(max_x, (long long)dx);
        min_y = min(min_y, (long long)dy);
        max_y = max(max_y, (long long)dy);
    }

    const int GRID_SIZE = 500;
    long long delta_x = max_x - min_x;
    long long delta_y = max_y - min_y;
    double s = max(delta_x, delta_y) / (double)GRID_SIZE;
    if (s == 0) {
        s = 1;
    }

    // Function to get grid cell indices
    auto get_grid_cell = [&](long long x_n, long long y_n) {
        int gx = int((x_n - min_x) / s);
        int gy = int((y_n - min_y) / s);
        return make_pair(gx, gy);
    };

    // Function to combine gx and gy into a single key
    auto get_grid_key = [](int gx, int gy) -> long long {
        return ((long long)gx << 32) | (unsigned int)gy;
    };

    // Map from grid cell key to list of circle indices
    unordered_map<long long, vector<int>> grid;

    // Map circles to grid cells
    for (int idx = 0; idx < n; ++idx) {
        int x, y, r;
        tie(x, y, r) = circles[idx];
        long long x_min = x - r;
        long long x_max = x + r;
        long long y_min = y - r;
        long long y_max = y + r;
        auto [gx_min, gy_min] = get_grid_cell(x_min, y_min);
        auto [gx_max, gy_max] = get_grid_cell(x_max, y_max);
        for (int gx = gx_min; gx <= gx_max; ++gx) {
            for (int gy = gy_min; gy <= gy_max; ++gy) {
                long long key = get_grid_key(gx, gy);
                grid[key].push_back(idx); // Store circle index
            }
        }
    }

    int ans = 0;

    // For each dart, check circles in its grid cell and adjacent cells
    for (const auto& p : points) {
        int dx = p.first;
        int dy = p.second;
        auto [gx, gy] = get_grid_cell(dx, dy);
        bool found = false;

        // Check the dart's grid cell and its 8 neighbors
        for (int ix = gx - 1; ix <= gx + 1; ++ix) {
            for (int iy = gy - 1; iy <= gy + 1; ++iy) {
                long long key = get_grid_key(ix, iy);
                if (grid.count(key)) {
                    const auto& circle_indices = grid[key];
                    for (int idx : circle_indices) {
                        int x, y, r;
                        tie(x, y, r) = circles[idx];
                        // Check if the dart is inside the circle
                        long long dx_sq = (long long)(dx - x) * (dx - x);
                        long long dy_sq = (long long)(dy - y) * (dy - y);
                        long long r_sq = (long long)r * r;
                        if (dx_sq + dy_sq <= r_sq) {
                            ans++;
                            found = true;
                            break; // Move to next dart
                        }
                    }
                }
                if (found) break;
            }
            if (found) break;
        }
    }

    cout << ans << '\n';
    return 0;
}

show all >>

9021_TUT_1

字数统计: 620字   |   阅读时长: 3min

Slide 1: Introduction

Today, we are going to walk through six Python functions that perform various tasks involving integers, lists, and text files. Each function demonstrates different ways to manipulate data, including string formatting, list processing, and reading from files.

Slide 2: Function 1 - f1(m, n)

The first function, f1, generates a simple string pattern. Here’s how it works:

1
2
def f1(m, n):
    return ('|' + '_' * n + '|') * m
  1. The function takes two integer arguments, m and n. Both are assumed to be at least 0.
  2. It constructs a pattern consisting of vertical bars (|) enclosing underscores (_), repeated m times. The number of underscores between the bars is determined by n.
  3. For example, if m = 3 and n = 4, the output would be:
    1
    |____||____||____|

Slide 3: Function 2 - f2(n)

The second function, f2, creates a square pattern made up of digits. Here’s the function:

1
2
def f2(n):
    return (str(n) * n + '\n') * n
  1. This function takes an integer n and generates a square of n rows, where each row contains the digit n repeated n times.
  2. The pattern ends with a newline after each row.
  3. For example, if n = 3, the output will be:
    1
    2
    3
    333
    333
    333

Slide 4: Function 3 - f3(L)

Next, we have f3, which works on a list of integers:

1
2
3
4
def f3(L):
    while len(L) > 1 and L[0] > L[1]:
        L.remove(L[0])
    print(L)
  1. This function removes elements from the start of the list until the first two consecutive elements are in non-decreasing order.
  2. The process continues as long as the first element is strictly greater than the second element.
  3. Once the list is stable, it prints the modified list.
  4. For example, if L = [9, 8, 7, 10], the function will remove 9, 8, and 7, leaving [10].

Slide 5: Function 4 - f4(D, n)

The fourth function, f4, works with dictionaries:

1
2
3
4
5
6
7
8
def f4(D, n):
    if n not in D:
        return []
    ans = [n]
    while n in D and D[n] > n:
        ans.append(D[n])
        n = D[n]
    return ans
  1. This function takes a dictionary D and an integer n. It generates a strictly increasing sequence of integers based on the relationships defined in the dictionary.
  2. Starting from n, it appends D[n], D[D[n]], and so on to the list, as long as each subsequent value is greater than the previous one.
  3. For example, if D = {1: 2, 2: 3, 3: 5} and n = 1, the function will return [1, 2, 3, 5].

Slide 6: Function 5 - f5(filename)

The fifth function, f5, reads from a file and processes each line:

1
2
3
4
5
6
def f5(filename):
    with open(filename) as f:
        for i in f:
            name, number = i.split(',')
            number = int(number) * 1000
            print(f"{number} people named {name}")
  1. This function reads a text file, where each line consists of a name and a count separated by a comma.
  2. The function multiplies the count by 1000 and prints the result in the format: “X people named Y”.
  3. For example, if the file contains a line “John,5”, it will print:
    1
    5000 people named John

Slide 7: Function 6 - f6(filename)

The final function, f6, also reads from a text file, but with a different format:

1
2
3
4
5
6
def f6(filename):
    with open(filename) as f:
        for i in f:
            if not i.isspace():
                number, charactor = i.split()
                print(int(number) * charactor)
  1. This function reads lines that contain an integer followed by a symbol (e.g., “5 *”).
  2. It multiplies the symbol by the integer and prints the result.
  3. For example, if the file contains the line “3 # “, the function will print:
    1
    ###

show all >>

Top of an article

字数统计: 339字   |   阅读时长: 2min

longsizhuo123.github.io

pattern_stripes-1_1_2_0-0_125_1__cc2a35_4f372d_00a1b0_edc951_eb6941

“Maybe it could be a nice memory”

Welcome to my personal blog repository on Github! My name is Sizhuo Long, and I am currently a student in Australia. This repository is home to my personal blog, which is built using the HEXO static site generator.

On my blog, you’ll find a variety of content including my thoughts on technology, programming, and the latest developments in my field of study. I also share my experiences and lessons learned from the projects I’ve worked on.

I hope that by sharing my knowledge and insights, I can help others who are interested in the same topics. I welcome any comments and feedback, and I am always open to collaboration.

Thank you for visiting my blog, I hope you will find something interesting here. And I would really appreciate it if you could pay more attention to my blog and follow me.

Why you should follow me

  • I’ll share my personal experiences and thoughts on technology and programming
  • I’ll keep you updated on the latest developments in my field of study
  • I’m open to collaboration and feedback.

How to contact me

Thank you for reading, and I hope you enjoy my blog!

pattern_stripes-1_1_2_0-0_125_1__cc2a35_4f372d_00a1b0_edc951_eb6941

Single -cellRNAData analysis tool
The project I did before，There are many errors，Don’t spray。
Shu Di Travel Bacteria
This is a small assignment when I was a second junior year，It’s a group operation。At first I couldn’t get the linkhtmldocument，I read a lot of official documents orCSDNdocument
。Finally read an article，Said to beHEXODang thegeneratewhen，I willsource中的documentappendarrivepublicMiddle，I tried many times later，Discover directly
public为源document夹，Just call the directory。Although this will cause it to be unable to bemddocument中超链接arrivedocument。

at the same time，也exist新的bugunsolved：login.htmlUnable toindex.htmlJump
Linkin:

Sizhuo Long
置顶

show all >>

964E

字数统计: 527字   |   阅读时长: 3min

Question:

E. Triple Operations
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

On the board Ivy wrote down all integers from l to r, inclusive.

In an operation, she does the following:

  • pick two numbers x and y on the board, erase them, and in their place write the numbers 3x and ⌊y3⌋. (Here ⌊∙⌋ denotes rounding down to the nearest integer).

What is the minimum number of operations Ivy needs to make all numbers on the board equal 0? We have a proof that this is always possible.

Input

The first line contains an integer t (1≤t≤104) — the number of test cases.

The only line of each test case contains two integers l and r (1≤l<r≤2⋅105).

Output

For each test case, output a single integer — the minimum number of operations needed to make all numbers on the board equal 0.

Example
Input
Copy
4
1 3
2 4
199999 200000
19 84
Output
Copy
5
6
36
263
Note

In the first test case, we can perform 5 operations as follows:

1,2,3→x=1,y=23,0,3→x=0,y=31,0,3→x=0,y=31,0,1→x=0,y=10,0,1→x=0,y=10,0,0.

[964E.md](https://codeforces.com/contest/1999/problem/E)

My think:

At first, I thought it was a simple simulation problem: calculate the number of times x when the smallest
number divided by 3 equals 0, and then the answer would be x * 2 plus the number of remaining times when
the left number divided by 3 equals 0. However, this approach is incorrect.

By utilizing the characteristics of exponential growth and performing some simple
calculations, we can quickly determine the minimum number of operations within a given range.
This method has a low time complexity and can efficiently handle large input ranges.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import math
t = int(input())
for i in range(t):
    num = list(map(int, input().split()))
    l = num[0]
    r = num[1]
    start_pow3 = 1
    cnt_start = 1
    while start_pow3 <= (l / 3):
        start_pow3 *= 3
        cnt_start += 1
    ans = cnt_start
    pow3 = start_pow3
    next_pow3 = start_pow3 * 3
    while pow3 <= r:
        ans += (min(r + 1, next_pow3) - max(l, pow3)) * cnt_start
        cnt_start += 1
        pow3 *= 3
        next_pow3 *= 3
    print(ans)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def min_operations_to_zero(n):
    operations = 0
    while n > 0:
        n = n // 3
        operations += 1
    return operations

t = int(input())
results = []
for _ in range(t):
    l, r = map(int, input().split())
    total_operations = 0
    oper = min_operations_to_zero(l)
    for n in range(l+1, r+1):
        total_operations += min_operations_to_zero(n)
    total_operations += oper*2
    results.append(total_operations)

for result in results:
    print(result)

show all >>

994.Rotten orange

字数统计: 739字   |   阅读时长: 4min

topic：

“””

Given m x n grid  grid middle，Each cell can have one of the following three values：

  • value 0 Represents the empty unit；
  • value 1 Represents fresh oranges；
  • value 2 代表Rotten orange。

every minute，Rotten orange around 4 Adjacent in this direction Fresh oranges will rot。

return 直到单元格middle没有新鲜橘子为止所必须经过的最小分钟数。If it is impossible，return -1 。

 

Exemplary example 1：

enter：grid = [[2,1,1],[1,1,0],[0,1,1]]
Output：4

Exemplary example 2：

enter：grid = [[2,1,1],[0,1,1],[1,0,1]]
Output：-1
explain：Orange in the lower left corner（First 2 OK， First 0 List）Never rot，Because rotten will only happen in 4 In the direction。

Exemplary example 3：

enter：grid = [[0,2]]
Output：0
explain：because 0 There is no fresh orange in minutes，So the answer is 0 。

 

hint：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] Only for 0、1 or 2
Related Topics
  • Priority search
  • Array
  • matrix

  • 👍 872
  • 👎 0
    • """

    Thought：

    这个问题可以用Priority search（BFS）To solve。We need to track the spread of rotten oranges，Record time，And check if there is a fresh orange that cannot be rotten。The initial idea of ​​the original idea：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    class Solution:
        def orangesRotting(self, grid: List[List[int]]) -> int:
            bad_orange = []
            # 找到所有初始Rotten orange
            for i in range(len(grid)):
                for j in range(len(grid[0])):
                    if grid[i][j] == 2:
                        # 存入初始队List
                        bad_orange.append((i, j))

    Similar to multi -threaded，每个线程存入一个初始队List，初始队List通过BFSGradual diffusion

    Code：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    from collections import deque

    class Solution:
        def orangesRotting(self, grid: List[List[int]]) -> int:
            bad_orange = deque()
            fresh_oranges = 0
            rows, cols = len(grid), len(grid[0])
            
            # 找到所有初始Rotten orange，And calculate the number of fresh oranges
            for i in range(rows):
                for j in range(cols):
                    if grid[i][j] == 2:
                        bad_orange.append((i, j))
                    elif grid[i][j] == 1:
                        fresh_oranges += 1
            
            # 方向Array：up down left right
            directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
            
            # If there is no fresh orange，直接return 0
            if fresh_oranges == 0:
                return 0
            
            # BFS
            minutes = 0
            while bad_orange:
                minutes += 1
                for _ in range(len(bad_orange)):
                    x, y = bad_orange.popleft()
                    for dx, dy in directions:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1:
                            grid[nx][ny] = 2
                            fresh_oranges -= 1
                            bad_orange.append((nx, ny))
            
            # If there are fresh oranges，return -1
            return minutes - 1 if fresh_oranges == 0 else -1
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    import (
    	"sync"
    )

    func orangesRotting(grid [][]int) int {
    	rows, cols := len(grid), len(grid[0])
    	badOranges := make([][2]int, 0)
    	freshOranges := 0

    	// 找到所有初始Rotten orange，And calculate the number of fresh oranges
    	for r := 0; r < rows; r++ {
    		for c := 0; c < cols; c++ {
    			if grid[r][c] == 2 {
    				badOranges = append(badOranges, [2]int{r, c})
    			} else if grid[r][c] == 1 {
    				freshOranges += 1
    			}
    		}
    	}

    	// If there is no fresh orange，直接return 0
    	if freshOranges == 0 {
    		return 0
    	}

    	directions := [][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
    	minutes := 0

    	var wg sync.WaitGroup

    	// BFS
    	for len(badOranges) > 0 {
    		minutes++
    		nextBadOranges := make([][2]int, 0)
    		for _, orange := range badOranges {
    			x, y := orange[0], orange[1]
    			wg.Add(1)
    			go func(x, y int) {
    				defer wg.Done()
    				for _, d := range directions {
    					nx, ny := x+d[0], y+d[1]
    					if nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == 1 {
    						grid[nx][ny] = 2
    						nextBadOranges = append(nextBadOranges, [2]int{nx, ny})
    						freshOranges--
    					}
    				}
    			}(x, y)
    		}
    		wg.Wait()
    		badOranges = nextBadOranges
    	}

    	// If there are fresh oranges，return -1
    	if freshOranges > 0 {
    		return -1
    	}
    	return minutes - 1
    }

    show all >>

    1124. The longest period of performance One question daily

    字数统计: 260字   |   阅读时长: 1min

    topic：

    2023-02-15.png
    1124. The longest period of performance.md

    Thought：

    This question is not，I thought it was a double pointer but timeout over time，结果是Prefix and算法。The following isSpiritual godSolution
    通过Prefix and，我们可以把Elements and elements of sub -array转换成两个Prefix and的差，Right now
    $$
    \sum_{j=left}^{right} nums[j] = \sum_{j=0}^{right} nums[j]− \sum_{j=0}^{left-1} nums[j]=s[right+1]−s[left]
    $$
    Now that I said it「Elements and elements of sub -array」，那么利用Prefix and s，Turn the problem to：
    Find two bidding i and j，satisfy j<ij<ij<i and s[j]<s[i]，maximize i−jValue。

    Code：

    Double pointer
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution:
        def longestWPI(self, hours: List[int]) -> int:
            ans = 0
            for index, i in enumerate(hours):
                count = 0
                j = index
                while j < len(hours):
                    if hours[j] <= 8:
                        count -= 1
                    elif hours[j] > 8:
                        count += 1
                    if count > 0:
                        ans = max(ans, j - index + 1)
                    j += 1
            return ans
    Prefix and
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution:
        def longestWPI(self, hours: List[int]) -> int:
            n = len(hours)
            s = [0] * (n + 1)
            st = [0]
            for j, h in enumerate(hours, 1):
                s[j] = s[j - 1] + (1 if h > 8 else -1)
                if s[j] < s[st[-1]]:
                    st.append(j)
            ans = 0
            for i in range(n, 0 , -1):
                while st and s[i] > s[st[-1]]:
                    ans = max(ans, i-st.pop())
            return ans

    show all >>

    1233Delete the subfolder folder One question daily

    字数统计: 587字   |   阅读时长: 3min

    topic：

    2023-02-09.png
    1233. Delete the subfolder folder

    Thought：

    脑子里的构思yesDictionary tree，ButClanguage的Dictionary tree，Whether it isPython
    still golangI won’t write。 So helpless can only look at the answer。
    ylbThe big guy is right firstlistSort，Then traverse the list。

    1.ifiBefore[len(ans[-1])]Just happensans[-1]The element is consistent，Explainiyes
    ans[-1]Subfolder folder，Then skip。

    2.ifyes["/a/b/c","/a/b/ca","/a/b/d"]This situation，Be alone1.的判断yes不够的，at this time
    "/a/b/ca"Before缀and"/a/b/c"yes一样的，但yescaandc实际上yes两个不同的文件夹，So add a judgment front end
    yes否yes/，"/a/b/ca"and"/a/b/c/a"中后者才会被判定yes前面一个元素的子集。

    Dictionary tree没太看懂:
    我们可以使用Dictionary tree存储数组 folder All folders in。
    Dictionary tree的每个节点包含 children Field，Sub -nodes for storing the current nodes，as well as fid Field，
    Used to store the folder corresponding to the current node in the array folder Bidding。

    For array folder Each folder in it f，We will first f according to / Divide into several skewers，
    Then start from the root node，依次将子串加入Dictionary tree中。Next，我们从根节点开始搜索Dictionary tree，
    if当前节点的 fid Field不为 -1，则说明当前节点对应的文件夹yes答案数组中的一个文件夹，
    We add it to the array and return。otherwise，We search for all sub -nodes of the current node，Finally return to the array of answers。

    Code：

    python3
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    class Solution:
        def removeSubfolders(self, folder: List[str]) -> List[str]:
            folder.sort()
            ans = [folder[0]]
            for i in folder[1:]:
                m, n = len(ans[-1]), len(i)
                # if它的长度大于等于答案数组中最后一个文件夹的长度，并且它Before缀包含答案数组的最后一个文件夹再加上一个 /
                if m >= n or not (ans[-1] == i[:m] and i[m] == '/'):
                    ans.append(i)
            return ans
    # Dictionary tree
    class Trie:
        def __init__(self):
            self.children = {}
            self.fid = -1

        def insert(self, i, f):
            node = self
            ps = f.split('/')
            for p in ps[1:]:
                if p not in node.children:
                    node.children[p] = Trie()
                node = node.children[p]
            node.fid = 1

        def search(self):
            def dfs(root):
                if root.fid != -1:
                    ans.append(root.fid)
                    return
                for child in root.children.values():
                    dfs(child)
            ans = []
            dfs(self)
            return ans
        
        
    class Solution:
        def removeSubfolders(self, folder: List[str]) -> List[str]:
            trie = Trie()
            for i, f in enumerate(folder):
                trie.insert(i, f)
            return [folder[i] for i in trie.search()]
    golang
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    func removeSubfolders(folder []string) (ans []string) {
    	sort.Strings(folder)
    	ans = []string{folder[0]}
    	for _, i := range folder[1:] {
    		m, n := len(ans[len(ans)-1]), len(i)
    		if m >= n || !(ans[len(ans)-1] == i[:m] && i[m] == '/'){
    			ans = append(ans, i)
    		}
    	}
    	return 
    }

    show all >>

    1138. The path on the letter board One question daily

    字数统计: 311字   |   阅读时长: 1min

    topic：

    2023-02-12.png
    1138. The path on the letter board One question daily.md

    Thought：

    Read the wrong questions，According to the method of random letters above the subtitle version。butzSpecial circumstances are not considered，I thought about it later，Just turn the column into a line，Time complexity isOn3
    。Look atylbs answer，Use directlyasciiThe code watch simulates a letter board。

    From the starting point (0,0)(0, 0)(0,0) Set off，Simulate each step of movement，Style the movement of each step into the answer。Pay attention to the direction of moving“Left、superior、right、Down”Order。

    Code：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    class Solution:
        def alphabetBoardPath(self, target: str) -> str:
            str1 = ""
            board = ["abcde",
                     "fghij",
                     "klmno",
                     "pqrst",
                     "uvwxy",
                     "z"]
            now_i = 0
            now_j = 0
            for i in board:
                for j,value in enumerate(i):
                    pass
            for char in target:
                # See which line is
                for i in range(len(board)):
                    if char in board[i]:
                        if i - now_i > 0:
                            str1 += 'D' * (i - now_i)
                        if i - now_i < 0:
                            str1 += 'U' * (now_i - i)
                        now_i = i
                        # Which column
                        for j, value in enumerate(board[i]):
                            if value == char:
                                if j - now_j > 0:
                                    str1 += 'R' * (j - now_j)
                                if j - now_j < 0:
                                    str1 += 'L' * (now_j - j)
                                str1 += '!'
                                now_j = j
            return str1
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution:
        def alphabetBoardPath(self, target: str) -> str:
            i = j = 0
            ans = []
            for char in target:
                v = ord(char) - ord("a")
                x, y = v // 5, v % 5
                while j > y:
                    j -= 1
                    ans.append("L")
                while i > x:
                    i -= 1
                    ans.append("U")
                while j < y:
                    j += 1
                    ans.append("R")
                while i < x:
                    i += 1
                    ans.append("D")
                ans.append("!")
            return "".join(ans)

    show all >>

    1139. The greatest 1 Formation of the border One question daily

    字数统计: 331字   |   阅读时长: 2min

    topic：

    2023-02-17.png
    1139. The greatest 1 Formation of the border.md

    Thought：

    quiz6 Simple version，Prefix and求解。It should be noted that the upper left corner is0 Special circumstances are not considered，
    Need to verify # superior Left Down right Four -edge 1 The number of individuals d

    Code：

    错误Code
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class Solution:
        def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
            matrix_heng = copy.deepcopy(grid)
            matrix_su = copy.deepcopy(grid)
            ans = 0
            if len(grid) == 1:
                if 1 in grid[0]:
                    return 1
                else:return 0
            for ind, i in enumerate(grid):
                for index in range(len(i)):
                    # Each line adds
                    if index >= 1:
                        matrix_heng[ind][index] += matrix_heng[ind][index-1]
                    # Add each column
                    if ind >= 1:
                        matrix_su[ind][index] += matrix_su[ind-1][index]
            print(matrix_heng, matrix_su)
            for i in range(len(grid)):
                for j in range(len(grid[i])):
                    minus = min(matrix_heng[i][j], matrix_su[i][j])
                    try:
                        if grid[i-minus+1][j-minus+1] == 1 and i >= minus-1 and j >= minus-1:
                            ans = max(ans, minus ** 2)
                    except:
                        pass
            return ans
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution:
        def largest1BorderedSquare(self, grid: List[List[int]]) -> int:
            m, n = len(grid), len(grid[0])
            rs = [list(accumulate(row, initial=0)) for row in grid]  # 每行的Prefix and
            cs = [list(accumulate(col, initial=0)) for col in zip(*grid)]  # 每列的Prefix and
            for d in range(min(m, n), 0, -1):  # From large to small enumeration square edges d
                for i in range(m - d + 1):
                    for j in range(n - d + 1):  # 枚举正方形Leftsuperior角坐标 (i,j)
                        # superior Left Down right Four -edge 1 The number of individuals d
                        if rs[i][j + d] - rs[i][j] == d and \
                           cs[j][i + d] - cs[j][i] == d and \
                           rs[i + d - 1][j + d] - rs[i + d - 1][j] == d and \
                           cs[j + d - 1][i + d] - cs[j + d - 1][i] == d:
                            return d * d
            return 0

    show all >>

    1234. Replace the sub -string to get a balanced string One question daily

    字数统计: 445字   |   阅读时长: 2min

    topic：

    2023-02-13.png
    1234. Replace the sub -string to get a balanced string.md

    Thought：

    all():if bool(x) For all the values ​​in iterative objects x All for True，Then return True。 if可迭代对象为空，Then return True。

    Tongxiang dual pointer，The solution of the spiritual god of this question。
    If in this string，These four characters happen just to appear n/4 Second-rate，Then it is one「Balanced string」。
    if在待替换子串之外的任意字符的出现Second-rate数都Exceed $m=\dfrac{n}{4}$
    ，So no matter how you replace it，都无法make这个字符的出现Second-rate数等于m。
    on the other hand，if在待替换子串之外的任意字符的出现Second-rate数都不Exceed m，

    So it can be replaced ，make s 为Balanced string，即每个字符的出现Second-rate数均为 m。
    For this question，The left and right end points of the sub -string are left and right，enumerate right，
    if子串外的任意字符的出现Second-rate数都不Exceedm，The explanation from left arrive
    rightThis sub -string can be to replace the sub -string，Length right−left+1
    Update the minimum value of the answer，Move to the right left，Sumid sub -string length。

    Code：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution:
        def balancedString(self, s: str) -> int:
            s_c = Counter(s)
            n = len(s)
            if all(s_c[v] <= n//4 for v in s_c):
                return 0
            ans, left = inf, 0
            # enumerate右端点
            for i, j in enumerate(s):
                s_c[j] -= 1
                while all(s_c[v] <= n // 4 for v in s_c):
                    ans = min(ans, i - left + 1)
                    s_c[s[left]] += 1
                    left += 1
            return ans

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    func balancedString(s string) int {
    	cnt, m := ['X']int{}, len(s)/4
    	for _, c := range s {
    		cnt[c]++
    	}
    	if cnt['Q'] == m && cnt['W'] == m && cnt['E'] == m && cnt['R'] == m {
    		return 0
    	}
    	ans, left := len(s), 0
    	for right, c := range s {
    		cnt[c]--
    		for cnt['Q'] <= m && cnt['W'] <= m && cnt['E'] <= m && cnt['R'] <= m {
    			ans = min(ans, right-left+1)
    			cnt[s[left]]++
    			left++
    		}
    	}
    	return ans
    }
    func min(a, b int) int { if a > b { return b }; return a }

    show all >>