iii.run

科室素拓活动

科室素拓进行游戏，游戏规则如下：随机抽取9个人作为游戏参与人员，分别编号1至9，每轮要求k(k<=9且k>=0)个人自由组合使编号之和为n。输出满足规则的所有可能的组合。要求组合内部编号升序输出，组合之间无顺序要求。

输入描述:

输入数据为以空格分隔的两个整数k和n

输出描述:

每行输出一个可能的编号组合，组合内部各个编号以空格分隔升序输出。若无满足规则的组合，则输出None

示例1

输入

3 15

输出

1 5 9
1 6 8
2 4 9
2 5 8
2 6 7
3 4 8
3 5 7
4 5 6

其实是个背包问题

s = input().split(" ")
#s = "3 15".split(" ")
k = int(s[0])
n = int(s[1])
test = 1
answer = []
def sumOfNumber(sum,n,k):
    if sum<=0 or n<=0 :
        return
    if sum==n and k == 1:
        global test
        test = 2
        answer.reverse()
        print(n,end=" ")
        for i in answer:
            print(i,end=" ")
        print()
        answer.reverse()
    answer.append(n)
    sumOfNumber(sum-n,n-1,k-1)
    answer.remove(n)
    sumOfNumber(sum,n-1,k)
sumOfNumber(n,9,k)
if test == 1:
    print('None')

字符串处理

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
python

# -*- coding:utf-8 -*-
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        new = []
        j = 0
        for i in s:
            if i != " ":
                new.append(i)
            else:
                new.append('%20')
        return ''.join(new)

cpp

class Solution {
public:
    void replaceSpace(char *str, int length) {
        int newlength = 0;
        int oldlength = 0;
        int j = 0;
        while (str[j]) {
            newlength++;
            oldlength++;
            if (str[j] == ' ') {
                newlength = newlength + 2;
            }
            j++;
        }
        str[newlength] = 0;
        for (int i = oldlength - 1,j = newlength-1; i >= 0; i--, j--) {
            if (str[i] == ' ') {
                str[j] = '0';
                str[--j] = '2';
                str[--j] = '%';
            }
            else {
                str[j] = str[i];
            }
        }
    }
};

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin)
    {
        if (pre.empty() || vin.empty()) {
            return NULL;
        }
        vector<int> preleft, preright, vinleft, vinright;
        int val = pre[0];
        TreeNode *root = new TreeNode(val);
        int pos;
        for (pos = 0; pos < vin.size(); ++pos) {
            if (vin[pos] == val)
                break;
        }
        for (int i = 0; i < vin.size(); ++i) {
            if (i < pos) {
                vinleft.push_back(vin[i]);
                preleft.push_back(pre[i + 1]);
            }
            else if(i>pos){
                vinright.push_back(vin[i]);
                preright.push_back(pre[i]);
            }
        }
        root->left = reConstructBinaryTree(preleft, vinleft);
        root->right = reConstructBinaryTree(preright, vinright);
        return root;
    }

};

用两个栈实现队列

class Solution
{
public:
    void push(int node) {
        int size1 = stack2.size();
        for (int i = 0; i < size1; i++) {
            int temp = stack2.top();
            stack2.pop();
            stack1.push(temp);
        }
        stack1.push(node);
        int size2 = stack1.size();
        for (int i = 0; i < size2; i++) {
            int temp = stack1.top();
            stack1.pop();
            stack2.push(temp);
        }
    }

    int pop() {
        int temp = stack2.top();
        stack2.pop();
        return temp;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};