var asteroidCollision = function(asteroids) {
const stack = [];
out: for (const it of asteroids) {
while (it < 0 && stack.length > 0 && stack[stack.length-1] > 0) {
const k = stack.pop();
if (k === -it) {
continue out;
} else if (k > -it) {
stack.push(k);
continue out;
}
}
stack.push(it);
}
return stack;
};
use std::collections::VecDeque;
impl Solution {
pub fn asteroid_collision(asteroids: Vec<i32>) -> Vec<i32> {
let mut deque: VecDeque<i32> = VecDeque::new();
asteroids.iter().for_each(|&x| {
let mut flag = true;
while let Some(&t) = deque.back() {
if x < 0 && t > 0 {
if x.abs() > t.abs() {
deque.pop_back();
} else if x.abs() < t.abs() {
flag = false;
break;
} else {
flag = false;
deque.pop_back();
break;
}
} else {
break;
}
}
if flag {
deque.push_back(x);
}
});
deque.into_iter().collect::<Vec<i32>>()
}
}
var asteroidCollision = function(asteroids) {
const n = asteroids.length
const stack = []
for(let i = 0; i < n; i++) {
if(!stack.length) {
stack.push(asteroids[i])
continue
}
const curAsteroid = asteroids[i]
let lastAsteroid = stack[stack.length - 1]
let canPushCur = true
while(isColliding(lastAsteroid, curAsteroid)) {
if(Math.abs(curAsteroid) > Math.abs(lastAsteroid)) {
stack.pop()
lastAsteroid = stack[stack.length - 1]
} else {
if(Math.abs(curAsteroid) === Math.abs(lastAsteroid)) stack.pop()
canPushCur = false
break
}
}
if(canPushCur) stack.push(curAsteroid)
}
return stack
};
const isColliding = (as1, as2) => as1 > 0 && as2 < 0
class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
stack<int>st;
vector<int>res,rev;
for(int p:asteroids)
{
while(!st.empty()&&st.top()<-p)st.pop();
if(!st.empty()&&p<0)
{
if(st.top()==-p)
{
st.pop();
}
continue;
}
if(p<0)
{
res.emplace_back(p);
}
else
{
st.push(p);
}
}
while(!st.empty())
{
rev.emplace_back(st.top());
st.pop();
}
res.insert(res.end(),rev.rbegin(),rev.rend());
return res;
}
};
class Solution {
public int[] asteroidCollision(int[] asteroids) {
int[] dq = new int[asteroids.length];
int end = -1;
for (int a: asteroids) {
if (a < 0) {
for (;;) {
int k = end < 0 ? 0 : dq[end--];
if (k == 0) {
dq[++end] = a;
break;
}
if (k < 0) {
dq[++end] = k;
dq[++end] = a;
break;
}
if (k == -a) {
break;
}
if (k > -a) {
dq[++end] = k;
break;
}
}
} else {
dq[++end] = a;
}
}
return Arrays.copyOf(dq, end+1);
}
}số âm bay về bên trái, số dương về bên phải, nếu input là [2,1,-1,2] thì mới ra rỗng, còn input như kia thì bọn nó bay về ngược hướng ko chạm nhau nên ra mảng ban đầu đó thím.
chiều lag y hệt bác
.
class Solution:
def asteroidCollision(self, asteroids: list[int]) -> list[int]:
if len(asteroids) <= 1:
return asteroids
left_asteroids = self.asteroidCollision(asteroids[:len(asteroids) // 2])
right_asteroids = self.asteroidCollision(asteroids[len(asteroids) // 2:])
pos_l = len(left_asteroids) -1
pos_r = 0
while True:
if pos_l < 0 or left_asteroids[pos_l] < 0 or pos_r == len(right_asteroids) or right_asteroids[pos_r] > 0:
new_asteroids = left_asteroids[:pos_l+1].copy()
new_asteroids.extend(right_asteroids[pos_r:])
return new_asteroids
right = abs(right_asteroids[pos_r])
left = abs(left_asteroids[pos_l])
if right >= left:
pos_l -= 1
if left >= right:
pos_r += 1
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
lis = [nums[0]]
buckets = [[-nums[0]]]
prefix_counts = [[1]]
for num in nums[1:]:
insert_index = bisect_left(lis, num)
if insert_index == len(lis):
lis.append(num)
buckets.append([])
prefix_counts.append([])
lis[insert_index] = num
buckets[insert_index].append(-num)
if len(prefix_counts[insert_index]) > 0:
prefix_counts[insert_index].append(prefix_counts[insert_index][-1])
else:
prefix_counts[insert_index].append(0)
if insert_index == 0:
prefix_counts[insert_index][-1] += 1
continue
prev_insert_index = insert_index - 1
insert_index_2 = bisect_right(buckets[prev_insert_index], -num)
if insert_index_2 == len(buckets[prev_insert_index]):
continue
if insert_index_2 == 0:
prefix_counts[insert_index][-1] += prefix_counts[prev_insert_index][-1]
continue
prefix_counts[insert_index][-1] += (
prefix_counts[prev_insert_index][-1] -
prefix_counts[prev_insert_index][insert_index_2 - 1]
)
return prefix_counts[-1][-1]
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n,1);
vector<int> sz(n,1);
for (int i = 0; i < n; i++){
for (int j = 0; j < i; j++){
if (nums[j] < nums[i]){
if (dp[j] + 1 > dp[i]){
dp[i] = dp[j] + 1;
sz[i] = sz[j];
}
else if (dp[j] + 1 == dp[i]){
sz[i] += sz[j];
}
}
}
}
int lis = *max_element(dp.begin(),dp.end()), ans = 0;
for (int i = 0; i < n; i++){
if (dp[i] == lis){
ans += sz[i];
}
}
return ans;
}
};#define lst(x) x&(-x)
struct BIT{
int n;
vector<pair<int,int>> tr;
BIT (int n_){
n = n_;
tr.resize(n+1);
tr[1] = {0,1};
}
void add(int p, pair<int,int> x){
for (;p<=n;p+=lst(p)){
int u = tr[p].first, v = tr[p].second;
if (u > x.first){
continue;
}
else if (u == x.first){
if (u > 0) v += x.second;
}
else{
v = x.second;
u = x.first;
}
tr[p] = {u,v};
}
}
pair<int,int> get(int p){
pair<int,int> x = {0,1};
for (;p;p-=lst(p)){
int u = tr[p].first, v = tr[p].second;
if (u < x.first){
continue;
}
else if (u == x.first){
if (u > 0) x.second += v;
}
else{
x.second = v;
x.first = u;
}
}
return x;
}
}; // fenwick tree
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n = nums.size();
BIT bit(n);
// nén
vector<int> dis(nums);
vector<int> new_nums(n);
sort(dis.begin(),dis.end());
dis.erase(unique(dis.begin(),dis.end()),dis.end());
for (int i = 0; i < n; i++){
new_nums[i] = lower_bound(dis.begin(),dis.end(),nums[i]) - dis.begin();
}
// xong nén
for (int i = 0; i < n; i++){
int p = new_nums[i];
auto pref = bit.get(p);
bit.add(p+1,{pref.first+1,pref.second});
}
return bit.get(n).second;
}
};
nay em rảnh nên code thêm cách này thôi bácLuyện leetcode chủ yếu để phỏng vấn, mà đi phỏng vấn chắc không ai code cái BIT như các bác đi thi CP đâu
. Tội gì mà phỏng vấn lôi BIT ra 
var findNumberOfLIS = function(nums) {
const n = nums.length, len = [], cnt = [];
let lis = -1, ans = 0;
for (let i = 0; i < n; i++) {
len[i] = 1;
cnt[i] = 1;
for (let j = 0; j < n; j++) {
if (nums[j] >= nums[i]) {
continue;
}
if (len[j] + 1 > len[i]) {
len[i] = len[j] + 1;
cnt[i] = cnt[j];
} else if (len[j] + 1 === len[i]) {
cnt[i] += cnt[j];
}
}
if (len[i] > lis) {
lis = len[i];
ans = cnt[i];
} else if (len[i] === lis) {
ans += cnt[i];
}
}
return ans;
};nay em rảnh nên code thêm cách này thôi bác
sao không update vị trí 0 là {1,1} mà còn khởi tạo hết hả bác. Hỏi ngu là em hay thấy một số tên biến có _ như code của bác là n_ thì có ý nghĩa gì thế
cảm ơn bác, em fix lại rồi. Em đặt thêm _ tiện cho constructor để phân biệt với biến n trong struct đó thôi, không thì dùng this cũng được, cái này tùy thói quen.
)def update(i, val, tree, OFFSET, MAX_RANGE):
i += OFFSET
while i <= MAX_RANGE:
tree[i] += val
i += i&-i
def get(i, tree, OFFSET, MAX_RANGE):
if not tree: return 0
i += OFFSET
s = 0
while i:
s += tree[i]
i -= i&-i
return s
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
OFFSET = max(0, 2-min(nums))
MAX_RANGE = max(nums) + OFFSET
d = [1-OFFSET]
cnt = defaultdict(lambda: defaultdict(int))
update(1-OFFSET, 1, cnt[0], OFFSET, MAX_RANGE)
ans = 0
for num in nums:
max_length = bisect.bisect_left(d, num)
number_of_ways = get(num-1, cnt[max_length-1], OFFSET, MAX_RANGE)
ans = max(ans, max_length)
if max_length == len(d):
d.append(num)
else:
d[max_length] = min(d[max_length], num)
update(num, number_of_ways, cnt[max_length], OFFSET, MAX_RANGE)
return get(MAX_RANGE-OFFSET, cnt[ans], OFFSET, MAX_RANGE)add lần lượt các số thay đổi trên index lis. Các số add vào sẽ giảm dần. Từ đó áp dụng binarysearch vs prefixsum thôiBài hôm nay là 1 biến thể của LIS, quá kinh điển trong các dạng quy hoạch động rồi.
Yêu cầu của đề ko chỉ tìm Longest, mà còn đếm số thằng Longest.
Hàm quy hoạch động thông thường sẽ là
f(i): longest subsequece end at i-th
và g(i) đếm số thằng là longest subsequece end at i-th
f = max(f[j]) + 1 với j < i và nums[j] < nums{i}
g = sum(g[j]) với j < i và nums[j] < nums{i} VÀ f[j] + 1 = f
Đơn giản cho 1 thuật N^2
Để cải tiến lên N log N thì dùng thêm kỹ thuật BS để tìm LIS và dùng cấu trúc dữ liệu quản lý đoạn (segment tree, fenwicktre, ....) để đếm số lượng ( giải thích dài nên hơi lười gõ
Hoặc có mấy thánh xài patience sort gì đấy mình không biết, mình đang thử tìm hiểu rồi ăn cắp code
Python:def update(i, val, tree, OFFSET, MAX_RANGE): i += OFFSET while i <= MAX_RANGE: tree[i] += val i += i&-i def get(i, tree, OFFSET, MAX_RANGE): if not tree: return 0 i += OFFSET s = 0 while i: s += tree[i] i -= i&-i return s class Solution: def findNumberOfLIS(self, nums: List[int]) -> int: OFFSET = max(0, 2-min(nums)) MAX_RANGE = max(nums) + OFFSET d = [1-OFFSET] cnt = defaultdict(lambda: defaultdict(int)) update(1-OFFSET, 1, cnt[0], OFFSET, MAX_RANGE) ans = 0 for num in nums: max_length = bisect.bisect_left(d, num) number_of_ways = get(num-1, cnt[max_length-1], OFFSET, MAX_RANGE) ans = max(ans, max_length) if max_length == len(d): d.append(num) else: d[max_length] = min(d[max_length], num) update(num, number_of_ways, cnt[max_length], OFFSET, MAX_RANGE) return get(MAX_RANGE-OFFSET, cnt[ans], OFFSET, MAX_RANGE)
