TopK
诸如 找出第K大/小、找出最小/大的K个数问题
- 方法效率排行
快排 > 堆 > 排序
- 方法简单排行
排序 > 堆 > 快排
快速幂
50. Pow(x, n)
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104
// cycclass Solution {public double myPow(double x, int n) {return n < 0 ? 1 / dfs(x, -n) : dfs(x, n);}double dfs(double x, int n) {if (n == 0) {return 1;}return (n % 2 == 0 ? 1 : x) * dfs(x * x, n / 2);}}
DFS/递归
372. 超级次方
你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。
示例 1：
输入：a = 2, b = [3] 输出：8
示例 2：
输入：a = 2, b = [1,0] 输出：1024
示例 3：
输入：a = 1, b = [4,3,3,8,5,2] 输出：1
示例 4：
输入：a = 2147483647, b = [2,0,0] 输出：1198
提示：
- 1 <= a <= 231 - 1
- 1 <= b.length <= 2000
- 0 <= b[i] <= 9
- b 不含前导 0
// cycclass Solution {final int MOD = 1337;public int superPow(int a, int[] b) {return dfs(a, b, b.length - 1);}int dfs(int a, int[] b, int index) {if (index == -1) {return 1;}return calRemain(dfs(a, b, index - 1), 10) * calRemain(a, b[index]) % MOD;}int calRemain(int base, int power) {long temp = base;while (power > 1) {temp = temp % MOD * base;power--;}return (int) (temp % 1337);}}
滑动窗口 / 双指针
☆☆☆ 689. 三个无重叠子数组的最大和
给你一个整数数组 nums 和一个整数 k ，找出三个长度为 k 、互不重叠、且 3 * k 项的和最大的子数组，并返回这三个子数组。
以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置（下标从 0 开始）。如果有多个结果，返回字典序最小的一个。
示例 1：
输入：nums = [1,2,1,2,6,7,5,1], k = 2
输出：[0,3,5]
解释：子数组 [1, 2], [2, 6], [7, 5] 对应的起始下标为 [0, 3, 5]。
也可以取 [2, 1], 但是结果 [1, 3, 5] 在字典序上更大。
示例 2：
输入：nums = [1,2,1,2,1,2,1,2,1], k = 2
输出：[0,2,4]
提示：
1 <= nums.length <= 2 * 104
1 <= nums[i] < 216
1 <= k <= floor(nums.length / 3)
通过次数18,909提交次数33,620
class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int[] ans = new int[3];
int sum1 = 0, maxSum1 = 0, maxSum1Idx = 0;
int sum2 = 0, maxSum12 = 0, maxSum12Idx1 = 0, maxSum12Idx2 = 0;
int sum3 = 0, maxTotal = 0;
for (int i = k * 2; i < nums.length; ++i) {
sum1 += nums[i - k * 2];
sum2 += nums[i - k];
sum3 += nums[i];
if (i >= k * 3 - 1) {
if (sum1 > maxSum1) {
maxSum1 = sum1;
maxSum1Idx = i - k * 3 + 1;
}
if (maxSum1 + sum2 > maxSum12) {
maxSum12 = maxSum1 + sum2;
maxSum12Idx1 = maxSum1Idx;
maxSum12Idx2 = i - k * 2 + 1;
}
if (maxSum12 + sum3 > maxTotal) {
maxTotal = maxSum12 + sum3;
ans[0] = maxSum12Idx1;
ans[1] = maxSum12Idx2;
ans[2] = i - k + 1;
}
sum1 -= nums[i - k * 3 + 1];
sum2 -= nums[i - k * 2 + 1];
sum3 -= nums[i - k + 1];
}
}
return ans;
}
}
3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。
示例 4:
输入: s = “”
输出: 0
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
// cyc
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>(); // 记录字符和其索引
int maxLen = 0;
int start = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.containsKey(c)) {
maxLen = Math.max(maxLen, i - start);
int newStart = map.get(c) + 1;
for (int j = start; j < newStart; j++){
map.remove(s.charAt(j));
}
start = newStart;
}
map.put(c, i);
}
return Math.max(maxLen, s.length() - start);
}
}
567. 字符串的排列
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
示例 1：
输入：s1 = “ab” s2 = “eidbaooo”
输出：true
解释：s2 包含 s1 的排列之一 (“ba”).
示例 2：
输入：s1= “ab” s2 = “eidboaoo”
输出：false
提示：
1 <= s1.length, s2.length <= 104
s1 和 s2 仅包含小写字母
// cyc
class Solution {
public boolean checkInclusion(String s1, String s2) {
int len1 = s1.length();
int len2 = s2.length();
if (len1 > len2) {
return false;
}
int[] s1Count = new int[26];
int[] s2Count = new int[26];
int s1Sum = 0;
int s2Sum = 0;
for (char c : s1.toCharArray()) {
s1Count[c - 'a']++;
s1Sum++;
}
// 左指针
int left = -1;
// right为右指针
for (int right = 0; right < len2; right++) {
char c = s2.charAt(right);
int index = c - 'a';
if (s1Count[index] > s2Count[index]) {
if (s2Sum == 0) {
left = right;
}
s2Count[index]++;
s2Sum++;
if (s2Sum == s1Sum) {
return true;
}
// 如果s1本身不包含c
} else if (s1Count[index] == 0) {
if (s2Sum > 0) {
s2Sum = 0;
Arrays.fill(s2Count, 0);
}
// 字符c已经饱和，要剔除第一个c之前的所有字符
} else {
while (s2.charAt(left) != c) {
s2Count[s2.charAt(left++) - 'a']--;
s2Sum--;
}
left++;
}
}
return false;
}
}
713. 乘积小于K的子数组
给定一个正整数数组 nums和整数 k 。
请找出该数组内乘积小于 k 的连续的子数组的个数。
示例 1:
输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。
示例 2:
输入: nums = [1,2,3], k = 0
输出: 0
提示:
1 <= nums.length <= 3 * 104
1 <= nums[i] <= 1000
0 <= k <= 106
- right从0遍历到len - 1，每次遍历结束时，结果增加right - left + 1
right-left+1的切入点是思维要放在区间的右边往左边延伸，例如区间[1, 2, 3, 4]满足要求，固定住right(4)的点，可选区间右[4]、[4, 3]、[4, 3, 2]、[4, 3, 2, 1]即为数组的长度，也就是right-left+1。而right是递增的，此时[1, 2, 3]的区间已经处理完（[3]、[3, 2]、[3、2、1]）。如果从left为切入点，就会有[1, 2, 3, 4]和[1, 2, 3]都有[1]，不就是重复了的错乱思维。
// cyc class Solution { public int numSubarrayProductLessThanK(int[] nums, int k) { if (k <= 1) { return 0; } int len = nums.length; int result = 0; int left = 0; // 乘积 int product = 1; for (int right = 0; right < len; right++) { product *= nums[right]; // 当乘积大于k时，不断移动左指针 while (product >= k) { product /= nums[left]; left++; } result += right - left + 1; } return result; } }
序列DP
689. 三个无重叠子数组的最大和
同滑动窗口689
TODO
字符串匹配
686.重复叠加字符串匹配
给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。
注意：字符串 “abc” 重复叠加 0 次是 “”，重复叠加 1 次是 “abc”，重复叠加 2 次是 “abcabc”。
示例 1：
输入：a = “abcd”, b = “cdabcdab”
输出：3
解释：a 重复叠加三遍后为 “abcdabcdabcd”, 此时 b 是其子串。
示例 2：
输入：a = “a”, b = “aa”
输出：2
示例 3：
输入：a = “a”, b = “a”
输出：1
示例 4：
输入：a = “abc”, b = “wxyz”
输出：-1
提示：
1 <= a.length <= 104
1 <= b.length <= 104
a 和 b 由小写英文字母组成
可以想到，a重复的次数小于b.length() / a.length() + 2，那么就有极速版的解答
// cyc
class Solution {
public int repeatedStringMatch(String a, String b) {
int lenA = a.length();
int lenB = b.length();
int count = lenB / lenA;
if (count * lenA == lenB && a.repeat(count).contains(b)) {
return count;
}
if (a.repeat(count + 1).contains(b)) {
return count + 1;
}
if (a.repeat(count + 2).contains(b)) {
return count + 2;
}
return -1;
}
}
速度快的是KMP算法，但是不想看暂时
双指针
1995. 统计特殊四元组
给你一个 下标从 0 开始 的整数数组 nums ，返回满足下述条件的 不同 四元组 (a, b, c, d) 的 数目 ：
nums[a] + nums[b] + nums[c] == nums[d] ，且
a < b < c < d
示例 1：
输入：nums = [1,2,3,6]
输出：1
解释：满足要求的唯一一个四元组是 (0, 1, 2, 3) 因为 1 + 2 + 3 == 6 。
示例 2：
输入：nums = [3,3,6,4,5]
输出：0
解释：[3,3,6,4,5] 中不存在满足要求的四元组。
示例 3：
输入：nums = [1,1,1,3,5]
输出：4
解释：满足要求的 4 个四元组如下：
- (0, 1, 2, 3): 1 + 1 + 1 == 3
- (0, 1, 3, 4): 1 + 1 + 3 == 5
- (0, 2, 3, 4): 1 + 1 + 3 == 5
- (1, 2, 3, 4): 1 + 1 + 3 == 5
提示：
4 <= nums.length <= 50
1 <= nums[i] <= 100
方法一：暴力
// cyc
class Solution {
public int countQuadruplets(int[] nums) {
int len = nums.length;
int result = 0;
for (int i = 0; i < len - 3; i++) {
for (int j = i + 1; j < len - 2; j++) {
for (int k = j + 1; k < len - 1; k++) {
for (int p = k + 1; p < len; p++) {
if (nums[i] + nums[j] + nums[k] == nums[p]) {
result++;
}
}
}
}
}
return result;
}
}
- 时间复杂度O(n^4)
class Solution {
public int countQuadruplets(int[] nums) {
int n = nums.length;
int ans = 0;
Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
for (int c = n - 2; c >= 2; --c) {
cnt.put(nums[c + 1], cnt.getOrDefault(nums[c + 1], 0) + 1);
for (int a = 0; a < c; ++a) {
for (int b = a + 1; b < c; ++b) {
ans += cnt.getOrDefault(nums[a] + nums[b] + nums[c], 0);
}
}
}
return ans;
}
}
class Solution {
public int countQuadruplets(int[] nums) {
int n = nums.length;
int ans = 0;
Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
for (int b = n - 3; b >= 1; --b) {
for (int d = b + 2; d < n; ++d) {
cnt.put(nums[d] - nums[b + 1], cnt.getOrDefault(nums[d] - nums[b + 1], 0) + 1);
}
for (int a = 0; a < b; ++a) {
ans += cnt.getOrDefault(nums[a] + nums[b], 0);
}
}
return ans;
}
}
贪心
55. 跳跃游戏
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
提示：
1 <= nums.length <= 3 * 104
0 <= nums[i] <= 105
刚开始用的dfs笨方法，用visited数组减少搜索dfs次数， 98ms，超过13%
// cyc class Solution { boolean[] visited; int len; public boolean canJump(int[] nums) { len = nums.length; visited = new boolean[len]; return dfs(nums, 0); } boolean dfs(int[] nums, int index) { if (index == len - 1) { return true; } int able = Math.min(index + nums[index], len - 1); for (int i = able; i >= index + 1; i--) { if (!visited[i] && dfs(nums, i)) { return true; } } visited[index] = true; return false; } }贪心，2ms，96%
// cyc
class Solution {
public boolean canJump(int[] nums) {
int len = nums.length;
int i = 0;
// 最远能到达的距离
int maxAble = 0;
while (i <= maxAble) {
maxAble = Math.max(maxAble, i + nums[i]);
if (maxAble >= len - 1) {
return true;
}
i++;
}
return false;
}
}
45. 跳跃游戏 II
给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
提示:
1 <= nums.length <= 104
0 <= nums[i] <= 1000
先用动归写了下，2ms，超过47%
// cyc class Solution { public int jump(int[] nums) { if (nums.length == 1) { return 0; } int len = nums.length; int[] dp = new int[len]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; int nowBest = 0; for (int i = 0; i < len; i++) { int able = i + nums[i]; if (able >= len - 1) { return dp[i] + 1; } if (able > nowBest) { for (int j = nowBest + 1; j <= able; j++) { dp[j] = dp[i] + 1; } nowBest = able; } } return dp[len - 1]; } }然后是贪心，1ms 99%
// cyc
class Solution {
public int jump(int[] nums) {
if (nums.length == 1) {
return 0;
}
// 当前能到达的地方
int able = nums[0];
// 当前步数
int nowStep = 1;
int index = 1;
while (index < nums.length - 1) {
// 如果现在就能到，返回当前步数 + 1
if (able >= nums.length - 1) {
return nowStep + 1;
}
// 当前到不了，向前进一步，并求出进一步后能到达的地方
nowStep++;
int tempAble = able;
while (index <= able) {
tempAble = Math.max(tempAble, index + nums[index++]);
}
able = tempAble;
}
return nowStep + 1;
}
}
旋转有序数组
剑指 Offer 11. 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为1。
示例 1：
输入：[3,4,5,1,2]
输出：1
示例 2：
输入：[2,2,2,0,1]
输出：0
刚开始写时，左侧最小值和右侧最大值固定在两端点，当midVal等于左右最值时，midVal可能在左侧有序也可能在右侧有序
- 此时只能通过遍历的方式找到midVal在左侧还是在右侧，最坏的时间复杂度可能到O(n)
不能采用r—或l++的方式，反例[3, 1, 3, 3]、[3, 3, 1, 3]
// cyc class Solution { public int minArray(int[] numbers) { int len = numbers.length; if (len == 1) { return numbers[0]; } int leftMin = numbers[0]; int rightMax = numbers[len - 1]; if (rightMax > leftMin) { return leftMin; } int l = 0; int r = len - 1; while (l < r) { int mid = l + (int) Math.ceil((r - l) / 2.0); int val = numbers[mid]; if (numbers[mid - 1] > val) { return val; } if (val > rightMax) { l = mid + 1; } else if (val == rightMax && val == leftMin) { /*当midVal可能在左侧也可能在右侧时，使用遍历的方式解决，略麻烦*/ // 此时可能在左侧也可能在右侧 int temp = mid; // true 在左侧, false在右侧 boolean flag = true; while (temp >= 0) { if (numbers[temp] > val || numbers[temp] < val) { flag = false; break; } temp--; } if (flag) { l = mid + 1; } else { r = mid - 1; } } else { r = mid - 1; } } return numbers[r]; } }
- 上述方法与我第一次写的方法最大的不同是，左侧最小值和右侧最大值不再固定，因为目标值是[最小值]，所以目标值左右总是旋转后的有序数组，因此左右侧最值是可以随着二分搜索的left和right指针移动的
当左右最值就是left和right指针所指的值时，当midVal等于左右最值时，将左轴或右轴移动一下就可以了
// cyc class Solution { public int minArray(int[] numbers) { int len = numbers.length; if (len == 1) { return numbers[0]; } int l = 0; int r = len - 1; int leftMin = numbers[l]; int rightMax = numbers[r]; // 当numbers整体有序时，直接返回最小值 if (rightMax > leftMin) { return leftMin; } while (l < r) { int mid = l + (r - l) / 2; int val = numbers[mid]; if (val > rightMax) { l = mid + 1; } else if (val == rightMax && val == leftMin) { // l++也可以 r--; } else { r = mid; } // 更新最值 leftMin = numbers[l]; rightMax = numbers[r]; } return numbers[l]; } }
中序遍历
剑指 Offer 36. 二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
为了让您更好地理解问题，以下面的二叉搜索树为例：
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
自写解
class Solution { Node minNode; Node maxNode; public Node treeToDoublyList(Node root) { if (root == null) { return null; } minNode = root; maxNode = root; traverse(root, true, null, null); minNode.left = maxNode; maxNode.right = minNode; return minNode; } void traverse(Node node, boolean leftChild, Node leftFather, Node rightFather) { if (node != null) { Node tempRight = node.right; traverse(node.left, true, node, rightFather); traverse(tempRight, false, leftFather, node); if (leftChild) { if (node.right == null) { node.right = leftFather; } if (node.left == null) { if (rightFather != null && rightFather.val < node.val) { node.left = rightFather; rightFather.right = node; } else { minNode = node.val < minNode.val ? node : minNode; } } } else { if (node.left == null) { node.left = rightFather; } if (node.right == null) { if (leftFather != null && leftFather.val > node.val) { node.right = leftFather; leftFather.left = node; } else { maxNode = node.val > maxNode.val ? node : maxNode; } } } } } }
class Solution {
Node pre, head;
public Node treeToDoublyList(Node root) {
if(root == null) return null;
dfs(root);
head.left = pre;
pre.right = head;
return head;
}
void dfs(Node cur) {
if(cur == null) return;
dfs(cur.left);
if(pre != null) pre.right = cur;
else head = cur;
cur.left = pre;
pre = cur;
dfs(cur.right);
}
}
排序
剑指 Offer 45. 把数组排成最小的数
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: “102”
示例 2:
输入: [3,30,34,5,9]
输出: “3033459”
提示:
0 < nums.length <= 100
说明:
输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
// cyc
class Solution {
public String minNumber(int[] nums) {
List<String> list = Arrays.stream(nums).mapToObj(String::valueOf).collect(Collectors.toList());
list.sort((o1, o2) -> (o1 + o2).compareTo(o2 + o1));
StringBuilder sb = new StringBuilder();
for (String num : list) {
sb.append(num);
}
return sb.toString();
}
}
堆
剑指 Offer 41. 数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例 1：
输入：
[“MedianFinder”,”addNum”,”addNum”,”findMedian”,”addNum”,”findMedian”]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
示例 2：
输入：
[“MedianFinder”,”addNum”,”findMedian”,”addNum”,”findMedian”]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]
限制：
最多会对 addNum、findMedian 进行 50000 次调用。
使用一个大根堆一个小根堆即可
// cyc class MedianFinder { private PriorityQueue<Integer> smallHeap; private PriorityQueue<Integer> bigHeap; private int total; public MedianFinder() { total = 0; smallHeap = new PriorityQueue<>(); bigHeap = new PriorityQueue<>((o1, o2) -> o2 - o1); } public void addNum(int num) { if (bigHeap.isEmpty()) { bigHeap.add(num); } else { int big = bigHeap.peek(); if (num < big) { if (bigHeap.size() > smallHeap.size()) { smallHeap.add(bigHeap.poll()); } bigHeap.add(num); } else { smallHeap.add(num); if (bigHeap.size() < smallHeap.size()) { bigHeap.add(smallHeap.poll()); } } } total++; } public double findMedian() { if (total % 2 == 0) { return (bigHeap.peek() + smallHeap.peek()) / 2.0; } else { return bigHeap.peek(); } } }
动态规划
918. 环形子数组的最大和
给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], …, nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。
示例 1：
输入：nums = [1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3
示例 2：
输入：nums = [5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
示例 3：
输入：nums = [3,-2,2,-3]
输出：3
解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
提示：
n == nums.length
1 <= n <= 3 104
-3 104 <= nums[i] <= 3 * 104
// cyc
class Solution {
public int maxSubarraySumCircular(int[] nums) {
int sum = nums[0];
int pre = nums[0];
int min = nums[0];
for (int i = 1; i < nums.length; i++) {
sum += nums[i];
pre = Math.min(nums[i], pre + nums[i]);
min = Math.min(min, pre);
}
pre = nums[0];
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
pre = Math.max(nums[i], pre + nums[i]);
max = Math.max(max, pre);
}
return max < 0 ? max : Math.max(max, sum - min);
}
}
洗牌算法
共有 n 个不同的数，根据每个位置能够选择什么数，共有 n! 种组合。
题目要求每次调用 shuffle 时等概率返回某个方案，或者说每个元素都够等概率出现在每个位置中。
我们可以使用 Knuth 洗牌算法，在 O(n) 复杂度内等概率返回某个方案。
具体的，我们从前往后尝试填充 [0, n−1] 该填入什么数时，通过随机当前下标与（剩余的）哪个下标进行值交换来实现。
对于下标 x 而言，我们从 [x,n−1] 中随机出一个位置与 xx 进行值交换，当所有位置都进行这样的处理后，我们便得到了一个公平的洗牌方案。
对于下标为 0 位置，从 [0, n−1] 随机一个位置进行交换，共有 n 种选择；下标为 1 的位置，从 [1, n - 1] 随机一个位置进行交换，共有 n - 1 种选择 …
代码：
class Solution {
int[] nums;
int n;
Random random = new Random();
public Solution(int[] _nums) {
nums = _nums;
n = nums.length;
}
public int[] reset() {
return nums;
}
public int[] shuffle() {
int[] ans = nums.clone();
for (int i = 0; i < n; i++) {
swap(ans, i, i + random.nextInt(n - i));
}
return ans;
}
void swap(int[] arr, int i, int j) {
int c = arr[i];
arr[i] = arr[j];
arr[j] = c;
}
}
时间复杂度：O(n)O(n)
空间复杂度：O(n)O(n)
若有收获，就点个赞吧
0 人点赞
