打卡leetcode第14天_给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 nee

1.实现strStr（三种解法）

【题目】

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

【分析】

法1：暴力解法：

我们可以让字符串 needle 与字符串 haystack 的所有长度为 m 的子串均匹配一次。

为了减少不必要的匹配，我们每次匹配失败即立刻停止当前子串的匹配，对下一个子串继续匹配。如果当前子串匹配成功，我们返回当前子串的开始位置即可。如果所有子串都匹配失败，则返回 −1。

【C】

int strStr(char * haystack, char * needle){
    for(int i=0;i+strlen(needle)<=strlen(haystack);i++){
        bool flag=true;
        for(int j=0;j<strlen(needle);j++){
        if(haystack[i+j]!=needle[j]){
            flag=false;
            break;
        }
    }
    if(flag){
        return i;
    }
}
return -1;

【C++】

枚举原串 ss 中的每个字符作为「发起点」，每次从原串的「发起点」和匹配串的「首位」开始尝试匹配：

    匹配成功：返回本次匹配的原串「发起点」。
    匹配失败：枚举原串的下一个「发起点」，重新尝试匹配。

class Solution {
public:
    int strStr(string s, string p) {
        int n = s.size(), m = p.size();
        for(int i = 0; i <= n - m; i++){
            int j = i, k = 0; 
            while(k < m and s[j] == p[k]){
                j++;
                k++;
            }
            if(k == m) return i;
        }
        return -1;
    }
};

都很慢

法2：直接用strStr()返回第一个符合的位置，再减去第一个长字符串

【C】

int strStr(char * haystack, char * needle){
    if (needle==0)
    return 0;
    int ans=strstr(haystack,needle)-haystack;
    if (ans<0)
    return -1;
    else
    return ans;
}

这种很快 ，比后边kmp算法还快

法3：KMP算法，求next数组，详细解答见代码随想录

【C】

前缀表不减一版本
void getNext(int* next, char* s) {
    //初始化 next
    int j = 0;
    next[0] = j;
    for (int i = 1; i < strlen(s); i++) {	//注意 i 从 1 开始
        //若前后缀不相同
        while (j > 0 && s[i] != s[j]) {
            //则向前回退
            j = next[j - 1];
        }
        //若前后缀相同
        if (s[i] == s[j]) {
            //i 和 j 同时向后移动（i 的增加在 for 循环里）
            j++;
        }
        //将 j（前缀的长度）赋值给 next[i]
        next[i] = j;
    }
}
 
int strStr(char * haystack, char * needle){
    int len1 = strlen(haystack);
    int len2 = strlen(needle);
    //当 needle 为空字符串时，返回 0
    if (len2 == 0) {
        return 0;
    }
 
    //构建 next 数组
    int* next = malloc(sizeof(int) * len2);
    getNext(next, needle);
    //next 记录的起始位置为 0，所以这里也从 0 开始
    int j = 0;
    for (int i = 0; i < len1; i++) {	//注意匹配时 i 从 0 开始
        //若不匹配
        while (j > 0 && haystack[i] != needle[j]) {
            //j 退回到之前匹配的位置
            j = next[j - 1];
        }
        //若匹配
        if (haystack[i] == needle[j]) {
            //i 和 j 同时向后移动（i 的增加在 for 循环里）
            j++;
        }
        //当 j 等于 needle 的长度时，说明字符串 haystack 里出现了字符串 needle
        if (j == len2) {
            //返回 needle 字符串出现的第一个位置
            return (i - len2 + 1);
        }
    }
	
    //若未找到则说明不存在，返回 -1
    return -1;
}

 

 2.通过删除字母匹配到字典中的最长单词

【题目】

【分析】快排再比较

int cmp(const void* a, const void* b){
    char* ap = *(char**)a;
    char* bp = *(char**)b;
    if(strlen(ap) != strlen(bp)){
        return strlen(bp) - strlen(ap);
    }
    return strcmp(ap, bp);
}
 
bool canDelete(char * s, char * d){
    int sLen = strlen(s);
    int dLen = strlen(d);
    int i = 0, j = 0;
    while(i < sLen && j < dLen){
        if(s[i] == d[j]){
            j++;
            if(j == dLen){
                return true;
            }
        }
        i++;
    }
    return false;
}
 
char * findLongestWord(char * s, char ** dictionary, int dictionarySize){
    qsort(dictionary, dictionarySize, sizeof(char*), cmp);
    int sLen = strlen(s);
    int i, j, flag = 0;
    char* ans = malloc(sizeof(char) * (sLen + 1));
    for(i = 0; i < dictionarySize; i++){
        if(canDelete(s, dictionary[i]) && sLen >= strlen(dictionary[i])){
            strcpy(ans, dictionary[i]);
            flag = 1;
            break;
        }
    }
    if(flag == 0){
        ans = "";
    }
    return ans;
}

3.有序数组的平方

【题目】

【分析】

法1：先算平方再快排

int cmp(const void* a,const void* b){
    return (*(int*)a-*(int*)b);
}
int* sortedSquares(int* nums, int numsSize, int* returnSize){
    
    
    
    int *ans=(int*)malloc(sizeof(int)*numsSize);
    for(int i=0;i<numsSize;i++){
       ans[i]=nums[i]*nums[i];
    }
    qsort(ans,numsSize,sizeof(int),cmp);
    *returnSize=numsSize;
    return ans;
}

法2：双指针法

--直接平方再两边双指针--
int* sortedSquares(int* nums, int numsSize, int* returnSize) {
    int* ans = malloc(sizeof(int) * numsSize);
    *returnSize = numsSize;
    for (int i = 0, j = numsSize - 1, pos = numsSize - 1; i <= j;) {
        if (nums[i] * nums[i] > nums[j] * nums[j]) {
            ans[pos] = nums[i] * nums[i];
            ++i;
        } else {
            ans[pos] = nums[j] * nums[j];
            --j;
        }
        --pos;
    }
    return ans;
}
--第二种--
int* sortedSquares(int* nums, int numsSize, int* returnSize){
    int *reNums;
    int left = 0,right = numsSize - 1,i = numsSize - 1;//定义左右“指针”分别从最左和最右开始
    reNums = malloc(sizeof(int) * numsSize); //申请动态数组将原来的值计算比较赋值给新的数组即reNums
    for(int j = 0; j < numsSize; j++){  // 遍历整个数组计算各个数的平方值并重新赋值给nums
        nums[j] = pow(nums[j],2);
    }
    while(left <= right){             // 当右边大于等于左边时进入循环
        if(nums[right] >= nums[left]){//最后一次肯定是左边右边遍历到同一个位置所以等于也要判断
            reNums[i] = nums[right--];//右边赋值后像左偏移-1
        }
        else{
            reNums[i] = nums[left++];//左边赋值后向右偏移即+1
        }
        i--;
    }
    *returnSize = numsSize;//返回数组大小和传入的大小一致
    return reNums;
}
 

4.移动0

【题目】

【分析】

法1：循环遍历法：

void moveZeroes(int* nums, int numsSize){
    /* 方法一：先统计所有非零数、然后放到数组前端，剩余空间全补0 */
    int j = 0;
    for (int i = 0; i <= numsSize -1; i++) {
        // 第1步：找到非零数放在数组前端
        if (nums[i] != 0) {
            nums[j] = nums[i];
            j++;
        }
    }
 
    // 第2步：从j开始到数组末端全赋值0（j之前都是非0数）
    while (j <= numsSize-1) {
        nums[j++] = 0;
    }
}

法2：双指针法：参考：https://leetcode-cn.com/problems/move-zeroes/solution/cyu-yan-ti-jie-xun-huan-bian-li-fa-by-ma-3xgu/

/*
    方法二：双指针交换法（该题的本质是考察双指针，i 代表右指针，j代表左指针）
    0  1  0  3  12
    i
    j

    0  1  0  3  12     i指向数组第1个非零数，准备交换nums[i]和nums[j]，即准备交换1和0
       i
    j

    1  0  0  3  12
       i               swap(&nums[i], &nums[j])交换，即1和0交换完成（第1轮交换）
    j

    1  0  0  3  12
             i         i移动到下一个非0数字，j向前移动1步，准备交换nums[i]和nums[j]，即准备交换3和0
       j

    1  3  0  0  12
             i         swap(&nums[i], &nums[j])交换，即3和0交换完成（第2轮交换）
       j

    1  3  0  0  12
                 i     i移动到下一个非0数字（刚好是数组结尾），j向前移动1步，准备交换nums[i]和nums[j]，即准备交换12和0
          j

    1  3  12  0  0
                 i     swap(&nums[i], &nums[j])交换，即12和0交换完成（第3轮交换）。由于i已经到达数组结尾，因此结束。
           j
*/

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}
 
void moveZeroes(int* nums, int numsSize) {
    // 方法二：双指针交换法（i为右指针， j为左指针）
    int j = 0;
    for (int i = 0; i <= numsSize -1; i++) {
        if (nums[i] != 0) {
            swap(&nums[i], &nums[j]); // 交换数组下标索引i和j对应的元素值
            j++;  // 左指针右移1步
        }
    }
}

5.反转字符串

【题目】

【分析】

双指针法：

【C】

void swap(char *a, char *b) {
    char t = *a;
    *a = *b, *b = t;
}
 
void reverseString(char *s, int sSize) {
    for (int left = 0, right = sSize - 1; left < right; ++left, --right) {
        swap(s + left, s + right);
    }
}
 

【C++】

reverse()

class Solution {
public:
    void reverseString(vector<char>& s) {
        reverse(s.begin(),s.end());
    }
};