ຊຸດຍ່ອຍ Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
Array ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ

ບັນຫາ leetcode ລວມທີ່ລະບຸໄວ້ວ່າໃຫ້ array a [] ຂອງຂະ ໜາດ n. ກວດເບິ່ງວ່າອາເລສາມາດແບ່ງອອກເປັນສອງຍ່ອຍໄດ້ເຊັ່ນວ່າຜົນລວມຂອງຄ່າຂອງ ໜຶ່ງ ຊຸດຍ່ອຍເທົ່າກັບຊຸດຍ່ອຍອື່ນ. ພິມ“ ແມ່ນແລ້ວ” ຖ້າມັນເປັນໄປໄດ້ອີກ“ ບໍ່”.

ຍົກຕົວຢ່າງ

a[ ] = {2, 3, 5}
Yes

ຄໍາອະທິບາຍ: ຜົນລວມຂອງອົງປະກອບທີ ໜຶ່ງ ແລະທີສອງເທົ່າກັບອົງປະກອບທີສາມ. ດັ່ງນັ້ນ, ອາເລທີ່ມອບໃຫ້ສາມາດແບ່ງອອກເປັນສອງຊຸດຍ່ອຍ.

a[ ] = {1, 2, 4, 9}
No

ຄໍາອະທິບາຍ: ບໍ່ມີການປະສົມປະສານທີ່ເປັນໄປໄດ້ເຊັ່ນວ່າອາເລສາມາດແບ່ງອອກເປັນສອງຍ່ອຍ, ເຊັ່ນວ່າພວກມັນມີຍອດລວມເທົ່າກັນ.

ແບບທົດແທນ

ລະບົບວິເຄາະ

1. ເລີ່ມຕົ້ນຂບວນ a [] ຂອງຂະ ໜາດ n.
2. ຂ້າມອາເລແລະພົບຜົນລວມຂອງສ່ວນປະກອບທັງ ໝົດ ໃນອາເລທີ່ໃຫ້ເປັນ a []. ກວດເບິ່ງວ່າ sum mod 2 ບໍ່ແມ່ນ 0, ສົ່ງຄືນບໍ່ຖືກຕ້ອງ.
3. ສ້າງກ ຫນ້າທີ່ ທີ່ກວດເບິ່ງວ່າມີຂໍ້ຍ່ອຍຢູ່ໃນຂບວນໃດ ໜຶ່ງ ເຊິ່ງຜົນລວມຂອງມັນເທົ່າກັບເຄິ່ງ ໜຶ່ງ ຂອງຜົນລວມຂອງອາເລເຕັມ.
4. ເອີ້ນຟັງຊັນນີ້ຄືນໂດຍການລວມເອົາອົງປະກອບສຸດທ້າຍແລະໂດຍບໍ່ລວມເອົາອົງປະກອບສຸດທ້າຍ.
5. ຖ້າຜົນລວມແມ່ນສູນ, ໃຫ້ກັບຄືນມາເປັນຄວາມຈິງ. ອື່ນຖ້າຜົນລວມບໍ່ແມ່ນສູນແລະ n ແມ່ນສູນ, ສົ່ງຄືນຂໍ້ມູນທີ່ບໍ່ຖືກຕ້ອງ.

ການຈັດຕັ້ງປະຕິບັດ ສຳ ລັບ Subset Sum Leetcode

ລະຫັດ C ++ ສຳ ລັບ Subset Sum

#include <bits/stdc++.h> 
using namespace std; 
  
bool isEqualSum(int a[], int n, int sum){  
    if(sum == 0)  
        return true;  
    if(n == 0 && sum != 0)  
        return false;  
  
    if(a[n-1] > sum)  
       return isEqualSum(a, n-1, sum);  
  
    return isEqualSum(a, n-1, sum) ||  
        isEqualSum(a, n-1, sum-a[n-1]);  
}  
  
bool Partiion(int a[], int n){  
    int sum = 0;  
    for(int i=0; i<n; i++)  
    sum += a[i];  
  
    if(sum%2 != 0)  
        return false;  
  
    return isEqualSum (a, n, sum/2);  
}  
  
int main(){  
    int a[] = {2, 3, 5};  
    int n = sizeof(a)/sizeof(a[0]);  
    if(Partiion(a, n))  
        cout << "Yes";  
    else
        cout << "No";  
    return 0;  
}
Yes

ລະຫັດ Java ສຳ ລັບຊຸດຍ່ອຍ

import java.io.*; 
  
class equalSum{ 
    static boolean isEqualSum(int a[], int n, int sum){ 
        if(sum == 0) 
            return true; 
        if(n == 0 && sum != 0) 
            return false; 
  
        if(a[n-1] > sum) 
            return isEqualSum(a, n-1, sum); 
  
        return isEqualSum(a, n-1, sum) || 
               isEqualSum(a, n-1, sum-a[n-1]); 
    } 
  
    static boolean Partition (int a[], int n){ 
        int sum = 0; 
        for(int i = 0; i < n; i++) 
            sum += a[i]; 
  
        if (sum%2 != 0) 
            return false; 
  
        return isEqualSum(a, n, sum/2); 
    } 
  
    public static void main (String[] args){ 
  
        int a[] = {2, 3, 5}; 
        int n = a.length; 
        if(Partition(a, n) == true) 
            System.out.println("Yes"); 
        else
            System.out.println("No"); 
    } 
}
Yes

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບ Subset Sum Leetcode

ຄວາມສັບສົນເວລາ

ເນື່ອງຈາກແຕ່ລະບັນຫາຖືກແບ່ງອອກເປັນສອງໂຄງການຍ່ອຍທີ່ນ້ອຍກວ່າ. ນັ້ນແມ່ນສູດການຄິດໄລ່ມີ O (2n) ຄວາມສັບສົນເວລາ, ບ່ອນທີ່ n ແມ່ນ ຈຳ ນວນເລກເຕັມໃນແຖວທີ່ໃຫ້ [a].

ຄວາມສັບສົນໃນອະວະກາດ

O (1), ເພາະວ່າພວກເຮົາໃຊ້ພື້ນທີ່ເພີ່ມເຕີມທີ່ຄົງທີ່.

ວິທີການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ

ລະບົບວິເຄາະ

1. ເລີ່ມຕົ້ນຂບວນ a [] ຂອງຂະ ໜາດ n.
2. ລອກລວງຂບວນແລະຊອກຫາຜົນລວມຂອງທຸກໆອົງປະກອບ. ກວດເບິ່ງວ່າ sum mod 2 ບໍ່ແມ່ນ 0, ສົ່ງຄືນບໍ່ຖືກຕ້ອງ.
3. ສ້າງແຖວ 2D.
4. ປັບປຸງແຖວ ທຳ ອິດເປັນຂອງແທ້ແລະຖັນ ທຳ ອິດຂອງແຕ່ລະແຖວແມ່ນບໍ່ຖືກຕ້ອງ.
5. ເລີ່ມຕົ້ນການຫລອກລວງແລະປັບປຸງສ່ວນ [] [] ເປັນຄວາມຈິງຖ້າຜົນລວມຂອງຊຸດຍ່ອຍໃດໆຕໍ່ໄປຈົນກວ່າ j-1 ຈະເທົ່າກັບ i. ອື່ນທີ່ບໍ່ຖືກຕ້ອງ.
6. ສົ່ງຄືນມູນຄ່າບູຊາສຸດທ້າຍໃນສ່ວນ ໜຶ່ງ.

ການຈັດຕັ້ງປະຕິບັດ ສຳ ລັບ Subset Sum Leetcode

ລະຫັດ C ++ ສຳ ລັບ Subset Sum

#include <bits/stdc++.h> 
using namespace std; 
  
bool Partiion(int a[], int n){  
    int sum = 0; 
    int i, j; 

    for(i=0; i<n; i++) 
        sum += a[i]; 

    if(sum%2 != 0) 
        return false; 

    bool part[sum / 2 + 1][n + 1]; 

    for (i = 0; i <= n; i++) 
        part[0][i] = true; 

    for (i = 1; i <= sum/2; i++) 
        part[i][0] = false; 

    for(i=1; i<=sum/2; i++){ 
        for(j=1; j<=n; j++){ 
            part[i][j] = part[i][j-1]; 
            if(i >= a[j-1]) 
                part[i][j] = part[i][j] || 
                             part[i - a[j-1]][j-1]; 
        } 
    }
    return part[sum/2][n];   
}  
  
int main(){  
    int a[] = {2, 3, 5};  
    int n = sizeof(a)/sizeof(a[0]);  
    if(Partiion(a, n))  
        cout << "Yes";  
    else
        cout << "No";  
    return 0;  
}
Yes

ລະຫັດ Java ສຳ ລັບ Subset Sum

import java.io.*; 
  
class equalSum{ 
    static boolean Partition (int a[], int n){ 
        int sum = 0; 
        int i, j; 
  
        for(i=0; i<n; i++) 
            sum += a[i]; 
  
        if(sum%2 != 0) 
            return false; 
  
        boolean part[][]=new boolean[sum/2+1][n+1]; 
  
        for (i = 0; i <= n; i++) 
            part[0][i] = true; 
  
        for (i = 1; i <= sum/2; i++) 
            part[i][0] = false; 
  
        for(i=1; i<=sum/2; i++){ 
            for(j=1; j<=n; j++){ 
                part[i][j] = part[i][j-1]; 
                if(i >= a[j-1]) 
                    part[i][j] = part[i][j] || 
                                 part[i - a[j-1]][j-1]; 
            } 
        }
        return part[sum/2][n];  
    } 
  
    public static void main (String[] args){ 
  
        int a[] = {2, 3, 5}; 
        int n = a.length; 
        if(Partition(a, n) == true) 
            System.out.println("Yes"); 
        else
            System.out.println("No"); 
    } 
}
Yes

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບ Subset Sum Leetcode

ຄວາມສັບສົນເວລາ

O (ຜົນລວມ * n) ບ່ອນທີ່ n ແມ່ນ ຈຳ ນວນເລກເຕັມໃນແຖວທີ່ໃຫ້ [a] ແລະຜົນລວມແມ່ນ ຈຳ ນວນທັງ ໝົດ ຂອງອົງປະກອບໃນແຖວທີ່ໃຫ້ [a].

ຄວາມສັບສົນໃນອະວະກາດ

O (ຜົນລວມ * n) ເນື່ອງຈາກວ່າພວກເຮົາໄດ້ໃຊ້ sum * n ເນື້ອທີ່ພິເສດ.

ເອກະສານ