This is the 19th day of my participation in the August More Text Challenge

1961. Checks if the string is an array prefix

Thought analysis

Slong.find (s) == 0; slong.find(s) == 0; slong.find(s) == 0;

But this approach does not handle the following case

“a”

[“aa”,”aaaa”,”banana”]

Later, TMP records the cursor of S and loops through words in a double loop:

for(int i = 0; i < words.size(a); i++){for(int j = 0 ; j < words[i].size(a); j++){if (tmp < n){
            if(words[i][j] ! = s[tmp++]){return false; }}else{
            if(j == 0) {return true;
            }
            return false; }}}Copy the code

If TMP == n, check whether the entire array is traversed. When the loop breaks, check whether the traversal is complete again (excluding the case where s is much larger than words).

1962 remove stones to minimize the total

Thought analysis

Answer to ask us to return the minimum total number of stones, and each operation is a number / 2, so this problem is generally thought must be greedy, this way let us finally to obtain the minimum total number of stones, so is the simplest way to traverse, for loop by k times, every time a maximum find stones, obtained the final sum total number of stones.

The second way is to sort the array, divide by two each time, and then reinsert the array, but this takes O(NlogN) + O(kN).

This time complexity is far more than the first way.

Another way of thinking is given to solve the official problem of li Kou

int minStoneSum(vector<int>& piles, int k) {
        // Generate the maximum heap
        make_heap(piles.begin(), piles.end());
        for (int i = 0; i < k; ++i){
            // Single operation: record and pop up the maximum value, modify it and add it to the heap again
            pop_heap(piles.begin(), piles.end());
            piles.back() -= piles.back(a) /2;
            push_heap(piles.begin(), piles.end());
        }
        return accumulate(piles.begin(), piles.end(), 0);
    }

Copy the code

Find the maximum value each time through heap operations.