最大公约数

牛客链接：NC151 最大公约数

题解1：辗转相减法

class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 求出a、b的最大公约数。 * @param a int * @param b int * @return int */
    int gcd(int a, int b) {
   
        // write code here
        int z= b;
        while(a!=b){
   
            if(a>b)
                a = a-b;
            if(b>a)
                b -= a;
        }
        return b;
    }
};

题解2：辗转相除法

class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 求出a、b的最大公约数。 * @param a int * @param b int * @return int */
    int gcd(int a, int b) {
   
        // write code here
        if(a<b)
            swap(a, b);
        int z = b;
        while(a%b!=0){
   
            z = a%b;
            a = b;
            b = z;
        }
        return z;
    }
};

最小公倍数

牛客链接：HJ108 求最小公倍数

解题思路：最小公倍数 = 两数之积除以最大公约数

#include<iostream>
using namespace std;

//递归求最大公约数 (x > y)
int gcd(int x, int y){
      
	if(y==0)
		return x;
	else
		return gcd(y,x%y);
}

int main(){
   
	int x,y;
	cin>>x;
	cin>>y;
	if(x<y)
		swap(x,y);
	cout<< x*y/gcd(x,y);
}

计算器(一)

牛客链接：NC240 计算器(一)

解法1

公式可以分为：左表达式值 + 符号位 + 右表达式值
我们可以考虑所有数字为+号，当出现-的时候，表示后续右表达式值为负数，最终还是执行加法操作。
当遇到 ‘( ’的时候，将之前的计算结果与符号位放入栈中，当遇到‘)’的时候，去除符号位，表示当前括号内的值的真实大小，在取出结果栈中的之前结果求和，就是当前正确的结果。

class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型 */
    int calculate(string s) {
   
        // write code here
        stack<int> num;
        stack<char> sign;
        int temp = 0, res = 0, sig = 1;
        for(int i =0;i<s.size();++i){
   
            if(i<s.size() && s[i] - '0'>=0 &&  s[i] - '0'<=9){
       //防止有>9的数字
                temp = temp * 10 + (s[i] - '0');
            }
            else if(i<s.size() && (s[i] == '-' or  s[i] == '+')){
      //确定当前位的符号位，默认为+
                res += sig * temp;
                temp = 0;
                sig = (s[i]=='+')?1:-1;
            }
            else if(i<s.size() && s[i] == '('){
         //遇到(
                num.push(res);
                sign.push(sig);
                res = 0;                //初始化括号内计算值与符号
                sig = 1;
            }
            else if(i<s.size() && s[i] == ')') {
         //遇到)
                res += sig*temp;
                temp = 0;
                res *= sign.top();
                sign.pop();
                res += num.top();
                num.pop();
            }
        }
        res += sig*temp;        //最终的一个数字求和（i== s.size()时退出循环）
        return res;
    }
};

解法2

将所有的括号拆开，即1-(1-2) = 1-1+2, 所以要保留括号外的那个字符，从而正确获得括号内的用于求和的值。

class Solution {
   
public:
    int calculate(string s) {
   
        stack<int> sign;
        int res = 0, tmp = 0, sig = 1;
// 分别位最后的答案，临时数，符号
        sign.push(sig);
// 我们开辟的栈用于存储符号
        for (auto &it : s) {
   
            if(it>='0' && it<='9') tmp = tmp*10 + it-'0';
            else{
   
                res += sig * tmp;       //遇到符号，计算之前的结果
                tmp = 0;				//默认下一数字的值
                switch(it){
       			//判断符号真实正负
                    case '+':
                        sig = 1 * sign.top();
                        break;
                    case '-':
                        sig = -1 * sign.top();
                        break;
                    case '(':
                        sign.push(sig);
                        break;
                    default:
                        sign.pop();
                        break;
                }
            }
        }
        res += sig * tmp;
// 把最后一个也算进去
        return res;
    }
};

计算器(二)

牛客链接:NC241 计算器(二)

和上面一题类似，但是去掉了括号，加入了乘除。我们这里通过一个栈保存局部的结果（将乘法除法以及减法算出来的结果看成是一部分，最终只存在加法操作），用两个变量保存是否当前是在执行局部乘法或者除法操作，如果是要先进行乘法和除法的运算。

#include <numeric>
class Solution {
   
public:
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型 */
    int calculate(string s) {
   
        // write code here
        stack<int> nums;
        int temp = 0, res =0, sig = 1;
        bool mult = false, div = false;   //是否正在进行乘除法
        for(char c:s){
   
            if(c>='0' && c<='9') temp = temp*10 + c-'0';
            else{
   
                if(mult){
             			//正在执行乘法操作
                    temp *=  nums.top();   //弹出首个保存的值，用于执行乘法。
                    mult = false;
                    nums.pop();
                }
                else if(div){
                    //正在执行除法操作
                    temp =  nums.top()/temp;
                    div = false;
                    nums.pop();
                }
                
                if(c == '+' )                  //加法减法直接连同符号位一起保存进栈
                {
   
                    nums.push(temp*sig);
                    sig = 1;
                    temp = 0;
                }
                else if(c == '-' )
                {
   
                    nums.push(temp*sig);
                    sig = -1;
                    temp = 0;
                }
                else if(c == '*' )   //乘除法，将当前乘数或者除数保存进结果，之后获得下一个值之后，在将head元素拿出来使用。
                {
   
                    nums.push(temp*sig);
                    mult = true;
                    sig = 1;
                    temp = 0;
                }
                else if(c == '/' )
                {
   
                    nums.push(temp*sig);
                    div = true;
                    sig = 1;
                    temp = 0;
                }
            }
        }
        
        res = 0;
        while(div or mult)     //如果最后一个操作是乘除，先解决乘除法
        {
   
            if(mult){
   
                temp*=nums.top();
                mult = false;
                nums.pop();
            }
            else if(div){
   
                temp=nums.top()/temp;
                div = false;
                nums.pop();
            }
        }
        
        nums.push(temp*sig);    //将结果加入栈
        while(nums.size() >0){
   
            res+=nums.top();
            nums.pop();
        }
        return res;
    }
};