leetcode刷题(1)

向右看齐 2023-09-25 21:52 77阅读 0赞

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

#### 文章目录 ####

*  两数相加
 *   *  题目要求
     *  用例输入
     *  做题思路
     *  代码实现
 *  无重复字符的最长字串
 *   *  题目要求
     *  用例输入
     *  做题思路
     *  代码实现
 *  小结

## 两数相加 ##

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

### 题目要求 ###

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

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

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

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

### 用例输入 ###

示例 1：  
![在这里插入图片描述][9ec0fd8fb0bf41b990653f43dcd3603a.png]

输入：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;
    }

我们写完了代码之后我们来运行一下，看看是否能通过。  
![在这里插入图片描述][8b594b01cb1c41e8999061d1554d5082.png]  
当我们提交的时候会出现这个执行错误，那么这是为什么呢？这并不代表我们的代码有问题，而是因为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;
    }

![在这里插入图片描述][ac753f3d8dab4edd8b91151f31217f26.png]

## 无重复字符的最长字串 ##

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

### 题目要求 ###

给定一个字符串 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;
    }

![在这里插入图片描述][b2d097bf22b249868b954e21c961a6a9.png]

## 小结 ##

那么这些就是我今天的分享了，希望对大家能有帮助。如果大家有更优的解法，欢迎大家在评论区留言。如果觉得博主写的不错，记得点个关注和赞，跟着博主每天几道代码题。

[leetcode]: https://leetcode.cn/problems/add-two-numbers/description/
[9ec0fd8fb0bf41b990653f43dcd3603a.png]: https://img-blog.csdnimg.cn/9ec0fd8fb0bf41b990653f43dcd3603a.png
[8b594b01cb1c41e8999061d1554d5082.png]: https://img-blog.csdnimg.cn/8b594b01cb1c41e8999061d1554d5082.png
[ac753f3d8dab4edd8b91151f31217f26.png]: https://img-blog.csdnimg.cn/ac753f3d8dab4edd8b91151f31217f26.png
[leetcode 1]: https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
[b2d097bf22b249868b954e21c961a6a9.png]: https://img-blog.csdnimg.cn/b2d097bf22b249868b954e21c961a6a9.png