给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后，返回修改后的链表的头节点。
示例 1：
输入： nums = [1,2,3], head = [1,2,3,4,5]
输出： [4,5]
解释：
移除数值为 1, 2 和 3 的节点。
示例 2：
输入： nums = [1], head = [1,2,1,2,1,2]
输出： [2,2,2]
解释：
移除数值为 1 的节点。
示例 3：
输入： nums = [5], head = [1,2,3,4]
输出： [1,2,3,4]
解释：
链表中不存在值为 5 的节点。
提示：
登录
1 <= nums.length <= 1051 <= nums[i] <= 105nums 中的所有元素都是唯一的。[1, 105] 的范围内。1 <= Node.val <= 105nums 中出现过。如何在遍历链表的同时，删除链表节点？请看【基础算法精讲 08】。
对于本题，由于直接判断节点值是否在 $\textit{nums}$ 中，需要遍历 $\textit{nums}$，时间复杂度为 $\mathcal{O}(n)$。把 $\textit{nums}$ 中的元素保存一个哈希集合中，然后判断节点值是否在哈希集合中，这样可以做到 $\mathcal{O}(1)$。
具体做法：
注：$\textit{dummy}$ 和 $\textit{cur}$ 是同一个节点的引用，修改 $\textit{cur}.\textit{next}$ 也会修改 $\textit{dummy}.\textit{next}$。
本题视频讲解，欢迎点赞关注~
###py
class Solution:
def modifiedList(self, nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:
st = set(nums)
cur = dummy = ListNode(next=head)
while cur.next:
nxt = cur.next
if nxt.val in st:
cur.next = nxt.next # 从链表中删除 nxt 节点
else:
cur = nxt # 不删除 nxt，继续向后遍历链表
return dummy.next
###java
class Solution {
public ListNode modifiedList(int[] nums, ListNode head) {
Set<Integer> set = new HashSet<>(nums.length, 1); // 预分配空间
for (int x : nums) {
set.add(x);
}
ListNode dummy = new ListNode(0, head);
ListNode cur = dummy;
while (cur.next != null) {
ListNode nxt = cur.next;
if (set.contains(nxt.val)) {
cur.next = nxt.next; // 从链表中删除 nxt 节点
} else {
cur = nxt; // 不删除 nxt，继续向后遍历链表
}
}
return dummy.next;
}
}
###cpp
class Solution {
public:
ListNode* modifiedList(vector<int>& nums, ListNode* head) {
unordered_set<int> st(nums.begin(), nums.end());
ListNode dummy(0, head);
ListNode* cur = &dummy;
while (cur->next) {
ListNode* nxt = cur->next;
if (st.contains(nxt->val)) {
cur->next = nxt->next; // 从链表中删除 nxt 节点
} else {
cur = nxt; // 不删除 nxt，继续向后遍历链表
}
}
return dummy.next;
}
};
###c
#define MAX(a, b) ((b) > (a) ? (b) : (a))
struct ListNode* modifiedList(int* nums, int numsSize, struct ListNode* head) {
int mx = 0;
for (int i = 0; i < numsSize; i++) {
mx = MAX(mx, nums[i]);
}
bool* has = calloc(mx + 1, sizeof(bool));
for (int i = 0; i < numsSize; i++) {
has[nums[i]] = true;
}
struct ListNode dummy = {0, head};
struct ListNode* cur = &dummy;
while (cur->next) {
struct ListNode* nxt = cur->next;
if (nxt->val <= mx && has[nxt->val]) {
cur->next = nxt->next; // 从链表中删除 nxt 节点
free(nxt);
} else {
cur = nxt; // 不删除 nxt，继续向后遍历链表
}
}
free(has);
return dummy.next;
}
###go
func modifiedList(nums []int, head *ListNode) *ListNode {
has := make(map[int]bool, len(nums)) // 预分配空间
for _, x := range nums {
has[x] = true
}
dummy := &ListNode{Next: head}
cur := dummy
for cur.Next != nil {
nxt := cur.Next
if has[nxt.Val] {
cur.Next = nxt.Next // 从链表中删除 nxt 节点
} else {
cur = nxt // 不删除 nxt，继续向后遍历链表
}
}
return dummy.Next
}
###js
var modifiedList = function(nums, head) {
const set = new Set(nums);
const dummy = new ListNode(0, head);
let cur = dummy;
while (cur.next) {
const nxt = cur.next;
if (set.has(nxt.val)) {
cur.next = nxt.next; // 从链表中删除 nxt 节点
} else {
cur = nxt; // 不删除 nxt，继续向后遍历链表
}
}
return dummy.next;
};
###rust
use std::collections::HashSet;
impl Solution {
pub fn modified_list(nums: Vec<i32>, head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let set = nums.into_iter().collect::<HashSet<_>>();
let mut dummy = Box::new(ListNode { val: 0, next: head });
let mut cur = &mut dummy;
while let Some(ref mut nxt) = cur.next {
if set.contains(&nxt.val) {
cur.next = nxt.next.take(); // 从链表中删除 nxt 节点
} else {
cur = cur.next.as_mut()?; // 不删除 nxt，继续向后遍历链表
}
}
dummy.next
}
}
见下面链表题单的「§1.2 删除节点」。
欢迎关注 B站@灵茶山艾府
不会有人链表题真的去操作原链表吧？把链表里的数提取出来，按题意算出答案后新建一个链表即可。复杂度 $\mathcal{O}(n)$。
###cpp
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* modifiedList(vector<int>& nums, ListNode* head) {
// 按题意模拟
unordered_set<int> st;
for (int x : nums) st.insert(x);
vector<int> vec;
for (; head != nullptr; head = head->next) if (st.count(head->val) == 0) vec.push_back(head->val);
// 根据答案 vec 中新建一个链表
ListNode *dummy = new ListNode(), *now = dummy;
for (int x : vec) {
now->next = new ListNode(x);
now = now->next;
}
return dummy->next;
}
};
使用哈希表统计 $\textit{nums}$ 中出现了两次的数字，返回结果。
###C++
class Solution {
public:
vector<int> getSneakyNumbers(vector<int>& nums) {
vector<int> res;
unordered_map<int, int> count;
for (int x : nums) {
count[x]++;
if (count[x] == 2) {
res.push_back(x);
}
}
return res;
}
};
###Go
func getSneakyNumbers(nums []int) []int {
res := []int{}
count := make(map[int]int)
for _, x := range nums {
count[x]++
if count[x] == 2 {
res = append(res, x)
}
}
return res
}
###Python
class Solution:
def getSneakyNumbers(self, nums: List[int]) -> List[int]:
res = []
count = {}
for x in nums:
count[x] = count.get(x, 0) + 1
if count[x] == 2:
res.append(x)
return res
###Java
class Solution {
public int[] getSneakyNumbers(int[] nums) {
List<Integer> res = new ArrayList<>();
Map<Integer, Integer> count = new HashMap<>();
for (int x : nums) {
count.put(x, count.getOrDefault(x, 0) + 1);
if (count.get(x) == 2) {
res.add(x);
}
}
return res.stream().mapToInt(i -> i).toArray();
}
}
###TypeScript
function getSneakyNumbers(nums: number[]): number[] {
const res: number[] = [];
const count = new Map<number, number>();
for (const x of nums) {
count.set(x, (count.get(x) || 0) + 1);
if (count.get(x) === 2) {
res.push(x);
}
}
return res;
}
###JavaScript
var getSneakyNumbers = function(nums) {
const res = [];
const count = new Map();
for (const x of nums) {
count.set(x, (count.get(x) || 0) + 1);
if (count.get(x) === 2) {
res.push(x);
}
}
return res;
};
###C#
public class Solution {
public int[] GetSneakyNumbers(int[] nums) {
List<int> res = new List<int>();
Dictionary<int, int> count = new Dictionary<int, int>();
foreach (int x in nums) {
if (!count.ContainsKey(x)) count[x] = 0;
count[x]++;
if (count[x] == 2) {
res.Add(x);
}
}
return res.ToArray();
}
}
###C
int* getSneakyNumbers(int* nums, int numsSize, int* returnSize) {
int* res = (int*)malloc(2 * sizeof(int));
int* count = (int*)calloc(101, sizeof(int));
*returnSize = 0;
for (int i = 0; i < numsSize; i++) {
int x = nums[i];
count[x]++;
if (count[x] == 2) {
res[(*returnSize)++] = x;
}
}
free(count);
return res;
}
###Rust
impl Solution {
pub fn get_sneaky_numbers(nums: Vec<i32>) -> Vec<i32> {
let mut res = Vec::new();
let mut count = std::collections::HashMap::new();
for x in nums {
let c = count.entry(x).or_insert(0);
*c += 1;
if *c == 2 {
res.push(x);
}
}
res
}
}
复杂度分析
时间复杂度：$O(n)$。
空间复杂度：$O(n)$。
我们将 $\textit{nums}$ 的所有数字和 $0$ 到 $n - 1$ 的所有数字进行异或，那么计算结果为两个额外多出现一次的数字的异或值 $y$。那么两个数字最低不相同的位为 $\textit{lowBit} = y \land -y$，利用 $\textit{lowBit}$ 将 $\textit{nums}$ 的所有数字和 $0$ 到 $n - 1$ 的所有数字分成两部分，然后分别计算这两部分数字的异或值，即为结果。
###C++
class Solution {
public:
vector<int> getSneakyNumbers(vector<int>& nums) {
int n = (int)nums.size() - 2;
int y = 0;
for (int x : nums) {
y ^= x;
}
for (int i = 0; i < n; i++) {
y ^= i;
}
int lowBit = y & (-y);
int x1 = 0, x2 = 0;
for (int x : nums) {
if (x & lowBit) {
x1 ^= x;
} else {
x2 ^= x;
}
}
for (int i = 0; i < n; i++) {
if (i & lowBit) {
x1 ^= i;
} else {
x2 ^= i;
}
}
return {x1, x2};
}
};
###Go
func getSneakyNumbers(nums []int) []int {
n := len(nums) - 2
y := 0
for _, x := range nums {
y ^= x
}
for i := 0; i < n; i++ {
y ^= i
}
lowBit := y & -y
x1, x2 := 0, 0
for _, x := range nums {
if x&lowBit != 0 {
x1 ^= x
} else {
x2 ^= x
}
}
for i := 0; i < n; i++ {
if i&lowBit != 0 {
x1 ^= i
} else {
x2 ^= i
}
}
return []int{x1, x2}
}
###Python
class Solution:
def getSneakyNumbers(self, nums: List[int]) -> List[int]:
n = len(nums) - 2
y = 0
for x in nums:
y ^= x
for i in range(n):
y ^= i
lowBit = y & -y
x1 = x2 = 0
for x in nums:
if x & lowBit:
x1 ^= x
else:
x2 ^= x
for i in range(n):
if i & lowBit:
x1 ^= i
else:
x2 ^= i
return [x1, x2]
###Java
class Solution {
public int[] getSneakyNumbers(int[] nums) {
int n = nums.length - 2;
int y = 0;
for (int x : nums) {
y ^= x;
}
for (int i = 0; i < n; i++) {
y ^= i;
}
int lowBit = y & -y;
int x1 = 0, x2 = 0;
for (int x : nums) {
if ((x & lowBit) != 0) {
x1 ^= x;
} else {
x2 ^= x;
}
}
for (int i = 0; i < n; i++) {
if ((i & lowBit) != 0) {
x1 ^= i;
} else {
x2 ^= i;
}
}
return new int[]{x1, x2};
}
}
###TypeScript
function getSneakyNumbers(nums: number[]): number[] {
const n = nums.length - 2;
let y = 0;
for (const x of nums) {
y ^= x;
}
for (let i = 0; i < n; i++) {
y ^= i;
}
const lowBit = y & -y;
let x1 = 0, x2 = 0;
for (const x of nums) {
if (x & lowBit) {
x1 ^= x;
} else {
x2 ^= x;
}
}
for (let i = 0; i < n; i++) {
if (i & lowBit) {
x1 ^= i;
} else {
x2 ^= i;
}
}
return [x1, x2];
}
###JavaScript
function getSneakyNumbers(nums) {
const n = nums.length - 2;
let y = 0;
for (const x of nums) {
y ^= x;
}
for (let i = 0; i < n; i++) {
y ^= i;
}
const lowBit = y & -y;
let x1 = 0, x2 = 0;
for (const x of nums) {
if (x & lowBit) {
x1 ^= x;
} else {
x2 ^= x;
}
}
for (let i = 0; i < n; i++) {
if (i & lowBit) {
x1 ^= i;
} else {
x2 ^= i;
}
}
return [x1, x2];
}
###C#
public class Solution {
public int[] GetSneakyNumbers(int[] nums) {
int n = nums.Length - 2;
int y = 0;
foreach (int x in nums) {
y ^= x;
}
for (int i = 0; i < n; i++) {
y ^= i;
}
int lowBit = y & -y;
int x1 = 0, x2 = 0;
foreach (int x in nums) {
if ((x & lowBit) != 0) {
x1 ^= x;
} else {
x2 ^= x;
}
}
for (int i = 0; i < n; i++) {
if ((i & lowBit) != 0) {
x1 ^= i;
} else {
x2 ^= i;
}
}
return new int[] { x1, x2 };
}
}
###C
int* getSneakyNumbers(int* nums, int numsSize, int* returnSize) {
int n = numsSize - 2;
int y = 0;
for (int i = 0; i < numsSize; i++) {
y ^= nums[i];
}
for (int i = 0; i < n; i++) {
y ^= i;
}
int lowBit = y & -y;
int x1 = 0, x2 = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] & lowBit) {
x1 ^= nums[i];
} else {
x2 ^= nums[i];
}
}
for (int i = 0; i < n; i++) {
if (i & lowBit) {
x1 ^= i;
} else {
x2 ^= i;
}
}
int* res = (int*)malloc(2 * sizeof(int));
res[0] = x1;
res[1] = x2;
*returnSize = 2;
return res;
}
###Rust
impl Solution {
pub fn get_sneaky_numbers(nums: Vec<i32>) -> Vec<i32> {
let n = nums.len() as i32 - 2;
let mut y = 0;
for &x in &nums {
y ^= x;
}
for i in 0..n {
y ^= i;
}
let low_bit = y & -y;
let mut x1 = 0;
let mut x2 = 0;
for &x in &nums {
if x & low_bit != 0 {
x1 ^= x;
} else {
x2 ^= x;
}
}
for i in 0..n {
if i & low_bit != 0 {
x1 ^= i;
} else {
x2 ^= i;
}
}
vec![x1, x2]
}
}
复杂度分析
时间复杂度：$O(n)$。
空间复杂度：$O(1)$。
令两个额外多出现一次的数字为 $x_1$ 和 $x_2$。$\textit{nums}$ 的和与平方和分别为 $\textit{sum}$ 和 $\textit{squaredSum}$，从 $0$ 到 $n-1$ 的整数和与平方和分别为 $\frac{n(n-1)}{2}$ 和 $\frac{n(n-1)(2n-1)}{6}$。记 $\textit{sum}_2 = \textit{sum} - \frac{n(n-1)}{2}$ 和 $\textit{squaredSum}_2 = \textit{squaredSum} - \frac{n(n-1)(2n-1)}{6}$，那么有以下方程：
$$
\begin{cases}
x_1 + x_2 = \textit{sum}_2 \
x_1^2 + x_2^2 = \textit{squaredSum}_2
\end{cases}
$$
解得：
$$
\begin{cases}
x_1 = \frac{\textit{sum}_2 - \sqrt{2 \times \textit{squaredSum}_2 - \textit{sum}_2^2}}{2} \
x_2 = \frac{\textit{sum}_2 + \sqrt{2 \times \textit{squaredSum}_2 - \textit{sum}_2^2}}{2}
\end{cases}
$$
###C++
class Solution {
public:
vector<int> getSneakyNumbers(vector<int>& nums) {
int n = (int)nums.size() - 2;
int sum = 0, squaredSum = 0;
for (int x : nums) {
sum += x;
squaredSum += x * x;
}
int sum2 = sum - n * (n - 1) / 2;
int squaredSum2 = squaredSum - n * (n - 1) * (2 * n - 1) / 6;
int x1 = (sum2 - sqrt(2 * squaredSum2 - sum2 * sum2)) / 2;
int x2 = (sum2 + sqrt(2 * squaredSum2 - sum2 * sum2)) / 2;
return {x1, x2};
}
};
###Go
func getSneakyNumbers(nums []int) []int {
n := len(nums) - 2
sum, squaredSum := 0.0, 0.0
for _, x := range nums {
sum += float64(x)
squaredSum += float64(x * x)
}
sum2 := sum - float64(n * (n - 1) / 2)
squaredSum2 := squaredSum - float64(n * (n - 1) * (2 * n - 1) / 6)
x1 := (sum2 - math.Sqrt(2 * squaredSum2 - sum2 * sum2)) / 2
x2 := (sum2 + math.Sqrt(2 * squaredSum2 - sum2 * sum2)) / 2
return []int{int(x1), int(x2)}
}
###Python
class Solution:
def getSneakyNumbers(self, nums: List[int]) -> List[int]:
n = len(nums) - 2
sum_ = sum(nums)
squared_sum = sum(x*x for x in nums)
sum2 = sum_ - n*(n-1)//2
squared_sum2 = squared_sum - n*(n-1)*(2*n-1)//6
x1 = (sum2 - math.sqrt(2*squared_sum2 - sum2*sum2)) / 2
x2 = (sum2 + math.sqrt(2*squared_sum2 - sum2*sum2)) / 2
return [int(x1), int(x2)]
###Java
class Solution {
public int[] getSneakyNumbers(int[] nums) {
int n = nums.length - 2;
double sum = 0, squaredSum = 0;
for (int x : nums) {
sum += x;
squaredSum += x * x;
}
double sum2 = sum - n * (n - 1) / 2.0;
double squaredSum2 = squaredSum - n * (n - 1) * (2 * n - 1) / 6.0;
int x1 = (int)((sum2 - Math.sqrt(2 * squaredSum2 - sum2 * sum2)) / 2);
int x2 = (int)((sum2 + Math.sqrt(2 * squaredSum2 - sum2 * sum2)) / 2);
return new int[]{x1, x2};
}
}
###TypeScript
function getSneakyNumbers(nums: number[]): number[] {
const n = nums.length - 2;
let sum = 0, squaredSum = 0;
for (const x of nums) {
sum += x;
squaredSum += x * x;
}
const sum2 = sum - n * (n - 1) / 2;
const squaredSum2 = squaredSum - n * (n - 1) * (2 * n - 1) / 6;
const x1 = (sum2 - Math.sqrt(2 * squaredSum2 - sum2 * sum2)) / 2;
const x2 = (sum2 + Math.sqrt(2 * squaredSum2 - sum2 * sum2)) / 2;
return [Math.floor(x1), Math.floor(x2)];
}
###JavaScript
function getSneakyNumbers(nums) {
const n = nums.length - 2;
let sum = 0, squaredSum = 0;
for (const x of nums) {
sum += x;
squaredSum += x * x;
}
const sum2 = sum - n * (n - 1) / 2;
const squaredSum2 = squaredSum - n * (n - 1) * (2 * n - 1) / 6;
const x1 = (sum2 - Math.sqrt(2 * squaredSum2 - sum2 * sum2)) / 2;
const x2 = (sum2 + Math.sqrt(2 * squaredSum2 - sum2 * sum2)) / 2;
return [Math.floor(x1), Math.floor(x2)];
}
###C#
public class Solution {
public int[] GetSneakyNumbers(int[] nums) {
int n = nums.Length - 2;
double sum = 0, squaredSum = 0;
foreach (int x in nums) {
sum += x;
squaredSum += x * x;
}
double sum2 = sum - n * (n - 1) / 2.0;
double squaredSum2 = squaredSum - n * (n - 1) * (2 * n - 1) / 6.0;
int x1 = (int)((sum2 - Math.Sqrt(2 * squaredSum2 - sum2 * sum2)) / 2);
int x2 = (int)((sum2 + Math.Sqrt(2 * squaredSum2 - sum2 * sum2)) / 2);
return new int[]{x1, x2};
}
}
###C
int* getSneakyNumbers(int* nums, int numsSize, int* returnSize) {
int n = numsSize - 2;
double sum = 0, squaredSum = 0;
for (int i = 0; i < numsSize; i++) {
sum += nums[i];
squaredSum += nums[i] * nums[i];
}
double sum2 = sum - n * (n - 1) / 2.0;
double squaredSum2 = squaredSum - n * (n - 1) * (2 * n - 1) / 6.0;
int x1 = (int)((sum2 - sqrt(2 * squaredSum2 - sum2 * sum2)) / 2);
int x2 = (int)((sum2 + sqrt(2 * squaredSum2 - sum2 * sum2)) / 2);
int* res = (int*)malloc(2 * sizeof(int));
res[0] = x1;
res[1] = x2;
*returnSize = 2;
return res;
}
###Rust
impl Solution {
pub fn get_sneaky_numbers(nums: Vec<i32>) -> Vec<i32> {
let n = nums.len() as i32 - 2;
let sum: f64 = nums.iter().map(|&x| x as f64).sum();
let squared_sum: f64 = nums.iter().map(|&x| (x*x) as f64).sum();
let sum2 = sum - (n * (n - 1) / 2) as f64;
let squared_sum2 = squared_sum - (n * (n - 1) * (2 * n - 1) / 6) as f64;
let x1 = (sum2 - ((2.0 * squared_sum2 - sum2 * sum2).sqrt())) / 2.0;
let x2 = (sum2 + ((2.0 * squared_sum2 - sum2 * sum2).sqrt())) / 2.0;
vec![x1 as i32, x2 as i32]
}
}
复杂度分析
时间复杂度：$O(n)$。
空间复杂度：$O(1)$。
我们可以用一个数组 $\textit{cnt}$ 记录每个数字出现的次数。
遍历数组 $\textit{nums}$，当某个数字出现次数为 $2$ 时，将其加入答案数组中。
遍历结束后，返回答案数组即可。
###python
class Solution:
def getSneakyNumbers(self, nums: List[int]) -> List[int]:
cnt = Counter(nums)
return [x for x, v in cnt.items() if v == 2]
###java
class Solution {
public int[] getSneakyNumbers(int[] nums) {
int[] ans = new int[2];
int[] cnt = new int[100];
int k = 0;
for (int x : nums) {
if (++cnt[x] == 2) {
ans[k++] = x;
}
}
return ans;
}
}
###cpp
class Solution {
public:
vector<int> getSneakyNumbers(vector<int>& nums) {
vector<int> ans;
int cnt[100]{};
for (int x : nums) {
if (++cnt[x] == 2) {
ans.push_back(x);
}
}
return ans;
}
};
###go
func getSneakyNumbers(nums []int) (ans []int) {
cnt := [100]int{}
for _, x := range nums {
cnt[x]++
if cnt[x] == 2 {
ans = append(ans, x)
}
}
return
}
###ts
function getSneakyNumbers(nums: number[]): number[] {
const ans: number[] = [];
const cnt: number[] = Array(100).fill(0);
for (const x of nums) {
if (++cnt[x] > 1) {
ans.push(x);
}
}
return ans;
}
时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\textit{nums}$ 的长度。
设数组 $\textit{nums}$ 的长度为 $n + 2$，其中包含 $0 \sim n - 1$ 的整数，且有两个数字出现了两次。
我们可以通过异或运算来找出这两个数字。首先，我们对数组 $\textit{nums}$ 中的所有数字以及 $0 \sim n - 1$ 的整数进行异或运算，得到的结果为这两个重复数字的异或值，记为 $xx$。
接下来，我们可以通过 $xx$ 找到这两个数字的某些特征，进而将它们分开。具体步骤如下：
###python
class Solution:
def getSneakyNumbers(self, nums: List[int]) -> List[int]:
n = len(nums) - 2
xx = nums[n] ^ nums[n + 1]
for i in range(n):
xx ^= i ^ nums[i]
k = xx.bit_length() - 1
ans = [0, 0]
for x in nums:
ans[x >> k & 1] ^= x
for i in range(n):
ans[i >> k & 1] ^= i
return ans
###java
class Solution {
public int[] getSneakyNumbers(int[] nums) {
int n = nums.length - 2;
int xx = nums[n] ^ nums[n + 1];
for (int i = 0; i < n; ++i) {
xx ^= i ^ nums[i];
}
int k = Integer.numberOfTrailingZeros(xx);
int[] ans = new int[2];
for (int x : nums) {
ans[x >> k & 1] ^= x;
}
for (int i = 0; i < n; ++i) {
ans[i >> k & 1] ^= i;
}
return ans;
}
}
###cpp
class Solution {
public:
vector<int> getSneakyNumbers(vector<int>& nums) {
int n = nums.size() - 2;
int xx = nums[n] ^ nums[n + 1];
for (int i = 0; i < n; ++i) {
xx ^= i ^ nums[i];
}
int k = __builtin_ctz(xx);
vector<int> ans(2);
for (int x : nums) {
ans[(x >> k) & 1] ^= x;
}
for (int i = 0; i < n; ++i) {
ans[(i >> k) & 1] ^= i;
}
return ans;
}
};
###go
func getSneakyNumbers(nums []int) []int {
n := len(nums) - 2
xx := nums[n] ^ nums[n+1]
for i := 0; i < n; i++ {
xx ^= i ^ nums[i]
}
k := bits.TrailingZeros(uint(xx))
ans := make([]int, 2)
for _, x := range nums {
ans[(x>>k)&1] ^= x
}
for i := 0; i < n; i++ {
ans[(i>>k)&1] ^= i
}
return ans
}
###ts
function getSneakyNumbers(nums: number[]): number[] {
const n = nums.length - 2;
let xx = nums[n] ^ nums[n + 1];
for (let i = 0; i < n; ++i) {
xx ^= i ^ nums[i];
}
const k = Math.clz32(xx & -xx) ^ 31;
const ans = [0, 0];
for (const x of nums) {
ans[(x >> k) & 1] ^= x;
}
for (let i = 0; i < n; ++i) {
ans[(i >> k) & 1] ^= i;
}
return ans;
}
时间复杂度 $O(n)$，其中 $n$ 为数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$。
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈 😄~
数字小镇 Digitville 中，存在一个数字列表 nums，其中包含从 0 到 n - 1 的整数。每个数字本应 只出现一次，然而，有 两个 顽皮的数字额外多出现了一次，使得列表变得比正常情况下更长。
为了恢复 Digitville 的和平，作为小镇中的名侦探，请你找出这两个顽皮的数字。
返回一个长度为 2 的数组，包含这两个数字（顺序任意）。
示例 1：
输入： nums = [0,1,1,0]
输出： [0,1]
解释：
数字 0 和 1 分别在数组中出现了两次。
示例 2：
输入： nums = [0,3,2,1,3,2]
输出： [2,3]
解释:
数字 2 和 3 分别在数组中出现了两次。
示例 3：
输入： nums = [7,1,5,4,3,4,6,0,9,5,8,2]
输出： [4,5]
解释:
数字 4 和 5 分别在数组中出现了两次。
提示：
2 <= n <= 100nums.length == n + 20 <= nums[i] < nnums 中 恰好 包含两个重复的元素。最简单的思路是使用哈希集合存储数组 $\textit{nums}$ 中出现过的数字。遍历数组 $\textit{nums}$ 中的每个数字，如果该数字尚未在哈希集合中则将其加入哈希集合，如果该数字已经在哈希集合中则将其加入答案数组。遍历结束之后，即可得到两个重复出现的数字。
###Java
class Solution {
public int[] getSneakyNumbers(int[] nums) {
int[] duplicates = new int[2];
int index = 0;
Set<Integer> set = new HashSet<Integer>();
for (int num : nums) {
if (!set.add(num)) {
duplicates[index] = num;
index++;
}
}
return duplicates;
}
}
###C#
public class Solution {
public int[] GetSneakyNumbers(int[] nums) {
int[] duplicates = new int[2];
int index = 0;
ISet<int> set = new HashSet<int>();
foreach (int num in nums) {
if (!set.Add(num)) {
duplicates[index] = num;
index++;
}
}
return duplicates;
}
}
时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 中的不同整数个数。数组 $\textit{nums}$ 的长度是 $n + 2$，需要遍历数组一次。
空间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 中的不同整数个数。哈希表的空间是 $O(n)$。
用 $x$ 和 $y$ 表示两个重复出现的数字，$0 \le x, y < n$ 且 $x \ne y$。数组 $\textit{nums}$ 的长度是 $n + 2$，其中 $x$ 和 $y$ 各出现两次，其余每个数字各出现一次。如果在数组 $\textit{nums}$ 的 $n + 2$ 个元素以外再添加 $0$ 到 $n - 1$ 的每个数字各一次，则有 $2n + 2$ 个元素，其中 $x$ 和 $y$ 各出现三次，其余每个数字各出现两次。
根据按位异或运算的性质，如果一个数字被计算奇数次则该数字会对按位异或运算结果产生一次影响，如果一个数字被计算偶数次则该数字不会对按位异或运算结果产生影响，因此上述 $2n + 2$ 个元素的按位异或运算结果为 $\textit{xorVal} = x \oplus y$。由于 $x \ne y$，因此 $\textit{xorVal} \ne 0$。
得到 $\textit{xorVal}$ 之后，计算 $\textit{lowbit} = \textit{xorVal} ~&~ (-\textit{xorVal})$，则 $\textit{lowbit}$ 为 $\textit{xorVal}$ 的二进制表示的最低位的 $1$。为了区分 $x$ 和 $y$，可以规定 $\textit{lowbit}$ 在 $x$ 中的对应位是 $1$，$\textit{lowbit}$ 在 $y$ 中的对应位是 $0$。
得到 $\textit{lowbit}$ 之后，再次遍历上述 $2n + 2$ 个元素并计算 $x$ 和 $y$。对于每个整数 $\textit{num}$，执行如下操作。
如果 $\textit{num} ~&~ \textit{lowbit}$ 的结果不为 $0$，则将 $x$ 的值更新为 $x \oplus \textit{num}$。
如果 $\textit{num} ~&~ \textit{lowbit}$ 的结果为 $0$，则将 $y$ 的值更新为 $y \oplus \textit{num}$。
如果 $\textit{num}$ 是出现两次的数字，则会对 $x$ 或 $y$ 执行两次异或运算，不会改变 $x$ 和 $y$ 的值。如果 $\textit{num}$ 是出现三次的数字，则使用 $\textit{num}$ 更新 $x$ 或 $y$ 的值。遍历结束之后，即可得到 $x$ 和 $y$ 的值。
###Java
class Solution {
public int[] getSneakyNumbers(int[] nums) {
int[] duplicates = new int[2];
int xorValue = 0;
int n = nums.length - 2;
for (int num : nums) {
xorValue ^= num;
}
for (int i = 0; i < n; i++) {
xorValue ^= i;
}
int lowbit = xorValue & (-xorValue);
for (int num : nums) {
update(duplicates, num, lowbit);
}
for (int i = 0; i < n; i++) {
update(duplicates, i, lowbit);
}
return duplicates;
}
public void update(int[] duplicates, int num, int lowbit) {
if ((num & lowbit) != 0) {
duplicates[0] ^= num;
} else {
duplicates[1] ^= num;
}
}
}
###C#
public class Solution {
public int[] GetSneakyNumbers(int[] nums) {
int[] duplicates = new int[2];
int xorValue = 0;
int n = nums.Length - 2;
foreach (int num in nums) {
xorValue ^= num;
}
for (int i = 0; i < n; i++) {
xorValue ^= i;
}
int lowbit = xorValue & (-xorValue);
foreach (int num in nums) {
Update(duplicates, num, lowbit);
}
for (int i = 0; i < n; i++) {
Update(duplicates, i, lowbit);
}
return duplicates;
}
public void Update(int[] duplicates, int num, int lowbit) {
if ((num & lowbit) != 0) {
duplicates[0] ^= num;
} else {
duplicates[1] ^= num;
}
}
}
时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 中的不同整数个数。数组 $\textit{nums}$ 的长度是 $n + 2$，计算按位异或运算需要遍历 $4n + 4$ 个数字。
空间复杂度：$O(1)$。
用 $x$ 和 $y$ 表示两个重复出现的数字。将数组 $\textit{nums}$ 中的所有元素的和记为 $\textit{sum}$，所有元素的平方和记为 $\textit{squaredSum}$，由于从 $0$ 到 $n - 1$ 的所有整数的和等于 $\dfrac{n(n - 1)}{2}$，所有整数的平方和等于 $\dfrac{n(n - 1)(2n - 1)}{6}$，因此有 $x + y = \textit{remainSum} = \textit{sum} - \dfrac{n(n - 1)}{2}$，$x^2 + y^2 = \textit{remainSquaredSum} = \textit{squaredSum} - \dfrac{n(n - 1)(2n - 1)}{6}$。问题转换成计算如下二元二次方程组的解。
$$
\begin{cases}
x + y = \textit{remainSum} \\
x^2 + y^2 = \textit{remainSquaredSum}
\end{cases}
$$
由于 $x \ne y$ 且将 $x$ 和 $y$ 的值可以交换，因此可以规定 $x < y$，该二元二次方程组的解如下。
$$
\begin{cases}
x = \dfrac{\textit{remainSum} - \sqrt{2 \times \textit{remainSquaredSum} - \textit{remainSum}^2}}{2} \\
y = \dfrac{\textit{remainSum} + \sqrt{2 \times \textit{remainSquaredSum} - \textit{remainSum}^2}}{2}
\end{cases}
$$
###Java
class Solution {
public int[] getSneakyNumbers(int[] nums) {
int[] duplicates = new int[2];
int n = nums.length - 2;
int sum = 0, squaredSum = 0;
for (int num : nums) {
sum += num;
squaredSum += num * num;
}
int remainSum = sum - n * (n - 1) / 2;
int remainSquaredSum = squaredSum - n * (n - 1) * (2 * n - 1) / 6;
duplicates[0] = (int) ((remainSum - Math.sqrt(2 * remainSquaredSum - remainSum * remainSum)) / 2);
duplicates[1] = (int) ((remainSum + Math.sqrt(2 * remainSquaredSum - remainSum * remainSum)) / 2);
return duplicates;
}
}
###C#
public class Solution {
public int[] GetSneakyNumbers(int[] nums) {
int[] duplicates = new int[2];
int n = nums.Length - 2;
int sum = 0, squaredSum = 0;
foreach (int num in nums) {
sum += num;
squaredSum += num * num;
}
int remainSum = sum - n * (n - 1) / 2;
int remainSquaredSum = squaredSum - n * (n - 1) * (2 * n - 1) / 6;
duplicates[0] = (int) ((remainSum - Math.Sqrt(2 * remainSquaredSum - remainSum * remainSum)) / 2);
duplicates[1] = (int) ((remainSum + Math.Sqrt(2 * remainSquaredSum - remainSum * remainSum)) / 2);
return duplicates;
}
}
代码中使用了 $\texttt{Math.sqrt}$ 方法，该方法调用了本地方法 $\texttt{StrictMath.sqrt}$，因此其时间与空间复杂度取决于本地方法的实现，这里将该方法的时间复杂度和空间复杂度视为 $O(1)$。
时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{nums}$ 中的不同整数个数。数组 $\textit{nums}$ 的长度是 $n + 2$，需要遍历数组一次。
空间复杂度：$O(1)$。
Problem: 3289. 数字小镇中的捣蛋鬼
[TOC]
计数
执行用时分布41ms击败100.00%；消耗内存分布16.45MB击败100.00%
###Python3
class Solution:
def getSneakyNumbers(self, nums: List[int]) -> List[int]:
return [x for x, c in Counter(nums).items() if c == 2]
本题和 2965. 找出缺失和重复的数字 本质是一样的，见 我的题解，有位运算和数学两种做法。
需要两次遍历。一次遍历见下面的数学做法。
###py
class Solution:
def getSneakyNumbers(self, nums: List[int]) -> List[int]:
n = len(nums) - 2
xor_all = n ^ (n + 1) # n 和 n+1 多异或了
for i, x in enumerate(nums):
xor_all ^= i ^ x
shift = xor_all.bit_length() - 1
ans = [0, 0]
for i, x in enumerate(nums):
if i < n:
ans[i >> shift & 1] ^= i
ans[x >> shift & 1] ^= x
return ans
###java
class Solution {
public int[] getSneakyNumbers(int[] nums) {
int n = nums.length - 2;
int xorAll = n ^ (n + 1); // n 和 n+1 多异或了
for (int i = 0; i < nums.length; i++) {
xorAll ^= i ^ nums[i];
}
int shift = Integer.numberOfTrailingZeros(xorAll);
int[] ans = new int[2];
for (int i = 0; i < nums.length; i++) {
if (i < n) {
ans[i >> shift & 1] ^= i;
}
ans[nums[i] >> shift & 1] ^= nums[i];
}
return ans;
}
}
###cpp
class Solution {
public:
vector<int> getSneakyNumbers(vector<int>& nums) {
int n = nums.size() - 2;
int xor_all = n ^ (n + 1); // n 和 n+1 多异或了
for (int i = 0; i < nums.size(); i++) {
xor_all ^= i ^ nums[i];
}
int shift = __builtin_ctz(xor_all);
vector<int> ans(2);
for (int i = 0; i < nums.size(); i++) {
if (i < n) {
ans[i >> shift & 1] ^= i;
}
ans[nums[i] >> shift & 1] ^= nums[i];
}
return ans;
}
};
###go
func getSneakyNumbers(nums []int) []int {
n := len(nums) - 2
xorAll := n ^ (n + 1) // n 和 n+1 多异或了
for i, x := range nums {
xorAll ^= i ^ x
}
shift := bits.TrailingZeros(uint(xorAll))
ans := make([]int, 2)
for i, x := range nums {
if i < n {
ans[i>>shift&1] ^= i
}
ans[x>>shift&1] ^= x
}
return ans
}
设多出的两个数分别为 $x$ 和 $y$。
也就是说，$\textit{nums} = [0,1,2,\cdots,n-1,x,y]$。
设 $\textit{nums}$ 的元素和为 $s$，$\textit{nums}$ 的元素平方之和为 $s_2$，那么有
$$
\begin{aligned}
&x+y = s - (0 + 1 + 2 + \cdots + n-1) = a \
&x^2+y^2 = s_2 - (0^2 + 1^2 + 2^2 + \cdots + (n-1)^2) = b \
\end{aligned}
$$
解得
$$
\begin{cases}
x = \dfrac{a-\sqrt{2b-a^2}}{2} \
y = \dfrac{a+\sqrt{2b-a^2}}{2} \
\end{cases}
$$
也可以先算出 $x$，然后算出 $y=a-x$。
本题视频讲解，欢迎点赞关注~
###py
class Solution:
def getSneakyNumbers(self, nums: List[int]) -> List[int]:
n = len(nums) - 2
a = -n * (n - 1) // 2
b = -n * (n - 1) * (n * 2 - 1) // 6
for x in nums:
a += x
b += x * x
x = (a - isqrt(b * 2 - a * a)) // 2
return [x, a - x]
###java
class Solution {
public int[] getSneakyNumbers(int[] nums) {
int n = nums.length - 2;
int a = -n * (n - 1) / 2;
int b = -n * (n - 1) * (n * 2 - 1) / 6;
for (int x : nums) {
a += x;
b += x * x;
}
int x = (a - (int) Math.sqrt(b * 2 - a * a)) / 2;
return new int[]{x, a - x};
}
}
###cpp
class Solution {
public:
vector<int> getSneakyNumbers(vector<int>& nums) {
int n = nums.size() - 2;
int a = -n * (n - 1) / 2;
int b = -n * (n - 1) * (n * 2 - 1) / 6;
for (int x : nums) {
a += x;
b += x * x;
}
int x = (a - (int) sqrt(b * 2 - a * a)) / 2;
return {x, a - x};
}
};
###go
func getSneakyNumbers(nums []int) []int {
n := len(nums) - 2
a := -n * (n - 1) / 2
b := -n * (n - 1) * (n*2 - 1) / 6
for _, x := range nums {
a += x
b += x * x
}
x := (a - int(math.Sqrt(float64(b*2-a*a)))) / 2
return []int{x, a - x}
}
欢迎关注 B站@灵茶山艾府
我们可以逐行统计每行的安全设备数量，如果当前行没有安全设备，直接跳过，否则我们将当前行的安全设备数量乘以前一行的安全设备数量，累加到答案中。然后更新前一行的安全设备数量为当前行的安全设备数量。
###python
class Solution:
def numberOfBeams(self, bank: List[str]) -> int:
ans = pre = 0
for row in bank:
if (cur := row.count("1")) > 0:
ans += pre * cur
pre = cur
return ans
###java
class Solution {
public int numberOfBeams(String[] bank) {
int ans = 0, pre = 0;
for (String row : bank) {
int cur = 0;
for (int i = 0; i < row.length(); ++i) {
cur += row.charAt(i) - '0';
}
if (cur > 0) {
ans += pre * cur;
pre = cur;
}
}
return ans;
}
}
###cpp
class Solution {
public:
int numberOfBeams(vector<string>& bank) {
int ans = 0, pre = 0;
for (auto& row : bank) {
int cur = count(row.begin(), row.end(), '1');
if (cur) {
ans += pre * cur;
pre = cur;
}
}
return ans;
}
};
###go
func numberOfBeams(bank []string) (ans int) {
pre := 0
for _, row := range bank {
if cur := strings.Count(row, "1"); cur > 0 {
ans += pre * cur
pre = cur
}
}
return
}
###ts
function numberOfBeams(bank: string[]): number {
let [ans, pre] = [0, 0];
for (const row of bank) {
const cur = row.split('1').length - 1;
if (cur) {
ans += pre * cur;
pre = cur;
}
}
return ans;
}
###rust
impl Solution {
pub fn number_of_beams(bank: Vec<String>) -> i32 {
let mut ans = 0;
let mut pre = 0;
for row in bank {
let cur = row.chars().filter(|&c| c == '1').count() as i32;
if cur > 0 {
ans += pre * cur;
pre = cur;
}
}
ans
}
}
###c
int numberOfBeams(char** bank, int bankSize) {
int ans = 0, pre = 0;
for (int i = 0; i < bankSize; ++i) {
int cur = 0;
for (int j = 0; bank[i][j] != '\0'; ++j) {
if (bank[i][j] == '1') {
cur++;
}
}
if (cur) {
ans += pre * cur;
pre = cur;
}
}
return ans;
}
时间复杂度 $O(m \times n)$，其中 $m$ 和 $n$ 分别为行数和列数。空间复杂度 $O(1)$。
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈 😄~
银行内部的防盗安全装置已经激活。给你一个下标从 0 开始的二进制字符串数组 bank ，表示银行的平面图，这是一个大小为 m x n 的二维矩阵。 bank[i] 表示第 i 行的设备分布，由若干 '0' 和若干 '1' 组成。'0' 表示单元格是空的，而 '1' 表示单元格有一个安全设备。
对任意两个安全设备而言，如果同时 满足下面两个条件，则二者之间存在 一个 激光束：
r1 和 r2 ，其中 r1 < r2 。r1 < i < r2 的 所有 行 i ，都 没有安全设备 。激光束是独立的，也就是说，一个激光束既不会干扰另一个激光束，也不会与另一个激光束合并成一束。
返回银行中激光束的总数量。
示例 1：
输入：bank = ["011001","000000","010100","001000"] 输出：8 解释：在下面每组设备对之间，存在一条激光束。总共是 8 条激光束： * bank[0][1] -- bank[2][1] * bank[0][1] -- bank[2][3] * bank[0][2] -- bank[2][1] * bank[0][2] -- bank[2][3] * bank[0][5] -- bank[2][1] * bank[0][5] -- bank[2][3] * bank[2][1] -- bank[3][2] * bank[2][3] -- bank[3][2] 注意，第 0 行和第 3 行上的设备之间不存在激光束。 这是因为第 2 行存在安全设备，这不满足第 2 个条件。
示例 2：
输入：bank = ["000","111","000"] 输出：0 解释：不存在两个位于不同行的设备
提示：
m == bank.lengthn == bank[i].length1 <= m, n <= 500bank[i][j] 为 '0' 或 '1'
int getNum(char *row) {
int sum = 0, len = strlen(row);
for (int i = 0; i < len; i++) {
sum += (row[i] - '0');
}
return sum;
}
int numberOfBeams(char ** bank, int bankSize){
int res = 0, lastCnt = 0;
for (int i = 0; i < bankSize; i++) {
int cnt = getNum(bank[i]);
if (cnt != 0) {
res += lastCnt * cnt;
lastCnt = cnt;
}
}
return res;
}
###javascript
const numberOfBeams = bank => {
let res = 0;
let pre = 0;
let cur = 0;
for (let i = 0; i < bank.length; i++) {
const item = bank[i];
// 统计当前行，安全设备的数量
cur = 0;
for (let i = 0; i < item.length; i++) {
if (item[i] === '1') cur++;
}
// 当前行没设备，直接跳过
if (cur === 0) continue;
// 更新res
if (pre > 0) {
res += pre * cur;
}
pre = cur;
}
return res;
};
题意：去掉没有安全设备的行，计算相邻行之间的激光束的数量之和。
{:width=250px}
示例 1 有 $4$ 行，安全设备的个数分别为 $3,0,2,1$。
去掉没有安全设备的行，剩下 $3,2,1$。
计算相邻行之间的激光束的数量之和，即 $3\times 2+ 2\times 1 = 8$。
class Solution:
def numberOfBeams(self, bank: List[str]) -> int:
ans = pre_cnt = 0
for row in bank:
cnt = row.count('1')
if cnt > 0:
ans += pre_cnt * cnt
pre_cnt = cnt
return ans
class Solution {
public int numberOfBeams(String[] bank) {
int ans = 0;
int preCnt = 0;
for (String row : bank) {
int cnt = 0;
for (char ch : row.toCharArray()) {
cnt += ch - '0';
}
if (cnt > 0) {
ans += preCnt * cnt;
preCnt = cnt;
}
}
return ans;
}
}
class Solution {
public:
int numberOfBeams(vector<string>& bank) {
int ans = 0, pre_cnt = 0;
for (auto& row : bank) {
int cnt = ranges::count(row, '1');
if (cnt > 0) {
ans += pre_cnt * cnt;
pre_cnt = cnt;
}
}
return ans;
}
};
int numberOfBeams(char **bank, int bankSize) {
int ans = 0, pre_cnt = 0;
for (int i = 0; i < bankSize; i++) {
char* row = bank[i];
int cnt = 0;
for (int j = 0; row[j]; j++) {
cnt += row[j] - '0';
}
if (cnt > 0) {
ans += pre_cnt * cnt;
pre_cnt = cnt;
}
}
return ans;
}
func numberOfBeams(bank []string) (ans int) {
preCnt := 0
for _, row := range bank {
cnt := strings.Count(row, "1")
if cnt > 0 {
ans += preCnt * cnt
preCnt = cnt
}
}
return
}
var numberOfBeams = function(bank) {
let ans = 0, preCnt = 0;
for (const row of bank) {
const cnt = row.split('1').length - 1;
if (cnt > 0) {
ans += preCnt * cnt;
preCnt = cnt;
}
}
return ans;
};
impl Solution {
pub fn number_of_beams(bank: Vec<String>) -> i32 {
let mut ans = 0;
let mut pre_cnt = 0;
for row in bank {
let cnt = row.bytes().filter(|&c| c == b'1').count() as i32;
if cnt > 0 {
ans += pre_cnt * cnt;
pre_cnt = cnt;
}
}
ans
}
}
欢迎关注 B站@灵茶山艾府
设一周的天数为 $D=7$。
根据题意，第一周存的钱数为
$$
\textit{base} = 1+2+\cdots+D = \dfrac{D(D+1)}{2}
$$
第二周每天存的钱都比 $D$ 天前多 $1$，所以第二周存的钱数为
$$
\textit{base} + D
$$
第三周每天存的钱都比 $D$ 天前多 $1$，所以第三周存的钱数为
$$
\textit{base} + 2D
$$
依此类推。我们存了完整的 $w=\left\lfloor\dfrac{n}{D}\right\rfloor$ 周，在第 $w$ 周存的钱数为
$$
\textit{base} + (w-1)\cdot D
$$
$w$ 周一共存的钱数为
$$
\begin{aligned}
\sum_{i=0}^{w-1} \textit{base} + i\cdot D &= w\cdot \textit{base} + \dfrac{w(w-1)}{2}\cdot D \
&= w\cdot \dfrac{D(D+1)}{2} + \dfrac{w(w-1)}{2}\cdot D \
&= \dfrac{wD(w+D)}{2} \
\end{aligned}
$$
如果 $n$ 不是 $D$ 的倍数，还有 $r = n\bmod D$ 天，存的钱数为
$$
(w+1) + (w+2) + \cdots + (w+r) = rw + \dfrac{r(r+1)}{2} = \dfrac{r(2w+r+1)}{2}
$$
最终答案为
$$
\dfrac{wD(w+D)}{2} + \dfrac{r(2w+r+1)}{2} = \dfrac{wD(w+D) + r(2w+r+1)}{2}
$$
其中 $D=7$，$w=\left\lfloor\dfrac{n}{D}\right\rfloor$，$r = n\bmod D$。
class Solution:
def totalMoney(self, n: int) -> int:
D = 7
w, r = divmod(n, D)
return (w * D * (w + D) + r * (w * 2 + r + 1)) // 2
class Solution {
public int totalMoney(int n) {
final int D = 7;
int w = n / D;
int r = n % D;
return (w * D * (w + D) + r * (w * 2 + r + 1)) / 2;
}
}
class Solution {
public:
int totalMoney(int n) {
constexpr int D = 7;
int w = n / D, r = n % D;
return (w * D * (w + D) + r * (w * 2 + r + 1)) / 2;
}
};
int totalMoney(int n) {
const int D = 7;
int w = n / D, r = n % D;
return (w * D * (w + D) + r * (w * 2 + r + 1)) / 2;
}
func totalMoney(n int) int {
const d = 7
w, r := n/d, n%d
return (w*d*(w+d) + r*(w*2+r+1)) / 2
}
var totalMoney = function(n) {
const D = 7;
const w = Math.floor(n / D), r = n % D;
return (w * D * (w + D) + r * (w * 2 + r + 1)) / 2;
};
impl Solution {
pub fn total_money(n: i32) -> i32 {
const D: i32 = 7;
let w = n / D;
let r = n % D;
(w * D * (w + D) + r * (w * 2 + r + 1)) / 2
}
}
欢迎关注 B站@灵茶山艾府
Hercy 想要为购买第一辆车存钱。他 每天 都往力扣银行里存钱。
最开始，他在周一的时候存入 1 块钱。从周二到周日，他每天都比前一天多存入 1 块钱。在接下来每一个周一，他都会比 前一个周一 多存入 1 块钱。
给你 n ，请你返回在第 n 天结束的时候他在力扣银行总共存了多少块钱。
示例 1：
输入：n = 4 输出：10 解释：第 4 天后，总额为 1 + 2 + 3 + 4 = 10 。
示例 2：
输入：n = 10 输出：37 解释：第 10 天后，总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37 。注意到第二个星期一，Hercy 存入 2 块钱。
示例 3：
输入：n = 20 输出：96 解释：第 20 天后，总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4 + 5 + 6 + 7 + 8) + (3 + 4 + 5 + 6 + 7 + 8) = 96 。
提示：
1 <= n <= 1000根据题意推导数学公式
###Python3
class Solution:
def totalMoney(self, n: int) -> int:
return (div:=n//7) * (1 + 7) * 7 // 2 + (m:=max(div - 1, 0)) * (m + 1) * 7 // 2 + (1 + (r:=n%7)) * r // 2 + div * r
###Java
class Solution {
public int totalMoney(int n) {
int div = n / 7, r = n % 7, m = Math.max(div - 1, 0);
return div * (1 + 7) * 7 / 2 + m * (m + 1) * 7 / 2 + (r + 1) * r / 2 + div * r;
}
}
###JavaScript
/**
* @param {number} n
* @return {number}
*/
var totalMoney = function(n) {
const div = Math.floor(n / 7), r = n % 7, m = Math.max(div - 1, 0)
return div * (1 + 7) * 7 / 2 + m * (m + 1) * 7 / 2 + (r + 1) * r / 2 + div * r
};
###Go
func totalMoney(n int) int {
div, r, m := n / 7, n % 7, 0
if div > 0 {
m = div - 1
}
return div * (1 + 7) * 7 / 2 + m * (m + 1) * 7 / 2 + (r + 1) * r / 2 + div * r
}
###C
int totalMoney(int n){
int div = n / 7, r = n % 7, m = 0;
if(div > 0) {
m = div - 1;
}
return div * (1 + 7) * 7 / 2 + m * (m + 1) * 7 / 2 + (r + 1) * r / 2 + div * r;
}
稍微整理一下数学公式简化为：
###Python3
class Solution:
def totalMoney(self, n: int) -> int:
return (div:=n//7) * (div + 7) * 7 // 2 + (1 + (r:=n%7)) * r // 2 + div * r
###Java
class Solution {
public int totalMoney(int n) {
int div = n / 7, r = n % 7;
return div * (div + 7) * 7 / 2 + (r + 1) * r / 2 + div * r;
}
}
###JavaScript
/**
* @param {number} n
* @return {number}
*/
var totalMoney = function(n) {
const div = Math.floor(n / 7), r = n % 7
return div * (div + 7) * 7 / 2 + (r + 1) * r / 2 + div * r
};
###Go
func totalMoney(n int) int {
div, r := n / 7, n % 7
return div * (div + 7) * 7 / 2 + (r + 1) * r / 2 + div * r
}
###C
int totalMoney(int n){
int div = n / 7, r = n % 7;
return div * (div + 7) * 7 / 2 + (r + 1) * r / 2 + div * r;
}
时间复杂度 $o(1)$
空间复杂度 $o(1)$
根据题意进行模拟即可，分两步进行计算。
先计算完整周：共 $a = \left \lfloor \frac{n}{7} \right \rfloor$ 周，第一周起始日金额为 $1$，每周的起始日的金额递增 $1$，周内金额可使用「等差数列求和」公式直接求解。
然后再计算最后一周（若有）的金额：共 $b = n \pmod 7$ 天，使用紧接的起始日金额继续进行累加即可。
代码：
###Java
class Solution {
public int totalMoney(int n) {
int a = n / 7, b = n % 7;
int ans = 0, k = 1;
while (a-- > 0) {
ans += (k + (k + 6)) * 7 / 2;
k++;
}
while (b-- > 0) ans += k++;
return ans;
}
}
时间复杂度：$O(a + b)$
空间复杂度：$O(1)$
更进一步，每个完整周的起始日金额相比上周起始日金额多 $1$，同时周内每日金额递增 $1$，因此相邻完整周的金额之和也满足「等差」性质，可直接使用「等差数列求和」公式 $O(1)$ 求解完整周部分的金额之和；最后一周（若有）的金额也是同理。
代码：
###Java
class Solution {
public int totalMoney(int n) {
int a = n / 7, b = n % 7;
int a1 = (1 + 7) * 7 / 2, an = (a + (a + 6)) * 7 / 2;
int s1 = (a1 + an) * a / 2;
a++;
int s2 = (a + (a + b - 1)) * b / 2;
return s1 + s2;
}
}
时间复杂度：$O(1)$
空间复杂度：$O(1)$
题太简单？不如来学习热乎的 简单图论搜索题 🍭🍭🍭
或是加练如下「模拟」内容：
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/
也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
