NC103 反转字符串

//输入："abcd"
//返回值："dcba"

class Solution {
public:
    /**
     * 反转字符串
     * @param str string字符串 
     * @return string字符串
     */
    string solve(string str) {
        // write code here
        string r;
        for(int i = 0; i < str.length(); ++i)
        {
            r = str[i] + r;
            //每次取出一位加到最后面
        }
        return r;
    }
};

//还有一种方法是直接用C++里的reverse()函数
#include<string>
class Solution {
public:
    /**
     * 反转字符串
     * @param str string字符串 
     * @return string字符串
     */
    string solve(string str) {
        // write code here
        reverse(str.begin(),str.end());
        return str;
    }
};

/**
*上面的方法用到了begin()和end()成员
*begin() 返回一个迭代器，指向容器的第一个元素
*end() 返回一个迭代器，它指向容器的最后一个元素的下一个位置
*下面的方法用到了rbegin()和rend()成员
*rbegin() 返回一个逆序迭代器，它指向容器的最后一个元素
*rend() 返回一个逆序迭代器，它指向容器的第一个元素前面的位置
*/
class Solution {
public:
    string solve(string str) {
       return string(str.rbegin(), str.rend());
    }
};

NC65 斐波那契数列

//输入：4
//返回值：3
//说明：根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为4。
//斐波那契数列：f[n]=f[n-1]+f[n-2],f[0]=1,f[1]=1

class Solution {
public:
    int Fibonacci(int n) {
        if(n<=2){ 
            return 1; 
        } 
        else{ 
        return Fibonacci(n-2)+Fibonacci(n-1); 
            //直接递归公式，比较好理解
        }  
    }
};

//上面是用的递归的方法，下面是从讨论区看到的递推的方法
class Solution {
public:
    int Fibonacci(int n) {
        int f1 = 1, f2 = 1;
        for (int i = 3; i <= n; i++) {
            f2 = f1 + f2;
            //得到f1和f2后一位的数
            f1 = f2 - f1;
            //得到上面那个数的前一位数，也就是之前f2的值
        }
        return f2;
    }
};

NC151 最大公约数

//输入：3,6
//返回值：3

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

//相减法
class Solution {
public:
    int gcd(int a,int b)
    {
        while(a!=b)
        {
            if(a>b)
            {
            a=a-b;
            }
            else if(a<b)
            {
            b=b-a;    
            }
        }
        //不断的用较大数减去较小数，直到相等，则为最大公约数
        return a; 
    }
};

//穷举法
class Solution {
public:
    int gcd(int a,int b)
    {
        int c;
        if(a>b)
        c=b;
        else if(a<b)
        c=a;
        while(a%c!=0||b%c!=0)
        {
            c--;
        }
        //取出两个数中的较小一个，判断与另一个数相除余数是否为0，不为0就自减1，直到余数为0
        return c;
    }
};

NC141 判断是否为回文字符串

//输入："absba"
//返回值：true
//输入："ranko"
//返回值：false

//最直观的做法，取最前面的后最后面的逐个对比
class Solution {
public:
    bool judge(string str) {
        // write code here
        int end = str.length()-1;
        for(int i = 0;i<str.length()/2;i++)
        {
            if(str[i] != str[end-i])
            {
                return false;
            }
        }
        return true;
    }
};

//双指针法，两个指针一个从前往后走，一个从后往前走，碰到不一样的就返回出来
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param str string字符串 待判断的字符串
     * @return bool布尔型
     */
    bool judge(string str) {
        // write code here
        if(str.length()<1)
        {
            return true;
        }
      int left = 0;
      int right = str.length() - 1;
      //遍历数组
      while (left <= right) {
          if(str[left]==str[right])
          {
              left++;
              right--;
          }
          else
          {
              return false;
          }
      }
        return true;
    }
};

//这种用语言自带的函数实现的，个人感觉已经脱离了算法的范畴
class Solution {
public:
    bool judge(string str) {
        string tmp(str.rbegin(),str.rend());
        return tmp==str;
    }
};

NC38 螺旋矩阵

//输入：[[1,2,3],[4,5,6],[7,8,9]]
//返回值：[1,2,3,6,9,8,7,4,5]

//这道题花的时间最长，事实上只要找到矩阵的边界，就能做出来了
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        if(matrix.empty()||matrix[0].empty())
          return vector<int>();
        //空矩阵
        vector<int> res;
        int n=matrix.size();
        int m=matrix[0].size();
        //m行 n列
        int top=0,left=0;
        //上边界和左边界
        int right=m-1,bottom=n-1;
        //右边界和下边界
        while(res.size()<m*n)
        {
            if(top<=bottom)
            {
                for(int i=left;i<=right;i++){
                    res.emplace_back(matrix[top][i]);
                    //从左上角到右上角
                }
            }
            top++;
            if(left<=right)
            {
                for(int i=top;i<=bottom;i++){
                    res.emplace_back(matrix[i][right]);
                    //从右上角到右下角
                }
            }
            right--;
            if(top<=bottom)
            {
                for(int i=right;i>=left;i--){
                    res.emplace_back(matrix[bottom][i]);
                    //从右下角到左下角
                }
            }
            bottom--;
            if(left<=right)
            {
                for(int i=bottom;i>=top;i--){
                    res.emplace_back(matrix[i][left]);
                    //从左下角到左上角
                }
            }
            left++;
        }
        return res;
    }
};