Skip to content

Latest commit

 

History

History
686 lines (557 loc) · 12.5 KB

0.C++语法刷题练习.md

File metadata and controls

686 lines (557 loc) · 12.5 KB

变量、表达式与顺序语句

语法

  1. define语句末尾不加分号；

  2. 输出三位小数

cout.setf(ios_base::fixed);

cout.precision(3);

cin 和 scanf读入字符串时遇到空格就停止了。

圆的面积

输入包含一个浮点数，为圆的半径 R。Π取3.14159

输出格式为 A=X，其中 X 为圆的面积，用浮点数表示，保留四位小数。

#include<cstdio>
#define PI 3.14159
using namespace std;

int main(){
    double s,r;
    scanf("%lf",&r);
    s=r*r*PI;
    printf("A=%.4lf",s);
    
    return 0;
}

简单乘积

输入两行，每行包含一个整数

输出格式为 PROD = X，其中 X 为乘积结果。

#include<iostream>
using namespace std;

int main(){
    int a[2];
    for(int i=0;i<=1;i++)cin>>a[i];
    cout<<"PROD = "<<a[0]*a[1]<<endl;
    return 0;
    
}
#include<iostream>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    cout << "PROD = " << a * b << endl;
    return 0;
}

乘积相加

输入两行，每行一个浮点数，第一个数乘5，第二个数乘7。

输出格式为 MEDIA = X，其中 X 为结果，结果保留五位小数。

#include<cstdio>
using namespace std;
int main()
{
    double a,b;
    scanf("%lf",&a);
    scanf("%lf",&b);
    printf("MEDIA = %.5lf",a*5+7*b);
    return 0;
}

球的面积

输入半径r，输出球的面积，结果保留三位小数，Π取3.14159

#include<cstdio>
# define PI 3.14159
using namespace std;

int main(){
    double a;
    scanf("%lf",&a);
    printf("VOLUME = %.3lf",4/3.0*a*a*a * PI);
    return 0;
}

返回三个数最大值

输入一行包含三个整数，输出最大值

解法一：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,max;
    cin>>a>>b>>c;
    if(a>b)
        if(a>c)
            max=a;
        else
            max=c;
    else
        if(b>c)
            max=b;
        else
            max=c;
    cout<<max<<" eh o maior";
    return 0;
}

解法二：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,max;
    cin>>a>>b>>c;
    max=(a+b+abs(a-b))/2;
    max=(max+c+abs(max-c))/2;
    return 0;
}

解法三：

#include <iostream>
#include <algorithm>///一定要写这个头文件
using namespace std;
int main(){
    int a,b,c;
    int max1 = 0;
    cin>>a>>b>>c;
    max1 = max(a,b);///调用库函数max
    max1 = max(max1,c);

    cout<<max1<<" eh o maior"<<endl;
    return 0;
}

两点间距离

输入四个整数，空格分隔，分别代表x1，y1,x2,y2,输出两点间距离

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    double x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    printf("%.4lf", sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2)));
    return 0;
}

循环语句

换零钱

给定一个整数,换成面值有 100,50,20,10,5,2,1的钞票，钞票数量应该尽量少

#include <iostream>

using namespace std;

int main()
{
    int n, a[7] = {100, 50, 20, 10, 5, 2, 1};
    cin >> n;
    printf("%d\n", n);
    for (int i = 0; i < 7; i ++ )
    {
        printf("%d nota(s) de R$ %d,00\n", n / a[i], a[i]);
        n %= a[i];
    }
    return 0;
}

菱形输出

输入一个奇数 n，输出一个由 * 构成的 n 阶实心菱形。

abs(sx - i) + abs(sy - j) <= n / 2

输入：

5

输出

  *  
 *** 
*****
 *** 
  *  

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    int sx = n / 2, sy = n / 2;

    for (int i = 0; i < n ; i ++ )
    {
        for (int j = 0; j < n; j ++ )
        {
            if ( abs(sx - i) + abs(sy - j) <= n / 2 ) cout << "*";
            else cout << " ";
        }
        cout << endl;    
    }

    return 0;
}

数组

螺旋数组

#include<bits/stdc++.h>
using namespace std;
int n,m,a[109][109],x,y,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0},u;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n*m;++i){
        a[x][y]=i,x+=dx[u],y+=dy[u];
        if(x<0||y<0||x>=n||y>=m||a[x][y]) x-=dx[u],y-=dy[u],u=(u+1)&3,x+=dx[u],y+=dy[u];
    }
    for(int i=0;i<n;++i){for(int j=0;j<m;++j) cout<<a[i][j]<<" ";cout<<"\n";}
}

字符串

字符串长度

输入一个字符串，输出其长度

#include<iostream>
#include<cstring>
using namespace std;
int main(){
    string str;
    getline(cin,str);
    cout<<str.size()<<endl;
    return 0;
}

连续字符

输入一个字符串，输出这个字符串连续长度最大的字符及其连续长度

#include <iostream>
using namespace std;
int main()
{
    string str,maxs;//maxs记录最大长度时的字符
    cin >> str;
    int j = 0,cnt=-1;
    for(int i = 0; i < str.size(); i ++)
    {
        if (str[i]==str[j]){
            if(i-j+1>cnt){
                maxs=str[i];
                cnt=i-j+1;
            }
        }
        else{
            j=i;
        }
    }
    cout << maxs << " " << cnt<< endl;
}

只出现一次

输入一个只含小写字符的字符串，判断其中是否有字符只出现一次

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int main()
{
    string A;
    bool s=0;
    while(getline(cin,A))
    {
        for(int i=0;i<A.size();i++)
        {
            if(A.find(A[i])==A.rfind(A[i]))
            {
                cout<<A[i]<<endl;
                s=1;
                break;
            }
        }
    }
    if(s==0)
        cout<<"no"<<endl;
    return 0;
}

字符串拼接

输入一个字符串一个数字，将字符串前n位拼接在后面

class Solution {
public:
    string leftRotateString(string str, int n) {

        return str.substr(n)+str.substr(0,n);
    }
};
class Solution {
public:
    string leftRotateString(string str, int n) {
        string s;
        for(int i=0;i<str.size();i++){
            s+=str[(i+n)%str.size()];
        }
        return s;
    }
};

加法

计算1+2+…+n

class Solution {
public:
    int getSum(int n) {
        char a[n][n+1];
        return sizeof(a)>>1;
    }
};

反转链表

迭代

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *prev = nullptr;
        ListNode *cur = head;
        while (cur)
        {
            ListNode *next = cur->next;
            cur->next = prev;
            prev = cur, cur = next;
        }
        return prev;
    }
};

递归

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode *tail = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return tail;
    }
};

两个链表的第一个公共节点

class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        auto p = headA, q = headB;
        while(p != q) {
            if(p) p = p->next;
            else p = headB;
            if (q) q = q->next;
            else q = headA;
        }
        return p;
    }
};

题目描述 求一个排好序的数组中k的个数

解题思路 目的是练习stl和常用的库函数

题解一：使用有序多重集合multiset

class Solution {
    public:
    int getNumberOfK(vector<int>& nums , int k) {
        multiset<int> s;
        for(int x : nums) s.insert(x);
        return s.count(k);
    }
};

题解二：遍历vector，计数

class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        int cnt = 0;
        for(int x : nums)
            if(x == k)
                cnt++;
        return cnt;
    }
};

题解三：使用lower_bound和upper_bound,指针运算得出次数

class Solution {
    public:
    int getNumberOfK(vector<int>& nums , int k) {
        auto l = lower_bound(nums.begin(), nums.end(), k);  
        //在排好序的数组中，利用二分搜索找到指向满足nums >= k的nums的最小指针
        auto r = upper_bound(nums.begin(), nums.end(), k);
        //在排好序的数组中，利用二分搜索找到指向满足nums > k的nums的最小指针
        return r - l;
    }
};
int num = count(nums.begin(), nums.end(), k);

数组奇数在偶数前面

class Solution {
public:
    void reOrderArray(vector<int> &array) {
         int l = 0, r = array.size() - 1;
         while (l < r) {
             while (l < r && array[l] % 2 == 1) l ++ ;
             while (l < r && array[r] % 2 == 0) r -- ;
             if (l < r) swap(array[l], array[r]);
         }
    }
};

尾到头打印链表

// 法一：reverse 答案数组. 时间:O(n);空间:O(n). 4ms; 8.5MB
class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
        vector<int> res;
        while (head) {
            res.push_back(head->val);
            head = head->next;
        }
        // reverse(res.begin(), res.end());
        // return res;
        return vector<int>(res.rbegin(), res.rend());
    }
};

// 法二：递归. 时间:O(n);空间:栈空间O(n). 4ms; 10.8MB
class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
        if (!head) return {};
        auto res = printListReversingly(head->next);
        res.push_back(head->val);
        return res;
    }
};

// 法三：辅助栈法. 时间:O(n);空间:O(n). 4ms; 8.5MB
class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
        stack<int> s;
        while (head) {
            s.push(head->val); // 存的是 val
            head = head->next;
        }

        int n = s.size();
        vector<int> res(n);
        for (int i = 0; i < n; i ++ ) {
            res[i] = s.top();
            s.pop();
        }

        return res;
    }
};

栈实现队列

算法 (栈，队列) O(n)O(n) 这是一道基础题，只要把功能实现对就可以，不需要考虑运行效率。

我们用两个栈来做，一个主栈，用来存储数据；一个辅助栈，用来当缓存。

push(x)，我们直接将x插入主栈中即可。 pop()，此时我们需要弹出最先进入栈的元素，也就是栈底元素。我们可以先将所有元素从主栈中弹出，压入辅助栈中。则辅助栈的栈顶元素就是我们要弹出的元素，将其弹出即可。然后再将辅助栈中的元素全部弹出，压入主栈中。 peek()，可以用和pop()操作类似的方式，得到最先压入栈的元素。 empty()，直接判断主栈是否为空即可。 时间复杂度分析 push()：O(1)O(1)； pop(): 每次需要将主栈元素全部弹出，再压入，所以需要 O(n)O(n) 的时间； peek()：类似于pop()，需要 O(n)O(n) 的时间； empty()：O(1)O(1)； C++ 代码

class MyQueue {
    public:
    /** Initialize your data structure here. */
    stack<int> stk, cache;
    MyQueue() {
    }

    /** Push element x to the back of queue. */
    void push(int x) {
        stk.push(x);
    }

    void copy(stack<int> &a, stack<int> &b) {
        while (a.size()) {
            b.push(a.top());
            a.pop();
        }
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        copy(stk, cache);
        int res = cache.top();
        cache.pop();
        copy(cache, stk);
        return res;
    }

    /** Get the front element. */
    int peek() {
        copy(stk, cache);
        int res = cache.top();
        copy(cache, stk);
        return res;
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return stk.empty();
    }
};

/**

 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * bool param_4 = obj.empty();
  * */

最小k个数

class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        sort(input.begin(),input.end());
        input.erase(input.begin() + k,input.end());
        return input;
    }
};

和为S的两个数

//cpp
class Solution {
public:
    vector<int> findNumbersWithSum(vector<int>& nums, int target) 
    {
        unordered_map<int, int> hash;//创建哈希表
        for (int i = 0; i < nums.size(); ++i) {
            if(hash[target - nums[i]] == 0)//如果哈希表中没有target - nums[i]
                hash[nums[i]]++;//nums[i]出现次数加1
            else//如果哈希表中有target - nums[i]
                return {nums[i], target - nums[i]};//返回答案
        }
        return {};

    }
};