Examination papers

The examination paper includes 4 Problem ,3 Programming problem ,1 Questions and answers , Time limit 100 minute .

The first programming problem

subject ： Niuniu has a character only ’1’ To ’9’ The length of the composition is n String s, Now Niuniu can intercept a section with a length of k The substring of is treated as a positive decimal integer , For example, for substring "123", Its corresponding decimal number is 123. Niuniu wants this positive integer to be as large as possible , Please help Niuniu calculate the positive integer . The function passes in a length of n String s And a positive integer k, Please return to the answer .

remarks ： Mainly investigate the conversion between string and decimal number .

class Solution {
    
public:
    int maxValue(string s, int k) {
    
        int n = s.size(), ans = 0;
        for (int i = 0; i <= n - k; ++i) {
    
            int t = 0;
            for (int j = 0; j < k; ++j) {
    
                t = t * 10 + (s[i + j] - '0');
            }
            ans = max(ans, t);
        }
        return ans;
    }
};

Input "321456987" and 3 Get the results 987.

The second programming problem

subject ： Niuniu has one n A binary tree of nodes , Its root node is root. Niuniu wants to prune the leaf nodes of the current binary tree , But Niuniu cannot delete leaf nodes directly . He can only prune the parent nodes of leaf nodes , After pruning the parent node , Leaf nodes will also be deleted , Niuniu wants to leave as many nodes as possible , Trim off all leaf nodes . Please return to the pruned binary tree .

remarks ： This inscription cannot be written , Later, I referred to a big man's Python Code recurrence , among pair The first value indicates whether the node is a leaf node , The second value indicates whether the node should be deleted .

class Solution {
    
private:
	pair<bool, bool> dfs(TreeNode* root) {
    
		if (!root) {
    
			return {
     false, false };
		}
		pair<bool, bool> lp, rp;
		if (root->left) {
    
			lp = dfs(root->left);
		}
		if (root->right) {
    
			rp = dfs(root->right);
		}
		if (lp.first || rp.first) {
    
			return {
     false, true };
		}
		if (lp.second) {
    
			root->left = nullptr;
		}
		if (rp.second) {
    
			root->right = nullptr;
		}
		return {
     true, false };
	}
public:
	TreeNode* pruneLeaves(TreeNode* root) {
    
		TreeNode* t = new TreeNode(-1);
		t->left = root;
		dfs(t);
		root = t->left;
		delete t;
		t = nullptr;
		return root;
	}
};

The third programming problem

subject ： Niu Mei gave Niu Niu a length of n The subscript of is a positive integer array starting from zero a, Careless Niuniu accidentally deleted some of the figures . Join in ai Been deleted , be ai=0. For all deleted numbers , Niuniu chooses a positive integer and fills it in . Now Niuniu wants to know how many filling schemes make ：a0≤a1≤…≤an-1 And for all 0≤i≤n-1 Satisfy 1≤ai≤k. Function passes in a subscript from 0 Starting array a And a positive integer k, Please return the legal number of filling scheme pairs 10^9+7 The value of the die , The number of schemes guaranteed to be nonexistent is 0 The data of .

remarks ： I know that this problem should be solved by dynamic programming, but I can't write it , The following questions are from the same Python bosses , I use C++ Reappeared .

class Solution {
    
private:
	int dfs(int p, int q, map<pair<int, int>, int>& map) {
    
		if (map.count({
     p, q })) {
    
			return map[{
    p, q}];
		}
		if (p == 0 || q == 0) {
    
			return 1;
		}
		if (p == 1) {
    
			return q;
		}
		if (q == 1) {
    
			return 1;
		}
		map[{
    p, q}] = (dfs(p - 1, q, map) + dfs(p, q - 1, map)) % ((int)pow(10, 9) + 7);
		return map[{
    p, q}];
	}
public:
	int fillArray(vector<int>& a, int k) {
    
		map<pair<int, int>, int> map;
		a.insert(a.begin(), 1);
		a.emplace_back(max(a[a.size() - 1], k));
		int idx = 0, ans = 1;
		for (int i = 1; i < a.size(); ++i) {
    
			if (a[i] != 0) {
    
				ans = ans * dfs(i - idx - 1, a[i] - a[idx] + 1, map) % ((int)pow(10, 9) + 7);
				idx = i;
			}
		}
		return ans;
	}
};

I'm just a programmer , Blogging is for summarizing and communicating , Please criticize and correct ！