本文主要是介绍LintCode 练习【C++】，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

这里是LintCode【新手必刷编程50题】的解题思路

目录

1.反转一个三位整数

2.A+B问题

 3.巴什博弈

4.计算圆的周长和面积 

5.简单计算器 

 6.三数之中的最大值

 7.大小写转换

8.判断数字与字母字符 

 9.月份天数

11.生成给定大小的数组

12.交换数组两个元素 

13.整数排序

14. 数组的最大值

15. 打印X

16.寻找素数

17. 寻找最大值

18.旋转数组

 19.回文数II

 20.杨辉三角

21.翻转数组

 22.移动零

 23.数组第二大数

 24.分解质因数

25.加一

26.冰雹猜想

27.翻转字符串

28.数组剔除元素后的乘积

29.主元素

30. Fizz Buzz 问题

31.转换字符串到整数（容易版）

 32.大小写转换 II

33.字符串查找

34.转换成小写字母

 35.两字符串和

36.首字母大写

37.回文数

38.最长单词

39.最后一个单词的长度

40.最大字母

41.翻转字符串

42.二阶阶乘

 43.实现栈

44.队列维护

 45.有效的括号序列

46. 小括号匹配

 47.斐波纳契数列

 48.二叉树的后序遍历

49.二叉树的中序遍历

50.二叉树的前序遍历

1.反转一个三位整数

样例

样例 1：

输入：

number = 123

输出：

321

样例 2：

输入：

number = 900

输出：

9

运用了最基础简单的思路，除法和取余得到该三位数的个、十、百三个数字，调整顺序输出即可，记得个位或者十位个位均为零的情况要讨论一下。

class Solution 
{
public:
    /**
     * @param number: A 3-digit number.
     * @return: Reversed number.
     */
    int reverseInteger(int number) 
    {
        // write your code here
        int a=number/100;
        int b=number/10%10;
        int c=number%10;
        if(c==0&&b==0)
        {
            return a;
        }
        else if(c==0)
        {
            int s1=b*10+a;
            return s1;
        }
        else
        {
            int s2=c*100+b*10+a;
            return s2;
        }

    }
};

2.A+B问题

给出两个整数 a 和 b , 求他们的和并以整数（int）的形式返回。

样例 ：

输入：

a = 1
b = 2

输出：

3

没什么好说的

class Solution {
public:
    /**
     * @param a: An integer
     * @param b: An integer
     * @return: The sum of a and b 
     */
    int aplusb(int a, int b) {
        // write your code here
        int c=0;
        c=a+b;
        return c;
    }
};

 3.巴什博弈

描述

你正在和朋友玩一个游戏：桌子上有一堆石头，每一次你们都会从中拿出1到3个石头。拿走最后一个石头的人赢得游戏。游戏开始时，你是先手。假设两个人都绝对理性，都会做出最优决策。给定石头的数量，判断你是否会赢得比赛。

举例：有四个石头，那么你永远不会赢得游戏。不管拿几个，最后一个石头一定会被你的朋友拿走。

样例 1：

输入：n = 4 
输出：False
解析：先手取走1,2或者3，对方都会取走最后一个

样例 2：

输入：n = 5 
输出：True
解析：先手拿1个，必胜

由两个案例，我们会发现一个事情，当一人拿走石头后，可以将剩余石头数量维持在4时，则下一个拿石头的人必输。因此，当我们先手时，只需要考虑初始石头的数量是否为4的倍数。

因为若不为4的倍数，我们可以拿走石头，让它维持在4的倍数，而对手一次无法拿走大于3个的石头，导致下一次我们仍可以将其维持在4的倍数，因此获得胜利。反之，若不为4的倍数，则先手必输。 

class Solution {
public:
    /**
     * @param n: an integer
     * @return: whether you can win the game given the number of stones in the heap
     */
    bool canWinBash(int n) {
        // Write your code here
        return n%4!=0;
    }
};

4.计算圆的周长和面积 

给定一个整数r代表一个圆的半径。
你的任务是返回一个数组。
其中数组的第一个元素代表圆的周长，数组的第二个元素代表圆的面积。（PI=3.14）

样例 1:

输入 : r = 2
输出 : [12.56, 12.56]

利用vector容器解决，注意push_back的先后顺序。 

class Solution {
public:
    /**
     * @param r: a Integer represent radius
     * @return: the circle's circumference nums[0] and area nums[1]
     */
    vector<double> calculate(int r) 
    {
        // write your code here
        double PI=3.14;
        double c=2*PI*r;
        double s=PI*r*r;
        vector<double> v;
        v.push_back(c);
        v.push_back(s);
        return v;
    }
};

5.简单计算器 

给出两个整数 a , b ,以及一个操作符 opeator

+, -, *, /

样例 1：

输入：

a = 1
b = 2
operator = +

输出：

3

switch选择或者if顿号else if判断即可 

class Calculator {
public:
    /**
     * @param a: An integer
     * @param op: A character, +, -, *, /.
     * @param b: An integer
     * @return: The result
     */
    int calculate(int a, char op, int b)
    {
        // write your code here
        int d;
        switch(op)
        {
            case'+':d=a+b;
            break;
            case'-':d=a-b;
            break;
            case'*':d=a*b;
            break;
            case'/':d=a/b;
            break;
        }
        return d;
    }
};

 6.三数之中的最大值

给三个整数，求他们中的最大值。

样例  1:
	输入:  num1 = 1, num2 = 9, num3 = 0
	输出: 9

可排序，但三目运算符更简便。 

class Solution {
public:
    /**
     * @param num1: An integer
     * @param num2: An integer
     * @param num3: An integer
     * @return: an interger
     */
    int maxOfThreeNumbers(int num1, int num2, int num3) {
        // write your code here
        int s1=num1>num2?num1:num2;
        int s2=s1>num3?s1:num3;
        return s2;
    }
};

 7.大小写转换

 将一个字符由小写字母转换为大写字母

样例 1:

输入: 'a'
输出: 'A'

大写字母的ASCII码比对应小写的ASCII码小32.

class Solution {
public:
    /**
     * @param character: a character
     * @return: a character
     */
    char lowercaseToUppercase(char character) {
        // write your code here
        return character-=32;
    }
};

8.判断数字与字母字符 

给出一个字符c，如果它是一个数字或字母，返回true，否则返回false。

输入：

c = '1'

输出：

true

利用ASCII码即可

class Solution {
public:
    /**
     * @param c: A character.
     * @return: The character is alphanumeric or not.
     */
    bool isAlphanumeric(char c) {
        // write your code here
    if (((c >= '0') && (c <= '9')) || ((c >= 'a') && (c <= 'z')) || ((c <= 'Z') && (c >= 'A')))
	{
		return true;
	}
	else
		return false;
    }
};

 9.月份天数

给定年份和月份，返回这个月的天数

样例 1:

输入: 
2020 
2
输出: 
29

建立数组存放每月对应天数，用月份来匹配数组下标。记得判断该年份是否为闰年。

class Solution {
public:
    /**
     * @param year: a number year
     * @param month: a number month
     * @return: return the number of days of the month.
     */
    int getTheMonthDays(int year, int month) {
        // write your code here
        int arr[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };
	if (month == 2)
	{
		if ((year % 400 == 0) || ((year % 4 == 0) && (year % 100 != 0)))
			arr[1] = 29;
	}
	return arr[month - 1];
    }
};

10.闰年

给出一个年份，判断是否为闰年。

样例 1:

输入 : n = 2008
输出 : true

会上一题自然会本题，不多说。 

class Solution {
public:
    /**
     * @param n: a number represent year
     * @return: whether year n is a leap year.
     */
    bool isLeapYear(int n) {
        // write your code here
        if ((n % 400 == 0) || ((n % 4 == 0) && (n % 100 != 0)))
		return true;
	else
		return false;
    }
};

11.生成给定大小的数组

给你一个大小size,生成一个元素从1 到 size的数组 

样例 1:
	输入:  size = 4
	输出: [1, 2, 3, 4]

 利用vector容器

class Solution {
public:
    /**
     * @param size: An integer
     * @return: An integer list
     */
    vector<int> generate(int size) {
        // write your code here
        vector<int> v;
		for (int i = 1;i <= size;i++)
		{
			v.push_back(i);
		}
		return v;
    }
};

12.交换数组两个元素 

给你一个数组和两个索引，交换下标为这两个索引的数字

输入:  [1, 2, 3, 4], index1 = 2, index2 = 3
输出:  交换后你的数组应该是[1, 2, 4, 3]， 不需要返回任何值，只要就地对数组进行交换即可。
样例解释: 就地交换，不需要返回值。

设置临时变量。

class Solution {
public:
    /**
     * @param A: An integer array
     * @param index1: the first index
     * @param index2: the second index
     * @return: nothing
     */
    void swapIntegers(vector<int> &A, int index1, int index2) {
        // write your code here
        int temp=A[index1];
        A[index1]=A[index2];
        A[index2]=temp;
    }
};

13.整数排序

给一组整数，按照升序排序，使用选择排序，冒泡排序，插入排序或者任何 O(n2) 的排序算法。

样例  1:
	输入:  [3, 2, 1, 4, 5]
	输出:  [1, 2, 3, 4, 5]

利用冒泡排序

class Solution {
public:
    /**
     * @param A: an integer array
     * @return: nothing
     */
    void sortIntegers(vector<int> &A) {
        // write your code here
    for (int i=0;i<A.size()-1;i++)
		{
			for (int j=0;j<A.size()-i-1;j++)
			{
				int temp = 0;
				if (A[j] > A[j+1])
				{
					temp = A[j];
					A[j] = A[j+1];
					A[j+1] = temp;
				}
			}
		}
    }
};

14. 数组的最大值

 给一个浮点数数组，求数组中的最大值。

输入:  [1.0, 2.1, -3.3]
输出: 2.1	
样例解释: 返回最大的数字

先排序，后取值。

float cusSort(float a, float b)
{
	return a > b;
}
class Solution {
public:
    /**
     * @param A: An integer
     * @return: a float number
     */
    float maxOfArray(vector<float> &A) {
        // write your code here
        sort(A.begin(), A.end(), cusSort);
		return A[0];
    }
};

15. 打印X

输入一个正整数N， 你需要按样例的方式返回一个字符串列表。

X   X 
 X X  
  X   
 X X  
X   X 

本题描述太长了，直接放一个例子。

对称的将字符串两个位置由“ ”替换为“X”。

class Solution {
public:
    /**
     * @param n: An integer.
     * @return: A string list.
     */
    vector<string> printX(int n) {
        // write your code here
        vector<string> reSult;
        string x(n,' ');
        for(int i=0;i<n;i++){
            x[i]='X';
            x[n-i-1]='X';
            reSult.push_back(x);
            x[i]=' ';
            x[n-i-1]=' ';
        };
        return reSult;
    }
};

16.寻找素数

给定n，输出n以内所有的素数。 （n<100）

输入：5
输出：[2, 3, 5]

设置计数变量index，若有约数，index+1。最后index为0则为素数。

class Solution {
public:
    /**
     * @param n: an integer
     * @return: return all prime numbers within n.
     */
    vector<int> prime(int n) {
        // write your code here
       vector<int> v;
		if (n == 2)
			v.push_back(2);
		else if (n > 2 && n <= 100)
		{
			v.push_back(2);
			for (int i = 3;i <= n;i++)
			{
				int index = 0;
                for (int j = 2;j <= i/2;j++)
				{
					if (i%j == 0)
						index++;
				}
				if (index == 0)
					v.push_back(i);
			}
		}
		return v;
    }
};

17. 寻找最大值

寻找 n 个数中的最大值。

输入：[1, 2, 3, 4, 5]
输出：5

与14题本质是一个题。相同做法。

int cusSort(int a,int b)
{
    return a>b;
}
class Solution {
public:
    /**
     * @param nums: the list of numbers
     * @return: return the maximum number.
     */
    int maxNum(vector<int> &nums) {
        // write your code here
        sort(nums.begin(),nums.end(),cusSort);
        return nums[0];
    }
};

18.旋转数组

给定一个数组，将数组向右移动k步，其中k为非负数。

输入: [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转1步: [7,1,2,3,4,5,6]
向右旋转2步: [6,7,1,2,3,4,5]
向右旋转3步: [5,6,7,1,2,3,4]

 利用STL的reverse反转，记得k若大于等于数组长度，循环将超过一轮。

class Solution {
public:
    /**
     * @param nums: an array
     * @param k: an integer
     * @return: rotate the array to the right by k steps
     */
    vector<int> rotate(vector<int> &nums, int k) {
        // Write your code here
        if ((k == 0) || nums.size() < 2)
		{
			return nums;
		}
		k = k % nums.size();
		reverse(nums.begin(), nums.end() - k);
		reverse(nums.end() - k, nums.end());
		reverse(nums.begin(), nums.end());
		return nums;
    }
};

 19.回文数II

判断一个非负整数 n 的二进制表示是否为回文数。

输入: n = 0
输出: True
解释:
0 的二进制表示为：0。

 除以二取余来获得二进制，首位对比判断是否为回文数。

class Solution {
public:
    /**
     * @param n: non-negative integer n.
     * @return: return whether a binary representation of a non-negative integer n is a palindrome.
     */
    bool isPalindrome(int n) {
        // Write your code here
        vector<int> array;
     while(n/2 != 0){
        int yushu = n % 2;
        n = n /2;
        array.push_back(yushu);
     }
     array.push_back(n%2);

int record =0;
for(int i = 0; i < array.size(); i++){
        if(array[i] != array[array.size()-i-1])
        record ++;
}
if (record == 0)
return true;
else 
return false;
    }
};

 20.杨辉三角

给一整数 n, 返回杨辉三角的前 n 行

输入 : n = 4
输出 :
[
 [1]
 [1,1]
 [1,2,1]
 [1,3,3,1]
]

杨辉三角的每行作为一个vector<int>容器，开头和结尾的1单独添加，中间的数由上一行给出。

class Solution {
public:
    /**
     * @param n: a Integer
     * @return: the first n-line Yang Hui's triangle
     */
    vector<vector<int>> calcYangHuisTriangle(int n)
    {
        // write your code here
        vector<vector<int>>res;
        if(n == 0) 
        {
            return res;
        }
        for(int i = 0; i < n; i++) 
        {
            vector<int> temp;
            temp.push_back(1);
            for(int j = 1; j < i; j++) 
            {
                temp.push_back(res[i - 1][j - 1] + res[i - 1][j]);
            }
            if(i > 0)
            {
                temp.push_back(1);
            }
            res.push_back(temp);
        }
        return res;
    }
};

21.翻转数组

原地翻转给出的数组 nums

输入 : nums = [1,2,5]
输出 : [5,2,1]

最简单的方法是直接reverse。但还是用了常规一点的思路。

class Solution {
public:
    /**
     * @param nums: a integer array
     * @return: nothing
     */
    void reverseArray(vector<int> &nums) {
        // write your code here
        vector<int> res;
		for (int i = nums.size() - 1;i >= 0;i--)
		{
			res.push_back(nums[i]);
		}
		nums.clear();
		for (int i = 0;i < res.size();i++)
		{
			nums.push_back(res[i]);
		}

    }
};

 22.移动零

给一个数组 nums 写一个函数将 0 移动到数组的最后面，非零元素保持原数组的顺序

输入: nums = [0, 1, 0, 3, 12],
输出: [1, 3, 12, 0, 0].

 本题使用了erase方法。但注意删除当前元素后，下一个位置的元素会被移动到当前迭代器指向的位置，因此要判断是否有好几个0连在一起的情况，若不判断，则会越过连在一起的第二个0。同时要保证数组下标不越界。

class Solution {
public:
    /**
     * @param nums: an integer array
     * @return: nothing
     */
    void moveZeroes(vector<int> &nums) {
        // write your code here
        int index = 0;
		if (nums.size() == 1)
			return;
		for (vector<int>::iterator it = nums.begin();it != nums.end();it++)
		{
			while (*it == 0)
			{
				nums.erase(it);
				index++;
				if (it == nums.end())
					break;
			}
			if (it == nums.end())
				break;
		}
		for (int i = 0;i < index;i++)
		{
			nums.push_back(0);
		}
    }
};

提供一种使用find方法的简单代码 。不用考虑太多问题。

class Solution {
public:
    /**
     * @param nums: an integer array
     * @return: nothing
     */
    void moveZeroes(vector<int> &nums) {
        // write your code here
         int num = count(nums.begin(), nums.end(), 0);
          for(int i=0;i<num;i++)  {
            vector<int>::iterator it = find(nums.begin(), nums.end(), 0);
            nums.erase(it);
            nums.push_back(0);
        }
    }
};

 23.数组第二大数

在数组中找到第二大的数。

输入：[1,3,2,4]
输出：3

输入：[1,1,2,2]
输出：2

 本题注意重复的数字也可以作为第二大数。所以排序取第二个数就行了。

int cusSort(int a, int b)
{
	return a > b;
}
class Solution {
public:
    /**
     * @param nums: An integer array
     * @return: The second max number in the array.
     */
    int secondMax(vector<int> &nums) {
        // write your code here
		sort(nums.begin(), nums.end(), cusSort);
		return nums[1];
    }
};

 24.分解质因数

将一个整数分解为若干质因数之乘积。

输入：10
输出：[2, 5]

输入：660
输出：[2, 2, 3, 5, 11]

 首先明白质因数分解的含义。之后由2起，增加因数的大小，能被整除则保留因数。最后剩余的数若不为1则就是其本身。

class Solution {
public:
    /**
     * @param num: An integer
     * @return: an integer array
     */
    vector<int> primeFactorization(int num) {
        // write your code here
        vector<int> res;
        for(int i = 2; i*i <= num; i++)
        {
            while(num % i == 0)
            {
                num /= i;
                res.push_back(i);
            }
        }
        if(num != 1)
        {
            res.push_back(num);
        }
        return res;
    }
};

25.加一

给定一个非负数，表示一个数字数组，在该数的基础上+1，返回一个新的数组。

该数字按照数位高低进行排列，最高位的数在列表的最前面。

输入：[1,2,3]
输出：[1,2,4]

输入：[9,9,9]
输出：[1,0,0,0]

 逢九进一，记得判断是否为下标为0的元素。若是，改其为1，尾插0。也可以insert头插1。

class Solution {
public:
    /**
     * @param digits: a number represented as an array of digits
     * @return: the result
     */
    vector<int> plusOne(vector<int> &digits) {
        // write your code here
        int nums = digits.size() - 1;
		if (digits[nums] != 9)
			digits[nums] += 1;
		else
		{
			while (digits[nums] == 9)
			{
				if (nums == 0)
				{
					digits[nums] = 1;
					digits.push_back(0);
					break;
				}
				digits[nums] = 0;
				nums--;
				if (digits[nums] != 9)
				{
					digits[nums] += 1;
					break;
				}
			}
		}
		return digits;
    }
};

26.冰雹猜想

数学家们曾提出一个著名的猜想——冰雹猜想。
对于任意一个自然数N，如果N是偶数，就把它变成N / 2；
如果N是奇数，就把它变成 3 * N+1。
按照这个法则运算下去，最终必然得1。
试问，该数通过几轮变换，会变成1呢？

输入： 
4
输出： 
2
解释： 
第一轮：4/2=2
第二轮：2/2=1
答案为2

 while判断是否为1。设置计数器index记录循环次数。

class Solution {
public:
    /**
     * @param num: an integer
     * @return: an integer
     */
    int getAnswer(int num) {
        // write your code here.
        int index = 0;
		while (num != 1)
		{
			if (num % 2 == 0)
			{
				num /= 2;
			}
			else
			{
				num = num * 3 + 1;
			}
			index++;
		}
		return index;
    }
};

27.翻转字符串

给定一个字符串，逐个翻转字符串中的每个单词。

输入：

s = "the sky is blue"

输出：

"blue is sky the"

 从前往后以空格为界，每次取一个单词为子串。下一次取子串放在上一个子串前面。

class Solution {
public:
    /*
     * @param s: A string
     * @return: A string
     */
    string reverseWords(string &s) {
        // write your code here
        string res = "";
        s += " ";
        int start = 0;
        bool flag = false;
        for(int i=0; i<s.size(); i++)
        {
            if(s[i]!=' ' && !flag)   start = i, flag=true;

            else if(s[i]==' ' && flag)   res = s.substr(start, i-start) + " " + res, flag = false;
        }

        return res.substr(0, res.size()-1);
    }
};

28.数组剔除元素后的乘积

给定一个整数数组A。
定义B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]B[i]=A[0]∗...∗A[i−1]∗A[i+1]∗...∗A[n−1]， 计算B的时候请不要使用除法。请输出B。

A = [1,2,3]

输出：

[6,3,2]

解释：

B[0] = A[1] * A[2] = 6; B[1] = A[0] * A[2] = 3; B[2] = A[0] * A[1] = 2

两个循环，外部循环次数数等于数组元素下标时跳过本轮循环。

class Solution {
public:
    /*
     * @param nums: Given an integers array A
     * @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
     */
    vector<long long> productExcludeItself(vector<int> &nums) {
        // write your code here
        vector<long long> v;
		for (int i = 0;i < nums.size();i++)
		{
			long long res = 1;
			for (int j = 0;j < nums.size();j++)
			{
				if (i == j)
					continue;
				res *= nums[j];
			}
			v.push_back(res);
		}
		return v;
    }
};

29.主元素

给定一个整型数组，找出主元素，它在数组中的出现次数大于数组元素个数的二分之一。

输入：

数组 = [1, 1, 1, 1, 2, 2, 2]

输出：

1

 数组内每个元素在数组内检索一遍，每有一个相同的，次数加一，次数大于数组长度一半时，返回元素。

class Solution {
public:
    /*
     * @param nums: a list of integers
     * @return: find a  majority number
     */
    int majorityNumber(vector<int> &nums) {
        // write your code here
        for (int i = 0;i < nums.size();i++)
		{
			int res = nums[i];
			int index = 0;
			for (int j = 0;j < nums.size();j++)
			{
				if (res == nums[j])
				{
					index++;
				}
				if (index > (nums.size() / 2))
					return res;
			}
		}
    }
};

30. Fizz Buzz 问题

给定整数 n ，按照如下规则打印从 1 到 n 的每个数：

• 如果这个数被3整除，打印fizz。
• 如果这个数被5整除，打印buzz。
• 如果这个数能同时被3和5整除，打印fizz buzz。
• 如果这个数既不能被 3 整除也不能被 5 整除，打印数字本身。

输入：

n = 15

输出：

[
  "1", "2", "fizz",
  "4", "buzz", "fizz",
  "7", "8", "fizz",
  "buzz", "11", "fizz",
  "13", "14", "fizz buzz"
]

 用的笨办法，多个if语句进行条件判断。

class Solution {
public:
    /**
     * @param n: An integer
     * @return: A list of strings.
     */
    vector<string> fizzBuzz(int n) {
        // write your code here
       vector<string> results;
		vector<string> exm{ "", "fizz", "buzz", "fizz buzz" };
		for (int i = 1; i <= n; i++) 
		{
			exm[0] = to_string(i);
			int index = 0;
			if (i % 3 == 0 && (i % 15 != 0))
			{
				index = 1;
			}
			else if (i % 5 == 0 && (i % 15 != 0))
			{
				index = 2;
			}
			else if (i % 15 == 0)
			{
				index = 3;
			}
			else
				index = 0;
			string result = exm[index];
			results.push_back(result);
		}
		return results;
    }
};

31.转换字符串到整数（容易版）

给一个字符串, 转换为整数。你可以假设这个字符串是一个有效整数的字符串形式， 且范围在32位整数之间 (-231 ~ 231 - 1)。

输入:  "123"
	输出: 123

 现将string转成c标准字符串，再用atoi函数将字符串转成整形。

class Solution {
public:
    /**
     * @param target: A string
     * @return: An integer
     */
    int stringToInteger(string &target) {
        // write your code here
        return atoi(target.c_str());
    }
};

 32.大小写转换 II

将一个字符串中的小写字母转换为大写字母。不是字母的字符不需要做改变。

输入: str = "abc"
输出: "ABC"

 挨个转换就好。

class Solution {
public:
    /**
     * @param letters: A string
     * @return: A string
     */
    string lowercaseToUppercase2(string &letters) {
        // write your code here
        for (int i=0;i<letters.length();i++)
        {
            //if ((letters[i]>=65)&&(letters[i]<=90))
              //  letters[i]=letters[i]+32;
            if((letters[i]>=97)&&letters[i]<=122)
                letters[i]=letters[i]-32;
        };
        return letters;
    }
};

33.字符串查找

对于一个给定的 source 字符串和一个 target 字符串，你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在，则返回 -1。

输入：

source = "abcdabcdefg"
target = "bcd"

输出：

1       

 用string容器自带的find函数，轻松解决。

class Solution {
public:
    /**
     * @param source: 
     * @param target: 
     * @return: return the index
     */
    int strStr(string &source, string &target) {
        // Write your code here
        int pos = source.find(target);
		if (pos != -1)
			return pos;
		else
			return -1;
    }
};

34.转换成小写字母

实现函数 ToLowerCase()，该函数接收一个字符串参数 str，并将该字符串中的大写字母转换成小写字母，之后返回新的字符串。

输入: "Hello"
输出: "hello"

与32题一样，挨个转换。

class Solution {
public:
    /**
     * @param str: the input string
     * @return: The lower case string
     */
    string toLowerCase(string &str) {
        // Write your code here
        for(int i=0;i<str.size();i++)
        {
            if(str[i]>='A'&&str[i]<='Z')
            {
                str[i]+=32;
            }
        }
        return str;
    }
};

 35.两字符串和

给定两个仅含数字的字符串，你需要返回一个由各个位之和拼接的字符串

输入:
A = "99"
B = "111"
输出: "11010"
解释: 因为 9 + 1 = 10, 9 + 1 = 10, 0 + 1 = 1,连接之后的结果是 "11010"

 取每一个数分别相加，在填入新字符串。最后哪一个字符串还有剩余，就全部填入新字符串。

class Solution {
public:
    /**
     * @param A: a string
     * @param B: a string
     * @return: return the sum of two strings
     */
    string SumofTwoStrings(string &A, string &B) {
        // write your code here
        string str = "";
        int i=A.size()-1, j=B.size()-1;
        for(; i>=0 && j>=0; i--,j--)
        { 
            str = to_string(A[i]-'0'+B[j]-'0')+str;
        }
        if(i>=0) str = A.substr(0,i+1) + str;
        if(j>=0) str = B.substr(0,j+1) + str;
        return str;
    }
};

36.首字母大写

输入一个英文句子，将每个单词的第一个字母改成大写字母

输入: s =  "i want to get an accepted"
输出: "I Want To Get An Accepted"

 整个字符串的第一个字符转换为大写，其余不是空格的字符，若前一个字符为空格，转为大写。

class Solution {
public:
    /**
     * @param s: a string
     * @return: a string after capitalizes the first letter
     */
    string capitalizesFirst(string &s) {
        // Write your code here
        int n = s.size();
        if (s[0] >= 'a' && s[0] <= 'z')
        {
            s[0] -= 32;
        }
        for (int i = 1; i < n; i++) 
        {
            if (s[i - 1] == ' ' && s[i] != ' ') 
            {
                s[i] -= 32;
            }
        }
        return s;
    }
};

37.回文数

判断一个正整数是不是回文数。

回文数的定义是，将这个数反转之后，得到的数仍然是同一个数。

例1：

输入：11
输出：true

例2：

输入：1232
输出：false
解释：
1232!=2321

 将整数转为字符串，反转字符串，判断是否与原字符串相等

class Solution {
public:
    /**
     * @param num: a positive number
     * @return: true if it's a palindrome or false
     */
    bool isPalindrome(int num) {
        // write your code here
       string str1 = to_string(num), str2 = str1;
       reverse(str2.begin(), str2.end());
       return str1 == str2;
    }
};

38.最长单词

给一个词典，找出其中所有最长的单词。

样例 1:
	输入:   {
		"dog",
		"google",
		"facebook",
		"internationalization",
		"blabla"
		}
	输出: ["internationalization"]



样例 2:
	输入: {
		"like",
		"love",
		"hate",
		"yes"		
		}
	输出: ["like", "love", "hate"]

 给出用C++第一时间想到的代码，但是运行时间超时，思路和代码没问题，无论怎么运行都是超时。记录最大的单词长度，后面有相同长度的单词就一并加入vector容器，遇到更长的单词，就清空容器，放入新单词。

class Solution {
public:
	/*
	 * @param dictionary: an array of strings
	 * @return: an arraylist of strings
	 */
	vector<string> longestWords(vector<string> &dictionary) {
		// write your code here
		int max_length = 0;
		vector<string> res;
		int n = dictionary.size();
		for (int i = 0; i < n; i++) {
			if (dictionary[i].length() > max_length) {
				res.clear();
				max_length = dictionary[i].length();
				res.push_back(dictionary[i]);
			}
			else if (dictionary[i].length() == max_length) {
				res.push_back(dictionary[i]);
			}
		}
		return res;
	}
};

大佬们可以帮忙改改，让它不再超时。

以下给出Java在相同思路下的代码。

public class Solution {
    /*
     * @param dictionary: an array of strings
     * @return: an arraylist of strings
     */
    public List<String> longestWords(String[] dictionary) {
        // write your code here
		List<String> list = new ArrayList<>();
        if (dictionary.length == 0) {
    		return list;
    	}
    	list.add(dictionary[0]);
    	for (int i = 1; i < dictionary.length; i++) {
    		if(dictionary[i].length() > list.get(list.size() - 1).length()) {
    			list.clear();
    			list.add(dictionary[i]);
    		} else if (dictionary[i].length() == list.get(list.size() - 1).length()) {
    			list.add(dictionary[i]);
    		} else {
    			continue;
    		}
    	}
    	return list;
    }
}

39.最后一个单词的长度

给定一个字符串， 包含大小写字母、空格 ' '，请返回其最后一个单词的长度。

如果不存在最后一个单词，请返回 0 。

输入："Hello World"
输出：5

注意要考虑最后该字符串不以单次结尾的情况。 

class Solution {
public:
    /**
     * @param s: A string
     * @return: the length of last word
     */
    int lengthOfLastWord(string &s) {
        // write your code here
        int len = s.size();
        int res = 0, flag = 0;
        for(int i = len - 1; i >= 0; i --)
        {
            if(s[i] == ' ' && flag == 0)
                continue;
            flag = 1;
            if(s[i] == ' ')
                break;
            res ++;
        }
        return res;
    }
};

40.最大字母

给定字符串S，找到最大的字母字符，其大写和小写字母均出现在S中，则返回此字母的大写，若不存在则返回"NO"。

输入: S = "admeDCAB"
输出: "D"

输入: S = "adme"
输出: "NO"

 先选出最大小写字母，在遍历字符串寻找是否有该字母的大写。

class Solution {
public:
    /**
     * @param s: a string
     * @return: a string
     */
    string largestLetter(string &s) {
        // write your code here
        int max_length = 0;
		char ch = 'A';
		bool find = false;
		bool find2 = false;
		string res = "";
		for (int i = 0;i < s.size();i++)
		{
			int distance = s[i] - 'A';
			if (distance >= max_length && distance <= 25)
			{
				max_length = distance;
				ch = s[i];
				find = true;
			}
		}
		if (find)
		{
			for (int i = 0; i < s.length();i++)
			{
				if (s[i] == ch - 'A' + 'a')
				{
					find2 = true;
				}
			}
		}
		if (find && find2)
		{
			res = res + ch;
		}
		else {
			res = res + "NO";
		}
		return res;
    }
};

41.翻转字符串

给定一个字符串str和一个偏移量，根据偏移量原地旋转字符串(从左向右旋转)。
对于不同的语言，str将以不用的形式给出，例如对于字符串 "abc" ，将以下面的形式给出

输入：

str = "abcdefg"
offset = 3

输出：

"efgabcd"

取子串即可，注意offset大于字符串长度的话会循环一次，因此对字符串长度取余。 

class Solution {
public:
    /**
     * @param str: An array of char
     * @param offset: An integer
     * @return: nothing
     */
    void rotateString(string &str, int offset) {
        // write your code here
        if(offset <= 0 || str.length() == 0){
            return;
        }
        offset = offset % str.size();
        str = str.substr(str.size() - offset, offset) + str.substr(0, str.size() - offset);
    }
};

42.二阶阶乘

给定一个数n，返回该数的二阶阶乘。在数学中，正整数的二阶阶乘表示不超过这个正整数且与它有相同奇偶性的所有正整数乘积。

输入: n = 5
输出: 15
解释:
5!! = 5 * 3 * 1 = 15

简单递归

class Solution {
public:
    /**
     * @param n: the given number
     * @return:  the double factorial of the number
     */
    long long doubleFactorial(int n) {
        // Write your code here
        if(n<=2)
        {
            return n;
        }
        return n*doubleFactorial(n-2);
    }
};

 43.实现栈

实现一个栈，可以使用除了栈之外的数据结构

输入：
push(1)
pop()
push(2)
top()  // return 2
pop()
isEmpty() // return true
push(3)
isEmpty() // return false

 利用vector实现

class Stack {
public:
    /*
     * @param x: An integer
     * @return: nothing
     */
    vector<int> v;
    void push(int x) {
        // write your code here
        v.push_back(x);

    }

    /*
     * @return: nothing
     */
    void pop() {
        // write your code here
        if(!this->isEmpty())
        {
            v.pop_back();
        }
    }

    /*
     * @return: An integer
     */
    int top() {
        // write your code here
        if(!this->isEmpty())
        {
            return v[v.size()-1];
        }
    }

    /*
     * @return: True if the stack is empty
     */
    bool isEmpty() {
        // write your code here
        return v.size()==0;
    }
};

44.队列维护

按链表实现队列。支持以下基本方法：

1. enqueue(item).将新元素放入队列中。
2. dequeue(). 将第一个元素移出队列，返回它。

输入：
enqueue(1)
enqueue(2)
enqueue(3)
dequeue() // return 1
enqueue(4)
dequeue() // return 2

利用queue容器

class MyQueue {
public:
    /*
     * @param item: An integer
     * @return: nothing
     */
    queue<int> q;
    void enqueue(int item) {
        // write your code here
        q.push(item);
    }

    /*
     * @return: An integer
     */
    int dequeue() {
        // write your code here
        int rs = q.front();
        q.pop();
        return rs;
    }
};

 45.有效的括号序列

给定一个字符串所表示的括号序列，包含以下字符： '(', ')', '{', '}', '[' and ']'， 判定是否是有效的括号序列。

样例 1：

输入："([)]"
输出：False

样例 2：

输入："()[]{}"
输出：True

一次读取一个完整的括号，若是有效的括号序列，则最后字符串的长度会恰好为零。

class Solution {
public:
    /**
     * @param s: A string
     * @return: whether the string is a valid parentheses
     */
    bool isValidParentheses(string &s) {
        // write your code here
        int size=s.size();
        for(int i=0;i<size/2;i++)
        {
            for(int j=0;j<s.size()-1;j++)
            {
                if((s[j]=='('&&s[j+1]==')') || (s[j]=='['&&s[j+1]==']') ||(s[j]=='{'&&s[j+1]=='}'))
                {
                    s.erase(j,2);
                    break;
                }
            }
        }
        if(s.size()>0){
            return false;
        }else{
            return true;
        }
    }
};

46. 小括号匹配

给定一个字符串所表示的括号序列，包含以下字符： '(', ')'， 判定是否是有效的括号序列。

括号必须依照 "()" 顺序表示， "()" 是有效的括号，但 ")(" 则是无效的括号。

样例 1：

输入：")("
输出：False

样例 2：

输入："()"
输出：True

建立一个栈，若字符串第一个字符为“)”，则直接false。为“(”则将其入栈，读取下一个字符，下一个字符若为“(”，则继续入栈。直至为“)”时，进行出栈。每一个“)”对应一个“(”出栈。

当最后读完所有字符，栈为空，则输出true，若栈不为空，则证明不匹配，输出false。

class Solution {
public:
    /**
     * @param string: A string
     * @return: whether the string is valid 
     */
    bool matchParentheses(string &string) {
        // write your code here
        stack<char> res;
        if (string[0] == ')') return false;
        else res.push(string[0]);
        for (int i = 1; i < string.size(); i++) 
        {
            if (string[i] == '(') 
            {
                 res.push(string[i]);
            } else 
            {
                if (!res.empty()) 
                {
                    res.pop();
                } 
                else
                {
                    return false;
                }
            }
        }
        if (res.empty()) 
            return true;
    }
};

 47.斐波纳契数列

查找斐波纳契数列中第 N 个数。

所谓的斐波纳契数列是指：

• 前2个数是 0 和 1 。
• 第 i 个数是第 i-1 个数和第i-2 个数的和。

斐波纳契数列的前10个数字是：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

样例  1:
	输入:  1
	输出: 0
	
	样例解释: 
	返回斐波那契的第一个数字，是0.

样例 2:
	输入:  2
	输出: 1
	
	样例解释: 
	返回斐波那契的第二个数字是1.

裴波那契数列求和用简单递归，但这个是求第n个数，所以才用了笨办法。

class Solution {
public:
    /**
     * @param n: an integer
     * @return: an ineger f(n)
     */
    int fibonacci(int n) {
        // write your code here
        if (n == 1)
		{
			return 0;
		}
		int a = 0, b = 0, s = 1;
		for (int i = 2; i < n; ++i) {
			a = b;
			b = s;
			s = a + b;
		}
		return s;
    }
};

 48.二叉树的后序遍历

给出一棵二叉树，返回其节点值的后序遍历。

输入：

二叉树 = {1,2,3}

输出：

[2,3,1]

解释：

   1
/  \
2     3
它将被序列化为{1,2,3}之后进行后序遍历

 递归做法。

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: A Tree
     * @return: Postorder in ArrayList which contains node values.
     */
    void postOrder(TreeNode * root, vector<int> &v) 
	{
		if (root->left != nullptr)
			postOrder(root->left, v);
		if (root->right != nullptr)
			postOrder(root->right, v);
		v.push_back(root->val);
	}
    vector<int> postorderTraversal(TreeNode *root) {
        // write your code here
        vector<int> v;
		if (root != nullptr)
			postOrder(root, v);
		return v;
    }
};

49.二叉树的中序遍历

给出一棵二叉树,返回其中序遍历。

输入：

二叉树 = {1,2,3}

输出：

[2,1,3]

解释：

   1
/  \
2     3
它将被序列化为{1,2,3}中序遍历

同样使用递归做法。

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: A Tree
     * @return: Inorder in ArrayList which contains node values.
     */
    void inOrder(TreeNode * root, vector<int> &v) 
	{
		if (root->left != nullptr)
			inOrder(root->left, v);
		v.push_back(root->val);
		if (root->right != nullptr)
			inOrder(root->right, v);
	}
    vector<int> inorderTraversal(TreeNode *root) {
        // write your code here
        vector<int> v;
        if (root != nullptr )
            inOrder(root, v);
        return v;
    }
};

50.二叉树的前序遍历

给出一棵二叉树，返回其节点值的前序遍历。

输入：

二叉树 = {1,2,3}

输出：

[1,2,3]

解释：

   1
/  \
2     3
它将被序列化为{1,2,3}前序遍历

同样也是递归做法。

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: A Tree
     * @return: Preorder in ArrayList which contains node values.
     */
    void preOrder(TreeNode * root, vector<int> &v) 
	{
		v.push_back(root->val);
		if (root->left != nullptr)
			preOrder(root->left, v);
		if (root->right != nullptr)
			preOrder(root->right, v);
	}
    vector<int> preorderTraversal(TreeNode *root) {
        // write your code here
        vector<int> v;
        if (root != nullptr )
            preOrder(root, v);
        return v;
    }
};

这篇关于LintCode 练习【C++】的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！