Funny Solution without DFS,Just random


  • 0
    7

    because only 15 matchstick

    so,just random

    • first, we look it's can split two array: a & b
    • second, look a & b can split two array

    easy and funny : ) the time just guess. obviously it's be sure

    class Solution {
        public:
        bool makesquare(vector<int>& nums) {
            int total = 0;
            for_each(nums.begin(), nums.end(), [&](const int num){
                total += num;
            });
            int target = total/4;
            if(target * 4 != total || total == 0) return false;
            
            srand((int)time(NULL));
            vector<int> a;
            vector<int> b;
            int time = 500;
            while(time--){
                if(!canBin(nums, a, b, target * 2)) continue;
                vector<int> aa,bb;
                if(canBin(a, aa, bb, target) && canBin(b, aa, bb, target)) return true;
            }
            
            
            return false;
        }
        
        bool canBin(vector<int>&nums,vector<int>& a, vector<int>& b, int target){
            a.clear();
            b.clear();
            
            int suma = 0,sumb = 0;
            for(int i=0;i<nums.size();i++){
                if(i%2) a.push_back(nums[i]),suma+=nums[i];
                else b.push_back(nums[i]),sumb+=nums[i];
            }
            
            if(suma == sumb) return true;
            int tmp = 0;
            int time = 10;
            while(time--){
                if(suma == sumb) break;
                
                if(rand()%2 && a.size()>0 && b.size()>0){ // change item value, make suma equal sumb
                    int aidx = rand()%a.size();
                    int bidx = rand()%b.size();
                    
                    suma = suma - a[aidx] + b[bidx];
                    sumb = sumb - b[bidx] + a[aidx];
                    tmp = a[aidx];
                    a[aidx] = b[bidx];
                    b[bidx] = tmp;
                } else{  // add & remove item value . make suma equal sumb
                    if(suma > sumb){
                        tmp = a.back();
                        b.push_back(a.back());
                        a.pop_back();
                        sumb += tmp;
                        suma -= tmp;
                    } else{
                        tmp = b.back();
                        a.push_back(b.back());
                        b.pop_back();
                        suma += tmp;
                        sumb -= tmp;
                    }
                }
                    
            }
            
            return suma == sumb;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.