听海 - 算法瞎解
type: channel
link: https://seahi.me/category/algorithm/
items: LeetCode 540.有序数组中的单一元素
items: LeetCode 448.找到所有数组中消失的数字
items: LeetCode 95.不同的二叉搜索树
items: LeetCode 263.丑数
items: LeetCode 153.寻找旋转排序数组中的最小值
items: LeetCode 2.两数相加
items: LeetCode 961.单词子集

LeetCode 540.有序数组中的单一元素
type: item
date: 2019-10-15T17:03:00+08:00
description: 题目描述给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。示例 1:输入: [1,1,2,3,3,4,4,8,8] 输出: 2示例 2:输入: [3,3,7,7,10,11,11] 输出: 10注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。解法分析题目中要求 log n 的时间复杂度，已经提示不能直接遍历，我们可以考虑二分查找。我们看下图，如果所有数字成对出现，则偶数位置的数字应该与它右边的数字相等；相应地，奇数位置的数字应该与它左边的数字相等。否则，说明当前位置左侧已经出现了唯一的数字。我们把这个作为二分查找缩小范围的条件： 当前为偶位置，但与右边数字不相等 -->向左查找； 当前为奇位置，但与左边数字不相等 -->向左查找。 代码示例（C++）class Solution { public: int singleNonDuplicate(vector<int>& nums) { int left = 0; int right = nums.size() - 1; int mid = 0; if (nums.size() == 1 || nums[0] != nums[1]) // 数组长度为1，或第一个数字就是唯一数字 return nums[0]; while (mid = (left + right) / 2, left < right) { if (mid % 2 == 0) { // 下标为偶数。如果左侧都是成对出现的数字，其值应与右边相等 if (nums[mid] != nums[mid + 1] && nums[mid] != nums[mid - 1]) return nums[mid]; if (nums[mid] != nums[mid + 1]) right = mid - 1; else left = mid + 1; } else { // 下标为奇数。如果左侧都是成对出现的数字，其值应与左边相等 if (nums[mid] != nums[mid + 1] && nums[mid] != nums[mid - 1]) return nums[mid]; if (nums[mid] != nums[mid - 1]) right = mid - 1; else left = mid + 1; } } return nums[mid]; } };

LeetCode 448.找到所有数组中消失的数字
type: item
date: 2019-09-30T18:32:00+08:00
description: 这个题目名字有点怪，需要注意“所有”修饰最后的“数字”，而不是“数组”。题目描述给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。找到所有在 [1, n] 范围之间没有出现在数组中的数字。您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。示例:输入:[4,3,2,7,8,2,3,1]输出:[5,6]解法思路解法一将元素值作为下标，按照这个下标去对应的位置加负号。最后没有被加负号的元素，其下标即“消失的数字”。解法二同解法一，只是将加负号变为加数组长度。最后小于数据长度的元素，其下标即“消失的数字”。解法三将元素值作为下标，将该元素移动到下标的位置，除非该位置的元素和自己相等。最后没有在自己位置的元素，其下标即为“消失”的数字。示例：4，3，2，7，8，2，3，1第1个元素是4，和nums[3]=7交换：7，3，2，4，8，2，3，17，和nums[6]=3交换：3，3，2，4，8，2，7，13，和nums[2]=2交换：2，3，3，4，8，2，7，12，和nums[1]=3交换：3，2，3，4，8，2，7，13，无需和nums[2]=3交换第2个元素是2，当前位置即nums[1]，无需交换第3个元素是3，和nums[2]=3无需交换第4个元素是4，和nums[3]=4无需交换第5个元素是8，和nums[7]=1交换：3，2，3，4，1，2，7，81，和nums[0]=3交换：1，2，4，3，3，2，7，83，和nums[2]=4交换：1，2，3，3，4，2，7，84，和nums[3]=3交换：1，2，3，4，3，2，7，83，和nums[2]=3无需交换第6个元素是 -2，和nums[1]=2无需交换第7个元素和第8个元素也无需交换结果：1，2，3，4，3，2，7，8nums[4]!=4+1nums[5]!=5+1所以5和6是消失的数字。代码示例vector<int> findDisappearedNumbers(vector<int>& nums) { // 解法一 vector<int> res; for (int i = 0; i < nums.size(); ++i) { int index = abs(nums[i]) - 1; nums[index] = -abs(nums[index]); } for (int i = 0; i < nums.size(); ++i) { if (nums[i] > 0) res.push_back(i+1); } return res; } vector<int> findDisappearedNumbers2(vector<int>& nums) { // 解法二 vector<int> res; for (int i = 0; i < nums.size(); ++i) { int index = (nums[i] - 1) % nums.size(); nums[index] += nums.size(); } for (int i = 0; i < nums.size(); ++i) { if (nums[i] <= nums.size()) res.push_back(i + 1); } return res; } void swap(vector<int>& nums, int index1, int index2) { if (index1 == index2) return; nums[index1] = nums[index1] ^ nums[index2]; nums[index2] = nums[index1] ^ nums[index2]; nums[index1] = nums[index1] ^ nums[index2]; } vector<int> findDisappearedNumbers3(vector<int>& nums) { // 解法三 vector<int> res; for (int i = 0; i < nums.size(); ++i) { while (nums[i] != nums[nums[i] - 1]) swap(nums, i, nums[i] - 1); } for (int i = 0; i < nums.size(); ++i) if (nums[i] != i + 1) res.push_back(i + 1); return res; }

LeetCode 95.不同的二叉搜索树
type: item
date: 2019-09-30T15:06:30+08:00
description: 题目描述给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。示例:输入: 3 输出: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ] 解释: 以上的输出对应以下 5 种不同结构的二叉搜索树： 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3解法思路递归从 1,2...n 中选择 i 作为根，剩余 1,2,...i-1 用于左子树，i+1,i+2,...n 用于右子树。 对 1,2,...i-1 重复上述过程，生成所有左子树；对 i+1,i+2,...n 重复上述过程生成所有右子树。 最后，将得到的所有左子树和右子树连接到树根上。代码示例（C++）class Solution { public: vector<TreeNode*> generateTrees(int n) { if (n == 0) return vector<TreeNode*>(); return generate_trees(1, n); } vector<TreeNode*> generate_trees(int start, int end) { vector<TreeNode*> all_trees; if (start > end) { all_trees.push_back(NULL); // 如果不插入NULL，后面最里层的两个循环会不能进入 return all_trees; } for (int i = start; i <= end; ++i) { vector<TreeNode*> left_trees = generate_trees(start, i - 1); vector<TreeNode*> right_trees = generate_trees(i + 1, end); for (TreeNode* l : left_trees) { for (TreeNode* r : right_trees) { TreeNode* current_tree = new TreeNode(i); current_tree->left = l; current_tree->right = r; all_trees.push_back(current_tree); } } } return all_trees; } };

LeetCode 263.丑数
type: item
date: 2019-09-27T18:54:34+08:00
description: 题目描述编写一个程序判断给定的数是否为丑数。丑数就是只包含质因数 2, 3, 5 的正整数。示例 1:输入: 6 输出: true解释: 6 = 2 × 3示例 2:输入: 8 输出: true解释: 8 = 2 × 2 × 2示例 3:输入: 14 输出: false解释: 14 不是丑数，因为它包含了另外一个质因数 7。说明： 1 是丑数。 输入不会超过 32 位有符号整数的范围: [−231, 231 − 1]。 解题思路如果一个数的因子只有2, 3, 5，那它不断除以2, 3或5，最后会成为1。代码示例class Solution { public: bool isUgly(int num) { if (num < 1) return false; while (true) { if (num == 1) // 注意是在循环里（不是在判断题目“说明”中的情况1） return true; else if (num % 2 == 0) num /= 2; else if (num % 3 == 0) num /= 3; else if (num % 5 == 0) num /= 5; else return false; } return true; } };

LeetCode 153.寻找旋转排序数组中的最小值
type: item
date: 2019-09-27T18:12:59+08:00
description: 题目描述假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。请找出其中最小的元素。你可以假设数组中不存在重复元素。示例 1:输入: [3,4,5,1,2] 输出: 1示例 2:输入: [4,5,6,7,0,1,2] 输出: 0解法思路直观方法：从左到右遍历，遇到一个元素比它左右都小，就是所找的答案（需要注意没有经过旋转和在最小值在末尾的情况）。优化：二分搜索代码如下：class Solution { public: int findMin(vector<int>& nums) { if (nums.size() == 1) { return nums[0]; } int left = 0; int right = nums.size() - 1; if (nums[right] > nums[0]) return nums[0]; while (left < right) { int mid = (left + right) / 2; if (nums[mid] > nums[mid + 1]) return nums[mid + 1]; if (nums[mid] < nums[mid - 1]) return nums[mid]; if (nums[mid] > nums[0]) left = mid + 1; else right = mid - 1; } return -1; }附：暴力的直观方法代码int findMin2(vector<int>& nums) { if (nums.size() == 1) { return nums[0]; } if (nums[nums.size() - 1] < nums[nums.size() - 2]) // 最小值在末尾 return nums[nums.size() - 1]; if (nums[nums.size() - 1] > nums[0]) // 没有经过旋转 return nums[0]; for (int i = 1; i < nums.size() - 1; ++i) { if (nums[i] < nums[i - 1] && nums[i] < nums[i + 1]) return nums[i]; } return -1; }在LeetCode的测试集下，两种方法相差4ms

LeetCode 2.两数相加
type: item
date: 2019-09-26T11:09:37+08:00
description: 题目描述：给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。示例：输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807思路： 将两个链表看成是相同长度的进行遍历，如果一个链表较短则在前面补 0，比如 987 + 23 = 987 + 023 = 1010； 每一位计算的同时需要考虑上一位的进位问题，即sum=x+y+carry；而当前位计算结束后同样需要更新进位值，即carry=sum/10； 如果两个链表全部遍历完毕后，进位值为 1，则在新链表最前方添加节点 1。 代码示例：/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* head = new ListNode(0); ListNode* current = head; int carry = 0; int sum = 0; int x = 0; int y = 0; while (l1 != nullptr || l2 != nullptr) { x = l1 == nullptr ? 0 : l1->val; y = l2 == nullptr ? 0 : l2->val; sum = x + y + carry; carry = sum / 10; sum = sum % 10; current->next = new ListNode(sum); current = current->next; if (l1 != nullptr) l1 = l1->next; if (l2 != nullptr) l2 = l2->next; } if (carry == 1) { current->next = new ListNode(carry); current = current->next; } current->next = nullptr; return head->next; } };执行结果：

LeetCode 961.单词子集
type: item
date: 2019-09-25T15:44:46+08:00
description: 题目描述我们给出两个单词数组 A 和 B。每个单词都是一串小写字母。现在，如果 b 中的每个字母都出现在 a 中，包括重复出现的字母，那么称单词 b 是单词 a 的子集。 例如，“wrr” 是 “warrior” 的子集，但不是 “world” 的子集。如果对 B 中的每一个单词 b，b 都是 a 的子集，那么我们称 A 中的单词 a 是通用的。你可以按任意顺序以列表形式返回 A 中所有的通用单词。示例 1：输入：A = [amazon,apple,facebook,google,leetcode], B = [e,o] 输出：[facebook,google,leetcode]示例 2：输入：A = [amazon,apple,facebook,google,leetcode], B = [l,e] 输出：[apple,google,leetcode]示例 3：输入：A = [amazon,apple,facebook,google,leetcode], B = [e,oo] 输出：[facebook,google]示例 4：输入：A = [amazon,apple,facebook,google,leetcode], B = [lo,eo] 输出：[google,leetcode]示例 5：输入：A = [amazon,apple,facebook,google,leetcode], B = [ec,oc,ceo] 输出：[facebook,leetcode]提示： 1 <= A.length, B.length <= 10000 1 <= A[i].length, B[i].length <= 10 A[i] 和 B[i] 只由小写字母组成。 A[i] 中所有的单词都是独一无二的，也就是说不存在 i != j 使得 A[i] == A[j]。 解题思路：对于任意一个字母，它在B中单词中出现的最大次数，不能大于它在A中单词中的出现次数，否则这个A中的单词就不是符合要求的“通用单词”。利用B中对于每一个字母出现次数取最大值的方法构建一个table，这个table是用来存放B中每一个字母出现次数最大值，对于A中每一个的单词都必须满足table中每一个不等于0的字母出现的次数需要大于等于table中的次数，此时则放入ret中代码示例（C++）：class Solution { public: vector<string> wordSubsets(vector<string>& A, vector<string>& B) { vector<vector<int> > mapa(A.size(), vector<int>(26, 0)); vector<vector<int> > mapb(A.size(), vector<int>(26, 0)); vector<int> table(26, 0); vector<string> ret; for (int i = 0; i < A.size(); ++i) { for (int j = 0; j < A[i].size(); ++j) { mapa[i][A[i][j] - 'a'] ++; } } for (int i = 0; i < B.size(); ++i) { for (int j = 0; j < B[i].size(); ++j) { mapb[i][B[i][j] - 'a'] ++; } for (int j = 0; j < 26; ++j) { if (mapb[i][j] > table[j]) table[j] = mapb[i][j]; } } for (int i = 0; i < A.size(); ++i) { bool flag = true; for (int j = 0; j < 26; ++j) { if (table[j] != 0 && mapa[i][j] < table[j]) { flag = false; break; } } if (flag) ret.push_back(A[i]); } return ret; } };