LeetCode字符串高频题目整理（持续更新中）

/*这是一道很简单的题目，用栈可以很轻松的实现
当左括号出现的时候入栈，当右括号出现的出栈，如果匹配就继续，不匹配就错误
当字符串遍历完成之后，栈内仍有字符串就错误
用一个数组进行和一个记录栈顶值的int进行了栈的模拟，代码很简单，很好理解（虽说题目也很简单就是了）
*/
bool isValid(char * s){
   
    int len = strlen(s);
    char stack[3500];
    int top = -1;
    int i = 0;
    for( i=0;i<len;i++)
    {
      if((s[i] == '(')||(s[i] == '{')||(s[i] == '['))
        stack[++top] = s[i];
      else
        {
               if(top<0)//出现了右括号，但数组为空，即没有左括号与之匹配
                return false;
                if((s[i] == ')'))
                {
                     if(stack[top]!='(') return false;
                     else top--;
                }


             if((s[i] == '}'))  
             {
              if(stack[top]!='{') return false;
               else top--;
             }
        
            if((s[i] == ']'))  
            {
              if(stack[top]!='[') return false;  
              else top--;
            }

        }   
    }
    if(top>=0) //数组内仍有左括号，没有右括号与之匹配
        return false;\
        //这里一定要有返回值
         return true;

}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 void generate(char *item,int index,int left,int right,char **result,int *count,int n)
 {
     if(left==0&&right==0)//已经全部插满了
        {
            result[(*count)]=(char*)malloc(sizeof(char)*(2*n+1));
            strcpy(result[(*count)++],item);
            return;
        }
        //result[(*count)++][]=item;
        item[index]='(';//插入左括号
        item[index+1]='\0';

        if(left>0)
        generate(item,index+1,left-1,right,result,count,n);
        if(right>left)//待插入右括号的个数多余待插入左括号的个数
        {
            item[index]=')';//插入右括号
            generate(item,index+1,left,right-1,result,count,n);
        }
 }
char ** generateParenthesis(int n, int* returnSize){
    //左右括号的总个数
    int left=n,right=n;
    int length=2*2*n;
    int count=0;//记录已经插入的个数
    int index=0;//记录当前插入元素的下标

    char **result=(char **)malloc(sizeof(char *)*(5000));//创建二维数组
    char *item=(char *)malloc(sizeof(char)*(2*n+1));//创建存储数组

    generate(item,index,left,right,result,&count,n);
    *returnSize=count;

    return result;
}

char* stack;
int top;

void Push(char val)
{
    stack[++top] = val;
}
void Pop()
{
     top--;
}
char Gettop()  {
    if(top>=0) return stack[top];
    else return '0';
}

bool isValid(char * S){
    int len = strlen(S);
    stack = (char*)calloc(sizeof(char), len); top = -1;
    for (int i = 0; i < len; i++) {
        //入栈
        if (S[i] != 'c') {
            Push(S[i]);
        } else {
            //不为b则false
            if (Gettop() != 'b')
                return false;
            Pop();
             //不为b则false
            if (Gettop() != 'a')
                return false;
            Pop();
        }
    }
    //如果栈中没有元素，则为true
    if (top < 0)
        return true;
    return false;
}

char res[5103] = {'\0'};
char * addStrings(char * num1, char * num2){
    
    short s1 = strlen(num1), s2 = strlen(num2), len = 5101, carry = 0;
    for (s1--, s2--; s1 >= 0 || s2 >= 0 || carry;) 
    {
        //长度为0时，数值取0
        carry += (s1 >= 0 ? num1[s1--] - 48: 0) + (s2 >= 0 ? num2[s2--] - 48 : 0);  // 最长遍历处理
        res[len--] = carry % 10 + 48;
        carry /= 10;
    }
    return &res[len+1];  // 返回指针，取地址


}

char * addBinary(char * a, char * b){

    int carry = 0;	//进位

	int length = (strlen(a)>strlen(b)? strlen(a)+2:strlen(b)+2);

	char* result = (char*)malloc(sizeof(char)*length);		//开辟空间
	result[length-1] = '\0';
	//多开辟两个空间 一个存储进位，一个存储结束符
	for(int i = strlen(a)-1,j = strlen(b)-1,k = length -2; (i >=0)||(j >= 0); i--,j--,k--)
	{
		int sum = carry;
		sum += (i >= 0? a[i]-'0':0);
		sum += (j >= 0? b[j]-'0':0);

		carry = sum /2;
		result[k] = '0'+ sum % 2;
	}
	
	if(carry == 0)  //最后无进位，直接返回
	//为什么result+1可以 result[0]+1会报错
		return result+1;  
	else  
	result[0] = '1';    //有进位，补一个最高位
		return result;
}

char * addBinary(char * a, char * b){

    int len1 = strlen(a)-1;
    int len2 = strlen(b)-1;
    int carry = 0;
    //多开辟了两个空间存储进位和结束符
    char*res = (char*)malloc(sizeof(char)*10002);
    //倒着开始存储
    int cnt = 10000;
    res[10001] = '\0';
    while(len1>=0||len2>=0||carry)
    {
        //注意判断数组是否为空
        carry +=(len1<0?0:a[len1]-'0')+(len2<0?0:b[len2]-'0');  
        res[cnt--] = carry%2+48;   
        carry = carry/2; 
       //注意判断结束条件len1 len2
        len1 = (len1>=0?len1-1:-1);
        len2 = (len2>=0?len2-1:-1);
    }
    
    return &res[cnt+1];
}

    8 9  <- num2
    7 6  <- num1
-------
    5 4
  4 8
  6 3
5 6
-------
6 7 6 4

      1 2 5  <- num2
        8 8  <- num1
-----------
        4 0
      1 6
      8 
      4 0
    1 6
    8
-----------
  1 1 0 0 0

for(int i = length1  - 1; i >= 0; i--)
{
    for(int j = length2 - 1; j >= 0; j--)
    {
        value[i + j + 1] += (num1[i] - '0') * (num2[j] - '0');
    }
}

   0     1     2     3
 -----------------------
|  0  |  56 | 111 |  54 |
 -----------------------

   for(int i= totalLength - 1; i > 0; i--)                 //获取每个位置上面的数字并处理进位
   {
       value[i - 1] += value[i] / 10;
       value[i] %= 10;
   }

   0     1     2     3
 -----------------------
|  6  |  7  |  6  |  4  |
 -----------------------

char * multiply(char * num1, char * num2)
{
    int length1 = strlen(num1);
    int length2 = strlen(num2);
    int totalLength = length1 + length2;                     //获取相乘后字符串的总有效位数
    
    int charIndex = 0;                                       //定义负责索引字段
    int valueIndex = 0;
    
    //int *value = (int *)malloc(sizeof(int) * totalLength);
    //memset(value, 0, sizeof(int) * totalLength);
    int *value = (int *)calloc(totalLength,sizeof(int));
    
    //char *result = (char *)malloc(sizeof(char) * (totalLength + 1));
    char *result =(char *)calloc(totalLength + 1,sizeof(char));
    
    
    for(int i = length1  - 1; i >= 0; i--)
    {
        for(int j = length2 - 1; j >= 0; j--)
        {
            value[i + j + 1] += (num1[i] - '0') * (num2[j] - '0');
        }
    }
     //获取每个位置上面的数字并处理进位
    for(int i= totalLength - 1; i > 0; i--)                
    {
    	//后一个的进位要加到前一个 取商获得进位
        value[i - 1] += value[i] / 10;
        //当前位置只保留余数
        value[i] %= 10;
    }
    
    // //忽略掉前面多余的0，但是最高位也就是唯一的一位0不能忽略
    //因为我们设置的最大长度为length1 + length2，并且初始化为了0，实际长度有可能没有占满，前面会有多于的0，处理掉
    while(value[valueIndex] == 0 && valueIndex < totalLength -1 ) 
    {
        valueIndex++;                                       
    }
    //将数值转化为字符串
    while(valueIndex < totalLength)
    {
        result[charIndex++] = value[valueIndex++] + '0';
    }
    
    result[charIndex] = '\0';                                //默认补上字符串的终止符
    
    return result;
    
    
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    struct ListNode* l3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* p1 = l1;
    struct ListNode* p2 = l2; 
    struct ListNode* q = l3; 
    int carry = 0;
    int sum = 0;
    while((p1!=NULL) ||(p2!=NULL))
    {
        sum = 0;
        if(p1!=NULL)
        {
            sum += p1->val;
            printf("sum:%d\r\n",sum);
        }
        if(p2!=NULL)
        {
            sum += p2->val;
            printf("sum:%d\r\n",sum);
        }
        
        printf("sum:%d,carry:%d\r\n",sum,carry);
        struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
        temp->val = sum%10+carry;
        carry = (sum>=10)? 1 : 0;
        printf("temp->val:%d\r\n",temp->val);
         printf("\r\n");
        temp->next = NULL;
        q->next = temp;
        q = temp;

        p1 = p1->next;
        p2 = p2->next;
    }
    return l3->next;
}

int findLUSlength(char * a, char * b){
  int lenA=strlen(a),lenB=strlen(b);
    if (strcmp(a,b)==0)return -1;
        return lenA>lenB?lenA:lenB;
}

// 按照字符串长度降序排序
// 字符串比较：如果该字符串不是之前字符串的子序列，
//而且与后面跟他长度相同的字符串不是相同的字符串，则该字符串本身为特殊序列
// 如果跟后面字符串比较是重复的话，顺序到不是重复的下一个字符串再进行判断
int cmp1(const void *a, const void *b)
{
    return strlen(*(char **)b) - strlen(*(char **)a);
}

int cmp2(const void *a, const void *b)
{
    return strcmp(*(char **)a, *(char **)b);
}
//a是不是b的子序列  a为当前序列 b为当前序列之前的序列
bool isSequence(char *a, char *b)
{
    int len1 = strlen(a);
    int len2 = strlen(b);
    printf("%d,%d\r\n",len1,len2);
    int count = 0;
    int j = 0;
    for (int i = 0; i < len1; i++) {
        while (j < len2) {
            if (a[i] == b[j++]) {
                count++;
                break;
            }
            // j++;
        }
    }
    if (count == len1)
        return true;
    return false;
}

int findLUSlength(char ** strs, int strsSize){
    bool flag = false;
    qsort(strs, strsSize, sizeof(strs[0]), cmp2);
    qsort(strs, strsSize, sizeof(strs[0]), cmp1);
   // 向前查询是否为子串 
    for (int i = 0; i < strsSize; i++) {
        bool f1 = true, f2 = true;
        //从第二个序列开始，往前查询 之前的序列是否为当前序列的子序列
        if (i >= 1) {
            for (int j = 0; j < i; j++) {
                //第二个序列strs[i] 是不是第一个序列strs[j]的子序列
                if (isSequence(strs[i], strs[j])) {
                    f1 = false;
                    break;
                }
            }
        }
        // 向后查询有无重复字符串
        for (int k = i + 1; k < strsSize; k++) {
            //长度不同 内容肯定不同 跳出循环，继续往后比较
            if (strlen(strs[k]) != strlen(strs[i]))
                break;
            //长度相同时，比较内容是否相同 
            if (strcmp(strs[k], strs[i]) == 0) {
                f2 = false;
                //内容不同时，将从此序列开始比较 
                i = k;
            }
        }
        if (f1 && f2)
            return strlen(strs[i]);
    }

    return -1;
}

void swap(char *s,int start,int end)
{
    while(start<end)
    {
        char temp;
        temp = s[start];
        s[start] = s[end];
        s[end] = temp;
        start++;
        end--;
    }
}

void reverseString(char* s, int sSize){

        int start = 0;
        int end = sSize-1;
        swap(s,start,end);
        
 
}

void swap(char *str,int start,int end)
{
    
    while(start<end)
    {      
        char temp = str[start];
        str[start] = str[end];
        str[end] = temp;
        start++;
        end--;
    }

}
char * reverseStr(char * s, int k){
   int len = strlen(s);
    for (int i = 0; i < len; i += 2 * k) {
        int start = i;
        //如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
        //如果剩余字符少于 k 个，则将剩余字符全部反转。
        int end = (len-start+1 >k ) ? i + k - 1 : len - 1; //是否超界？
        swap(s,start,end);

    }
    return s;

}

void swap(char *str,int start,int end)
{
    
    while(start<end)
    {      
        char temp = str[start];
        str[start] = str[end];
        str[end] = temp;
        start++;
        end--;
    }

}
char * reverseWords(char * s){

    int i = 0;
    int start = 0;
    int end = 0;
    int len = strlen(s);

    while(s[end++]!='\0')
    {
        //注意边界条件
        if(s[end] == ' ' || s[end] == '\0')
        {         
            swap(s,start,end-1);   
            start = end+1;
        }

    }
    
    return s;
}

void swap(char *str,int start,int end)
{
       
        char temp = str[start];
        str[start] = str[end];
        str[end] = temp;
}

int vowel(char c)
{
    if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
        c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U')
        return 1;
    else
        return 0;
}

char * reverseVowels(char * s){
    int i = 0
    int j = strlen(s) - 1;
    while(i < j)
    {
    	//注意不要越界
        while(i < j && !vowel(s[i]))
            i++;
        while(i < j && !vowel(s[j]))
            j--;
        swap(s,i,j);
        i++;
        j--;
    }
    return s;
}

int repeatedStringMatch(char * A, char * B){
    int lenA = strlen(A);
    int lenB = strlen(B);
    //最大复制次数
    int max = lenB / lenA + 2;
    //空间大小的确定
    char newStr[max * lenA + 1];
    memset(newStr, 0, sizeof(newStr));
    for (int i = 0; i < max; i++) {
        strcat(newStr, A);
        char *tmp = NULL;
        if (strlen(newStr) >= strlen(B)) {
            tmp = strstr(newStr, B);
        }
        if (tmp == NULL) {
            continue;
        } else {
            return i + 1;
        }
    }
    return -1;
}

bool repeatedSubstringPattern(char * s){
   int len =strlen(s);
   char *ch =(char *)malloc(sizeof(char)*(2*len -1));
   //屏蔽掉第一个字符
   strcpy(ch,s+1);
   printf("%s\r\n",ch);
   //将len-1个字符连接到ch后面，即屏蔽掉最后一个
   strncat(ch,s,len-1);
  //返回非空，说明可以由循环节构成
   return strstr(ch,s);
}

int strStr(char * haystack, char * needle){
    int n,n1,start=0;   //n,n1分别为字符串长度，start记录正确匹配开始的位置。
    n=strlen(haystack);
    n1=strlen(needle);
    if(n1==0)
        return 0;
    if(n<n1)
        return -1;    
    for(int i=0;i<n;++i) //首先i为haystack数组的指针，遍历该数组
    {
        //在遍历过程中，找到haystack与needle数组第一个字符相同的位置，并且用haystack减去该位置     
        //（n-i）看是否大于needle数组的长度 如果不大于直接跳出，减少遍历次数
        if(needle[0]==haystack[i] && (n-i)>=n1)  
        {
            int count=0;     //用来记录下一个for循环匹配正确的次数
            start=i;
            int z=i;                   
            for(int j=0;j<n1;++j)
            {
                if(needle[j]==haystack[z])
                {
                    ++count;   //正确则加1
                    ++z;       //并且haystack数组z指针后移
                }
            }
            if(count==n1) //看匹配正确次数是否等于needle数组的长度
                return start;
        }     
    }
    return -1;

}

int compress(char* chars, int charsSize){
int start = 0, end = 0, k = 0, t, i, j;
    for(; start < charsSize; start++){
        if(start + 1 == charsSize || chars[start] != chars[start+1]){
            chars[k++] = chars[end];    //chars 存下字符
            if(start > end){            //连续次数大于1时保存次数
                t = start - end + 1;    //相同字符出现的次数
                i = k;              //次数转为字符串时需要翻转，用i保存翻转的起点
                while(t > 0){       //测试用例的次数最多两位数，但我们要考虑多位数的情况
                    chars[k++] = t % 10 + '0';  //chars 存下次数
                    t /= 10;
                }
                for(j = 0; j < (k - i) / 2; j++){     //翻转
                    char tmp = chars[i + j];
                    chars[i + j] = chars[k - 1 -j];
                    chars[k - 1 -j] = tmp;
                }
            }
            end = start + 1;
        }
    }
    return k;
}

bool isPalindrome(char * s){

  int len = strlen(s);
  //空字符串定义为有效的回文串
  if (len == 0) return true;
  //单个字符定义为有效的回文串
  if (len == 1) return true;
  //两个指针，一个指向开头，一个指向结尾
    char *p = s;
    char *q = s+len-1;
    //双指针同时遍历字符串
      while(p<q)
      {
        //跳过非字符和非字母，注意每次判断是否两个指针相遇  
        while((!(isalpha(*p))&&!(isdigit(*p)))&&(p<q))
        {
            p++;
        }

        while((!(isalpha(*q))&&!(isdigit(*q)))&&(p<q))
        {
             q--;     
        }
        //只要有一个不相等就返回false 
            if((tolower(*p)!=tolower(*q)))
                 return false;
        //下一个字符的比较
            p++;
            q--;
        }    
    return true;
}

bool isPalindrome (char* start, char* end)   //检查s中一段是否为回文数
{
    while(start <= end) {
        if(*start != * end) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

bool validPalindrome(char * s)
{
    int flag = 0;    // 一次删除机会
    int len = strlen(s);
    if (len <= 2) {   //单独一字符或者两字符肯定能变成回文
        return true;
    }
    char* start = s;
    char* end = s + len -1;
    while (start <= end) {
        if (*start != *end) {
            //删除左边
            if (isPalindrome(start+1, end)) {
                return true;
            }
            //删除右边
            if (isPalindrome(start, end - 1)) {
                return true;
            }
            return false;
        }
        start++;
        end--;
    }
    return true;

}

//设置一个辅助数组flag[26]，两次遍历：第一遍统计各字符出现次数，第二遍找到第一个值为1的索引即为所求
int firstUniqChar(char * s){

    int flag[26]={0};
    int len=strlen(s);
    int i;
    for(i=0;i<len;i++){
        flag[s[i]-'a']++;
    }
    for(i=0;i<len;i++){
        if(flag[s[i]-'a']==1) return i;
    }
    return -1;
}

char * frequencySort(char * s){  
    int flag[128] = {0};
    int len = strlen(s);
    if (len <= 2)
        return s;
    for(int i = 0;i<len;i++)
    {
        printf("%d ",s[i]);
        flag[s[i]]++;
    }
    int i ,j = 0;
    while(i < len){
		int maxValue = 0;
		int maxIndex = 0;
        //每次都找到最大值 记录下最大值和下标
		for( j = 0; j < 128; j++){
			if (flag[j] > maxValue){
				maxValue = flag[j];
				maxIndex = j;
			}
		}

        //把最大值对应的内容置0 表示已经打印了
		if (maxValue != 0){
			flag[maxIndex] = 0;
		}

        //将当前的字符串中出现的最大频率的字母放在s中
		for(j = 0; j < maxValue; j++){
			s[i++] = maxIndex;
		}
	}
    return s;
}

#define Hash_SIZE 20001
#define OFFSET 10000//对下标为负数进行偏移使数组下标>=0

typedef struct 
{
    int val;
    int cnt;
}HashTable;
//结构体数组
HashTable hash[Hash_SIZE];
//比较函数，对cnt出现次数进行排序
int comp(const void *a, const void *b) {
    return (((HashTable *)a)->cnt - ((HashTable *)b)->cnt);
}

int* topKFrequent(int* nums, int numsSize, int k, int* returnSize){
    
    memset(hash,0,sizeof(hash));//初始化sizeof(hash)个字节
    int i=0,j=0;
    for(i=0;i<numsSize;i++)//将nums数组的值和出现的次数放入hash表中
    {
        hash[(nums[i]+OFFSET)%Hash_SIZE].cnt++;
        hash[(nums[i]+OFFSET)%Hash_SIZE].val=nums[i];
    }
    
    //对原hash表进行优化  把所有非零值靠前存放
    for(i=0;i<Hash_SIZE;i++)
    {
        if(hash[i].cnt!=0)
        {
            hash[j].cnt=hash[i].cnt;
            hash[j].val=hash[i].val;
            j++;
        }
    }

    //对hash表中的cnt进行快速排序，出现次数少的在前面，次数多的在后面
    //hash[j-i-1]
	//注意sizeof里面是hashtable
    qsort(hash,j,sizeof(HashTable),comp);
    //输出前k个高频元素  从最后一个开始  j-0-1  j-1-1 j-2-1
    for(i=0;i<k;i++)
        nums[i]=hash[j-i-1].val;

    *returnSize=k;
    return nums;
}

#include <uthash.h>
struct Number {
    int key;
    int cnt;
    UT_hash_handle hh;
};

static void CountNum(struct Number **hash, int num, int cnt)
{
    struct Number *node = NULL;
    HASH_FIND_INT(*hash, &num, node);
    if (node != NULL) {
        node->cnt++;
        return;
    }
    node = malloc(sizeof(struct Number));
    node->cnt = cnt;
    node->key = num;
    HASH_ADD_INT(*hash, key, node);
}

static void CountArray(struct Number **hash, int *array, int n)
{
    for (int i = 0; i < n; i++) {
        CountNum(hash, array[i], 1);
    }
}

static void Release(struct Number **hash)
{
    struct Number *node, *next;
    HASH_ITER(hh, *hash, node, next) {
        HASH_DEL(*hash, node);
    }
}

static int Cmp(struct Number *a, struct Number *b)
{
    return b->cnt - a->cnt;
}

int *topKFrequent(int *nums, int numsSize, int k, int *returnSize)
{
    int *result = malloc(sizeof(int) * k);
    assert(result != NULL);
    *returnSize = k;
    struct Number *ha = NULL;
    CountArray(&ha, nums, numsSize);
    HASH_SORT(ha, Cmp);
    
    int index = 0;
    struct Number *node = NULL;
    struct Number *next = NULL;
    HASH_ITER(hh, ha, node, next) {
        result[index++] = node->key;
        if (index == k) {
            break;
        }
    }
    Release(&ha);
    return result;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
//哈希表
#define MAX_NUM 50000
typedef struct {
    int num;
    int cnt;
    UT_hash_handle hh;
}hash_entry;

hash_entry* users = NULL;
hash_entry hash_item[MAX_NUM];
int g_cnt = 0;

void add_users(int num) {
    hash_entry* t = NULL;
    HASH_FIND_INT(users,&num,t);
    if(t == NULL) {
        hash_item[g_cnt].num = num;
        hash_item[g_cnt].cnt = 1;
        t = &hash_item[g_cnt];
        g_cnt++;
        HASH_ADD_INT(users,num,t);
        return;
    }
    t->cnt++;
}
int cmp(hash_entry* a,hash_entry* b) {
    return b->cnt - a->cnt;
}
int* topKFrequent(int* nums, int numsSize, int k, int* returnSize){
    users = NULL;
    hash_entry* t = NULL;
    for(int i = 0;i < numsSize;i++) {
        add_users(nums[i]);
    }
    //对哈希表进行排序
    HASH_SORT(users,cmp);
    int* res = (int*)malloc(sizeof(int) * k);
    int cnt = 0;
    //遍历哈希表
    for(t = users;t != NULL;t = t->hh.next) {
        if(cnt >= k) {
            break;
        }
        res[cnt++] = t->num;
    }
    *returnSize = k;
    return res;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
typedef struct node{
    char word[20];
    int num;
}NODE;

int cmp1(const NODE* a, const NODE* b){
    return (b->num - a->num);
}
int cmp2(const NODE* a, const NODE* b){
    return strcmp(a->word, b->word);
}

char ** topKFrequent(char ** words, int wordsSize, int k, int* returnSize){
    NODE* node = calloc(wordsSize, sizeof(NODE));
    char** ret = calloc(wordsSize, sizeof(char*));
    int node_len = 0;
    for (int i = 0; i < wordsSize; i++) {// 建立结构体数组，存储出现次数
        bool flag = false;
        // 若前面出现过这个单词，直接累加次数
        for (int j = 0; j < node_len; j++) {
            // printf("check : \"%s\" ", node[j].word);
            // printf("compare with \"%s\"\n", words[i]);
            if (strcmp(words[i], node[j].word) == 0) {
                node[j].num++;
                flag = true;
                // printf("node[%d].num++\n", j);
                break;
            }
        }
        if (!flag) {// 若前面没出现过，新增一个节点
            strcpy(node[node_len].word, words[i]);
            node[node_len].num = 1;
            // printf("add node : \"%s\" %d\n", node[node_len].word, node[node_len].num);
            node_len++;
            // puts("-----");
        }
    }

    qsort(node, node_len, sizeof(NODE), cmp2);// 排序字符串
    qsort(node, node_len, sizeof(NODE), cmp1);// 排序出现次数
    for (int i = 0; i < k; i++) {
        // printf("print node : \"%s\" %d\n", node[i].word, node[i].num);
        ret[i] = node[i].word;
    }

    *returnSize = k;
    return ret;
}

int cmp(const void*a, const void* b) {
    return *(int*)b - *(int*)a;
}

int findKthLargest(int* nums, int numsSize, int k){

    if(nums==NULL||numsSize==0) return 0;

    qsort(nums, numsSize, sizeof(int), cmp);

    return nums[k-1];
}

void quickSort(int arr[], int low, int high)
{
    int first = low;
    int last  = high;
    int key = arr[first];
    if(first >= last)
        return;
    while(first < last)
    {
        while(first < last && arr[last] <= key)
        {
            last--;
        }
        //从后往前，找到一个比key大的和first指向的位置交换
        arr[first] = arr[last];

        while(first < last && arr[first] > key)
        {
            first++;
        }
        //从前往后，找到一个比key小的和last指向的位置交换
        arr[last] = arr[first];
    }
    //最后跳出时 first == last first就是key的位置
    arr[first] = key;
    //继续排序前半部分 和后半部分
    quickSort(arr, low, first-1);
    quickSort(arr, first+1, high);
}

int findKthLargest(int* nums, int numsSize, int k){
    
    if(nums==NULL||numsSize==0) return 0;
    quickSort(nums,0,numsSize-1);
    //for(int i = 0;i<numsSize;i++)
        //printf("%d\r\n",nums[i]);
    return nums[k-1];
}

int cmp(const void*a, const void*b)
{
//将(int**)指针解一次引用再用索引访问元素，解一次引用相当于一维数组
	int x1=(*(int**)a)[0], y1=(*(int**)a)[1];
	int x2=(*(int**)b)[0], y2=(*(int**)b)[1];
	return (x1*x1+y1*y1) - (x2*x2+y2*y2);
}

int** kClosest(int** a, int n, int* col, int k, 
	int* returnSize, int** returnColumnSizes)
{
	qsort(a, n, sizeof(int**), cmp);	
	*returnColumnSizes = (int*)calloc(k, sizeof(int));
	for (int i = 0; i < k; i++) {
		(*returnColumnSizes)[i] = 2;
	}
	*returnSize = k;
	return a;
}

/*************************************************************************/
/* qsort排序二维数组，cmp的每个元素都是一个独立的 int 数组，也就是指针 */
int cmp(const void* a, const void* b) {

    // 解一次引用转换为对应一维数组
    int* arry1 = *(int**)a;
    int* arry2 = *(int**)b;
    
    // 解两次引用 获取对应arry1 的两个元素
    int x1 = *arry1;
    int y1 = *(arry1 + 1);

    int x2 = *arry2;
    int y2 = *(arry2+1);

    return (x1*x1 + y1*y1) - (x2*x2 + y2*y2);
}


int** kClosest(int** points, int pointsSize, int* pointsColSize, int K, int* returnSize, int** returnColumnSizes){
    if(points==NULL || pointsSize==0 || K==0) return NULL;
    
    qsort(points, pointsSize, sizeof(int)*pointsColSize[0], cmp);
    /*   这里注意 qsort 的传参，使用不当会报错
    Line 11: Char 11: runtime error: load of misaligned address 0x602000000032 for type 'int *', which requires 8 byte alignment (solution.c)       0x602000000032: note: pointer points here
    */

    // 指定return输出的二维数组是包含有几个一维数组
    *returnSize = pointsSize > K ? K : pointsSize;
    
    *returnColumnSizes = (int*)malloc(sizeof(int*)*(*returnSize));
    // 指定每个一维数组的 col 
    for(int i = 0; i< (*returnSize); i++) {
        (*returnColumnSizes)[i] = 2;
    }
    return points;
}

typedef struct node {
	int x, y;
	int d;
} node_t;

int cmp(const void*a, const void*b)
{
	node_t *a1 = (node_t *)a;
	node_t *b1 = (node_t *)b;
	return a1->d - b1->d;
}

int** kClosest(int** a, int n, int* col, int k, 
	int* returnSize, int** returnColumnSizes)
{
	if (a == NULL || col == NULL || n == 0 || k == 0
		|| returnSize == NULL || returnColumnSizes== NULL) {
		return NULL;
	}
	*returnSize = k;
	*returnColumnSizes = (int*)calloc(k, sizeof(int));
	int **result = (int**)calloc(k, sizeof(int*));
	node_t *p = (node_t *)calloc(n, sizeof(node_t)); 
	for (int i = 0; i < n; i++) {
		int x = a[i][0];
		int y = a[i][1];
		int d = x*x+y*y;
		p[i].x=x;
		p[i].y=y;
		p[i].d=d;
		// printf("(%d,%d)=%d\n", x, y, d);
	}
	qsort(p, n, sizeof(node_t), cmp);	
	/* for (int i = 0; i < n; i++) {
		printf("(%d,%d)=%d\n", p[i].x, p[i].y, p[i].d);
	}*/
	for (int i = 0; i < k; i++) {
		(*returnColumnSizes)[i] = 2;
		result[i] = (int*)malloc(sizeof(int)*2); 
		result[i][0] = p[i].x;
		result[i][1] = p[i].y; 
	}
	free(p);
	return result;
}

typedef struct node{
    int row;
    int column;
    int dist;
}Node_t,*pNode_t;
void adjustheap(pNode_t heap,int start,int end)
{
    Node_t temp;
    int dad=start;
    int son=dad*2+1;
    while(son<end)
    {
        if(son+1<end&&heap[son+1].dist>heap[son].dist)
            son++;
        if(heap[dad].dist>heap[son].dist)
            return;
        else
        {
            temp=heap[dad];
            heap[dad]=heap[son];
            heap[son]=temp;
            dad=son;
            son=dad*2+1;
        }
    }
}

int lengthOfLastWord(char * s){

    int l;
    int i;
    int res = 0;

    if(NULL == s)
        return 0;

    l = strlen(s);
    for(i = l-1; i >=0; i--)
    {
        if(isalpha(s[i]))
            res++;
        //空格字符
        else
            if(res)
                break;
    }
    return res;
}

int countSegments(char * s){

    if(s[0] == '\0') return 0;
    int cnt=0;
    int i = 0;
    int len = strlen(s);
    for(i =0; i < len; i++){
        //注意第一个单词的判断 i == 0
         if ((i == 0 || s[i-1] == ' ') && s[i] != ' ')
        cnt++;

    }
    return cnt;

}

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

int romanToInt(char * s){
    
  int count = 0;
	while (*s){
		if (*s == 'V')         count += 5;
		else if (*s == 'L')    count += 50;
		else if (*s == 'D')    count += 500;
		else if (*s == 'M')    count += 1000;
		else if (*s == 'I')
			//加多了减去，巧妙地规律判断
			count = (*(s + 1) == 'V' || *(s + 1) == 'X') ? count - 1 : count + 1;
		else if (*s == 'X')
			count = (*(s + 1) == 'L' || *(s + 1) == 'C') ? count - 10 : count + 10;
		else
			count = (*(s + 1) == 'D' || *(s + 1) == 'M') ? count - 100 : count + 100;
		s++;
	}
	return count;
}

bool checkRecord(char * s){

    if (s[0] == '\0') return false;
    int len = strlen(s);
    int cntA = 0;
    int cntL = 0;
    //计数
    for(int i = 0;i<len;i++)
    {
        if(s[i] == 'A')
            cntA++;
        //允许出现两个连续的L，但不允许连续的三个L
        //只要满足cntL条件就会+3，说明已经超过。不满足条件说明小于三个连续L，cntL就会小于3，下面进行判断的时候会判断为true。
        if((s[i] == 'L')&&(s[i+1])&&(s[i+1] == 'L')&&(s[i+2] == 'L'))
            cntL+=3;
    }
    if((cntA<=1)&&(cntL<=2))
        return true;
    else
        return false;
}

}

char * longestCommonPrefix(char ** strs, int strsSize){
    if(0==strsSize)return "";
    char *s0= strs[0];  //首个字符串作为基准
    for(int col=0; s0[col]!='\0' ;++col){   //s0的第col个字符作为基准
        for(int row=1; row<strsSize; ++row){//扫描其他字符串，仅当所有字符串的第col个字符都同基准，才会正常结束循环
            if(s0[col]!=strs[row][col]){    //不会越界！因为即将越界会有 '\0'停止符作为哨兵，此时马上跳出。
                s0[col]='\0';   // 用'\0'表示结束，改短s0
                return s0;  
            }
        }//而且C语言即便越界，只要越的界没有超出整个进程代码段的地址空间，都不会报错。
    }return s0;     //其他字符串不存在或都包含s0的前缀
}

bool judgeCircle(char * moves){

    int cntR = 0;
    int cntL = 0;
    int cntU = 0;
    int cntD = 0;
    int len = strlen(moves);
    for(int i = 0;i<len;i++)
    {
        if(moves[i] == 'R')
            cntR++;
        else if(moves[i] == 'L')
            cntL++;
        else if(moves[i] == 'U')
            cntU++;
        else if(moves[i] == 'D')
            cntD++;
    }

    if(((cntR == cntL))&&((cntU == cntD))) return true;
    

    return false;

}

int numUniqueEmails(char **emails, int emailsSize){
    //初始化
    char **res = calloc(emailsSize, sizeof(char*));
    for (int i = 0; i < emailsSize; i++) {
        res[i] = calloc(101, sizeof(char));
    }
    
    char *first, *last;
    int count1 = 0, count2 = 0, flag = 0;

    for (int i = 0; i < emailsSize; i++) {
        //以@为界限进行分割为first，last两部分
        //首次调用时，s必须指向要分解的字符串，随后调用要把s设成NULL。
        //https://blog.csdn.net/sxy19930313/article/details/78548174
        first = strtok(emails[i], "@");
        last = strtok(NULL, "@");

        for (int j = 0; j < strlen(first); j++) {
            //遇到 . 跳过，进行下一次循环
            if (first[j] == '.') 
            {
                continue;
            } 
            //遇到+直接跳出循环，+后面的都不要
            else if (first[j] == '+')
            {
                break;
            } 
            //其余的都放进res数组
            else
            {
                res[count1][count2++] = first[j];
            }
        }
        //连接@ 和last部分
        strcat(res[count1], "@");
        strcat(res[count1], last);
        flag = 1;
        //比较res中已有内容res[j] 和目前的res[count1]的内容是否相同
        for (int j = 0; j < count1; j++) {
            //二者相同，flag置1 同时清空res[count1]
            if (!strcmp(res[count1], res[j])) {
                flag = 0;
                memset(res[count1], 0, sizeof(char) * 101);
                break;
            }
        }
        //flag为1说明二者不等，count1++，进行下一个
        if (flag == 1) {
            count1++;
        }
        count2 = 0;
    }
    //最后count1的值就是不同的内容的个数
    return count1;
}

int uniqueMorseRepresentations(char ** words, int wordsSize){
      char dict[26][5] = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
    //5*12 = 60
    char morse[100][60] = {0};
    int count = 0;
    for (int i = 0; i < wordsSize; i++) {
        char tmp[60] = { 0 };
        int flag = 0;
        //每个字符串对应的摩斯码放入tmp中
        for (int j = 0; j < strlen(words[i]); j++) {
            strcat(tmp, dict[words[i][j] - 'a']);
        }
        //定义flag分辨相同和不同，如果tmp和morse中的不同 就放入morse中
        for (int k = 0; k < count; k++) {
            if (strcmp(morse[k], tmp) == 0) {
                flag = 1;
                break;
            }
        }
        //不同的话就放入morse中
        if (flag == 0) {
            strcpy(morse[count], tmp);
            count++;
        }
    }
    return count;
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define MAX_SIZE 50000

void transfer_bitree(struct TreeNode* t, char *s, int *len)
{
    if (t) {
        *len += sprintf(s + *len, "%d", t->val);
        if (t->left || t->right) {
            *len += sprintf(s + *len, "%s", "(");
            transfer_bitree(t->left, s, len);
            *len += sprintf(s + *len, "%s", ")");
        }
        if (t->right) {
            *len += sprintf(s + *len, "%s", "(");
            transfer_bitree(t->right, s, len);
            *len += sprintf(s + *len, "%s", ")");
        }
    }
}

char * tree2str(struct TreeNode* t)
{
    char *str = malloc(MAX_SIZE);
    int len = 0;

    transfer_bitree(t, str, &len);
    str[len] = '\0';
    return str;
}

bool canConstruct(char * ransomNote, char * magazine){

    int count[26] = {0};//初始化为全零
    int i;
    char ch;
    for(i = 0; (ch=magazine[i]) != '\0'; i++)
        count[ch-'a']++;
    for(i = 0; (ch=ransomNote[i])!= '\0'; i++){
        if(count[ch-'a']==0) return false;
        else count[ch-'a']--;
    }
    return true;
}

int countBinarySubstrings(char * s){
    int n = 0, pre = 0, curr = 1, len = strlen(s)-1;
    for (int i = 0; i < len; ++i) {
        if (s[i] == s[i+1]) ++curr;
        else               {pre = curr; curr = 1;}
        if (pre >= curr) ++n;
    }
    return n;
}

bool detectCapitalUse(char * word){
    
    int len = strlen(word);
    int cnt = 0;
    for(int i = 0;i<len;i++)
    {
        if((word[i] >='A' )&&(word[i] <='Z'))
        cnt++;     
    }
    //对应情况1和情况3
    if((cnt == len)||(cnt == 0))
        return true;
    //对应情况2  要考虑到首字母
    else if(((word[0]>='A')&&(word[0]<='Z')&&(cnt==1)))
         return true;
    else 
    return false;