两数相加
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; }
小结
那么这些就是我今天的分享了，希望对大家能有帮助。如果大家有更优的解法，欢迎大家在评论区留言。如果觉得博主写的不错，记得点个关注和赞，跟着博主每天几道代码题。
