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

_Gia_Cat_Luong_ · 3/9/22

tui code dài quá, thím nào thạo python chỉ tui cách viết ngắn lại với :sweat:

updated: sửa lại theo solution ngắn hơn rùi

Python:

class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        res = set()
  
        def gen_num(val, index, arr):
      
            if index == n:
                res.add(arr)
                return
      
            if val < 0 or val > 9:
                return
      
            arr = arr*10 + val
          
            gen_num(val - k, index + 1, arr)
            gen_num(val + k, index + 1, arr)
      
            arr = arr//10
      
        for i in range(1, 10):
            gen_num(i, 0, 0)

        return list(res)

Cũng k biết giải thích sao nhưng bài này dùng queue thì sẽ ngắn gọn hơn nhiều:
https://leetcode.com/submissions/detail/790257883/

cachlyxahoi · 3/9/22

thớt hay xin phép chấm hóng học tập

Aristides · 3/9/22

bài hôm nay khó thế

sau_tim_thiep_hong · 3/9/22

Aristides đã nói:
bài hôm nay khó thế

Xem tệp đính kèm 1359593

nghĩ thêm chỗ termination đi bác gần đúng rồi

Cong_Go_De_Su · 3/9/22

Dạo này đệ quy suốt vậy

Mã:

defmodule Solution do
  @starters %{
    1 => 1..9,
    2 => 1..9,
    3 => 1..9,
    4 => 1..9,
    5 => 1..9,
    6 => [1, 2, 3, 6, 7, 8, 9],
    7 => [1, 2, 7, 8, 9],
    8 => [1, 8, 9],
    9 => [9]
  }

  def nums_same_consec_diff(n, 0) do
    for i <- 1..9 do
      i |> Integer.to_string() |> String.duplicate(n) |> String.to_integer()
    end
  end

  def nums_same_consec_diff(n, k) do
    @starters
    |> Map.get(k)
    |> Enum.flat_map(fn digit ->
      to_num(0, digit, n - 1, k) |> List.flatten()
    end)
  end

  defp is_digit?(n), do: n >= 0 and n <= 9

  defp to_num(upper, digit, 0, k), do: [upper + digit]

  defp to_num(upper, digit, n, k) do
    val = digit * 10 ** n

    case {is_digit?(digit - k), is_digit?(digit + k)} do
      {true, true} ->
        [to_num(upper + val, digit - k, n - 1, k), to_num(upper + val, digit + k, n - 1, k)]
      {true, _} ->
        to_num(upper + val, digit - k, n - 1, k)
      {_, true} ->
        to_num(upper + val, digit + k, n - 1, k)
    end
  end
end

Aristides · 3/9/22

uầy cuối cùng cũng xong, khử đệ quy vẫn luôn là chân ái

stackOverFlow cái đầu bờ

Java:

class Solution {
    public int[] numsSameConsecDiff(int n, int k) {
        ArrayList<Integer> arr = new ArrayList<Integer>();
        Stack<Integer> st = new Stack<>();
        for(int i = 1; i <= 9; i++)
        {
            st.push(i);
            while(!st.isEmpty())
            {
                int nums = st.pop();
                if(numLength(nums) == n)
                {
                    if(!arr.contains(nums))
                    {
                        arr.add(nums);
                    }
                    continue;
                }
                int currentDigit = nums % 10;
                if(currentDigit >= k)
                {
                    st.push(nums * 10 + currentDigit - k);
                }
                if(currentDigit + k < 10)
                {
                    st.push(nums * 10 + currentDigit + k);
                }
            }
        }
        return arr.stream().mapToInt(Integer::intValue).toArray();
    }
    private int numLength(int nums)
    {
        int count = 0;
        while(nums != 0)
        {
            nums = nums / 10;
            count++;
        }
        return count;
    }
}

Time Complexity thì ở top 5% từ dưới đếm lên nhưng space complexity thì 99% luôn nhé

Edit: à sửa lại luôn cái điều kiện terminate đệ quy luôn thì cũng được luôn. Nhưng Time Complexity vẫn top 5% từ dưới đếm lên

Java:

class Solution {
    public int[] numsSameConsecDiff(int n, int k) {
        ArrayList<Integer> arr = new ArrayList<>();
        for(int i = 1; i <= 9; i++)
        {
            recursion(i, n - 1, k, arr);
        }
        return arr.stream().mapToInt(Integer::intValue).toArray();
    }
    private void recursion(int nums, int n, int k, ArrayList<Integer> arr)
    {
        if(n == 0)
        {
            if(!arr.contains(nums))
            {
                arr.add(nums);
            }
            return;
        }
        int currentDigit = nums % 10;
        if(currentDigit >= k)
        {
            recursion(nums * 10 + currentDigit - k, n - 1, k, arr);
        }
        if(currentDigit + k <= 9)
        {
            recursion(nums * 10 + currentDigit + k, n - 1, k, arr);
        }
    }
}

kyo_pyro · 3/9/22

bribnt đã nói:
Nếu không bị tràn stack thì tất cả những thao tác bộ nhớ khi recursive đều là thao tác trên stack:
VD với x86:

allocate stack frame, gán stack pointer bản chất chỉ là giảm giá trị thanh ghi rsp. Không phải allocate cái gì ở đây cả,

return address thì được lưu tại ô nhớ rất gần địa chỉ hiện tại ==> cache friendly

parameter nếu không quá nhiều thì có thể lưu vào thanh ghi.

Trong khi nếu dùng CTDL Stack thì:

Data lưu tại bộ nhớ heap, cần cấp phát động trước,

Có thể phải giãn nở trong quá trình sử dụng, mỗi lần như vậy là phải cấp phát động lại, copy phần bộ nhớ cũ vào.

Tóm là là dùng CTDL Stack thì ít thao tác hơn, nhưng truy cập memory lại chậm hơn. Nếu có thể khắc phục, biết để allocate trước lượng bộ nhớ cần thiết thì chắc chắn nhanh hơn. Còn không thì phải benchmark.

Stack mặc định dùng container là deque mà toàn insert với remove ở cuối nên em nghĩ ko cần copy toàn bộ qua khi đổi size

Aristides · 3/9/22

kyo_pyro đã nói:
Stack mặc định dùng container là deque mà toàn insert với remove ở cuối nên em nghĩ ko cần copy toàn bộ qua khi đổi size

ủa stack trong java là thừa kế từ vector chứ deque đâu ra?

Cong_Go_De_Su · 3/9/22

Lâu lâu đổi gió thử convert code về Java xem sao, nhìn cumbersome thặc

Java:

import java.util.*;
import java.util.stream.*;

class Solution {
    private static final List<Integer> STARTERS_1_5 = List.of(1, 2, 3, 4, 5, 6, 7, 8, 9);
    
    private static final Map<Integer, List<Integer>> STARTERS_6_9 = Map.of(
        6, List.of(1, 2, 3, 6, 7, 8, 9),
        7, List.of(1, 2, 7, 8, 9),
        8, List.of(1, 8, 9),
        9, List.of(9)
    );
    
    public int[] numsSameConsecDiff(int n, int k) {
        if (k == 0) {
            return IntStream.range(1, 10)
                        .map(i -> Integer.parseInt(String.valueOf(i).repeat(n)))
                        .toArray();
        } else {
            var result = new ArrayList<Integer>();
            List<Integer> starters = null;
            if (k < 6) {
                starters = STARTERS_1_5;
            } else {
                starters = STARTERS_6_9.get(k);
            }
            starters
                .forEach(digit -> toNum(result, 0, digit, n - 1, k));
            
            return result.stream()
                .mapToInt(Integer::intValue)
                .toArray();
        }
    }

    private boolean isDigit(int n) {
        return n <= 9 && n >= 0;
    }

    private void toNum(List<Integer> result, int upper, int digit, int n, int k) {
        if (n == 0) {;
            result.add(upper + digit);
        } else {
            var val = digit *  (int)Math.pow(10, n) + upper;
            var low = digit - k;
            var high = digit + k;
            if (isDigit(low) && isDigit(high)) {
                toNum(result, val, low, n - 1, k);
                toNum(result, val, high, n - 1, k);
            } else if (isDigit(low)) {
                toNum(result, val, low, n - 1, k);
            } else {
                toNum(result, val, high, n - 1, k);
            }
        }
    }
}

Kân team v3 · 3/9/22

Aristides đã nói:
uầy cuối cùng cũng xong, khử đệ quy vẫn luôn là chân ái

stackOverFlow cái đầu bờ

Xem tệp đính kèm 1359629

Java:

class Solution { public int[] numsSameConsecDiff(int n, int k) { ArrayList<Integer> arr = new ArrayList<Integer>(); Stack<Integer> st = new Stack<>(); for(int i = 1; i <= 9; i++) { st.push(i); while(!st.isEmpty()) { int nums = st.pop(); if(numLength(nums) == n) { if(!arr.contains(nums)) { arr.add(nums); } continue; } int currentDigit = nums % 10; if(currentDigit >= k) { st.push(nums * 10 + currentDigit - k); } if(currentDigit + k < 10) { st.push(nums * 10 + currentDigit + k); } } } return arr.stream().mapToInt(Integer::intValue).toArray(); } private int numLength(int nums) { int count = 0; while(nums != 0) { nums = nums / 10; count++; } return count; } }

Time Complexity thì ở top 5% từ dưới đếm lên nhưng space complexity thì 99% luôn nhé

Edit: à sửa lại luôn cái điều kiện terminate đệ quy luôn thì cũng được luôn. Nhưng Time Complexity vẫn top 5% từ dưới đếm lên
Xem tệp đính kèm 1359643

Java:

class Solution { public int[] numsSameConsecDiff(int n, int k) { ArrayList<Integer> arr = new ArrayList<>(); for(int i = 1; i <= 9; i++) { recursion(i, n - 1, k, arr); } return arr.stream().mapToInt(Integer::intValue).toArray(); } private void recursion(int nums, int n, int k, ArrayList<Integer> arr) { if(n == 0) { if(!arr.contains(nums)) { arr.add(nums); } return; } int currentDigit = nums % 10; if(currentDigit >= k) { recursion(nums * 10 + currentDigit - k, n - 1, k, arr); } if(currentDigit + k <= 9) { recursion(nums * 10 + currentDigit + k, n - 1, k, arr); } } }

tại phải check cái này if(!arr.contains(nums)) nên chậm hơn nè

khỏi cần check arr.contains cũng được, chỉ cần thêm điều kiện k != 0 thì mới check cái if thứ 2 if(currentDigit + k <= 9)
dfs xài đệ quy: https://leetcode.com/submissions/detail/790368240/
bfs xài std::queue: https://leetcode.com/submissions/detail/790117291/

firefox_nxh · 3/9/22

Để dạng str nên chậm quá :sosad:

Runtime: 49 ms, faster than 83.67% of Python3 online submissions for Numbers With Same Consecutive Differences.
Memory Usage: 14.3 MB, less than 21.77% of Python3 online submissions for Numbers With Same Consecutive Differences.

Mã:

class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        def rec_num(n, num):
            if n == 1:
                return [str(num)]
            else:
                res = []
                for e in rec_num(n - 1, num):
                    first_num = int(e[0])
                    add, sub = first_num + k, first_num - k
                    # print(e, first_num, sub, add)
                    if (add >= 0) & (add <= 9):
                        res.append(str(add) + e)
                    if (sub >= 0) & (sub <= 9):
                        res.append(str(sub) + e)
                    # print(n, res)
                return list(set(res))
        ans = []
        for i in range(0, 10):
            tmp = rec_num(n, i)
            # print(tmp)
            if tmp is not None:
                for j in tmp:
                    if j[0] != '0':
                        ans.append(int(j))
        ans = list(set(ans))
        return ans

Aristides · 3/9/22

Kân team v3 đã nói:
tại phải check cái này if(!arr.contains(nums)) nên chậm hơn nè

khỏi cần check arr.contains cũng được, chỉ cần thêm điều kiện k != 0 thì mới check cái if thứ 2 if(currentDigit + k <= 9)
dfs xài đệ quy: https://leetcode.com/submissions/detail/790368240/
bfs xài std::queue: https://leetcode.com/submissions/detail/790117291/

không có cái đấy thì sai thuật toán

Aristides · 3/9/22

đã sửa theo ý bác cân team

Cải thiện được 15% time complexity

Kân team v3 · 3/9/22

Aristides đã nói:
đã sửa theo ý bác cân team

Cải thiện được 15% time complexity

Xem tệp đính kèm 1359875

submit lại đôi ba lần thế lào cũng có lần lẹ hơn tí

Aristides · 3/9/22

Kân team v3 đã nói:
submit lại đôi ba lần thế lào cũng có lần lẹ hơn tí

à thì như bác đã thấy

mấy lần submit dưới có cái tận 20ms lận

chắc tại java nó thế

Kân team v3 · 3/9/22

Aristides đã nói:
à thì như bác đã thấy

mấy lần submit dưới có cái tận 20ms lận

chắc tại java nó thế

thử xài đệ quy xem. Stack<Integer> thì mỗi int nó lại phải tạo thành Integer chậm hơn

viết luôn custom class IntArrayList để tránh ArrayList<Integer> luôn

nói chung Java phải xài ...<Integer> thì dỏm lắm, tốc độ chắc ngang Python

Aristides · 3/9/22

đù vãi nồi thật, implement bằng C++ perfomance nó khác bọt hẳn

đúng là ngôn ngữ thượng đẳng có khác

Kân team v3 · 3/9/22

https://leetcode.com/submissions/detail/790394358/ 95 phần chăm này

kết luận ...<Integer> chậm ko khác gì Python

Aristides · 3/9/22

thì Integer là wrapper class mà. Bản chất nó là 1 object thì allocate trên heap rồi garbage collection đương nhiên chậm hơn kiểu primitive type trên stack rồi

Edit: nghe bảo Java đang có project Valhalla hay cái éo gì ấy tương tự hứa hẹn generics giờ cũng sẽ cast được primitive type, nhưng vẫn đảm bảo backward compatibility lẫn hiệu năng tốt chứ không phải kiểu syntactic sugar

nghe ảo ma vãi lẫn mùi bánh vẽ thoang thoảng đâu đây

Blue Amethyst · 3/9/22

Aristides đã nói:
đã sửa theo ý bác cân team

Cải thiện được 15% time complexity

Xem tệp đính kèm 1359875

Nếu bác muốn nhanh hơn thì như này: đổi Stack thành ArrayDeque và thay vì dùng stream + mapToInt thì bác tạo array rồi tự map qua luôn :byebye:

Vì Stack trong Java không nhanh bằng Array Deque đâu

P/s: em không rõ hàm numLength bác viết gì trong đó, nhưng nhanh gọn lẹ thì cứ lấy log(10) + 1 thôi :byebye:

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

Senior Member

Senior Member

Senior Member

Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Đã tốn tiền

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này