20年833

1. 给一个带头结点单链表，删除所有值为k的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct ListNode{
    int val;
    struct ListNode *next;
};
ListNode * removeElements(ListNode *head,int k){
    if(head==NULL) return NULL;
    ListNode *p=head;
    ListNode *q;
    while(p->next!=NULL)//用p来遍历链表
    {
        if(p->next->val==k){//p的后一个节点为要删除的结点
            q=p->next;
            p->next=p->next->next;
            free(q);//删除值为k的结点，并释放内存
        }
        else
            p=p->next;
    }
    return head;
}

2. 建立二叉排序树

给定一个数组{10，18，9，2，20，5，6，15，19，25}，设计一个程序根据本数组建立一颗二叉排序树，输入数据时以-1作为结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//二叉排序树的定义
typedef struct BTNode{
    int key;
    struct BTNode *lchild;
    struct BTNode *rchild;
}BTNode,*BiTree;
//插入key到二叉排序树中
int BSTInsert(BiTree &bt,int key){
    if(bt==NULL){
        bt=(BTNode*)malloc(sizeof(BTNode));
        bt->lchild=bt->rchild=NULL;
        bt->key=key;
        return 1;
    }else{
        if(key<bt->key){
        BSTInsert(bt->lchild,key);
        }else if(key>bt->key){
            BSTInsert(bt->rchild,key);
        }else if(key==bt->key)
            return 0;
    }
}
void solve(){
    int x;
    BiTree tree=NULL;
    while(cin>>x&&x!=-1){
        BSTInsert(tree,x);
    }
}

3. 快速排序

给定数组{46，79，56，52，38，40，80，31，95，24}。要求：

  1. 写出快速排序的思想
  2. 实现快速排序算法，从键盘输入该数组，对其进行排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
思想：
快速排序使用分治法策略把一个序列分为较小和较大的两个子序列，然后递归排序两个子序列
1. 挑选基准值：从数列中挑出一个数组，称之为“基准”，一般可以挑选当前区间的第一个元素。
2. 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆放在基准后面（与基准值相等的数可以到任意一边）。在这个分割结束之后，对基准值的排序已经完成。
3. 递归排序子序列：递归将小于基准值元素的子序列和大于基准值元素的子序列排序。
4. 递归到最底部的判断条件是数列的大小是0或1，此时该数列显然已经有序。
*/
int qsort(int arr[],int left,int right){
    if(left>=right)	//当left==right时，说明当前区间只有一个值，该干的干完了，不用往下了
        return 0;
    int num=arr[left];//标兵的值
    int i=left;//左移动指针
    int j=right;//右移动指针
    while(i<j){//左右指针相碰撞时，划分操作结束，而相遇时的位置就是下一次划分的界限
        //重点！从右边开始扫
        while(i<j&&arr[j]>=num)j--;//从右边扫找到第一个小于标兵的点
        while(i<j&&arr[i]<=num)i++;//从左边扫找到第一个大于标兵的点
        swap(arr,i,j);			   //交换他们
    }
    swap(arr,left,j);//两指针相遇后，就找到了下一次划分的界限，把找到的分界线上的值与标兵换一下
    qsort(arr,left,j-1);//分界线左边继续划分
    qsort(arr,j+1,right);//分界线右边继续划分
}

4. 合法出入栈字符序列

输入一串字符串，如IOIOOOII，长度最长为50，其中I代表入栈操作，O代表出栈操作。试设计一个程序，判断输入的字符串序列是否合法的出入栈操作序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
1. 栈溢出
2. 空栈弹出
3. 栈不能遗留
本题为2.
*/
bool isLegal(char str[],int n){
    int cnt=0;
    for(int i=0;i<n;i++){
        if(str[i]=='O'){
            cnt--;
            if(cnt<0)
                return 0;
        }else
            cnt++;
    }
    return 1;
}

5. 统计二叉树叶子结点

给一个二叉树写一个函数统计叶子结点个数，函数声明void counterleaf(bitree *t,int &count)

1
2
3
4
5
6
7
8
9
10
void counterleaf(bitree *t,int &count){
    if(t->lchild==NULL && t->rchild==NULL){
        count++;
        return;
    }    
    if(t->lchild!=NULL)
        counterleaf(t->lchild,count);
    if(t->rchild!=NULL)
        counterleaf(t->rchild,count);
}

6. 最小乘船数问题

进行一次独木舟的旅行活动，独木舟可以在港口租到，并且之间没有区别。一条独木舟上乘客的总重量不能超过独木舟的最大承载量，并且每条船最多只能坐两个乘客。我们要尽量减少这次活动中的花销，所以要找出可以安置所有旅客的最少的独木舟条数。现在请写一个程序，读入独木舟的最大承载量、旅客数目和每位旅客的重量。根据给出的规则，计算要安置所有旅客必须的最少的独木舟条数，并输出结果。 第一行输入最大船载重量和乘客数 。第二行输入乘客的重量。输出为所需要的最少独木舟的条数 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int MinBoat(int people[],int n,int limit){
    Sort(people,n);
    int i=1;
    int j=n;
    int ans=0;
    while(i<=j){
        if(people[i]+people[j]<=limit)//两个人能坐
        {
            i++;j--;
        }
        else
            j--;
        ans++;
    }
    return ans;
}

7. 最长公共子序列

小王打枪，给定一个目标序列，如 ccca，子弹的序列为 acbc。打枪的规则如下：按照子弹序列的顺序 射击；子弹打中对应的目标得 1 分，否则无分；允许放空枪。假定：

（1）都是神枪手，只要射击就一定能打中；

（2）子弹打中目标，目标就销毁；

（3）共 26 种目标用 26 个小写字母表示。

输入第 1 行是子弹列，第 2 行是目标列，输出为 1 个数字，表示最高分 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//设数组A长度为n，数组B长度为m
int n,m;
char a[Maxn];
char b[Maxn];
int dp[Maxn][Maxn];//dp[i][j] 表示a串前i个与b串前j个 这两个串的最长公共子序列的值
void fun(){
    //初始化 i=0表示a串为空串和b串去匹配，则dp=0，j=0 同理
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            dp[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i]==b[j])//如果 i j匹配，取a b串规模更小的最优值+1
            	dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);//否则，a或b缩小规模，取两者更优值
        }
    }
}

公共汽车问题

假设某条街上每一公里就有一个公共汽车站，并且乘车费如下表：

公里数 1 2 3 4 5 6 7 8 9 10

费用 12 21 31 40 49 58 69 79 90 101

而任意一辆汽车行驶不能超过 10 公里。某人想行驶 n 公里，他可以任意次换车，请找到一种乘车方案，使得总费用最小。输入为某人想要行驶的公里数，输出为最小费用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*思路：动态规划问题
    假设我们最终的目的是走dis公里，那么有可能是从dis-1位置做1公里车过来，或者从dis-2位置坐2公里车...或者从dis-10公里坐10公里车过来。对于这十种情况，维护最小值，就是走到dis位置的最优值。
    那么自底向上解决这个问题即可。到1公里dp[1]最优值就是cost[1],到2公里dp[2]的最优值就是从0位置2公里车来或从1位置坐1公里车来，这两种情况维护更小。
*/
int Mincost(int cost[],int n,int Dis)//给了n个公里数分别的花费，Dis表示要走的距离
{
    int dp[Maxn];
    dp[0]=0;
    for(int i=1;i<=Dis;i++){
        int Min=inf;//inf表示很大的数字，赋值dp[i]是要找最小值，所以初试化为比较大的数字 考虑i是从哪里来，从i-1或i-2或i-n 共有n种可能，维护n中情况的最小值
        for(int j=1;j<=min(i,n);j++)//min(i,n)是因为 如果i<n,则i不可能从i-n来
            Min=min(Min,dp[i-j]+cost[j]);//dp[i-j]表示从七点走到i-j的位置的花费，再加上cost[j]就是从起点到i的总花费
        dp[i]=Min;//赋值最优情况给dp[i]
    }
    return dp[Mis];
}
void solve(){
    int n;
    int Dis;
    int cost[Maxn];
    //如果cost数组需要输入
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>cost[i];
    cin>>Dis;
    cout<<Mincost(cost,n,Dis)<<endl;
}