This is the ninth day of my participation in the August More text Challenge. For details, see: August More Text Challenge

1935. Maximum number of words that can be entered

Thought analysis

The logic of this problem is to determine whether each word contains a broken word, which can be queried using the string find function. But that adds to the time complexity, so here we’re going to store the broken letter keys in the array. Next comes a per-word determination, although you can divide arrays of words by space, so you can use a single space conditional count

int ret = 0;
int tmp = 0;
for(int i = 0; i < text.size(a); i ++){if( text[i] == ' ') {if (tmp == 0)ret++;
        tmp = 0;
    }else{
        if(arr[text[i] - 'a'] != 0){
            tmp = 1; }}}if (tmp == 0)ret++;
return ret;
Copy the code

Today, the force buckle official website do not know why collapsed, I did not save the manuscript, so write a acwing

18. Reconstruct the binary tree

Thought analysis

This question often makes a choice in the examination of postgraduate studies, according to the sequence before the sequence and the sequence in the sequence of inference after the sequence (may also be the other two inference one).

In this case, the left side of the first node in the middle order corresponding to the preorder must be a left subtree, and the right side must be a right subtree, which we made clear before we did this problem. Suppose the length of the in-order traversal of the left subtree is L, then the number of L after the root node in the pre-order traversal is the node of the left subtree. The remaining numbers are nodes of the right subtree. By analogy, recursion, and the left and right subtrees, then create the root node.

TreeNode* dfs(vector<int>&pre, vector<int>&in, int pl, int pr, int il, int ir) {
        if (pl > pr) return NULL;
        int k = pos[pre[pl]] - il;
        TreeNode* root = new TreeNode(pre[pl]);
        root->left = dfs(pre, in, pl + 1, pl + k, il, il + k - 1);
        root->right = dfs(pre, in, pl + k + 1, pr, il + k + 1, ir);
        return root;
}

Copy the code