作者：一个喜欢猫咪的的程序员
专栏：《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;
}