扑克牌顺子

题目描述

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。

思路

顺子可以看成抽出5个数字，最大最小值差值不大于5，且没有重复的数字。加上大王和小王设为0，0可以重复。

代码

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        if(numbers.empty())
            return false;
        int count[14] = {0};
        int max = -1, min = 14;
        for(int i=0; i<numbers.size();i++){
            if(numbers[i]==0)//0是可以有重复的,所以检测到0直接continue，不需要记录其count
                continue;
            count[numbers[i]]++;
            if(count[numbers[i]]>1)
                return false;
            if(numbers[i] < min)
                min = numbers[i];
            if(numbers[i] > max)
                max = numbers[i];
        }
        return max-min < 5 ;
    }
};

孩子们的游戏（圆圈中剩下的数字）

题目描述

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

如果没有小朋友，请返回-1

思路

使用了一个vector来时，当符合计数条件时，直接移除这个数据，最后vector大小为1的时候，就是找到了幸运星。中间要设置好每次删除一个标号，以便于下一个循环删除从该标号开始。

代码

class Solution {
public:
    int LastRemaining_Solution(int n,int m){
        if(n<1||m<1) return -1;
        if(n==1)
            return 0;
        vector<int> child(n);
        for(int i=0;i < n;i++){
            child[i] = i;
        }
        int temp = 0;
        while(child.size()>1){
            int count = temp + m -1; //从上一次删除开始继续数
            int num = count % (child.size());
            temp = num;
            child.erase(child.begin()+num);
        }
        return child[0];
    }
};

求1+2+3+…+n

题目描述

求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

思路

利用逻辑与的最短路特性，&&就是逻辑与，逻辑与有个短路特点，前面为假，后面不计算。

代码

class Solution {
public:
    int Sum_Solution(int n) {
        int ans = n;
        ans && (ans += Sum_Solution(n-1));
        return ans;
    }
};

把字符串转换成整数

题目描述

将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0

输入描述:

输入一个字符串,包括数字字母符号,可以为空

输出描述:

如果是合法的数值表达则返回该数字，否则返回0

示例1

输入

+2147483647
    1a33

输出

2147483647
    0

思路

主要难点在于如何处理int越界的情况

合理利用 INT_MAX/10
数值越界，即大于 2147483647，或小于 -2147483648。通过观察程序结构，我们发现，每次循环时 value 的值都会扩大10倍（乘以10），
那么，我们是否就可以利用 INT_MAX/10 的值来提前一步判断是否会越界呢？这里我们以正数的越界为例进行解释：

当 value > INT_MAX/10 时，说明本轮扩大10倍后，value 必将越界（超过 INT_MAX）；
当 value == INT_MAX/10 时，说明扩大10倍后，value 可能越界，也可能不越界，需要利用当前的加数 digit 来进行进一步的判断：
当 digit > 7 时（以正数为例），越界；负数则是digit >8, 越界；
否则，当 value < INT_MAX/10 时，本轮循环必不越界（扩大10倍后也小于 INT_MAX）；

代码

class Solution {
public:
    int StrToInt(string str) {
        int len = str.size(), sign = 1;
        int res = 0;
        if(len<=0)
            return 0;
        if(str[0]=='-')
            sign = -1;
        int overValue;
        for(int i = ((str[0]=='-'||str[0]=='+')? 1 : 0);i<len;i++){
            int digital = str[i]-'0';
            if(str[i]<'0'||str[i]>'9')
                return 0;
            overValue = res - INT_MAX/10;
            if(overValue<0)
                res = res*10 + digital;
            else if(overValue==0){
                if(digital + (sign+1)/2 > 8 )//由于整数负数比较的不同，要加sign一起计算
                    return 0;
                else
                    res = res*10 + digital;
            }else
                return 0;
        }
        return sign*res;
    }
};

剪绳子

题目描述

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]xk[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

输入描述:

输入一个数n，意义见题面。（2 <= n <= 60）

输出描述:

输出答案。

示例1

输入

8

输出

18

思路

题目分析：
先举几个例子，可以看出规律来。
4 ： 22
5 ： 23
6 ： 33
7 ： 223 或者43
8 ： 233
9 ： 333
10：2233 或者433
11：2333
12：3333
13：22333 或者4333
下面是分析：
首先判断k[0]到k[m]可能有哪些数字，实际上只可能是2或者3。
当然也可能有4，但是4=22，我们就简单些不考虑了。
5<23,6<33,比6更大的数字我们就更不用考虑了，肯定要继续分。
其次看2和3的数量，2的数量肯定小于3个，为什么呢？因为222<33，那么题目就简单了。
直接用n除以3，根据得到的余数判断是一个2还是两个2还是没有2就行了。
由于题目规定m>1，所以2只能是11，3只能是21，这两个特殊情况直接返回就行了。

乘方运算的复杂度为：O(log n)，用动态规划来做会耗时比较多。

代码

class Solution {
public:
    int max_cut_3(int number){
        if(number == 2)
            return 1;
        if(number == 3)
            return 2;
        int x = number%3;
        int y = number/3;
        if(x == 0){
            return pow(3, y);
        }else if(x == 1){
            return 2 * 2 * pow(3, y-1);
        }else{
            return 2 * pow(3, y);
        }
    }
    int cutRope(int number) {
        if(number<2)
            return 0;
        int res = max_cut_3(number);
        return res;
    }
};

---