笔试专题（四）

扑克牌顺子（模拟 + 排序）

题目链接

题解

1. 解法一：找规律
在x不为0的情况下满足下面两个条件就是顺子：
1、最大值和最小值之差小于等于为4
2、不出现重复的数
2. 解法二：排序 + 模拟
>比如实例一，排完序之后是 0 0 2 4 6，先统计0的个数，如果非0两个数之差 4 - 2 - 1 = 1，中间相差一个数，用0补，如果不够补返回false，如果有多余的0返回true</font

代码

// 规律
class Solution 
{
    int hash[14] = {0};
public:
    bool IsContinuous(vector<int>& nums) 
    {
        int minval = 14,maxval = 0;
        for(auto x : nums)
        {
            if(x)
            {
                if(hash[x]) return false;
                hash[x] = true;
                minval = min(minval,x);
                maxval = max(maxval,x);
            }
        }
        return maxval - minval <= 4;
    }
};

// 排序 + 模拟
class Solution 
{
public:
    bool IsContinuous(vector<int>& nums) 
    {
       int n = nums.size();
       int count = 0;
       sort(nums.begin(),nums.end());
       int ans = 0;
       for(int i = n-1;i >= 0;i--)
       {
            if(nums[i] != 0)
            {
                // nums[i-1] != 0 防止出现一个非0数之前出现0的情况
                if(i != 0 && nums[i-1] != 0)
                {
                    ans += (nums[i] - nums[i-1] - 1);
                }
                // 处理相同的数
                if(ans < 0) return false;
            }
            else 
            {
                count++;
            }
       }
       return ans > count ? false : true;
    }
};

最长回文子串（双指针）

题目链接

题解

1. 中心扩展算法：
1、考虑回文串长度的奇偶性，如果是奇数串，r = i + 1，l = i - 1，向两边扩展，如果是偶数串，l = i，r = i + 1，或者是 l = i -1，r = i
2、计算回文串的长度：right - left - 1

代码

class Solution 
{
public:
    int getLongestPalindrome(string s) 
    {
        int n = s.size();
        int ret = 0;
        // 枚举中心位置
        for(int i = 0;i < n;i++)
        {
            // 1.如果i是奇数的话
            int l = i-1,r = i+1;
            while(l >= 0 && r < n && s[l] == s[r])
            {
                l--;
                r++;
            }
            ret = max(ret,r-l-1);
            // 2.如果i是偶数的话
            l = i,r = i+1;
            while(l >= 0 && r < n && s[l] == s[r])
            {
                l--;
                r++;
            }
            ret = max(ret,r - l - 1);
        }
        return ret;
    }
};

买卖股票的最好时机（一）（贪心）

题解

1. 解法：贪心
1、如果是暴力解法的话，使用两个for循环，固定一个点，遍历另一个点，计算出最大的利润
2、如果是贪心解的话，每次都算出前驱数组中的最小值，和当前数进行相减，算出每次的利润，可以得到最大值

代码

class Solution 
{
public:
    int maxProfit(vector<int>& prices) 
    {
        int n = prices.size();
        int ret = 0,prevMin = prices[0];
        for(int i = 1;i < n;i++)
        {
            // 算出前驱数组中的最小值
            prevMin = min(prevMin,prices[i]);
            // 算出该点卖出的最大利润,最小都是当前买入,当前天卖出
            ret = max(ret,prices[i] - prevMin);
        }
        return ret;
    }
};

过河卒（动态规划）

题目链接

题解

1. 解法：动态规划，路径问题
1、细节问题：注意一下映射关系，x，y棋盘上的位置和dp表中位置是相差1的
2、状态转移方程：如果满足下列条件或者是满足i == x && j == y，dp表中的这些位置的方法数都是0

代码

class Solution 
{
public:
    int crossRiver(int n, int m, int x, int y) 
    {
        vector<vector<long long>> dp(n+2,vector<long long>(m+2));
        vector<vector<long long>> ret(n+1,vector<long long>(m+1));
        
        // 将x和y映射到dp表对应的位置上
        x += 1,y += 1;
        dp[1][0] = 1;
        for(int i = 1;i <= n+1;i++)
        {
            for(int j = 1;j <= m+1;j++)
            {
                if((abs(i-x) + abs(j-y) == 3 && i != x && j != y )||
                (i == x && j == y))
                {
                    dp[i][j] = 0;
                }
                else 
                {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }    

        return dp[n+1][m+1];
    }
};