难度中等607
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意： 输出结果可能非常大，所以你需要返回一个字符串而不是整数。
示例 1：
1 2 输入：nums = [10,2] 输出："210"
示例 2：
1 2 输入：nums = [3,30,34,5,9] 输出："9534330"
示例 3：
示例 4：
主要是对sort的使用，两个数进行比较大小的逻辑改为两个数进行组合再比较大小的逻辑。
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 class Solution {public : static bool cmp (const int & lhs, const int & rhs) { long weightl = 10 , weightr = 10 ; while (weightl <= rhs) { weightl *= 10 ; } while (weightr <= lhs) { weightr *= 10 ; } return lhs * weightl + rhs > rhs * weightr + lhs; } string largestNumber (vector <int >& nums) sort(nums.begin(), nums.end(), cmp); if (nums[0 ] == 0 ) return "0" ; string res; for (auto & num : nums) { res += to_string(num); } return res; } };
除自身以外数组的乘积 给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
进阶：
考虑前缀和后缀乘积的情况，先算前缀保存，然后和后缀乘积相乘得到结果。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution {public : vector <int > productExceptSelf(vector <int >& nums) { int left = 1 ; int n = nums.size(); vector <int > res = vector <int >(n, 0 ); if (n <= 1 ) return nums; for (int i = 0 ; i < n; ++i) { res[i] = left; left *= nums[i]; } int right = 1 ; for (int i = n - 1 ; i >= 0 ; --i) { res[i] *= right; right *= nums[i]; } return res; } };
四数相加 II 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。
例如:
输入:
输出:
解释:
(0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
(1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
复习两数相加和三数相加
用hash存储前两个组合的结果和对应有多少种组合，然后遍历后面两个数组。
O(n2)
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 class Solution {public : int fourSumCount (vector <int >& nums1, vector <int >& nums2, vector <int >& nums3, vector <int >& nums4) map <int , int > res2cnt; int len = nums1.size(); for (int i = 0 ; i < len; ++i) { for (int j = 0 ; j < len; ++j) { ++res2cnt[nums1[i] + nums2[j]]; } } int res = 0 ; for (int i = 0 ; i < len; ++i) { for (int j = 0 ; j < len; ++j) { int tmp = 0 - nums3[i] - nums4[j]; if (res2cnt.count(tmp)) { res += res2cnt[tmp]; } } } return res; } };
生命游戏 根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
示例 1：
输入：board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
输入：board = [[1,1],[1,0]]
提示：
m == board.length
进阶：
你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
难点主要在于原地算法，考虑这种二维数组的原地算法多用置换的思想，体现到这一题目就是用2表示将死去的活细胞，用3表示将复活的死细胞，则可以实现原地算法，第一遍用2，和3记录，第二遍用board[i][j] %= 2得到最终结果。
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 64 65 66 67 68 69 70 class Solution {public : int arroundCnt (const vector <vector <int >> & board, int i, int j) { int cnt = 0 ; int m = board.size(); int n = board[0 ].size(); int left = j - 1 >= 0 ? j - 1 : 0 ; int right = j + 1 < n ? j + 1 : j; int up = i - 1 >= 0 ? i - 1 : 0 ; int down = i + 1 < m ? i + 1 : i; for (int k = left; k <= right; ++k) { for (int l = up; l <= down; ++l) { if (l == i && k == j) { continue ; } else { if (board[l][k] == 2 || board[l][k] == 1 ) { ++cnt; } } } } return cnt; } void gameOfLife (vector <vector <int >>& board) int m = board.size(); int n = board[0 ].size(); for (int i = 0 ; i < m; ++i) { for (int j = 0 ; j < n; ++j) { int cnt = arroundCnt(board, i, j); if (board[i][j] == 0 ) { if (cnt == 3 ) { board[i][j] = 3 ; } } else if (board[i][j] == 1 ) { if (cnt < 2 || cnt > 3 ) { board[i][j] = 2 ; } } } } for (int i = 0 ; i < m; ++i) { for (int j = 0 ; j < n; ++j) { board[i][j] %= 2 ; } } } };
