「算法刷题」[剑指offer(第2版)]数组之情景题的实现

[TOC]

一、扑克牌相关

剑指 Offer 61. 扑克牌中的顺子（简单难度）

class Solution {
public:
    /*解析：本题要求判断一个5个元素的数组是否是顺子
    稍微思考下，明白首先要从小到大排序，然后判断是否有除0以外的重复数，有则肯定不是顺子
    难点在于0可以看做然后数来填补顺子，如何判断几张0填补顺子是算法的难点?
    解决方案：找到minVal（非0）和maxVal，通过maxVal-minVal的差来判断需要几张0填补
    */
    bool isStraight(vector<int>& nums) {
        int zeroCnt=0;//0的数组
        int n=nums.size();//此题固定为5
        sort(nums.begin(),nums.end());//从小到大排序
        // 遍历数组，记录0的个数并判断是否存在重复数
        for(int i=0;i<n;i++){
            if(nums[i]==0)zeroCnt++;
            else if(i+1<n&&nums[i]==nums[i+1]) return false;
        }
        // maxVal-minVal<5时必定可以
        return nums[n-1]-nums[zeroCnt]<5;
    }
};

二、字符串转整数

剑指 Offer 67. 把字符串转换成整数（中等难度）

8. 字符串转换整数 (atoi)（中等难度）

class Solution {
public:
    /*本题是要将字符串转为有符号的32位整数。
    根据示例，字符串可能存在前端空格、正负号、后缀字母、首字符非数字、数字越界共计5种情况，
    这也是本题的难点
    */
    bool isDigit(char c){
        return c-'0'>=0&&c-'0'<=9;
    }
    int strToInt(string str) {
        int n=str.length();
        if(n==0) return 0;//非有效转换输出0
        int start=0;
        int negative=false;
        // 去掉前端空格
        for(char c:str){
            if(c==' ') start++;
            else break;
        }
        if(start==n)return 0;//去掉前导空格后到了末尾
        // // 判断非空首字符
        if (str[start] == '-') {
            negative = true;
            start++;
        }
        else if (str[start] == '+') 
        {
            negative = false;
            start++;
        }
        else if (!isDigit(str[start])){
            return 0;//非数字
        } 
        // 判断
        int ans = 0;
        while (start < n && isDigit(str[start])) {
            int digit = str[start] - '0';
            if (ans > (INT_MAX - digit) / 10) {
                // 本来应该是 ans * 10 + digit > Integer.MAX_VALUE
                // 但是 *10 和 + digit 都有可能越界，所有都移动到右边去就可以了。
                return negative? INT_MIN : INT_MAX;
            }
            ans = ans * 10 + digit;
            start++;
        }
        return negative? -ans : ans;
    }
};