Imagine that you are working on a text classification model which detects patterns within strings. As an initial step, you should find the longest contiguous substring within a given string source, consisting of lowercase English letters. Your task is to find the longest contiguous substring of source consisting of the same character within source. If there are several substrings of the same length that meet this criterion, the rightmost one. Return a string consisting of this character concatenated with its number of occurrences in the longest contiguous substring (i.e., the length of the substring).

• source = "bbbeed" → "b3"
• source = "ccc" → "c3"

Constraints

1 ≤ source.length ≤ 100.

解法

双指针扫游程：对每段游程，若更长，或等长但起点严格更靠右(i > best_start)，就更新最优。复杂度 O(n)。

def solution(source: str) -> str:
    n = len(source)
    best_char, best_len, best_start = '', 0, -1
    i = 0
    while i < n:
        j = i
        while j < n and source[j] == source[i]: j += 1
        cur_len = j - i
        if cur_len > best_len or (cur_len == best_len and i > best_start):
            best_len, best_char, best_start = cur_len, source[i], i
        i = j
    return f"{best_char}{best_len}"

class Solution {
    static String solution(String source) {
        int n = source.length(), bestLen = 0, bestStart = -1;
        char bestChar = ' ';
        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && source.charAt(j) == source.charAt(i)) j++;
            int curLen = j - i;
            if (curLen > bestLen || (curLen == bestLen && i > bestStart)) {
                bestLen = curLen; bestChar = source.charAt(i); bestStart = i;
            }
            i = j;
        }
        return "" + bestChar + bestLen;
    }
}

#include <string>
using namespace std;

string solution(string source) {
 int n = source.size(), bestLen = 0, bestStart = -1;
 char bestChar = ' ';
 int i = 0;
 while (i < n) {
 int j = i;
 while (j < n && source[j] == source[i]) j++;
 int curLen = j - i;
 if (curLen > bestLen || (curLen == bestLen && i > bestStart)) {
 bestLen = curLen; bestChar = source[i]; bestStart = i;
 }
 i = j;
 }
 return string(1, bestChar) + to_string(bestLen);
}

Implement the missing code, denoted by ellipses. You may not modify the pre-existing code.

Your task is to implement parts of a Bagging algorithm from scratch (i.e., without importing any libraries or packages besides those already imported). As a reminder, Bagging classification comprises three major steps:

1. Bootstrap the train sample for each base classifier.
2. Train each base classifier based on its own bootstrapped samples.
3. Assign class labels by majority vote of the base classifiers.

To validate the algorithm implementation, you will need to use it for some classification tasks. You will be given x_train (2D float array), y_train (1D int array of labels), and x_test.

Notes:

• It is guaranteed that all training and test data will be float values.
• In case of a tie in the voting, select the class label with the lower number.
• For bootstrapping: n indices generated per classifier, where n is the number of training samples. Each index i generated by randint with 0 <= i < n. Indexes could repeat. seed should be used only in its initial place.

解法

Bootstrap = 有放回抽样(每个分类器 n 次)；每棵 DecisionTreeClassifier 在自己的 bootstrap 样本上训练；用多数投票预测，平局取类别标号最小者。ML 题，只给 Python(依赖 sklearn)。

from sklearn.tree import DecisionTreeClassifier
from random import randint, seed

def bootstrap(X: list, y: list) -> tuple:
    n = len(X)
    idx = [randint(0, n - 1) for _ in range(n)]
    return [X[i] for i in idx], [y[i] for i in idx]

def fit(classifiers, X, y):
    for clf in classifiers:
        bx, by = bootstrap(X, y)
        clf.fit(bx, by)

def predict(classifiers, X):
    out = []
    for sample in X:
        votes = {}
        for clf in classifiers:
            p = int(clf.predict([sample])[0])
            votes[p] = votes.get(p, 0) + 1
        best_count = max(votes.values())
        winners = [c for c, v in votes.items() if v == best_count]
        out.append(min(winners))
    return out

def solution(x_train, y_train, x_test, n_estimators):
    seed(0)
    classifiers = [DecisionTreeClassifier(random_state=0) for _ in range(n_estimators)]
    fit(classifiers, x_train, y_train)
    return predict(classifiers, x_test)

Implement the missing code, denoted by ellipses. You may not modify the pre-existing code.

Your task is to implement parts of a k-Means Clustering algorithm from scratch, given an initial set of centroids.

Calculate the distance between each data point and the k centroids. Assign each data point to its nearest centroid. Average the data points in each cluster to update the centroids' locations and repeat for a set number of iterations. Return the predicted cluster for each data point.

Note: If a particular cluster is not assigned data points in one iteration, do not include that cluster in the next iteration. Any different cluster enumeration is also considered a valid answer.

Constraints

1 ≤ |data| ≤ 10000, 2 ≤ k ≤ 20, 1 ≤ iterations ≤ 500.

Example: data=[[1,2],[1,4],[1,0],[10,2],[10,4],[10,0]], k=2, centroids=[[1,2],[10,2]], iterations=10 → [0,0,0,1,1,1].

解法

标准 Lloyd 算法：算两两距离(scipy.cdist)，每个点分到最近质心，质心更新为簇均值。空簇在下一轮丢弃。ML 题，只给 Python(依赖 scipy)。

from scipy.spatial.distance import cdist
from typing import List

def calculate_distance(data: List[List[float]], centroids: List[List[float]]) -> List[List[float]]:
    return cdist(data, centroids, metric='euclidean').tolist()

def get_clusters(data: List[List[float]], centroids: List[List[float]]) -> List[int]:
    d = calculate_distance(data, centroids)
    return [row.index(min(row)) for row in d]

def update_clusters(clusters: List[int], data: List[List[float]], k: int) -> List[List[float]]:
    dim = len(data[0])
    new_centroids = []
    for c in range(k):
        members = [data[i] for i in range(len(data)) if clusters[i] == c]
        if not members:
            continue
        avg = [sum(m[j] for m in members) / len(members) for j in range(dim)]
        new_centroids.append(avg)
    return new_centroids

def fit_predict(data, k, centroids, iterations):
    cur = [list(c) for c in centroids]
    for _ in range(iterations):
        clusters = get_clusters(data, cur)
        cur = update_clusters(clusters, data, len(cur))
    return get_clusters(data, cur)

def solution(data, k, centroids, iterations):
    return fit_predict(data, k, centroids, iterations)

You are given an array pins, where pins[i] is the height of the ith pin. There are k columns, and each column starts with total height 0. Process the pins in their original order. For each pin, append it to the column with the smallest current total height. If multiple columns are tied for the smallest height, choose the column with the smallest index. After appending a pin, that column's total height increases by the pin's height. Return a two-row matrix:

• The first row contains the assigned column index for each pin.
• The second row contains the final total height of each column.

Constraints

• 1 ≤ k ≤ pins.length
• 1 ≤ pins.length ≤ 2 * 10⁵
• 1 ≤ pins[i] ≤ 10⁹
• Use a min-heap or equivalent data structure for efficient assignment.

Example 1

Input:

pins = [1,2,3,4,5]
k = 2

Output:

[[0,1,0,1,0],[9,6]]

Explanation: The assigned columns are [0,1,0,1,0]. Final heights are 9 and 6.

Example 2

Input:

pins = [10,20,30]
k = 3

Output:

[[0,1,2],[10,20,30]]

Example 3

Input:

pins = [5,5,5,5,5,5]
k = 2

Output:

[[0,1,0,1,0,1],[15,15]]

You are given a board of cells, where each cell contains a bubble represented by an integer color. Two cells are neighbors if they share a side, which means adjacency is only vertical or horizontal. Perform exactly one bubble explosion using the following rules:

• A bubble is eligible to explode if it has the same color as bubbles in at least 2 neighboring cells.
• All eligible bubbles, together with same-colored bubbles in neighboring cells, are marked for explosion.
• All marked bubbles explode at the same time and are removed from the board, creating empty cells.
• After the explosion, bubbles above empty cells fall downward until all empty cells are filled from above. Return the board after the explosion. Use 0 for cells that end up empty. A solution with time complexity no worse than O(rows² * cols²) fits within the limit.

Constraints

• 1 ≤ bubbles.length ≤ 100
• 1 ≤ bubbles[0].length ≤ 100
• 1 ≤ bubbles[i][j] ≤ 10⁴

Example 1

Input:

bubbles = [[3, 1, 2, 1], [1, 1, 1, 4], [3, 1, 2, 2], [3, 3, 3, 4]]

Output:

[[0, 0, 0, 1], [0, 0, 0, 4], [0, 0, 2, 2], [3, 0, 2, 4]]

Explanation: The connected group of 1s in the upper-left area is marked and explodes, together with same-colored neighbors. After those cells are removed, bubbles above empty spaces fall downward within each column. Empty cells are represented by 0.

You are given a string expression</

Example 1

Input:

expression = "1639+5628"

Output:

"16(39+5)628"

Explanation: Placing the parentheses around 39+5 gives the minimum value among all valid choices for this expression.

Imagine that you are standing at the starting point of a straight street and are trying to reach the end of the street. The street is represented by a number line starting at 0 and ending at finish, where finish > 0. Electric scooters are scattered along the street. The array scooters stores their locations, where scooters[i] is the position of the i-th scooter. Each scooter can travel at most 10 points to the right before its battery is exhausted. You must follow this exact algorithm:

• From your current position, walk to the nearest scooter to your right. If there is no scooter to your right, walk directly to finish.
• Ride that scooter as far as possible toward finish, using all of its remaining range.
• If you have still not reached finish, repeat from step 1. Return the total distance that you travel while riding scooters. You are not required to provide the optimal asymptotic solution. A solution with time complexity no worse than O(scooters.length * finish) fits within the limit.

Constraints

• 1 ≤ finish ≤ 1000
• All scooter locations are distinct integers on the street.

Example 1

Input:

finish = 23
scooters = [7, 4, 14]

Output:

19

Explanation: From position 0, the nearest scooter to the right is at 4, so you ride from 4 to 14 for 10 scooter-distance. From 14, the next scooter to the right is at 14 itself, so you ride from 14 to 23 for 9 more. The total scooter distance is 19.

Example 2

Input:

finish = 27
scooters = [15, 7, 3, 10]

Output:

20

Explanation: You first walk to the scooter at 3 and ride it to 13. Then the nearest scooter to the right is at 15, which takes you to 25. After that, there are no more scooters to the right, so you finish on foot. The scooter distance is 10 + 10 = 20.

Example 3

Input:

finish = 10
scooters = []

Output:

0

Explanation: There are no scooters on the street, so you travel the entire route on foot and accumulate no scooter distance.