1、两数之和 已做
2. 两数相加 不错的题目
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
1、想要先把数字求出来再进行计算，然后再保存到数组中，最后转存为链表
链表表示的数字可能会超过int 甚至是long long
int getNum(ListNode* head) { if (head->val == 0) return 0; vector<int> result; while (head != nullptr) { result.push_back(head->val); head = head->next; } int sum = 0; for (int i = result.size() - 1; i >= 0; --i) sum = sum * 10 + result[i]; return sum; } ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int sum = getNum(l1) + getNum(l2); vector<int> sumV; if(sum==0) sumV.push_back(0); while (sum != 0) { sumV.push_back(sum % 10); sum /= 10; } ListNode* head = new ListNode(sumV[0]); ListNode* temp = head; for (int i = 1; i <= sumV.size()-1; ++i) { ListNode* node = new ListNode(sumV[i]); temp->next = node; temp = temp->next; } return head; }
2、新开辟一条链表来继续数据的保存
执行用时：28 ms, 在所有 C++ 提交中击败了85.88%的用户
内存消耗：9.4 MB, 在所有 C++ 提交中击败了100.00%的用户
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* head = new ListNode(l1->val + l2->val); ListNode* temp = head; l1 = l1->next; l2 = l2->next; while (l1 != nullptr && l2 != nullptr) { ListNode* node = new ListNode(l1->val + l2->val); temp->next = node; temp = temp->next; l1 = l1->next; l2 = l2->next; } temp->next = l1 == nullptr ? l2 : l1; temp = head; while (temp != nullptr) { if (temp->val > 9) { if (temp->next != nullptr) { temp->val = temp->val - 10;//这里千万注意是减去 10 而不是 9，好好想想 temp->next->val = temp->next->val + 1; } else {//说明到了最后一个节点了，这种情况很容易忽略。比如999 + 999 ListNode* node = new ListNode(1); //，最后加出来是 18->18->18，经过前面的处理后 8->9->19，最后一步不好处理了 temp->val = temp->val -10 ; temp->next = node; node->next = nullptr; break; } } temp = temp->next; } return head; }
3、直接在原内存上操作
执行用时：24 ms, 在所有 C++ 提交中击败了93.11%的用户
内存消耗：8.6 MB, 在所有 C++ 提交中击败了100.00%的用户
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode*pre=nullptr,* head = l1; while (l1 != nullptr && l2 != nullptr) { l1->val += l2->val; pre = l1;//这里注意要用一个pre节点保存尾节点 l1 = l1->next; l2 = l2->next; } if (l2 != nullptr) { pre->next = l2; } l1= head; while (l1 != nullptr) { if (l1->val > 9) { if (l1->next != nullptr) { l1->val = l1->val - 10; l1->next->val = l1->next->val + 1; } else {//说明到了最后一个节点了 ListNode* node = new ListNode(1); l1->val = l1->val - 10; l1->next = node; node->next = nullptr; break; } } l1 = l1->next; } return head; }
其实还有一种改进的方法，那就是将 if (l2 != nullptr) {pre->next = l2;}放在最后，因为即使l2还有剩下的，也没有节点值超过10的了，可以先处理合并后的节点，然后再将节点直接连接在后面即可
4、一种更快的神仙做法，我服了
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int carry = 0; int sum = 0; ListNode* newhead = new ListNode(0); ListNode* nownode = newhead; while (l1 || l2 || carry)//这里条件设置的很好 { sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry; carry = sum / 10; ListNode* node = new ListNode(sum % 10); nownode->next = node; nownode = nownode->next; l1 = l1 ? l1->next : l1; l2 = l2 ? l2->next : l2; } return newhead->next; }
3、无重复字符的最长子串 已做
4. 寻找两个正序数组的中位数 不会
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
5. 最长回文子串 已做
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
面试题46. 把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
1、跟1-N的数字中统计1出现的个数是差不多的题，需要好好想想，动动笔
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：5.8 MB, 在所有 C++ 提交中击败了97.84%的用户
比如0-9只有那一种分法，而10-25之间都是有2中分法的，比如18可以分为 1 + 8 或者直接 18 就可以，所以关键点就是要看十位和个位组成的数字在不在10-25之间。在的话就是2种分法加起来，不在的话比如44，只能分为 4 + 4.有点类似与 剑指offer中整数n中1出现的数字
int translateNum(int num) { if(num <= 9) return 1; int sub = num % 100;//求后两位 if(sub >= 10 && sub <= 25){//注意 0 -> 'a'，25->‘z’最大就是25了，而不是26 return translateNum(num / 10) + translateNum(num / 100); }else{ return translateNum(num / 10); } }
10. 正则表达式匹配 已做
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
s可能为空，且只包含从a-z的小写字母。p可能为空，且只包含从a-z的小写字母，以及字符.和*。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
