thảo luận Leetcode mỗi ngày

subs là dãy hiệu
remain_arr là dãy loại bỏ số 0 từ dãy hiệu
=> kết quả = từ dãy hiệu ta cần tìm các đoạn âm dương xen kẽ dài nhất có thể
gọi f là kết quả khi kết thúc tại i
khi trái dấu thì f[i+1] = f + 1
còn cùng dấu thì không thay đổi f[i+1] = f

Python: 
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 1

        subs = [nums[i] - nums[i-1] for i in range(1, len(nums))]

        remain_arr = []
        count_zero = 0
        for sub in subs:
            if sub == 0:
                count_zero += 1
                continue
            remain_arr.append(sub)
           
        if len(remain_arr) <= 1:
            return len(nums) - count_zero
       
        f = [0] * len(remain_arr)

        for i in range(len(remain_arr)-1):
            if remain_arr[i] * remain_arr[i+1] >= 0:
                f[i+1] = f[i] + 1
            else:
                f[i+1] = f[i]
        return len(nums) - f[len(remain_arr)-1] - count_zero
 
Last edited:
Lập Trình Viên Số Khổ said:
gọi
dp_up[i.] là chiều dài lớn nhất của subsequence positive đạt được với kết thúc là a[i.]

dp_down[i.] là chiều dài lớn nhất của subsequence negative đạt được với kết thúc là a[i.]

với cách gọi này thì dp_up[i.] cũng là chiều dài lớn nhất của subsequence positive đạt được lấy từ dãy có chiều dài đến vị trí i (không cần kết thúc tại a[i.] ).

Chứng minh bằng phản chứng: ví dụ có subs positive có m số kết thúc tại j < i mà dãy subs positive kết thúc ở a[i.] được có n số với n < m.

m số là: x1, x2, ....x(m-1), xm
n số là: y1,y2,...y(n-1),yn = a[i.]
nếu yn > x(m-1) ta có dãy m số kết thúc tại x1, x2, ....x(m-1), yn = a[i.]
nếu yn<= x(m-1) suy ra y(n-1) < yn <= x(m-1) < x(m-2) ta có dãy: x1, x2, ....x(m-2), y(n-1), yn = a[i.]

2 dãy trên đều có số lượng là m > n (vô lí)
Click to expand...

CTO cũng đỉnh đến đc như vầy là cùng
 
em được có 35% thui bác ơi :too_sad:

1656860314081.png


bác quân sư với bác violet chắc toàn 100% ai địch nổi :sweat:
 
Bọn leetcode này có vấn đề lúc 0ms, lúc 2ms, lúc 3ms.
https://leetcode.com/submissions/detail/737527656/

Code: 
func wiggleMaxLength(nums []int) int {
    if len(nums) <= 1 { return len(nums)}

    diff := make([]int, len(nums) - 1)
    var cur int
    var count int
    for i := 0; i < len(nums) - 1; i++ {
        if nums[i+1] > nums[i] {
            diff[i] = 1
        } else if nums[i+1] < nums[i] {
            diff[i] = -1
        } else {
            diff[i] = 0
        }
        
        if i == 0 {
            cur = diff[0]
            count = diff[0] * diff[0]
        } else {
            if diff[i] == 0 {
                continue
            }
            if cur != diff[i] {
                count++
                cur = diff[i]
            }
        }
    }
    
    return count + 1
}
 
Lập Trình Viên Số Khổ said:
em được có 35% thui bác ơi :too_sad:

View attachment 1244984

bác quân sư với bác violet chắc toàn 100% ai địch nổi :sweat:
Click to expand...
Hong, tui ít khi nào quan tâm cái % beat đó nên thường chỉ tầm 30% - 50% thôi. Khi nào dưới 20% mới optimize.

Cơ mà bài này tui làm đơn giản mà sao thấy mọi người suy nghĩ phức tạp thế nhỉ
https://leetcode.com/submissions/detail/737551242/

Ý tưởng greedy đơn giản là nếu số hiện tại mà nó nối được vào chuỗi thì nối, không thì thôi, swap qua lại giữa âm và dương. Sau đó run 2 lần xét riêng 2 trường hợp khởi đầu âm và khởi đầu dương, cái nào lớn hơn thì lấy. Code có mấy dòng

Python: 
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        maxLen = 0
        for initOrder in (-1, 1):
            lastNum = nums[0]
            order = initOrder
            count = 1
            for n in nums[1:]:
                if order * (n - lastNum) > 0:
                    count += 1
                    order *= -1
                lastNum = n
                
            maxLen = max(maxLen, count)
            
        return maxLen
 
Bài này có thể hiểu đơn giản là đếm số đoạn tăng giảm liên tục :)
C++: 
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int res = 1, is_incr = 0;
        for(int i=1; i<nums.size(); i++){
            if (nums[i-1] < nums[i]) {
                if (is_incr == -1 || is_incr == 0) {
                    is_incr = 1;
                    res++;
                }
            } else
            if ( nums[i-1] > nums[i]) {
                if (is_incr == 1 || is_incr == 0) {
                    is_incr = -1;
                    res++;
                }
            }
        }
        return res;
    }
};
 
C++: 
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() < 2) return nums.size();
        int total = 1;
        int curr_v = nums[1] - nums[0];
        int idx = 1;
        
        for(int i = idx; i < nums.size(); i++){
            if (nums[i] != nums[i-1]){
                idx = i;
                curr_v = nums[i] - nums[i-1];
                total += 1;
                break;
            }
        }
        
        for(int i = idx + 1; i < nums.size(); i++){           
            if ((nums[i] - nums[i - 1])*curr_v < 0){
                curr_v = nums[i] - nums[i - 1];
                total += 1;
            }
        }
        return total;
    }
};
Lâu quá mới làm lại leetcode nên hơi phèn
 
4/7/2022:
  • 1 câu hard tầm trung
  • nhìn vào đề bài ta thấy bài sẽ thấy số kẹo đứa trẻ i phụ thuộc vào cụm 3 số ratings[i - 1], ratings[i.], ratings[i + 1],
  • tạo mảng candies, candies[i.] là số kẹo của đứa trẻ i
  • nếu ratings[i - 1] >= ratings[i.] <= ratings[i + 1] -> candies[i.] = 1
  • nếu ratings[i - 1] < ratings[i.] -> candies[i.] > candies[i - 1]
  • nếu ratings[i + 1] < ratings[i.] -> candies[i.] > candies[i + 1]
  • Cách làm:
  • Các đứa trẻ nhận ít nhất 1 kẹo nên bước đầu phát cho mỗi đứa trẻ 1 cái kẹo.
  • duyệt i = 1 đến i = n - 1; nếu ratings[i - 1] < ratings[i.] -> candies[i .] = candies[i - 1] + 1 (vì nếu ratings của đứa trẻ i mà lớn hơn ratings của đứa trẻ kế bên thì số kẹo cũng vậy, nên để chia ít kẹo nhất thì candies[i.] = candies[i - 1] + 1)
  • duyệt từ i = n - 2 đến i = 0, nếu ratings[i + 1] < ratings[i.] -> candies[i .] = max(candies[i + 1] + 1, candies[i .]) (dùng max để xét trường hợp ratings[i.] lớn hơn ratings[i - 1] và ratings[i + 1])
  • tính tổng số kẹo
  • Time và space: O(n)
  • nghĩ mất 10p và code mất 20p
  • Code lúc đầu khá ngáo: https://leetcode.com/submissions/detail/737823836/
  • Code sau khi nhìn solution thì khá gọn: https://leetcode.com/submissions/detail/737827725/
  • còn solution space O(1) nữa, h nghĩ tiếp
Update: Solution O(1),
solution này khá khó đẻ kiểu giải thích trên này, nói chung là liên quan đến việc số phần tử ratings tăng liên tiếp và giảm liên tiếp, gợi ý thế thôi chứ giải thích mệt lắm :angry::angry:
Code: https://leetcode.com/submissions/detail/737850444/
 
Last edited:
Violet_7 said:
4/7/2022:
  • 1 câu hard tầm trung
  • nhìn vào đề bài ta thấy bài sẽ thấy số kẹo đứa trẻ i phụ thuộc vào cụm 3 số ratings[i - 1], ratings[i.], ratings[i + 1],
  • tạo mảng candies, candies[i.] là số kẹo của đứa trẻ i
  • nếu ratings[i - 1] >= ratings[i.] <= ratings[i + 1] -> candies[i.] = 1
  • nếu ratings[i - 1] < ratings[i.] -> candies[i.] > candies[i - 1]
  • nếu ratings[i + 1] < ratings[i.] -> candies[i.] > candies[i + 1]
  • Cách làm:
  • Các đứa trẻ nhận ít nhất 1 kẹo nên bước đầu phát cho mỗi đứa trẻ 1 cái kẹo.
  • duyệt i = 1 đến i = n - 1; nếu ratings[i - 1] < ratings[i.] -> candies[i .] = candies[i - 1] + 1 (vì nếu ratings của đứa trẻ i mà lớn hơn ratings của đứa trẻ kế bên thì số kẹo cũng vậy, nên để chia ít kẹo nhất thì candies[i.] = candies[i - 1] + 1)
  • duyệt từ i = n - 2 đến i = 0, nếu ratings[i + 1] < ratings[i.] -> candies[i .] = max(candies[i + 1] + 1, candies[i .]) (dùng max để xét trường hợp ratings[i.] lớn hơn ratings[i - 1] và ratings[i + 1])
  • tính tổng số kẹo
  • Time và space: O(n)
  • nghĩ mất 10p và code mất 20p
  • Code lúc đầu khá ngáo: https://leetcode.com/submissions/detail/737823836/
  • Code sau khi nhìn solution thì khá gọn: https://leetcode.com/submissions/detail/737827725/
  • còn solution space O(1) nữa, h nghĩ tiếp
Update: Solution O(1),
solution này khá khó đẻ kiểu giải thích trên này, nói chung là liên quan đến việc số phần tử ratings tăng liên tiếp và giảm liên tiếp, gợi ý thế thôi chứ giải thích mệt lắm :angry::angry:
Code: https://leetcode.com/submissions/detail/737850444/
Click to expand...
Cách t làm y chang, nhưng code viết gọn gàng hơn. Bài này t từng làm trước đó rồi nên làm chút xíu là xong. :big_smile:

C++: 
class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candies(ratings.size(), 1);
        for (int i = 1; i < ratings.size(); ++i) {
            if (ratings[i] > ratings[i-1]) candies[i] = candies[i-1] + 1;
        }
        int ret = candies.back();
        for (int i = ratings.size() - 2; i >= 0; --i) {
            if (ratings[i] > ratings[i+1]) candies[i] = max(candies[i], candies[i+1]+1);
            ret += candies[i];
        }
        return ret;
    }
};

Edit: sửa lại code để k phải loop 3 lần.
 
Last edited:
Bài này level hard, nghĩ 20 phút ko ra ý tưởng gì, nên em xem giải :ah:

  • dùng 2 dãy: dãy từ trái sang phải thoả mãn mọi điều kiện của ratings theo 1 chiều từ trái sang phải, và dãy từ phải sang trái là ngược lại.
  • xong tính dãy mới bằng cách lấy max của phần tử trên 2 dãy mà có cùng vị trí.
  • rồi tính tổng các phần tử của dãy này

Python: 
from typing import List


class Solution:
    def candy(self, ratings: List[int]) -> int:
        left2right = [1] * len(ratings)
        right2left = [1] * len(ratings)

        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i-1]:
                left2right[i] = left2right[i-1] + 1

        for i in range(len(ratings)-1, 0, -1):
            if ratings[i-1] > ratings[i]:
                right2left[i-1] = right2left[i] + 1

        return sum([max(a, b) for a, b in zip(left2right, right2left)])
 
Bài này làm theo cách suy nghĩ thông thường O(n^2) thấy pass rồi, rảnh rỗi nghiên cứu cách tối ưu sau.

* Duyệt tuần tự mảng ratings:
** Nếu ratings[i-1] > ratings[i] thì mảng đang trên đà giảm dần => chưa cần làm gì.
** Nếu ratings[i-1] <= ratings[i] thì mảng đang chuyển hướng tăng dần => quay lui, tăng số lượng kẹo lên cho đến khi mảng ratings hết giảm.

C#: 
public class Solution {
    public int Candy(int[] ratings) {
        int[] candies = new int[ratings.Length];
        Array.Fill(candies, 1);
        
        for (var i = 1; i < ratings.Length; i++)
        {
            if (ratings[i] < ratings[i-1])
                continue;
            
            for (var j = i - 2; j >= 0 && ratings[j] > ratings[j+1]; j--)
                candies[j] = Math.Max(candies[j], candies[j+1] + 1);
            
            if (ratings[i] > ratings[i-1])
                candies[i] = Math.Max(candies[i], candies[i-1] + 1);
        }
        
        for (var j = ratings.Length - 2; j >= 0 && ratings[j] > ratings[j+1]; j--)
                candies[j] = Math.Max(candies[j], candies[j+1] + 1);
        
        //Console.WriteLine(string.Join(',', candies));
        return candies.Sum();
    }
}
 
Bài này có thể giải bằng greedy.

Ý tưởng:
  • Bắt đầu từ số kẹo là 1,
  • Duyệt từ đầu đến cuối. Có 3 trường hợp:
+ chuỗi con tăng dần: cứ thêm một số thì tăng số kẹo lên 1. Tức là nếu chuỗi dài d thì sẽ cần phát thêm thêm d*(d+1)/2 kẹo,
+ chuỗi con bằng nhau: Từ người thứ 2 giảm số kẹo về 1,
+ chuỗi con giảm dần: phát cho người cuối cùng của chuỗi con đó số kẹo là 1, số gần cuối là 2, ... Ở đây sẽ có trường hợp là chuỗi con giảm dần có độ dài lớn hơn số kẹo phát cho người hiện tại (người bắt đầu của chuỗi giảm dần), ta sẽ bù vào lượng chênh lệch đó.

Độ phức tạp: time O(n), space O(1)

C++: 
class Solution {
public:
    int candy(vector<int>& ratings) {
        int res = 1, candy = 1;
        auto it = begin(ratings) + 1;
     
        while(it != end(ratings)) {
            auto it2 = it;
            // find increasing sequence
            while (it2 != end(ratings) && *it2 > *(it2-1)) ++it2;
            auto d = it2 - it;
            res += (d*(d+1+2*candy)) / 2;
            candy += d;
            it = it2;
         
            // find equal sequence
            while (it2 != end(ratings) && *it2 == *(it2-1)) ++it2;
            d = it2 - it;
            if (d > 0) {
                candy = 1;
                res += d;
            }
            it = it2;
         
            // find decreasing sequence
            while (it2 != end(ratings) && *it2 < *(it2-1)) ++it2;
            d = it2 - it;
            if (d > 0) {
                res += d * (d+1) / 2;
                if (d + 1 > candy)
                    res += (d + 1 - candy);
                candy = 1;
            }
            it = it2;
        }
        return res;
    }
};
 
Last edited:
5/7/2022:
  • 1 câu medium quen thuộc
  • nhìn vào đề bài thấy ngay cách dễ nhất là sort rồi tìm chuỗi số liên tiếp, nhưng lại bắt viết O(N) nên phải nghĩ cách khác
  • để ý đây là xét 1 tập hợp, nên nếu muốn qhđ thì vẫn phải sort trước, có thể dùng counting sort để time là O(n) nhưng max value = 10^9 nên ko dùng đc cách này
  • để ý đây là 1 tập hợp chỉ chứa các số liên tiếp, nên có thể dùng two pointer khá giống câu https://leetcode.com/problems/longest-palindromic-substring/
  • Cách làm:
  • bước đầu dùng hash map hoặc set để đánh dấu các số trong mảng
  • duyệt lại mảng 1 lần nữa, đến mỗi số ta tìm tập hợp lớn nhất có chứa số đó
  • vì mỗi số chỉ xuất hiện trong 1 tập hợp lớn nhất, nên để time O(n), tạo 1 hash map visited, để xét các số nào đã tới thăm r
  • dùng biến left để chạy số đó sang bên trái, right sang bên phải
  • VD xét đến số 4 -> left = 3, right = 5
while (nếu left có trong mảng) { visited [left.]= true; left--};
while (nếu right có trong mảng) { visited [right.]= true; right++};
 
Last edited:
Sáng nay nhìn cái bài LCS tưởng ez rồi, ai dè thấy yêu cầu O(n) :canny:

Đầu tiên nghĩ đến radix sort nhưng implement thấy rắc rối quá nên bỏ qua.

Sau đó nghĩ đến việc dùng HashSet, duyệt qua mảng 1 lần để tạo HashSet và min/max, sau đó duyệt các num từ min -> max là xong, nhưng sợ TLE. Đúng vậy thật, test thử với input [-10^9, 10^9] nó tạch nay lập tức
osCpCsi.png


Sau cùng thấy chỉ còn cách duyệt qua từng items trong input array hoặc hashset mới mong không bị TLE => bị duplicated nhiều quá => phải tạo thêm cái HashSet visited để giảm duplicated thì mới xong
uzQb2yt.png

C#: 
public class Solution {
    public int LongestConsecutive(int[] nums) {
        HashSet<int> set = new ();
        foreach (var num in nums)
        {
            set.Add(num);
        }
      
        int longest = 0, left = 0, right = 0;
        HashSet<int> visited = new ();
        foreach (var num in nums)
        {
            if (visited.Contains(num))
                continue;

            visited.Add(num);
          
            left = num;
            while (set.Contains(left-1))
            {
                left--;
                visited.Add(left);
            }
          
            right = num;
            while (set.Contains(right+1))
            {
                right++;
                visited.Add(right);
            }
          
            longest = Math.Max(longest, right - left + 1);
        }
      
        return longest;
    }
}
 
Violet_7 said:
5/7/2022:
  • 1 câu medium quen thuộc
  • nhìn vào đề bài thấy ngay cách dễ nhất là sort rồi tìm chuỗi số liên tiếp, nhưng lại bắt viết O(n) nên phải nghĩ cách khác
  • để ý đây là xét 1 tập hợp, nên nếu muốn qhđ thì vẫn phải sort trước, có thể dùng counting sort để time là O(n) nhưng max value = 10^9 nên ko dùng đc cách này
  • để ý đây là 1 tập hợp chỉ chứa các số liên tiếp, nên có thể dùng two pointer khá giống câu https://leetcode.com/problems/longest-palindromic-substring/
  • Cách làm:
  • bước đầu dùng hash map hoặc set để đánh dấu các số trong mảng
  • duyệt lại mảng 1 lần nữa, đến mỗi số ta tìm tập hợp lớn nhất có chứa số đó
  • vì mỗi số chỉ xuất hiện trong 1 tập hợp lớn nhất, nên để time O(n), tạo 1 hash map visited, để xét các số nào đã tới thăm r
  • dùng biến left để chạy số đó sang bên trái, right sang bên phải
  • VD xét đến số 4 -> left = 3, right = 5
while (nếu left có trong mảng) { visited [left.]= true; left--};
while (nếu right có trong mảng) { visited [right.]= true; right++};
Click to expand...
Bài này quen nên solution của em là Brute force cơ bản + phân tích kiểu dây chun để lấy Onlogn:
  • Sort array, streak và maxStreak nên là 1 (dù cỡ nào cũng min là 1, nếu arr empty thì res là 0)
  • Xét từ 1 -> length - 1, kiểm tra x != x[i-1] và x = x[i-1] + 1 hay không, nếu có thì streak tăng 1, còn không thì so sánh Max giữa streak và maxStreak , streak sẽ quay về 1, tương tự xét vòng mảng mới while-xx
    [*]Kết quả sẽ là 1 lần nữa so sánh Max streak và maxStreak


Java: 
public int longestConsecutive(int[] nums) {
        int length = nums.length;
        Arrays.sort(nums);
        if (length == 0) {
            return 0;
        }
        int streak = 1, maxStreak = 1;
        for (int i = 1; i < length; i++) {
            if (nums[i] != nums[i-1]) {
                if (nums[i -1] +1 == nums[i]) {
                    streak += 1;
                } else {
                    maxStreak = Math.max(maxStreak, streak);
                    streak = 1;
                }
            } else {
                    continue;
            }
        }

        return Math.max(maxStreak, streak);
    }
 
Last edited:
bài LCS này cần O(n) nên nghĩ đến sử dụng radix sort
C++: 
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }
     
        for (int &d : nums) {
            d += 1000000000; // nums[i] in [0...2e9]
        }
     
        vector<vector<int>> buckets(10, vector<int>()); // 10 buckets for sorting [0...9]
        long d1 = 10, d2 = 1;
        for (int i = 0; i < 10; i++) {
            for (int &d : nums) {
                buckets[(d % d1) / d2].push_back(d);
            }
         
            int j = 0;
            for (auto &bucket : buckets) {
                for (int &d : bucket) {
                    nums[j++] = d;
                }
                bucket.clear();
            }
         
            d1 *= 10;
            d2 *= 10;
        }
     
        int ans = 0;
        int c = 0;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == nums[i - 1] + 1) {
                c++;
            } else if (nums[i] == nums[i - 1]) {
                continue;
            } else {
                ans = max(ans, c + 1);
                c = 0;
            }
        }
     
        ans = max(ans, c + 1);
     
        return ans;
    }
};
trong related topic có union find nên em cài đặt thử
C++: 
class Solution {
public:
    inline int findParent(vector<int> &p, int i) {
        while (p[i] != -1) {
            i = p[i];
        }
        return i;
    }
 
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> m;
        vector<int> l(nums.size(), 1), p(nums.size(), -1); // l[i] is length of CS from nums[i], p[i] is index of parent of index i
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (m.find(nums[i]) == m.end()) {
                m[nums[i]] = i;
                l[i] = 1;
             
                if (m.find(nums[i] + 1) != m.end()) {
                    p[m[nums[i] + 1]] = i;
                    l[i] += l[m[nums[i] + 1]];
                }
             
                ans = max(ans, l[i]);
             
                if (m.find(nums[i] - 1) != m.end()) {
                    int p0 = findParent(p, m[nums[i] - 1]);
                    p[i] = p0;
                    l[p0] += l[i];
                    ans = max(ans, l[p0]);
                }
            }
        }
     
        return ans;
    }
};
 
Last edited:
Bài này giống bài của bác Fire of Heart, constraint không gắt bằng thôi :beauty:

Solution 1:
Time complexity: O(nlogn)
Space complexity: O(1)
  • Sort mảng, sau đó so sánh phần tử hiện tại với phần tử kế tiếp.
  • Với hai phần tử:
- Nếu liền nhau => tiếp tục so sánh theo cặp
- Nếu bằng nhau => tăng vị trí của phần tử kế tiếp lên một đơn vị
- Nếu không bằng => break

Vì con trỏ đến phần tử kế tiếp đã được process nên không cần thiết phải process lại lần nữa, cuối vòng lặp sẽ trỏ con trỏ hiện tại tới con trỏ phần tử kế
Java: 
class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length <= 1)
            return nums.length;
        Arrays.sort(nums);
        int max = 1;
        int curPos = 0;
        while (curPos < nums.length)
        {
            int nextPos = curPos + 1;
            int count = 1;
            int curVal = nums[curPos];
            while (nextPos < nums.length)
            {
                if (nums[nextPos] - 1 == curVal)
                {
                    curVal = nums[nextPos];
                    ++count;
                    ++nextPos;
                }
                else if (nums[nextPos] == curVal)
                    ++nextPos;
                else
                    break;
            }
            curPos = nextPos;
            max = Math.max(max, count);
        }
        return max;
    }
}


Solution 2:
Time complexity: O(n)
Space complexity: O(n)
  • Tạo một cái set để add hết tất cả phần tử unique vào set
  • Process từng phần tử trong mảng ban đầu:
- Nếu tồn tại trong set:
- Tạo một biến tạm bằng phần tử hiện tại rồi tăng dần + giảm dần, tổng số phần tử thu được là tổng của hiệu số phần tử - biến tạm (đối với giảm dần) và hiệu số biến tạm - phần tử (đối với tăng dần)
- Với mỗi phần tử tăng/giảm, nếu thỏa mãn, loại khỏi set ban đầu
- Nếu không tồn tại, bỏ qua

Vì phần tử thỏa mãn đã được loại nên không cần phải process đối với phần tử trùng lặp
Java: 
class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length <= 1)
            return nums.length;
        Set<Integer> set = new HashSet<>();
        for (int num : nums)
        {
            set.add(num);
        }
   
        int max = 1;
        for (int num : nums)
        {
            if (set.contains(num))
            {
                set.remove(num);
                int cur = num;
                while (set.remove(cur - 1))
                {
                    --cur;
                }
                int count = num - cur;
           
                cur = num;
                while (set.remove(cur + 1))
                {
                    ++cur;
                }
                count += cur - num;
                max = Math.max(count + 1, max);
            }
        }
   
        return max;
    }
}

Vậy mà thời gian chạy của cách 1 toàn nhanh hơn cách 2:beat_brick:
 

Similar threads

4 More Years
Nhiều người mất sạch bài đăng trên Facebook
Replies
0
Views
162
4 More Years
4 More Years
4 More Years
Elon Musk có kế hoạch tính phí người dùng X mới để cho phép đăng bài
2 3
Replies
48
Views
3K
bimatcuasoi5
bimatcuasoi5
Lenh Ho Dai Ca
Giám đốc Nhã Nam xin lỗi
2 3 4
Replies
63
Views
6K
snowangle987
snowangle987
buiduchanh1995
thắc mắc Cách thiết kế database cho hệ thống lớn
2
Replies
37
Views
3K
khonganhit19
khonganhit19
meekoo
thắc mắc [Hỏi AI] Cách làm sao để train AI hiểu một task nào đấy?
Replies
9
Views
1K
weed_bông
weed_bông

Share this page

Back
Top