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

C++: 
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;

        auto func = [&](auto &&self, int i, vector<int> path) -> void {
            if (i == nums.size()) {
                ans.push_back(path);
                return;
            }
            self(self, i + 1, path);
            path.push_back(nums[i]);
            self(self, i + 1, path);
            path.pop_back();
        };

        func(func, 0, {});
        return ans;
    }
};
 
Code ngu :too_sad:
C#: 
public class Solution {
    public static IList<IList<int>> result = new List<IList<int>>();
    public static IList<int> temp = new List<int>();

    public void BackTrack(int[] nums, int k, int n, int start)
    {
        for(int i = start; i<nums.Length-n+k+1; i++)
        {
            temp.Add(nums[i]);
            if(k < n-1)
            {
                BackTrack(nums, k+1, n, i+1);
            }
            if(k == n-1)
            {
                result.Add(temp.ToArray());
            }
            temp.RemoveAt(temp.Count - 1);
        }
    }

    public IList<IList<int>> Subsets(int[] nums) {
        result.Clear();
        result.Add([]);
        for(int i = 1; i<=nums.Length; i++)
        {
            BackTrack(nums, 0, i, 0);
        }
        return result;
    }
}
Fix lại cho đỡ ngu :too_sad:

C#: 
public class Solution {
    public void BackTrack(int[] nums, int k, List<int> temp, IList<IList<int>> result)
    {
        result.Add(temp.ToArray());
        for(int i = k;i<nums.Length; i++)
        {
            temp.Add(nums[i]);
            BackTrack(nums, i+1, temp, result);
            temp.RemoveAt(temp.Count - 1);
        }
    }

    public IList<IList<int>> Subsets(int[] nums) {
        IList<IList<int>> result = new List<IList<int>>();
        List<int> temp = new List<int>();
        BackTrack(nums, 0, temp, result);
        return result;
    }
}
 
Last edited:
Pick hoặc ko pick nums[pos] thôi, ko cần loops
Java: 
class Solution {
    List<List<Integer>> ans;
    int n;

    public List<List<Integer>> subsets(int[] nums) {
        n = nums.length;
        ans = new ArrayList<>();
        
        backtrack(0, new LinkedList<>(), nums);

        return ans;
    }

    private void backtrack(int pos, List<Integer> curList, int[] nums) {
        if (pos == n) {
            ans.add(new LinkedList<>(curList));
            return;
        }
        
        curList.add(nums[pos]);
        backtrack(pos + 1, curList, nums);
        curList.removeLast();
        backtrack(pos + 1, curList, nums);
    }
}
 
Hôm qua dùng chính bài hôm nay để làm luôn kkk
JavaScript: 
function subsets(nums: number[]): number[][] {
    let res: number[][] = [], n = nums.length
    const backtrack = (idx: number, cur: number[], curIdx: number) => {
        if (cur.length === curIdx) {
            res.push([...cur]);
            return;
        }

        for (let i = idx; i < n; i++) {
            cur.push(nums[i]);
            backtrack(i + 1, cur, curIdx)
            cur.pop();
        }
    }
    for (let k = 0; k < n + 1; k++) backtrack(0, [], k);
    return res;
};
 
JavaScript: 
var subsets = function(nums) {
    var backtrack = function (i, subset) {
        if (i === nums.length){
            subsets.push([...subset]);
            return;
        }

        subset.push(nums[i]);
        backtrack(i + 1, subset);
        subset.pop();
        backtrack(i + 1, subset);
    }

    const subsets = [];

    backtrack(0, []);

    return subsets;
};
 
Python: 
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        result = []
        chosen = [False] * n
        def backtracking(i, subset):
            if i >= n:
                result.append(subset.copy())
                return
            subset.append(nums[i])
            backtracking(i+1, subset)
            subset.pop()
            backtracking(i+1, subset)
        
        backtracking(0, [])
        return result
 
Ngoài lề tí, mọi người cho hỏi có nên mua tài khoản leedcode premium để luyện thuật toán không ạ? Trước đây mình thỉnh thoảng mới vào leetcode nên có xin dùng ké với một bạn nhưng tài khoản hay bị trục trặc nên mình muốn mua riêng?
 
C++: 
class Solution {
public:
    vector<vector<int>> subsets(vector<int> const& nums) {
        vector<vector<int>> res({{}});
        function<void(int)> solve = [&](int e) {
            int n = res.size();
            for (int i = 0; i < n; ++i) {
                auto v = res[i];
                v.emplace_back(e);
                res.emplace_back(v);
            }
        };
        for (auto e : nums) solve(e);
        return res;
    }
};
 
Java: 
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(res, new ArrayList<Integer>(), nums, 0);
        return res;
    }
    public void backtrack(List<List<Integer>> res, List<Integer> subset, int[] nums, int start){
        res.add(new ArrayList<Integer>(subset));
        for(int i = start; i<nums.length;i++){
            subset.add(nums[i]);
            backtrack(res, subset, nums, i+1);
            subset.remove(subset.size()-1);
        }
    }
}
 
C++: 
class Solution {
public:
  vector<vector<int>> subsets(vector<int> &nums) {
    vector<vector<int>> ans;
    for (int i = 0; i < 1 << nums.size(); i++) {
      vector<int> subset;
      for (int j = 0; j < nums.size(); j++) {
        if (i & (1 << j)) {
          subset.push_back(nums[j]);
        }
      }
      ans.push_back(subset);
    }
    return ans;
  }
};
 
Python: 
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = [[]]
        for num in nums:
            new_arr = [tmp + [num] for tmp in result]
            result += new_arr
        return result
 
ptk said:
Ngoài lề tí, mọi người cho hỏi có nên mua tài khoản leedcode premium để luyện thuật toán không ạ? Trước đây mình thỉnh thoảng mới vào leetcode nên có xin dùng ké với một bạn nhưng tài khoản hay bị trục trặc nên mình muốn mua riêng?
Click to expand...
premium chắc chỉ có list bài công ty xài pv là đáng tiền thôi, còn xài để học thì có vẻ không đáng
 
Nay page trôi xa dữ, tận trang 3 mới thấy. Ae spam lắm quá :doubt:
Python: 
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        ans = []
        def isPalindrome(string):
            left = 0
            right = len(string) - 1
            while left <= right:
                if string[left] == string[right]:
                    left += 1
                    right -= 1
                else:
                    return False

            return True

        def backtrack(index, items):
            if index == len(s):
                cloned = []
                for item in items:
                    cloned.append(item)

                ans.append(cloned)
                return
            
            for i in range(index, len(s)):
                string = s[index: i + 1]
                if isPalindrome(string):
                    items.append(string)
                    backtrack(i + 1, items)
                    items.pop(-1)
    
        backtrack(0, [])
        return ans
 
Bài này chỉ thêm mỗi cái check đối xứng thôi chứ cũng ko khác gì bài hôm qua
JavaScript: 
function partition(s: string): string[][] {
    const res = [];
    const path = [];
    
    const backtracking = (s: string, i: number, j: number) =>{
        if(i === s.length){
            res.push([...path]);
            return;
        }
        
        for(let index = j; index <= s.length; ++index){
            if(isPalindrome(s, i, index)){
                path.push(s.slice(i, index));
                backtracking(s, index, index+1);
                path.pop();
            }
        }
    }
    
    const isPalindrome = (s: string, i: number, j: number): boolean =>{
        while(i < j - 1){
            if(s[i] !== s[j-1]){
                return false;
            }
            ++i;
            --j;
        }
        return true;
    };
    
    backtracking(s, 0, 1);
    return res;
}
 
One shot :big_smile: lấy idea dp của mấy bài palindrome luôn
Java: 
class Solution {
    List<List<String>> ans;
    boolean[][] palindromes;
    int n;

    public List<List<String>> partition(String s) {
        ans = new ArrayList<>();
        palindromes = new boolean[s.length()][s.length()];
        n = s.length();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i; j++) {
                if (s.charAt(j + i) == s.charAt(j) && i < 2) {
                    palindromes[i][j] = true;
                } else if (s.charAt(j + i) == s.charAt(j)) {
                    palindromes[i][j] = palindromes[i - 2][j + 1] && s.charAt(j) == s.charAt(j + i);
                }
            }
        }

        backtrack(0, s, new LinkedList<>());

        return ans;
    }

    private void backtrack(int idx, String s, List<String> curList) {
        if (idx >= n) {
            ans.add(new LinkedList<>(curList));
            return;
        }

        for (int i = 0; i < n - idx; i++) {
            if (palindromes[i][idx]) {
                curList.add(s.substring(idx, idx + i + 1));
                backtrack(idx + i + 1, s, curList);
                curList.removeLast();
            }
        }
    }
}
 
Code: 
use std::str::*;

impl Solution {
    pub fn partition(s: String) -> Vec<Vec<String>> {
        let bytes = s.as_bytes();
        let n = bytes.len();
        let mut results = vec![];

        Self::partition_helper(bytes, &mut vec![], &mut results);

        results
    }

    pub fn partition_helper(remaining: &[u8], holder: &mut Vec<&[u8]>, acc: &mut Vec<Vec<String>>) {
        let l = remaining.len();

        if l == 0 {
            let mut results = vec![];

            for slice in holder {
                results.push(unsafe { from_utf8_unchecked(slice) }.to_owned());
            }

            acc.push(results);

            return;
        }

        for i in 0..l {
            let mut start = i;
            let mut end = i;

            while start > 0 && end < (l - 1) && remaining[start] == remaining[end] {
                start -= 1;
                end += 1;
            }

            if start == 0 && remaining[start] == remaining[end] {
                let mut cloned_holder = holder.clone();
                cloned_holder.push(&remaining[start..=end]);
                Self::partition_helper(&remaining[(end + 1)..], &mut cloned_holder, acc);
            }
        }

        for i in 0..(l - 1) {
            let mut start = i;
            let mut end = i + 1;

            if remaining[start] != remaining[end] {
                continue;
            }

            while start > 0 && end < (l - 1) && remaining[start] == remaining[end] {
                start -= 1;
                end += 1;
            }

            if start == 0 && remaining[start] == remaining[end] {
                let mut cloned_holder = holder.clone();
                cloned_holder.push(&remaining[start..=end]);
                Self::partition_helper(&remaining[(end + 1)..], &mut cloned_holder, acc);
            }
        }
    }
}

Code: 
use std::str::*;

impl Solution {
    pub fn partition(s: String) -> Vec<Vec<String>> {
        let bytes = s.as_bytes();
        let n = bytes.len();
        let mut results = vec![];

        Self::partition_helper(bytes, (0, n), &mut vec![], &mut results);

        results
    }

    pub fn partition_helper(s: &[u8], remaining: (usize, usize), holder: &mut Vec<(usize, usize)>, acc: &mut Vec<Vec<String>>) {
        let l = remaining.1 - remaining.0;

        if l == 0 {
            let mut results = vec![];

            for &(start, end) in holder.iter() {
                results.push(unsafe { from_utf8_unchecked(&s[start..=end]) }.to_owned());
            }

            acc.push(results);

            return;
        }

        let a = remaining.0;
        let b = remaining.1;

        for i in a..b {
            let mut start = i;
            let mut end = i;

            while start > a && end < (b - 1) && s[start - 1] == s[end + 1] {
                start -= 1;
                end += 1;
            }

            if start == a {
                holder.push((start, end));
                Self::partition_helper(s, (end + 1, b), holder, acc);
                holder.pop();
            }
        }

        for i in a..(b - 1) {
            let mut start = i;
            let mut end = i + 1;

            if s[start] != s[end] {
                continue;
            }

            while start > a && end < (b - 1) && s[start - 1] == s[end + 1] {
                start -= 1;
                end += 1;
            }

            if start == a {
                holder.push((start, end));
                Self::partition_helper(s, (end + 1, b), holder, acc);
                holder.pop();
            }
        }
    }
}
 
Last edited:
Nay cty nhiều task quá, brute force tạm vậy

C-like: 
class Solution {
    fun partition(s: String): List<List<String>> {
        return allPartition(s).filter { partition ->
            partition.all { it.isPalindrome() }
        }
    }

    fun allPartition(s: String): List<List<String>> {
        if (s.isEmpty()) {
            return emptyList()
        }
        val firstCharacter = s.first().toString()
        if (s.length == 1) {
            return listOf(listOf(firstCharacter))
        }
        val allPartitions = allPartition(s.drop(1))
        val result = mutableListOf<List<String>>()
        allPartitions.forEach {
            result.add(listOf(firstCharacter) + it)
            result.add(listOf(firstCharacter + it.first()) + it.drop(1))
        }
        return result
    }

    private fun String.isPalindrome(): Boolean {
        var start = 0
        var end = lastIndex
        while (start < end) {
            if (get(start) != get(end)) {
                return false
            }
            start++
            end--
        }
        return true
    }
}
 

Similar threads

Duy1122
thảo luận [Database] Hiệu Suất Phân Trang Xâu Trong SQL Database
Replies
6
Views
591
heocon0123
heocon0123
domino123
kiến thức PixelTap by Pixelverse
Replies
0
Views
143
domino123
domino123
T
thảo luận PIXELVERSE kèo hot đào trên tele dự kiến list b
Replies
15
Views
392
truonggiang!
T
@_shin
kiến thức PIXELVERSE kèo hot - inbox tele để lấy extension chạy auto đánh boss
Replies
0
Views
114
@_shin
@_shin
D
kiến thức Lộ trình tự học phát triển Website Fullstack - Fullstack Web Development
Replies
15
Views
2K
HarryNam
HarryNam

Share this page

Back
Top