leetcode解题思路分析（九十）789 - 795 题

左手的ㄟ右手 2022-09-10 04:09 217阅读 0赞

1.  逃脱障碍者  
    你在进行一个简化版的吃豆人游戏。你从 \[0, 0\] 点开始出发，你的目的地是 target = \[xtarget, ytarget\] 。地图上有一些阻碍者，以数组 ghosts 给出，第 i 个阻碍者从 ghosts\[i\] = \[xi, yi\] 出发。所有输入均为 整数坐标 。只有在你有可能成功逃脱时，输出 true ；否则，输出 false 。

**曼哈顿距离编辑求解**

class Solution { 
    public:
        int manhattanDistance(vector<int>& point1, vector<int>& point2) { 
            return abs(point1[0] - point2[0]) + abs(point1[1] - point2[1]);
        }
    
        bool escapeGhosts(vector<vector<int>>& ghosts, vector<int>& target) { 
            vector<int> source(2);
            int distance = manhattanDistance(source, target);
            for (auto& ghost : ghosts) { 
                int ghostDistance = manhattanDistance(ghost, target);
                if (ghostDistance <= distance) { 
                    return false;
                }
            }
            return true;
        }
    };

1.  多米诺和托米诺平铺  
    有两种形状的瓷砖：一种是 2x1 的多米诺形，另一种是形如 “L” 的托米诺形。两种形状都可以旋转。给定 N 的值，有多少种方法可以平铺 2 x N 的面板？返回值 mod 10^9 + 7。

**动态规划进行分析**

class Solution { 
    public:
        int numTilings(int n) { 
            int base = 1000000007;
            long d[4];
            long d2[4];
            memset(d, 0, sizeof(d));
            memset(d, 0, sizeof(d2));
            
            d[0] = 1;
            d[1] = 0;
            d[2] = 0;
            d[3] = 1;
            for (int i = 1; i < n; ++i)
            { 
                d2[0] = d[3] % base;
                d2[1] = (d[0] + d[2])%base;
                d2[2] = (d[0] + d[1])%base;
                d2[3] = (d[0] + d[1] + d[2] + d[3])%base;
                memcpy(d, d2, sizeof(d));
            }
    
            return d[3];
        }
    };

1.  自定义字符串排序  
    字符串S和 T 只包含小写字符。在S中，所有字符只会出现一次。  
    S 已经根据某种规则进行了排序。我们要根据S中的字符顺序对T进行排序。更具体地说，如果S中x在y之前出现，那么返回的字符串中x也应出现在y之前。  
    返回任意一种符合条件的字符串T。

class Solution { 
    public:
        string customSortString(string order, string s) { 
            uint8_t arr[26] = { 0};
            int i = 0;
            for (auto c : order) { 
                arr[c - 'a'] = i++;
            }
            sort(s.begin(), s.end(), [&arr](char l, char r)
            { 
                return arr[l - 'a'] < arr[r - 'a'];
            });
            return s;
        }
    };

1.  匹配子序列的单词数  
    给定字符串 S 和单词字典 words, 求 words\[i\] 中是 S 的子序列的单词个数。

**将字典中的单词按第一个字母分在26个桶中，然后遍历S，遇到了对应字母则检查，如果满足则滑动指针检查每个单词对应的第二个字母，依此类推，Index滑动至单词末尾则返回值++**

class Solution{ 
    public:
        int numMatchingSubseq(string s, vector<string>& words){ 
            vector<queue<pair<int,int>>>vcbucket(26);
            for(int i=0;i<words.size();i++){ 
                vcbucket[words[i][0]-'a'].push({ i,0});
            }
            int res=0;
            for(char& c:s){ 
                auto& que=vcbucket[c-'a'];
                int size=que.size();
                for(int i=0;i<size;i++){ 
                    auto [pos,index]=que.front();
                    que.pop();
                    if(index+1==words[pos].size()){ 
                        res++;
                    }
                    else{ 
                        vcbucket[words[pos][index+1]-'a'].push({ pos,index+1});
                    }
                }
            }
            return res;
        }
    };

1.  阶乘函数后K个零  
    f(x) 是 x! 末尾是 0 的数量。（回想一下 x! = 1 \* 2 \* 3 \* … \* x，且 0! = 1 ），给定 K，找出多少个非负整数 x ，能满足 f(x) = K 。

**k = x / 5 + x / 5 ^ 2 + … + x / 5 ^ m, 求出 x 的个数结果不是 0 就是 5。正规做法采用二分查找也一样**

class Solution 
    { 
    public:
        int preimageSizeFZF(int k) 
        { 
            return k % 61035156 % 12207031 % 2441406 % 488281 % 97656 % 19531 % 3906 % 781 % 156 % 31 == 30 ? 0 : !(k % 61035156 % 12207031 % 2441406 % 488281 % 97656 % 19531 % 3906 % 781 % 156 % 31 % 6 / 5) * 5;
        }
    };

1.  有效的井字游戏  
    用字符串数组作为井字游戏的游戏板 board。当且仅当在井字游戏过程中，玩家有可能将字符放置成游戏板所显示的状态时，才返回 true。该游戏板是一个 3 x 3 数组，由字符 " "，“X” 和 “O” 组成。字符 " " 代表一个空位。

**分析true的条件  
先手获胜，则x数量等于o的数量+1；后手获胜，则x的数量等于o的数量  
先手x数量不小于o的数量  
获胜只有一个连续三个就成功并结束，所以不会出现两个连续3的情况**

class Solution { 
    private:
        // 判断X或者O会赢
        bool isWin(const vector<string>& board, char c)
        { 
            // 横或者竖满足
            for (int i = 0; i < 3; ++i)
            { 
                if ((c == board[i][0] && c == board[i][1] && c == board[i][2])
                        || (c == board[0][i] && c == board[1][i] && c == board[2][i]))
                { 
                    return true;
                }
            }
            // 对角线满足
            if ((c == board[0][0] && c == board[1][1] && c == board[2][2])
                    || (c == board[0][2] && c == board[1][1] && c == board[2][0]))
            { 
                return true;
            }
    
            return false;
        }
    public:
        bool validTicTacToe(vector<string>& board) { 
            // 统计数量
            int cntX = 0;
            int cntO = 0;
            for (const string& s : board)
            { 
                for (char c : s)
                { 
                    if (c == 'X')
                    { 
                        ++cntX;
                    }
                    else if (c == 'O')
                    { 
                        ++cntO;
                    }
                }
            }
    
            // 排除数量不对的情况
            if (cntX != cntO && cntX != cntO+1)
            { 
                return false;
            }
    
            // 考虑X或者O获胜，同时满足数量要求，不满足则返回false
            if (isWin(board, 'X') && cntX != cntO+1)
            { 
                return false;
            }
            if (isWin(board, 'O') && cntX != cntO)
            { 
                return false;
            }
            // 其他情况都是满足的，返回true
            return true;
        }
    };

1.  区间子数组个数  
    给定一个元素都是正整数的数组A ，正整数 L 以及 R (L <= R)。求连续、非空且其中最大元素满足大于等于L 小于等于R的子数组个数。

**动态规划求解**

class Solution { 
    public:
        int numSubarrayBoundedMax(vector<int>& nums, int left, int right) { 
            int lastR = -1;
            int lastD = 0;
            int res = 0;
    
            int n = nums.size();
            for (int i = 0; i < n; i++)
            { 
                if (nums[i] > right)
                { 
                    lastR = i;
                    lastD = 0;
                }
                else if (nums[i] < left)
                { 
                    res += lastD;
                }
                else
                { 
                    lastD = i - lastR;
                    res += lastD;
                }
            }
            return res;
        }
    };