iii.run

科室素拓活動(dòng)

科室素拓進(jìn)行游戲，游戲規(guī)則如下：隨機(jī)抽取9個(gè)人作為游戲參與人員，分別編號(hào)1至9，每輪要求k(k<=9且k>=0)個(gè)人自由組合使編號(hào)之和為n。輸出滿足規(guī)則的所有可能的組合。要求組合內(nèi)部編號(hào)升序輸出，組合之間無(wú)順序要求。

輸入描述:

輸入數(shù)據(jù)為以空格分隔的兩個(gè)整數(shù)k和n

輸出描述:

每行輸出一個(gè)可能的編號(hào)組合，組合內(nèi)部各個(gè)編號(hào)以空格分隔升序輸出。若無(wú)滿足規(guī)則的組合，則輸出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

其實(shí)是個(gè)背包問題

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')

字符串處理

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，將一個(gè)字符串中的空格替換成“%20”。例如，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為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];
            }
        }
    }
};

重建二叉樹

輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{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;
    }

};

用兩個(gè)棧實(shí)現(xiàn)隊(duì)列

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;
};