力扣刷题记录

2022-07-17

记录自己刷算法题中遇到的问题和自己的思路；

1、无重复长度的最长子串：

题目描述：

bba26f3a71a90a406c18dc5f4fbb88e

提示：

`0 <= s.length <= 5 * 104；

s 由英文字母、数字、符号和空格组成；

思路：

就是做两个标志位，表示当前字符串的起始位置和正在比较的字符位置；

遍历整个字符串；

从起始标志位开始，到结束位置，依次比对是否有重复字符；

如果无，就结束位置加加；

如果有，就计算长度，并移动起始位置到重复字符的下一个位置；

然后一直循环；

要特别考虑：

1
2
3

au
abb
bba

这些特殊排序的字符串；

是因为最后一个没有办法比较；

题解代码：

int lengthOfLongestSubstring(char *s)
{
    int str_length = strlen(s);
    int end_flag = 1, start_flag = 0, max_length = 1;
    char flag = 0;
    int i = 0;
    if (str_length == 0)
    {
        return 0;
    }
    while (*(s + end_flag) != '\0')
    {
        for (i = start_flag; i < end_flag; i++)
        {
            if (*(s + i) == *(s + end_flag))
            {

                if (end_flag - start_flag > max_length)
                {
                    max_length = end_flag - start_flag;
                }
                flag = 1;
                break;
            }
            if (i == str_length - 2)
            {
                if ((*(s + end_flag + 1) == '\0'))
                {
                    if (end_flag - start_flag + 1 > max_length)
                    {
                        max_length = end_flag - start_flag + 1;
                    }
                }
            }
        }
        if (flag == 1)
        {
            flag = 0;
            start_flag = i + 1;
        }
        else
        {
            end_flag++;
        }
    }
    return max_length;

改进：

//方法2
int lengthOfLongestSubstring(char * s){
    int str_length=strlen(s);
    int end_flag=1,start_flag=0,max_length=1;
    char flag=0;
    int i=0;
    if(str_length==0)
    {
        return 0;
    }
    while(*(s+end_flag)!='\0')
    {
        for(i=start_flag;i<end_flag;i++)
        {
            if(*(s+i)==*(s+end_flag))
            {           
                flag=1;
                break;
            }
        }
        if(flag==1)
        {
            if(end_flag-start_flag>max_length)
            {
                 max_length=end_flag-start_flag;
            } 
            flag=0;
            start_flag=i+1;
        }
        else
        {
            if(end_flag-start_flag+1>max_length)
            {
                 max_length=end_flag-start_flag+1;
            }  
            end_flag++;
        }
    }
    return max_length;
}

2、括号匹配

test

bool isValid(char * s){
    char *temp_s;
    int p_temp=-1;
    if(strlen(s)%2!=0)
    {
        return false;
    }
    temp_s=(char *)malloc(strlen(s));
    if((*s==')')||(*s=='}')||(*s==']'))
    {
        return false;
    }
    while(*s!='\0')
    {
        switch(*s)
        {
            case '(':
                p_temp++;
                if(p_temp<0)
                {
                    return false;
                }
                *(temp_s+p_temp)=')';
                break;
            case '{':
                p_temp++;
                if(p_temp<0)
                {
                    return false;
                }
                *(temp_s+p_temp)='}';
                break;
            case '[':
                p_temp++;
                if(p_temp<0)
                {
                    return false;
                }
                *(temp_s+p_temp)=']';
                break;
            case ')':
            case '}':
            case ']':
                if(p_temp==-1)
                {
                    return false;
                }
                if(*(temp_s+p_temp)!=*s)//上面和这个条件不能放在一起，因为，p_temp==-1时，数组是无法访问的，越界
                {
                    return false;
                }
                {
                    p_temp--;
                }
                break;
        }
        s++;
    }
    if(p_temp==-1)
    { 
        return true;
    }
    else
    {
        return false;
    }
}

3、成最多水的容器

LC3

#define MY_MIN(a,b) ((a)<(b)?(a):(b))
int maxArea(int* height, int heightSize){
    int i,j;
    int max=0;
    int temp;
    int p_left=0,p_right=0;
    p_right=heightSize-1;
    while(p_left!=p_right)
    {
        temp=MY_MIN(height[p_left],height[p_right])*(p_right-p_left);
        if(temp>max)
        {
            max=temp;
        }
        if(height[p_left]<height[p_right])
        {
            p_left++;
        }
        else
        {
            p_right--;
        }
    }
    return max;
}

4、有序链表合并

题目描述：

code1

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


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode *dummy=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode *pre=dummy;
    while(list1!=NULL&&list2!=NULL)
    {
        if(list1->val<=list2->val)
        {
            pre->next=list1;
            list1=list1->next;
        }
        else
        {
            pre->next=list2;
            list2=list2->next;
        }
        pre=pre->next;
    }
    if(list1==NULL)
    {
        pre->next=list2;
    }
    else
    {
        pre->next=list1;
    }
    return dummy->next;
}

思路：

主要是不用考虑申请空间的问题，因为空间本身就是存在的，只需要改变链表中各个节点间的指向关系就可以；

最后看哪一个先为NULL，然后把不为空的整体连接上去，返回即可；