c++第一次作业

二进制转十进制

实现如下功能：输入一个二进制数，输出该二进制数对应的十进制表示。

输入描述

由0和1组成的字符串（长度不超过20）。

输出描述

十进制数。

示例

示例 1

输入

输出

示例 2

输入

输出

提示

不需要考虑负数。

代码

#include <iostream>
#include <cmath>
#include <string>
using namespace std;
int main(){
    string s;
    cin >> s;
    int sum = 0;
    int n = 0;
    for(int i = s.size() - 1; i >= 0; i--){
        if(s[i] == '1'){
            sum += pow(2,n);
        }
        n++;
    }
    cout << sum << endl;
    return 0;
}

最长公共后缀

给定一个字符串数组，请输出最长的公共后缀。

如果不存在公共后缀，请输出""。

输入描述

输入一个字符串数组。第一行是数组的长度，从第二行开始每行都是一个字符串

输出描述

输出一个对应最长公共后缀的字符串。

示例

示例一

输入

3
shower
flower
power

输出

ower

示例二

输入

2
java
python

输出

"" //空串

提示

1 <= 数组长度 <= 200
0 <= 字符串长度 <= 200
字符串仅由小写英文字母组成

代码

#include <iostream>
#include <vector>

using namespace std;
int main(){
    int n;
    cin >> n;
    vector<string> vec;
    string input;
    for(int i = 0; i < n; i++){
        cin >> input;
        vec.push_back(input);
    }
    string temp;
    int min_size = vec[0].size();
    for(int i = 1; i < n; ++i){
        if(vec[i].size() < min_size)min_size = vec[i].size();
    }
    for(int i = 0; i < min_size; ++i){
        bool flag = true;
        for(int j = 0; j < n - 1; j++){
            int len1 = vec[j].size();
            int len2 = vec[j + 1].size();
            if(vec[j][len1 - 1 - i] != vec[j + 1][len2 - 1 - i]){
                flag = false;
                break;
            }
        }
        if(flag){
            temp += vec[0][vec[0].size() - 1 - i];
        }else{
            break;
        }
    }
    for(int i = 0; i < temp.size(); ++i){
        cout << temp[temp.size() - i - 1];
    }
    return 0;
}

翻转数字

给定一个 int 类型的整数 N，请你将它数字部分 翻转，正负性不变，并输出。

输入描述

输入仅包含一个 int 类型的整数 N，保证 N 在 int 类型的范围之内（即，-231 <= N < 231）。

如果翻转后大于 int 最大值或小于 int 最小值，输出 -1.

输出描述

翻转后的数。

示例

示例 1

输入

输出

示例 2

输入

-120

输出

-21

示例 3

输入

2147483647

输出

-1

解释

翻转之后超过 int 最大值。

提示

可以使用 <limits> 头文件中的 numeric_limits<int>::max() 和 numeric_limits<int>::min() 获取 int 的最大值和最小值。

代码

#include <iostream>
#include <cmath>
#include <limits>
using namespace std;
int nums[10];
int main(){
    long n;
    cin >> n;
    bool flag = !(n < 0);
    if(n < 0){
        n = -n;
    }
    int cnt = 0;
    while(n > 0){
        int k = n % 10;
        nums[cnt] = k;
        cnt++;
        n /= 10;
    }
    long long ans = 0;
    for(int i = cnt - 1; i >= 0; i--){
        ans += nums[i] * pow(10, cnt - i - 1);
    }
    if (!flag) ans = -ans;
    if(ans > numeric_limits<int>::max() || ans < numeric_limits<int>::min()){
        cout << -1;
    }else{
        cout << ans;
    }
    return 0;
}

矩阵操作

按顺序给出多个二维矩阵，给定每个矩阵的长和宽，并按从左到右、从上到下的顺序给定矩阵的内容

一共需要实现4种操作指令，操作不要修改原矩阵

1. add Matrix1 Matrix2

前置条件：Matrix1.height==Matrix2.height && Matrix1.width==Matrix2.width

计算方式：Result[i][j] = Matrix1[i][j] + Matrix2[i][j]

2. sub Matrix1 Matrix2

前置条件：Matrix1.height==Matrix2.height && Matrix1.width==Matrix2.width

计算方式：Result[i][j] = Matrix1[i][j] - Matrix2[i][j]

3. mul Matrix1 Matrix2

前置条件：Matrix1.height==Matrix2.height && Matrix1.width==Matrix2.width

计算方式：Result[i][j] = Matrix1[i][j] * Matrix2[i][j]

4. conv MatrixOut MatrixIn

conv指代Convolution（卷积）

前置条件：MatrixOut.height>=MatrixIn.height && MatrixOut.width>=MatrixIn.width

计算方式：Result[i][j] = SumXY(MatrixOut[i+x][j+y] * MatrixIn[x][y])其中0<=x<MatrixIn.height && 0<=y<Matrix.width

后置条件：Result.height==MatrixOut.height-MatrixIn.height+1 && Result.width==MatrixOut.width-MatrixIn.width+1（不考虑边界的padding）

思考如何设计并简化代码

输入描述

第1行为待操作的矩阵数量n

第2到n+1行为矩阵的信息

每行前2个整型数字h和w分别表示矩阵的高度和宽度
后接h*w个整型数字表示矩阵的内容

第n+2行为操作指令数量m

第n+3行到第n+2+m行表示操作信息

每行第一个字符串cmd表示操作指令，需支持的指令包括add sub mul conv
后接两个整型数字m1和m2分别表示被操作的两个矩阵

输出描述

以矩阵的形式按顺序输出每个操作的结果

如果发生矩阵大小不匹配（即违反前置条件）的情况，打印error

示例 2

输入

2
2 2 1 2 3 4
3 3 1 2 3 1 2 3 1 2 3
2
add 0 0
add 0 1

输出

2 4
6 8
error

示例 1

输入

4
3 3 1 1 1 1 1 1 1 1 1
3 2 2 2 2 2 2 2
2 3 3 3 3 3 3 3
2 2 4 4 4 4
3
mul 0 0
add 1 1
conv 2 3

输出

代码

#include <iostream>
#include <vector>
#include <string>

using namespace std;
vector<vector<int>> input(int h, int w){
    vector<vector<int>> vec;
    for(int i = 0; i < h; ++i){
        vector<int> row;
        for(int j = 0; j < w; ++j){
            int n;
            cin >> n;
            row.push_back(n);
        }
        vec.push_back(row);
    }
    return vec;
}

vector<string> split(string s, char c){
    vector<string> vec;
    string temp;
    for (char i : s) {
        if (i != c){
            temp += i;
        }else{
            vec.push_back(temp);
            temp = "";
        }
    }
    vec.push_back(temp);
    return vec;
}

void add(vector<vector<int>> m1, vector<vector<int>> m2){
    int h1 = m1.size();
    int w1 = m1[0].size();
    int h2 = m2.size();
    int w2 = m2[0].size();
    if(h1 != h2 || w1 != w2)cout << "error" << endl;
    else{
        vector<vector<int>> ans;
        for(int i = 0 ; i < h1; i++){
            for(int j = 0; j < w1; j++){
                if(j == 0)cout << (m1[i][j] + m2[i][j]);
                else{
                    cout << " " << (m1[i][j] + m2[i][j]);
                }
            }
            cout << endl;
        }
    }
}


void sub(vector<vector<int>> m1, vector<vector<int>> m2){
    int h1 = m1.size();
    int w1 = m1[0].size();
    int h2 = m2.size();
    int w2 = m2[0].size();
    if(h1 != h2 || w1 != w2)cout << "error" << endl;
    else{
        vector<vector<int>> ans;
        for(int i = 0 ; i < h1; i++){
            for(int j = 0; j < w1; j++){
                if(j == 0)cout << (m1[i][j] - m2[i][j]);
                else{
                    cout << " " << (m1[i][j] - m2[i][j]);
                }
            }
            cout << endl;
        }
    }
}

void mul(vector<vector<int>> m1, vector<vector<int>> m2){
    int h1 = m1.size();
    int w1 = m1[0].size();
    int h2 = m2.size();
    int w2 = m2[0].size();
    if(h1 != h2 || w1 != w2)cout << "error" << endl;
    else{
        vector<vector<int>> ans;
        for(int i = 0 ; i < h1; i++){
            for(int j = 0; j < w1; j++){
                if(j == 0)cout << (m1[i][j] * m2[i][j]);
                else{
                    cout << " " << (m1[i][j] * m2[i][j]);
                }
            }
            cout << endl;
        }
    }
}

void conv(vector<vector<int>> m1, vector<vector<int>> m2){
    int h1 = m1.size();
    int w1 = m1[0].size();
    int h2 = m2.size();
    int w2 = m2[0].size();
    if(!(h1 >= h2 && w1 >= w2)){
        cout << "error" << endl;
    }else{
        int h3 = h1 - h2 + 1;
        int w3 = w1 - w2 + 1;
        for(int i = 0; i < h3; i++){
            for(int j = 0; j < w3; j++){
                int sum = 0;
                for(int m = 0; m < h2; m++){
                    for(int n = 0; n < w2; n++){
                        sum += m1[i + m][j + n] * m2[m][n];
                    }
                }
                if(j == 0)cout << sum;
                else{
                    cout << " " << sum;
                }
            }
            cout << endl;
        }
    }
}

int main(){
    int n;
    cin >> n;
    vector<vector<vector<int>>> vec;
    for(int i = 0; i < n; ++i){
        int h,w;
        cin >> h;
        cin >> w;
        vec.push_back(input(h,w));
    }
    int n_order;
    cin >> n_order;
    cin >> ws;
    for(int i = 0; i < n_order; i++){
        string s;
        getline(cin, s);
        vector<string> orders = split(s, ' ');
        int m1 = stoi(orders[1]);
        int m2 = stoi(orders[2]);
        if(orders[0] == "add"){
            add(vec[m1], vec[m2]);
        }else if(orders[0] == "sub"){
            sub(vec[m1], vec[m2]);
        }else if(orders[0] == "mul"){
            mul(vec[m1], vec[m2]);
        }else{
            conv(vec[m1], vec[m2]);
        }
    }
    return 0;
}

单词计数

实现如下功能：给出一段文本，输出这段文本包含的字符数、单词数（以空格和换行符为界）和行数。

输入描述

保证输入中只会出现英文字母、空格（' '）和换行符（'\n'）。输入保证每行末尾都有一个换行符。

输出描述

字符数、单词数和行数，用空格分隔。

示例

示例中用 [SPC] 表示空格，用 [RET] 表示换行符

示例 1

输入

hello[SPC]world[RET]

输出

12 2 1

解释

' ' 和 '\n' 也计入字符数内
单词以空格和换行为界，其中的两个单词分别为 hello 和 world

示例 2

输入

this[SPC][SPC][SPC]is[SPC]a[SPC]test[SPC]input[SPC][SPC][RET]

输出

25 5 1

提示

不需要考虑平台差异。

代码

#include <iostream>
using namespace std;
char chs[100005];
int main() {
    char ch;
    int cnt = 0;
    int lines = 0;
    int words = 0;
    int last = 0;
    while(cin.get(ch)){
        chs[cnt] = ch;
        cnt += 1;
        if(ch == '\n')lines += 1;
    }
    for(int i = 0; i < cnt - 1; i++){
        if((chs[i] != ' ' && chs[i] != '\n') && (chs[i + 1] == ' ' || chs[i + 1] == '\n')){
            words += 1;
        }
    }
    cout << cnt << " " << words << " " << lines << endl;
    return 0;
}

特殊元素

给定若干个 int 类型整数，其中一个数出现了一次，其他数出现了两次，请找出出现了一次的那个数。

输入描述

N 个 int 类型整数，以空格隔开，N >= 1。

输出描述

输出出现了一次的那个数。

示例

示例 1

输入

5 5 2

输出

示例 2

输入

输出

提示

考虑输入的读取方式与位运算。

代码

#include <iostream>
using namespace std;
int nums[100005];
int main(){
    int n = 0;
    int k = 0;
    while(cin >> n){
        nums[k] = n;
        k++;
    }
    n = 0;
    for(int i = 0; i < k; i++){
        n ^= nums[i];
    }
    cout << n;
    return 0;
}

股票价格

乔治是一名股市爱好者，他有一种神奇的预知能力，他知道从他买股票的那天开始，股票的股价必定会呈现以下的变化：第1天不变，之后涨1天，跌1天，涨2天，跌1天，涨3天，跌1天…依此类推。

假设每次涨跌幅度皆为1，股票初始单价也为1，请计算出乔治购买股票的第n天每股股票单价为多少钱？

输入描述

输入仅包含一个 int 类型的整数 n（n>=1）。

输出描述

输出第n天的股票价格

示例

示例 1

输入

输出

示例 2

输入

输出

代码

#include <iostream>
using namespace std;
int main(){
    int n = 0;
    cin >> n;
    if(n == 1)cout << 1;
    else{
        int stock = 1;
        int k = 1;
        int m = k;
        for(int i = 0; i < n - 1; i++){
            if(m > 0){
                m--;
                stock++;
            }else if(m == 0){
                k++;
                m = k;
                stock--;
            }
        }
        cout << stock << endl;
    }
}

完成汉诺塔的最小移动次数

汉诺塔是递归算法的经典例题。游戏有 3 根柱子及 N 个不同大小的穿孔圆盘，在开始时，所有的圆盘都在第一根柱子上，且直径自上而下按升序排列，你需要将所有的盘子移动到第三根柱子上，且需要遵循以下规则：

每次只能移动一个盘子
盘子只能从柱子顶端滑出移到下一根柱子
盘子只能叠在比它大的盘子上

你需要计算出完成N层汉诺塔的最小移动步数

输入描述

输入为一个int型整数N，表示汉诺塔的层数（既汉诺塔中圆盘的数量）

输出描述

输出为一个int型整数M，表示完成汉诺塔需要移动圆盘的次数

示例1

输入

输出

示例2

输入

输出

提示

汉诺塔属于经典递归算法题，也可以用数学的方式解决

代码

#include <iostream>
using namespace std;
int cnt = 0;
void hanoi(int n){
   if(n == 0)return;
   else{
       hanoi(n - 1);
       cnt++;
       hanoi(n - 1);
   }
}

int main(){
    int n = 0;
    cin >> n;
    hanoi(n);
    cout << cnt;
    return 0;
}

数据结构作业用java写的版本

public class Hanoi {
    int cnt = 0;
    public void moveDisks(int n, char fromTower, char toTower, char auxTower){
        if (n == 1){
            System.out.println("move disk 1 from" + fromTower + "->" + toTower);
            cnt++;
        }
        else{
            moveDisks(n - 1, fromTower, auxTower, toTower);
            System.out.println("move disk " + n +" from" + fromTower + "->" + toTower);
            cnt++;
            moveDisks(n - 1, auxTower, toTower, fromTower);
        }
    }

    public static void main(String[] args) {
        Hanoi h = new Hanoi();
        h.moveDisks(4, 'A', 'C', 'B');
        System.out.println(h.cnt);
    }
}

倒数第i个单词的长度

给你一个字符串 s 与一个整数 i，s 由若干单词组成，单词前后用一些空格字符隔开。返回字符串中倒数第 i 个单词的长度。

输入描述

字符串 s，单词是指仅由字母组成、不包含任何空格字符的最大子字符串整数 i

1 <= s.length <= 10000 1 <= i <= 10000 s 仅有英文字母和空格 ' ' 组成 s 中至少存在一个单词

输出描述

一个整数

示例

示例 1：

输入：

Hello World
1

输出

解释

倒数第 1 个单词是“World”，长度为5。

示例 2：

输入：

    show me   the code  
2

输出

解释

倒数第 2 个单词是“the”，长度为3。

代码

#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<string> split(string s, char c){
    vector<string> ret;
    string temp = "";
    for(int i = 0; i < s.length();i++){
        if(s[i] != c){
            temp += s[i];
        }else if(s[i] == c && !temp.empty()){
            ret.push_back(temp);
            temp = "";
        }
    }
    ret.push_back(temp);
    return ret;
}
int main(){
    string input;
    getline(cin, input);
    vector<string> inputs = split(input, ' ');
    int n = 0;
    cin >> n;
    cout << inputs[inputs.size() - n].size();
    return 0;
}

部分乘积

给定 N 个 int 类型的整数，计算前 i 个值的乘积，其中 i 为 1, 2, ..., N。

输入描述

首先是 int 类型的整数 N，接下来是 N 个 int类型的整数，其中 N >= 1，保证为正数。

输出描述

对于第 i 个数，输出前 i 个数的乘积，如果结果溢出，输出 -1 并结束处理。

示例

示例 1

输入

9 1 2 3 4 5 6 7 8 9

输出

1 2 6 24 120 720 5040 40320 362880

示例 2

输入

5 512 1024 2048 4096 8192

输出

512 524288 1073741824 -1

代码

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int n;
    cin >> n;
    int nums[n];
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    sort(nums, nums + n, less<int>());
    long long ans = nums[0];
    cout << nums[0] << " ";
    for(int i = 1; i < n; i++){
        ans *= nums[i];
        if(ans > INT32_MAX){
            cout << -1;
            break;
        }else{
            cout << ans << " ";
        }
    }
}

Kiyotaka Wang's Blog

Kiyotaka | C++作业一

c++第一次作业

二进制转十进制

输入描述

输出描述

示例

示例 1

示例 2

提示

代码

最长公共后缀

输入描述

输出描述

示例

示例一

示例二

提示

代码

翻转数字

输入描述

输出描述

示例

示例 1

示例 2

示例 3

提示

代码

矩阵操作

1. add Matrix1 Matrix2

2. sub Matrix1 Matrix2

3. mul Matrix1 Matrix2

4. conv MatrixOut MatrixIn

输入描述

输出描述

示例 2

示例 1

代码

单词计数

输入描述

输出描述

示例

示例 1

示例 2

提示

代码

特殊元素

输入描述

输出描述

示例

示例 1

示例 2

提示

代码

股票价格

输入描述

输出描述

示例

示例 1

示例 2

代码

完成汉诺塔的最小移动次数

输入描述

输出描述

示例1

输入

输出

示例2

输入

输出

提示

代码

倒数第i个单词的长度

输入描述

输出描述

示例

示例 1：

输入：

输出

解释