leetcode刷题(1)

各位朋友们，大家好，从今天开始我将陆续为大家更新我自己每天的leedcode刷题，我将会为大家说明每一步的来由，保证你一天新学会几道题目。各位朋友可以跟着博主每天刷几道题，相信两个月后大家的代码能力可以得到明显的提高。那么接下来就开始今天的刷题之路了哦。

文章目录

两数相加
无重复字符的最长字串
小结

两数相加

leetcode两数相加（难度：中等）

题目要求

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

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

用例输入

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

做题思路

因为题目给的链表就是倒序的，而我们平时做加法时也是从两个数字的个位开始加的，如果相加结果大于进位，就向前一位进一，并且当前位减去进位。
我们还需要注意的是，这道题没有说两个链表的长度相同，所以当到达了其中一个链表的尾结点时，就把当前链表的上一位当作0。并且当两个链表都到达了尾结点时，我们还需要做出判断，判断是否还有进位值，如果有我们就需要额外创建一个结点来放这个进位值。

代码实现

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
//创建一个哨兵位，不动的头结点
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    //cur1来连接返回的链表上的每一个结点
    struct ListNode* cur1 = head;
//创建临时变量来存放进位值
    int tmp = 0;
    //当l1和l2都为NULL时，结束循环
    while (l1 || l2)
    {
//这里是判断l1或l2是否到达了尾结点，如果到了，那么该链表结点的值为0
        int n1 = l1 ? l1->val : 0;
        int n2 = l2 ? l2->val : 0;
        int sum = n1 + n2 + tmp;
        struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        newNode->val = sum % 10;
        cur1->next = newNode;
        cur1 = cur1->next;
        tmp = sum / 10;
        if (l1)
        {
            l1 = l1->next;
        }
        if (l2)
        {
            l2 = l2->next;
        }
    }
//判断当l1和l2都到达了尾结点时，是否还有进位值
    if (tmp > 0)
    {
        struct ListNode* newNode1 = (struct ListNode*)malloc(sizeof(struct ListNode));
        newNode1->val = 1;
        cur1->next = newNode1;
    }

    return head->next;
}

我们写完了代码之后我们来运行一下，看看是否能通过。

当我们提交的时候会出现这个执行错误，那么这是为什么呢？这并不代表我们的代码有问题，而是因为leedcode的标准比较严格，我们在创建一个新结点的时候必须将该结点的next指针赋值。所以我们需要在创建结点的时候将next指针置为NULL。

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next = NULL;
    struct ListNode* cur1 = head;
    int tmp = 0;
    while (l1 || l2)
    {
        int n1 = l1 ? l1->val : 0;
        int n2 = l2 ? l2->val : 0;
        int sum = n1 + n2 + tmp;
        struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        newNode->next = NULL;
        newNode->val = sum % 10;
        cur1->next = newNode;
        cur1 = cur1->next;
        tmp = sum / 10;
        if (l1)
        {
            l1 = l1->next;
        }
        if (l2)
        {
            l2 = l2->next;
        }
    }
    if (tmp > 0)
    {
        struct ListNode* newNode1 = (struct ListNode*)malloc(sizeof(struct ListNode));
        newNode1->next = NULL;
        newNode1->val = 1;
        cur1->next = newNode1;
    }

    return head->next;
}

无重复字符的最长字串

leetcode之无重复字符的最长字串（难度：中等）

题目要求

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

用例输入

示例 1：
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2：
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3：
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是子串的长度，“pwke” 是一个子序列，不是子串。

做题思路

我们这个题使用双指针来解决，一个指针用来记住新的字符串的第一个元素的地址，另一个指针用来遍历字符串。当遍历字符串的指针指向的内容没有重复时，那么我们怎样知道当前的字符是否有重复呢？我们创建一个大小为128的数组，将字符所代表的ASCII码值作为数组下标。如果没有重复我们的计数器就加1，如果有重复就返回到那个记忆指针所在的位置。然后遍历的字符串再继续走，知道到达字符串的’\0’位置。

代码实现

int lengthOfLongestSubstring(char* s) {
//s1是记忆指针
    char* s1 = s;
//s2指针用来遍历字符串
    char* s2 = s;
    char arr[128] = { 0 };
//初始化数组，将数组的元素都初始化为0
    memset(arr, 0, 128);
    int count = 0;
//max用来存储最长的无重复字符的长度
    int max = 0;
    while (*s2 != '\0')
    {
        if (arr[*s2] == 0)
        {
    //我们向数组中对应下标第一次存放数据时，存放完成就将该下标的数据改为1
            arr[*s2] = 1;
            count++;
        }
        else
        {
    //如果有重复元素，就重新把数组中元素的数据初始化
            memset(arr, 0, 128);
            if (count > max)
            {
                max = count;
            }
            count = 0;
            s2 = s1;
            s1++;
        }
        s2++;
    }
//这里做判断是防止字符串中没有重复的字符，然后max就没有被赋值
    if(count>max)
    {
        max = count;
    }
    return max;
}