腾讯精选50题—Day16题目 237,238,292
第十六天~
目录
1. 题目237 删除链表中的节点
(1) 题目描述
(2) 思路
因为没有告诉链表头，所以直接复制+删除即可。
(3) 题解
class Solution {
public:
void deleteNode(ListNode* node) {
ListNode* p = node->next;
node->val = p->val;
node->next = p->next;
}
};
结果：
时间复杂度：
O
(
1
)
O(1)
O(1)
空间复杂度：
O
(
1
)
O(1)
O(1)
2. 题目238 除自身以外数组的乘积
(1) 题目描述
(2) 思路
正序统计前缀，倒序统计后缀。
(3) 题解
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int r = 1;
vector<int> result(nums.size(),0);
for (int i = 0; i < nums.size(); i++) {
if (i == 0)
result[i] = 1;
else {
result[i] = r * nums[i-1];
r = result[i];
}
}
r = 1;
for (int i = nums.size() - 1; i >= 0; i--)
{
result[i] = result[i] * r;
r = nums[i] * r;
}
return result;
}
};
结果：
时间复杂度：
O
(
n
)
O(n)
O(n)
空间复杂度：
O
(
1
)
O(1)
O(1)
3. 题目292 Nim游戏
(1) 题目描述
(2) 思路
如果被4整除，那么必输。
(3) 题解
class Solution {
public:
bool canWinNim(int n) {
if(n%4==0)
return false;
return true;
}
};
结果：
时间复杂度：
O
(
1
)
O(1)
O(1)
空间复杂度：
O
(
1
)
O(1)
O(1)