作者：一个喜欢猫咪的的程序员

专栏：《Leetcode》

喜欢的话：世间因为少年的挺身而出，而更加瑰丽。                                  ——《人民日报》

809.情感丰富的文字

题目：

情感丰富的文字

https://leetcode.cn/problems/expressive-words/

题目描述：

有时候人们会用重复写一些字母来表示额外的感受，比如 "hello" -> "heeellooo", "hi" -> "hiii"。我们将相邻字母都相同的一串字符定义为相同字母组，例如："h", "eee", "ll", "ooo"。

对于一个给定的字符串 S ，如果另一个单词能够通过将一些字母组扩张从而使其和 S 相同，我们将这个单词定义为可扩张的（stretchy）。扩张操作定义如下：选择一个字母组（包含字母 c ），然后往其中添加相同的字母 c 使其长度达到 3 或以上。

例如，以 "hello" 为例，我们可以对字母组 "o" 扩张得到 "hellooo"，但是无法以同样的方法得到 "helloo" 因为字母组 "oo" 长度小于 3。此外，我们可以进行另一种扩张 "ll" -> "lllll" 以获得 "helllllooo"。如果 S = "helllllooo"，那么查询词 "hello" 是可扩张的，因为可以对它执行这两种扩张操作使得 query = "hello" -> "hellooo" -> "helllllooo" = S。

输入一组查询单词，输出其中可扩张的单词数量。

示例：

输入：

S = "heeellooo"

words = ["hello", "hi", "helo"]

输出：1

解释：

我们能通过扩张 "hello" 的 "e" 和 "o" 来得到 "heeellooo"。

我们不能通过扩张 "helo" 来得到 "heeellooo" 因为 "ll" 的长度小于 3

思路：双指针

经典双指针题型，这里给出C语言解法。

1.在比较每对字符时，分别设置一个起始指针。

2.分别求出每个字符的连续相同个数。

3.基于个数进行判断。

本题我们首先确定当WordSize为0时，我们就不需要比较了，直接返回0就好了。

当wordSize不为0的情况下：

我们以heeellooo（str）和hello（word）为例：

我们要什么时候判断是否是扩张呢？-------------------当我们两个字符串的对应字符相等时！

当对应字符不相等时：

那就是不能扩张，返回0就是了

当对应字符相等时：

我们要将s中sid的位置与sid+1作比较，如果相等，继续比较直到不相等为止。在这个过程中一个变量num1尽量相等的次数。因为我们本题还设立一个变量将便于循环，所以num1要再加一次，num1>=3就是可以扩容的。

我们思考一个情况：当两个字符串的指针来到了llooo（s）和llo（word）时，

num1=2这个时候是不可以扩容的，但两个字符串中的ll都相等。所以是没有问题。

如何解决呢？

我们可以将did的位置和did的下一个位置做比较，跟num1的那个循环一样，利用一个变量num2。当num1==num2时字符串是可以扩容的。

我们这样遍历了两个字符串后，最后当sid和did的位置来到了各自字符串的最后就是可以扩容的，如果没有来到最后就是不能扩容。

时间复杂度：O(N^2)                             空间复杂度：O(1)

代码实现：

int dilate(char* str, char* word)
{
    int sid = 0;
    int did = 0;
    while (did < strlen(word) && sid <strlen(str))
    {
        if (word[did]!= str[sid])
            return 0;
        else
        {
            int num1 = 0;
            for (int i = sid; i < strlen(str); i++)
            {
                 if (str[i] == str[sid])
                    num1++;
                else
                    break;
            }
            int num2 = 0;
            for (int i = did; i < strlen(word); i++)
            {
                if (word[i] == word[did])
                    num2++;
                else
                    break;
            }
            if (num1 == num2 || (num1 > num2 && num1 >= 3))
            {
                sid += num1;
                did += num2;
            }
            else
                return 0;
        }
    }
        if (did < strlen(word) || sid < strlen(str))
            {return 0;}
        else
            {return 1;}
    }
    int expressiveWords(char* s, char** words, int wordsSize)
    {
        if (wordsSize == 0)
            return 0;
        int num = 0;
        for(int i=0;i<wordsSize;i++)
        {
        if(dilate(s, words[i]))
            num++;
        }
        return num;
    }

1351.统计有序数组中的负数

1351. 统计有序矩阵中的负数

https://leetcode.cn/problems/count-negative-numbers-in-a-sorted-matrix/

题目：

给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。 请你统计并返回 grid 中 负数 的数目。

示例：

示例 1：

输入：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]

输出：8

解释：矩阵中共有 8 个负数。

示例 2：

输入：grid = [[3,2],[1,0]]

输出：0

思路：

思路一：暴力解法（就不解释了哈哈哈哈哈哈哈哈哈大家都懂）

时间复杂度：O(N^2)                            空间复杂度：O(1)

思路二：二分查找法

注意到题目中给了一个性质，即矩阵中的元素无论是按行还是按列，都以非递增顺序排列，可以考虑把这个性质利用起来优化暴力。已知这个性质告诉了我们每一行的数都是有序的，所以我们通过二分查找可以找到每一行中从前往后的第一个负数，那么这个位置之后到这一行的末尾里所有的数必然是负数了，可以直接统计。

我们利用begin和end两个找到中间位置n，然后看n下标的值大于0小于0，再找出下一个中间位置，直到找到小于0的地方。

总时间复杂度是O(nlogn）     空间复杂度：O（1）

思路三：杨氏矩阵思想

我们发现从某一列j的数小于0的话，它下面的数都小于0.

前提条件：j=*gridcolsize-1  i=0；

循环结束条件：i<最大行数  || j<0

迭代原理：

1.grid[i][j]<0         j--;

2.grid[i][j]>0         i++;

时间复杂度：O(M+N)                            空间复杂度：O(1)

代码实现：

思路一：

int countNegatives(int** grid, int gridSize, int* gridColSize){
    int num=0;
    for(int i=0;i<gridSize;i++)
    {
        for(int j=0;j<gridColSize[0];j++)
        {
            if(grid[i][j]<0)
            num++;
        }
    }
    return num;
}

思路二：

int countNegatives(int** grid, int gridSize, int* gridColSize){
    int num=0;
    for(int i=0;i<gridSize;i++)
    {
        int m=0;
        int begin=0;
        int end=*gridColSize-1;
        while(begin<=end)
        {
            int n=(begin+end)/2;
            if(grid[i][n]<0)
            {
                end=n-1;
                m=*gridColSize-n;
            }
            else
            {
                begin=n+1;
            }
        }
        num+=m;
    }
    return num;
}

思路三：

int countNegatives(int** grid, int gridSize, int* gridColSize){
    int num=0;
    int i=0;
    int j=*gridColSize-1;
    while(i<=(gridSize-1)&&j>=0)
    {
        if(grid[i][j]<0)
        {
            num=num+gridSize-i;
            j--;
        }
        else
        {
            i++;
        } 
    }
    return num;
}