LeetCode 1-10

LeetCode 1. 两数之和

题目要求：

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例：

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

解答：

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int i,j; for(i=0;i<nums.size();i++) { for(j=i+1;j<nums.size();j++) { if(nums[i]+nums[j]==target) { return {i,j}; } } } return {}; } };

总结：

vector返回时可以使用{i,j}来代替。

LeetCode 2. 两数相加

题目要求：

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807

解答：

public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode *head = new ListNode(-1); ListNode *h=head; bool carry=false; int sum=0; while(l1!=NULL||l2!=NULL) { sum=0; if(l1!=NULL) { sum+=l1->val; l1=l1->next; } if(l2!=NULL) { sum+=l2->val; l2=l2->next; } if(carry) sum+=1; h->next=new ListNode(sum%10); h=h->next; carry=sum>=10?true:false; } if(carry) h->next=new ListNode(1); return head->next; } };

总结： 给出两个逆序链表，要求进行加法操作。 首先，建立第三个链表，ListNode(-1)，接着，对 l1 链表和 l2 链表分别进行加法操作。 其次，用carry作为是否进位的标志位。 即当sum=l1->val+l2->val>=10时，carry=true，否则carry为false。 最后，要对carry进行一次判断，因为最后两个数字进行相加可能要进位，此时，需要对新链表进行新建一个进位的结点。

LeetCode 3. 无重复字符的最长子串

题目要求：

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

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

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

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

解答：

class Solution { public: int lengthOfLongestSubstring(string s) { // 哈希集合，记录每个字符是否出现过 unordered_set<char> occ; int n = s.size(); // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动 int rk = -1, ans = 0; // 枚举左指针的位置，初始值隐性地表示为 -1 for (int i = 0; i < n; ++i) { if (i != 0) { // 左指针向右移动一格，移除一个字符 occ.erase(s[i - 1]); } while (rk + 1 < n && !occ.count(s[rk + 1])) { // 不断地移动右指针 occ.insert(s[rk + 1]); ++rk; } // 第 i 到 rk 个字符是一个极长的无重复字符子串 ans = max(ans, rk - i + 1); } return ans; } };

总结：

变化：

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

LeetCode 4. 寻找两个正序数组的中位数

题目要求：

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

**进阶：**你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

示例 1：

输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例 3：

输入：nums1 = [0,0], nums2 = [0,0] 输出：0.00000

示例 4：

输入：nums1 = [], nums2 = [1] 输出：1.00000

示例 5：

输入：nums1 = [2], nums2 = [] 输出：2.00000

提示：

nums1.length == m nums2.length == n 0 <= m <= 1000 0 <= n <= 1000 1 <= m + n <= 2000 -106 <= nums1[i], nums2[i] <= 106

解答：

class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int n=nums1.length; int m=nums2.length; int len=n+m; int astart=0,bstart=0; int left=-1,right=-1; for(int i=0;i<=len/2;i++) { left=right; if(astart<n&&(bstart>=m||nums1[astart]<nums2[bstart])) { right=nums1[astart++]; }else { right=nums2[bstart++]; } } if((len&1)==0) return (left+right)/2.0; else return right; } }

LeetCode 5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。 示例 2：

输入: “cbbd” 输出: “bb”

public String longestPalindrome(String s) { if (s.equals("")) return ""; String origin = s; String reverse = new StringBuffer(s).reverse().toString(); //字符串倒置 int length = s.length(); int[][] arr = new int[length][length]; int maxLen = 0; int maxEnd = 0; for (int i = 0; i < length; i++) for (int j = 0; j < length; j++) { if (origin.charAt(i) == reverse.charAt(j)) { if (i == 0 || j == 0) { arr[i][j] = 1; } else { arr[i][j] = arr[i - 1][j - 1] + 1; } } if (arr[i][j] > maxLen) { maxLen = arr[i][j]; maxEnd = i; //以 i 位置结尾的字符 } } } return s.substring(maxEnd - maxLen + 1, maxEnd + 1); }

总结： 最长回文串=正序字符串与倒序字符串的最长公共子串。 基于最长公共子串公式： 如果i处字符等于j处字符 arr[i][j]=arr[i-1][j-1]+1 特殊边界考虑： 如果i等于0或者j等于0，即为arr[i][j]=1；

LeetCode 6. Z 字形变换

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：

L C I R E T O E S I I G E D H N 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“LCIRETOESIIGEDHN”。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows); 示例 1:

输入: s = “LEETCODEISHIRING”, numRows = 3 输出: “LCIRETOESIIGEDHN” 示例 2:

输入: s = “LEETCODEISHIRING”, numRows = 4 输出: “LDREOEIIECIHNTSG” 解释:

L D R E O E I I E C I H N T S G

class Solution { public: string convert(string s, int numRows) { if (numRows == 1) return s; vector<string> rows(min(numRows, int(s.size()))); int curRow = 0; bool goingDown = false; for (char c : s) { rows[curRow] += c; if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown; curRow += goingDown ? 1 : -1; } string ret; for (string row : rows) ret += row; return ret; } };

LeetCode 7. 整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

示例 1:

输入: 123 输出: 321 示例 2:

输入: -123 输出: -321 示例 3:

输入: 120 输出: 21 注意:

假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

class Solution { public: int reverse(int x) { int sum=0; int max=0x7fffffff,min=0x80000000; while(x!=0) { if(sum>max/10) return 0; if(sum<min/10) return 0; sum=sum*10+x%10; x/=10; } return sum; } };

总结： if(sum>max/10) return 0; if(sum<min/10) return 0; 这两个语句，是用来防止溢出的。不能写成sum*10,因为照样会溢出。 注意： 防溢出：max=0x7fffffff,min=0x80000000

LeetCode 8. 字符串转换整数 (atoi)

请你来实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：

如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。 假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。 该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。 注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0 。

提示：

本题中的空白字符只包括空格字符 ’ ’ 。 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:

输入: “42” 输出: 42 示例 2:

输入: " -42" 输出: -42 解释: 第一个非空白字符为 ‘-’, 它是一个负号。 我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。 示例 3:

输入: “4193 with words” 输出: 4193 解释: 转换截止于数字 ‘3’ ，因为它的下一个字符不为数字。 示例 4:

输入: “words and 987” 输出: 0 解释: 第一个非空字符是 ‘w’, 但它不是数字或正、负号。 因此无法执行有效的转换。 示例 5:

输入: “-91283472332” 输出: -2147483648 解释: 数字 “-91283472332” 超过 32 位有符号整数范围。 因此返回 INT_MIN (−231) 。

class Solution: def myAtoi(self, s: str) -> int: return max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 2**31 - 1), -2**31)

^：匹配字符串开头 [+-]：代表一个+字符或-字符 ?：前面一个字符可有可无 \d：一个数字 +：前面一个字符的一个或多个 \D：一个非数字字符 *：前面一个字符的0个或多个 max(min(数字, 231 - 1), -231) 用来防止结果越界

LeetCode 9. 回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

输入: 121 输出: true 示例 2:

输入: -121 输出: false 解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。 示例 3:

输入: 10 输出: false 解释: 从右向左读, 为 01 。因此它不是一个回文数。 进阶:

你能不将整数转为字符串来解决这个问题吗？

class Solution { public: bool isPalindrome(int x) { long sum=0; float y=x; int m=0; if(x<0) return false; else { while(x!=0) { sum=sum*10+x%10; x/=10; } return sum==y; } } };

LeetCode 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 = “cab” 输出: true 解释: 因为 ‘*’ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。 示例 5:

输入: s = “mississippi” p = “misisp*.” 输出: false

class Solution: def isMatch(self, s: str, p: str) -> bool: if not p: return not s # 结束条件 first_match = (len(s) > 0) and p[0] in {s[0], '.'} # 先处理 `*` if len(p) >=2 and p[1] == '*': # 匹配0个 | 多个 return self.isMatch(s, p[2:]) or (first_match and self.isMatch(s[1:], p)) # 处理 `.` ，匹配一个 return first_match and self.isMatch(s[1:], p[1:])

正则表达式： 正则表达式(regular expression)描述了一种字符串匹配的模式（pattern），可以用来检查一个串是否含有某种子串、将匹配的子串替换或者从某个串中取出符合某个条件的子串等。

例如：

runoo + b，可以匹配 runoob、runooob、runoooooob 等，+ 号代表前面的字符必须至少出现一次（1次或多次）。

runoo * b，可以匹配 runob、runoob、runoooooob 等，* 号代表前面的字符可以不出现，也可以出现一次或者多次（0次、或1次、或多次）。

colou ? r 可以匹配 color 或者 colour，? 问号代表前面的字符最多只可以出现一次（0次、或1次）。