-
15. 三数之和
题目描述 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。 注意：答案中不可以包含重复的三元组。 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ] https://leetcode-cn.com/problems/3sum/ 解法1 首先对原数组nums进行排序, 用指针i指向nums的每个元素, 然后另指针j=i+1, k=|nums|-1. 指针j与k相向而行, 直到nums[i]+nums[j]+nums[k] == 0我们就找到了一个解, 此时需要继续相向而行直到k>=j. 将数组排序可以把算法的时间复杂度降低到O(n^2). 若不对数组排序, 为了寻找j, k使得nums[i]+nums[j]+nums[k] == 0, 需要使用双重循环遍历nums, 这样会使复杂度达到O(n^3). 因为题目要求“不可以包含重复的三元组”, 这就需要我们一旦找到符合条件的i, j, k. 就需要跳过nums中相同的元素(代码中被标记的部分), 以避免寻找重复的解. 例如…
-
9. 回文数
题目描述 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。 示例 1: 输入: 121 输出: true 示例 2: 输入: -121 输出: false 解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。 示例 3: 输入: 10 输出: false 解释: 从右向左读, 为 01 。因此它不是一个回文数。进阶:你能不将整数转为字符串来解决这个问题吗？ https://leetcode-cn.com/problems/palindrome-number/ 解法 我们按照进阶的要求，不将整数转化为字符串。代码模板中，变量x是int类型的。那么，将其反转结果使用long类型存放是不会溢出的。题目提到了一个case为“-121”，逆序读“121-”不是回文串。那么我们就可以推测，负数一定不是回文数。 我们按照“7.整数反转”这道题的技巧，判断反转后的数字与原数字是否一致来判定是否为回文数字即可。
-
7. 整数反转
题目描述 给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。 示例 1: 输入: 123 输出: 321 示例 2: 输入: -123 输出: -321 示例 3: 输入: 120 输出: 21 注意: 假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。 https://leetcode-cn.com/problems/reverse-integer/ 解法 首先说明一点，如果直接转成StringBuffer，然后reverse以下再转成int就没意思了。我们尽可能不要使用这种straightforward的方法去做，才能够学到东西。 变量x存放了要被反转的数字，假设x=123.我们让x对10取余就能获得末尾数字，然后再另x=x/10，直到x为0. 例如：123%10==3，123->12; 12%10==2, 12->1; 1%10==1, 1->0循环结束。让我们对取过来对数字3、2、1记为n，分别带入公式result = result*10 + n，其中result初值为0。列如：分别带入3、2、1，0*10+3==3；3*10+2==32；32*10+1==321。 这样，我们通过一次循环就能逆序取出x的各位数字，然后带入result = result*10 + n就能得到逆序后的数字。还有一点是，题目要求发生溢出返回0。为了能够判定溢出，我们就要用比int范围更广的类型来存储逆序后的结果。每次循环，都要判定result变量是否小于Integer.MIN_VALUE或大于Integer.MAX_VALUE。
-
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” 输出:…
-
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…