LeetCode 探索：发散你的思维 [437] 路径总和 III 给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000, 1000000] 的整数。
解题思路：将路径分为包含root节点和不包含root节点的情况，分别进行递归
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 class Solution { public : int pathSum (TreeNode *root, int sum) { if (root == NULL ) return 0 ; int res = 0 ; if (root->val == sum) res++; res += pathSum(root->left, sum); res += pathSum(root->right, sum); res += pathSumInclude(root->left, sum - root->val); res += pathSumInclude(root->right, sum - root->val); return res; } int pathSumInclude (TreeNode *root, int sum) { if (root == NULL ) return 0 ; int res = 0 ; if (root->val == sum) res++; res += pathSumInclude(root->left, sum - root->val); res += pathSumInclude(root->right, sum - root->val); return res; } };
[441] 排列硬币 你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
给定一个数字 n，找出可形成完整阶梯行的总行数。
n 是一个非负整数，并且在32位有符号整型的范围内。
解题思路：使用等差数列的通项公式
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public : int arrangeCoins (int n) { for (long i = 1 ; i <= n; i++) { if ((i * i + i) / 2 > n) return i - 1 ; else if ((i * i + i) / 2 == n) return i; } return 0 ; } };
[443] 压缩字符串 给定一组字符，使用原地算法将其压缩。
压缩后的长度必须始终小于或等于原数组长度。
数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。
在完成原地修改输入数组后，返回数组的新长度。
解题思路：使用双指针方法，一个read指针和一个write指针，均从左边开始移动
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 class Solution { public : int compress (vector <char > &chars) { int anchor = 0 ; int write = 0 ; for (int read = 0 ; read < chars.size(); read++) { if (read + 1 == chars.size() || chars[read] != chars[read + 1 ]) { chars[write++] = chars[anchor]; if (read > anchor) { string num = to_string(read - anchor + 1 ); for (char c : num) chars[write++] = c; } anchor = read + 1 ; } } return write; } };
[447] 回旋镖的数量 给定平面上 n 对不同的点，“回旋镖” 是由点表示的元组 (i, j, k) ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。
找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。
解题思路：使用哈希表，记录相同距离的点的数量
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution { public : int getDistance (vector <int > p, vector <int > q) { return pow (p[0 ] - q[0 ], 2 ) + pow (p[1 ] - q[1 ], 2 ); } int numberOfBoomerangs (vector <vector <int >> &points) { int res = 0 ; vector<map<int, int>> dis(points.size()); for (int i = 0 ; i < points.size() - 1 ; i++) { for (int j = i; j < points.size(); j++) { int d = getDistance(points[i], points[j]); res += 2 * (dis[i][d] + dis[j][d]); dis[i][d]++; dis[j][d]++; } } return res; } };
解题思路：使用距离矩阵，预排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 class Solution { public : int numberOfBoomerangs (vector <vector <int >> &points) { int dis[points.size()][points.size()]; int number = 0 ; for (int i = 0 ; i < points.size(); ++i) { for (int j = 0 ; j < points.size(); ++j) { dis[i][j] = pow (points[i][0 ] - points[j][0 ], 2 ) + pow (points[i][1 ] - points[j][1 ], 2 ); dis[j][i] = dis[i][j]; } } for (int i = 0 ; i < points.size(); ++i) { sort(dis[i], dis[i] + points.size()); int num = 0 ; for (int j = 1 ; j < points.size(); ++j) { if (dis[i][j] == dis[i][j - 1 ]) { num++; } else { if (num != 0 ) { number += factorial(num + 1 ); num = 0 ; } } } if (num != 0 ) { number += factorial(num + 1 ); num = 0 ; } } return number; } int factorial (int num) { int group = 1 ; if (num == 2 ) return 2 ; if (num == 3 ) return 6 ; for (int i = num; i > 2 ; i--) { group *= i; } return group; } };
[448] 找到所有数组中消失的数字 给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
解题思路：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public : vector <int > findDisappearedNumbers (vector <int > &nums) { vector <int > res; for (int i = 0 ; i < nums.size(); i++) { nums[abs (nums[i]) - 1 ] = -abs (nums[abs (nums[i]) - 1 ]); } for (int i = 0 ; i < nums.size(); i++) { if (nums[i] > 0 ) res.push_back(i + 1 ); } return res; } };
[453] 最小移动次数使数组元素相等 给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动可以使 n - 1 个元素增加 1。
解题思路：首先，假设我们在每一步计算 diff 之后正在更新有序数组的元素。下面展示如何在不遍历数组的情况下找到最大最小值。在第一步中，最后的元素即为最大值，因此 diff=a[n-1]-a[0]。我们对除了最后一个元素以外所有元素增加 diff。
现在，更新后的数组开头元素 a’[0] 变成了 a[0]+diff=a[n-1]。因此，a’[0] 等于上一步中最大的元素 a[n-1]。由于数组排过序，直到 i-2 的元素都满足 a[j]>=a[j-1]。因此，更新之后，a’[n-2] 即为最大元素。而 a[0] 依然是最小元素。
于是，在第二次更新时，diff=a[n-2]-a[0]。更新后 a’’[0] 会成为 a’[n-2]，与上一次迭代类似。
然后，由于 a’[0] 和 a’[n-1] 相等，在第二次更新后，a’’[0]=a’’[n-1]=a’[n-2]。于是，最大的元素为 a[n-3]。
于是，我们可以继续这样，在每一步用最大最小值差更新数组。
下面进入第二步。第一步中，我们假设每一步会更新数组 aa 中的元素。但事实上，我们不需要这么做。这是因为，即使是在更新元素之后，我们要登记的 diff 差值也不变，因为 max 和 min 增加的数字相同。
于是，我们可以简单的将数组排序一次， $moves=\sum_{i=1}^{n-1} (a[i]-a[0])$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public : int minMoves (vector <int > &nums) { int moves = 0 ; sort(nums.begin(), nums.end()); for (int i = nums.size() - 1 ; i >= 0 ; i--) { moves += (nums[i] - nums[0 ]); } return moves; } };
解题思路：该方法基于以下思路：将除了一个元素之外的全部元素+1，等价于将该元素-1，因为我们只对元素的相对大小感兴趣。因此，该问题简化为需要进行的减法次数。
显然，我们只需要将所有的数都减到最小的数即可。为了找到答案，我们不需要真的操作这些元素。只需要 $moves=\sum_{i=0}^{n-1} a[i] - min(a)*n$即可，其中 nn 为数组的数量。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public : int minMoves (vector <int > &nums) { long moves = 0 ; int m = INT_MAX; for (int i = 0 ; i < nums.size(); i++) { moves += nums[i]; m = min(m, nums[i]); } return moves - m * nums.size(); } };
[455] 分发饼干 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
解题思路：贪心算法。先对两个数组进行预排序，然后从左到右扫描，对于未分配饼干的需求量最小的孩子分配一个最小最适合的饼干
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution { public : int findContentChildren (vector <int > &g, vector <int > &s) { sort(g.begin(), g.end()); sort(s.begin(), s.end()); int count = 0 ; int j = 0 ; for (int i = 0 ; i < g.size(); i++) { while (j < s.size() && s[j] < g[i]) { j++; } if (j < s.size()) count++; j++; } return count; } };
[459] 重复的子字符串 给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public : bool repeatedSubstringPattern (string s) { return (s + s).find(s, 1 ) != s.size(); } };
[461] 汉明距离 两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public : int hammingDistance (int x, int y) { int count = 0 ; int z = x ^ y; while (z != 0 ) { if (z & 1 ) { count++; } z = z >> 1 ; } return count; } };
[463] 岛屿的周长 给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地 0 表示水域。
网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public : int islandPerimeter (vector <vector <int >> &grid) { int res = 0 ; for (int i = 0 ; i < grid.size(); i++) { for (int j = 0 ; j < grid[i].size(); j++) { if (grid[i][j]) { if (i == 0 || grid[i - 1 ][j] == 0 ) res++; if (j == 0 || grid[i][j - 1 ] == 0 ) res++; } } } return res * 2 ; } };
