Niuke - Huawei question bank (51~60)

---

51. Output the penultimate... In the one-way linked list k Nodes

#include <bits/stdc++.h>

using namespace std;

struct ListNode
{
    
    int m_nKey;
    ListNode* m_pNext;
    ListNode() : m_nKey(0), m_pNext(nullptr){
    };
    ListNode(int x) : m_nKey(x), m_pNext(nullptr){
    };
};

ListNode* findNode(ListNode* head, int k){
    
    ListNode* slow = head;
    ListNode* fast = head;
    
    while(k--){
    
        fast = fast->m_pNext;
    }
    //fast = fast->m_pNext;
    
    while(fast != nullptr){
    
        slow = slow->m_pNext;
        fast = fast->m_pNext;
    }
    
    return slow;
}

int main(){
    
    int num = 0;
    while(cin >> num){
    
        // Building linked lists 
        ListNode* head = new ListNode();
        ListNode* dummyHead = head;
        
        while(num--){
    
            int nodeNum = 0;
            cin >> nodeNum;
            ListNode* next = new ListNode(nodeNum);
            head->m_pNext = next; //
            head = next; //
        }
        
        // Looking for the penultimate k Nodes 
        int k = 0;
        cin >> k;       
        ListNode* res = findNode(dummyHead->m_pNext, k); //
        
        if(res != nullptr){
    
            cout << res->m_nKey << endl;
        }
        else{
    
            cout << "0" << endl;
        }
    }
    
    return 0;
}

52. Calculates the edit distance of the string

#include <bits/stdc++.h>

using namespace std;

// Dynamic programming 
int minDistance(string s1, string s2){
    
// There are actually only three different operations ：
// In the word  A  Insert a character in ;
// In the word  B  Insert a character in ;
// Modify the word  A  A character of .
// character string  A  It's empty , If you follow   The switch to  ro, Obviously, the edit distance is a string  B  The length of , Here is  2;
// character string  B  It's empty , If you follow  horse  The switch to  , Obviously, the edit distance is a string  A  The length of .
// Dynamic programming can be used to solve this problem .
// We use it  D[i][j]  Express  A  Before  i  Letters and  B  Before  j  The edit distance between letters .
    
    int n = s1.size(); int m = s2.size();
    if(n * m == 0) return n + m; // One is empty 
    
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    // Boundary initialization 
    for(int i = 0; i <= n; i++){
    
        dp[i][0] = i;
    }
    for(int j = 0; j <= m; j++){
    
        dp[0][j] = j;
    }
    
    for(int i = 1; i <= n; i++){
    
        for(int j = 1; j <= m; j++){
    
            if(s1[i - 1] == s2[j - 1]){
     //
                 //A  Of the  i  Characters and  B  Of the  j  The two characters are the same , No modification is required 
                dp[i][j] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1]);
            }
            else{
    
                dp[i][j] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
            }
        }
    }

    return dp[n][m];
  
}

int main(){
    
    string s1 = "";
    string s2 = "";
    while(cin >> s1 >>s2){
    
        cout << minDistance(s1, s2) << endl;
    }
    
    return 0;
}

53. The deformation of Yang Hui triangle

#include <bits/stdc++.h>

using namespace std;

// Looking for a regular 
// Analysis methods :
// 1
// 1 1 1
// 1 2 3 2 1
// 1 3 6 7 6 3 1
// 1 4 10 16 19 16 10 4 1
// 1 5 15 30 45 51 45 30 15 5 1
// 1 6 21 50 90 126 141 126 90 50 21 6 1
// 1 7 28 77
// 1 8 36 112
// 1 9 51 156
// 10 
// Through the above data analysis, the law is  {-1,-1,2,3,2,4,2,3,2,4,...}

void process(int n, int& res){
    
    if(n == 1 || n == 2) {
    
        res = -1;
        return;
    }

    /*// Build an ordinary Yang Hui triangle  vector<vector<int>> matrix(n + 1, vector<int>(n + 1, 0)); // // Two dimensional array  for(int i = 0; i <= n; i++){ matrix[i].resize(i + 1); // The first i All lines have i+1 Elements  matrix[i][0] = 1; matrix[i][i] = 1; // From beginning to end 1 for(int j = 1; j < i; j++){ // matrix[i][j] = matrix[i - 1][j - 1] + matrix[i - 1][j]; } }*/
    
    int myInt[]={
    4, 2, 3, 2};
    res=myInt[(n - 2) % 4]; //
    
    return;
    
}

int main(){
    
    int n = 0;
    while(cin >> n){
    
        int res = 0;
        process(n, res);
        
        cout << res << endl;
    }
    
    return 0;
}

54. Expression evaluation

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int calculate(int a, int b, char sym){
    
    switch(sym){
    
        case '+':
            return a + b;
            break;
        case '-':
            return a - b;
            break;
        case '*':
            return a * b;
            break;
        case '/':
            return a / b;
            break;
        default:
            return 0;
            break;
    }
}

int process(string s){
    
    int flag = 0; //0 Unsigned ,1 Is a plus sign ,2 It's a minus sign 
    stack<int> numst;
    stack<char> symbolst;
    
    for(int i = 0; i < s.size(); i++){
    
        if(isdigit(s[i])){
    
            int j = i; int num = 0;
            while(i + 1 < s.size() && isdigit(s[i + 1])) i++;
            string tmp = s.substr(j, i - j + 1);
            for(int k = 0; k < tmp.size(); k++){
    
                num = num * 10 + (tmp[k] - '0');
            }   
            
            if(flag == 2) num = 0 - num;
            flag = 0;
            numst.push(num);
        }
        else if(s[i] == '*' || s[i] == '/' || s[i] == '('){
    
            symbolst.push(s[i]);
        }
        else if(s[i] == '+' || s[i] == '-'){
    
            if(i == 0 || s[i - 1] == '('){
    
                if(s[i] == '+') flag = 1;
                else flag = 2;
            }
            
            while(!flag && !symbolst.empty() && symbolst.top() != '('){
    
                int b = 0, a = 0;
                char sym_tmp;
                b = numst.top(); numst.pop();
                a = numst.top(); numst.pop();
                sym_tmp = symbolst.top(); symbolst.pop();
                numst.push(calculate(a, b, sym_tmp));
            }
            
            if(!flag) symbolst.push(s[i]); //
        }
        else if(s[i] == ')'){
    
            while(symbolst.top() != '('){
    
                int b = 0, a = 0;
                char sym_tmp;
                b = numst.top(); numst.pop();
                a = numst.top(); numst.pop();
                sym_tmp = symbolst.top(); symbolst.pop();
                numst.push(calculate(a, b, sym_tmp));
            }
            symbolst.pop();
        }
        else{
    
            cout << "error!" << endl;
        }
    }
    
    while(!symbolst.empty()){
    
        int b = 0, a = 0;
        char sym_tmp;
        b = numst.top(); numst.pop();
        a = numst.top(); numst.pop();
        sym_tmp = symbolst.top(); symbolst.pop();
        numst.push(calculate(a, b, sym_tmp));
    }
    
    return numst.top();
}

int main(){
    
    string str = "";
    while(cin >> str){
    
        int res = process(str);
        cout << res << endl;
    }
    
    
    return 0;
}

55. pick 7

#include <bits/stdc++.h>

using namespace std;

bool is_7_beishu(int num){
    
    if(num % 7 == 0){
    
        return true;
    }
    return false;
}

bool bao_han_7(int num){
    
    string tmp = to_string(num);
    for(char c : tmp){
    
        if(c == '7'){
    
            return true;
        }
    }
    
    return false;
}

void process(int n, int& res){
    
    for(int i = 1; i <= n; i++){
    
        if(is_7_beishu(i) || bao_han_7(i)){
    
            res++;
        }
    }
}

int main(){
    
    int n = 0;
    cin >> n;
    
    int res = 0;
    process(n, res);
    
    cout << res << endl;
    
    return 0;
}

56. Perfect number calculation

#include<bits/stdc++.h>

using namespace std;

bool isAllNum(int num){
    
    int tmp = 0;
    for(int i = 1; i < num; i++){
    
        if(num % i == 0){
    
            tmp += i;
        }
    } 
    if(tmp == num){
    
        //cout << num<<" It's a complete number ."<<endl;
        return true;
        
    }
    return false;
}

int main(){
    
    int num = 0;
    while(cin>>num){
    
        int res = 0;
        for(int i = 1; i <= num; i++){
    
            if(isAllNum(i)) res++;   
        }        
        cout<<res<<endl;
    }
        
    return 0;
}

57. High precision integer addition

#include <bits/stdc++.h>

using namespace std;

long str2int(string s){
    
    long res = 0;
    
    for(int i = 0; i < s.size(); i++){
    
        res = res * 10 + (s[i] - '0');
        //cout << " " << res << endl;
    }
    //cout << res << endl;
    return res;
}

int main(){
    
    string A = "";
    string B = "";
    while(cin >> A >> B){
    
        /*long s1Num = str2int(s1); long s2Num = str2int(s2); cout << s1Num + s2Num << endl; // It's out of range */
        
        int i = A.size() - 1; int j = B.size() - 1;
        
        string res = "";
        int carry = 0; // carry 
        while(i >= 0 || j >= 0){
    
            int digitA = i >= 0 ? A[i--] - '0' : 0;
            int digitB = j >= 0 ? B[j--] - '0' : 0;
            
            int sum = digitA + digitB + carry;
            carry = sum / 10; // Whether there is carry 
            sum = sum % 10; // Current non carry sum 
            
            res += to_string(sum);
        }
        
        if(carry == 1) res += "1"; // The last carry  //
        
        reverse(res.begin(), res.end()); //
        
        cout << res << endl;
    }
    
    return 0;
}

58. Input n It's an integer , Output the smallest of them k individual

#include <bits/stdc++.h>

using namespace std;

int main(){
    
    int n = 0, k = 0;
    while(cin>>n>>k){
    
        vector<int> vec(n, 0);
        for(int i = 0; i < n; i++){
    
            int num = 0;
            cin>>num;
            vec[i] = num;
        }
        
        sort(vec.begin(), vec.end());
        
        for(int i = 0; i < k; i++){
    
            cout << vec[i] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

59. Find the first character in a string that appears only once

#include <bits/stdc++.h>

using namespace std;

void process(string s, char& c){
    
    unordered_map<char, int> m;
    for(char ch : s){
    
        m[ch]++;
    }
    
    for(char ch : s){
    
        if(m[ch] == 1){
    
            c = ch;
            break;
        }
    }
}

int main(){
    
    string str = "";
    getline(cin, str);
    
    char res;
    process(str, res);
    if(res)
        cout << res << endl;
    else
        cout << "-1" << endl;
    return 0;
}

60. Find the two prime numbers that make up an even number

#include <bits/stdc++.h>

using namespace std;

bool isSuShu(int num){
    
    for(int i = 2; i < num; i++){
    
        if(num % i == 0){
    
            return false;
        }
    }
    
    return true;
}

int main(){
    
    int num = 0;
    while(cin >> num){
    
        if(num <= 2 || num % 2 != 0){
    
            break;
        }
        
        vector<int> res;
        int minSub = INT_MAX; // Save the minimum difference 
        unordered_map<int, pair<int, int>> m; // Key is difference , The value is firstNum and secondNum
        for(int i = num; i >= num / 2; i--){
    
            int secondNum = i;
            int firstNum = num - i;
            // Judge whether two numbers are prime numbers   And calculate the difference   Save in hash table 
            if(isSuShu(secondNum) && isSuShu(firstNum)){
    
                int sub = secondNum - firstNum;
                //cout << sub << endl;
                m[sub] = make_pair(firstNum, secondNum);
                
                minSub = min(minSub, sub);             
            }  
        }
        
        for(auto item = m.begin(); item != m.end(); item++){
    
            if(minSub == item->first){
     // Traverse to find the corresponding position of the minimum difference in the hash table 
                res.push_back(item->second.first);
                res.push_back(item->second.second);
            }
        }
        
        for(int i = 0; i < res.size(); i++){
    
            cout << res[i] << endl;
        }
    }
    
    return 0;
}