JavaScript𞓜LeetCode 124;は78.サブセットを検索します.

22229 ワード

法1考え方:
  • 結果セット=現在の要素+現在の要素とその後の残りの要素のサブセットの組み合わせ+[]
  • トラップ:「現在の要素とその後の残りの要素のサブセットとの組み合わせ」:現在の要素は後の残りの要素のサブセットと組み合わされるべきであり、そうでないと重複した組み合わせ(および空のサブセットとの組み合わせ)が現れます.
  • /** 
    * @param {number[]} nums 
    * @return {number[][]} 
    */
    var subsets = function(nums) {    
        var i = 0, j = 0, temp = [], tmp = [], output = [];    
        for(i = 0; i < nums.length; i++) {        
            temp[0] = nums[i];        
            output.push(temp.concat([]));        
            tmp = realSubsets(nums.slice(i + 1));        
            for(j = 0; j < tmp.length; j++) {            
                output.push(temp.concat(tmp[j]));        
            }    
        }    
        output.push([]);    
        return output;
    };
    
    function realSubsets(nums) {    
        var i = 0, j = 0, temp = [], tmp = [], output = [];    
        for(i = 0; i < nums.length; i++) {        
            temp[0] = nums[i];        
            output.push(temp.concat([]));        
            tmp = realSubsets(nums.slice(i + 1));        
            for(j = 0; j < tmp.length; j++) {            
                output.push(temp.concat(tmp[j]));        
            }    
        }    
        return output;
    }
    法2で答えを見ました.
  • は、結果セット
  • に参加する要素に出会う.
  • は第二の要素に出会い、結果セットに参加する(結果集にあらかじめ[]を追加すると、この要素と空セットとの接続はそれ自体である).そしてそれを結果セットの他のサブセットに接続して新しいサブセットを構成します.
  • /** 
    * @param {number[]} nums 
    * @return {number[][]} 
    */
    var subsets = function(nums) {    
        var i = 0, j = 0, length = 0, temp = [], output = [];    
        output.push([]); // output ,            
        for(i = 0; i < nums.length; i++) {        
            temp[0] = nums[i];        
            length = output.length; //  temp output       ,   output        
            for(j = 0; j < length; j++) {            
                output.push(output[j].concat(temp));        
            }    
        }    
        return output;
    };
    法3:答えを振り返ってみました.
  • は、サブセットの長さ(要素の個数を含む)を終了条件とする
  • である.
    /** 
    * @param {number[]} nums 
    * @return {number[][]} 
    */
    var subsets = function(nums) {    
        var k = 0, temp = [], output = [];    
        for(k = 0; k <= nums.length; k++) { //      0 nums.length        
            backtrack(nums, temp, k, output);    
        }    
        return output;
    };
    
    function backtrack(nums, temp, k, output) {    
        if(temp.length == k) {        
            output.push(temp.concat([]));    
        }    
        var i = 0;    
        for(i = 0; i < nums.length; i++) {        
            temp.push(nums[i]);        
            backtrack(nums.slice(i + 1), temp, k, output);        
            temp.pop();    
        }
    }
    法4:2進数/01は答えの考えを見ました.
  • はnumsにおける対応する位置数が存在するかどうかを01列で表します.0は存在しない、1は存在を表します.存在する場合はtemp(numsのサブセットの一つ)に参加し、最後にtempをoutput
  • に追加する.
  • の1つの01列は、1つのサブセット
  • の状態を表しています.
    /** 
    * @param {number[]} nums 
    * @return {number[][]} 
    */
    var subsets = function(nums) {    
        var i = 0, j = 0, temp = [], output = [], state = "";    
        for(i = Math.pow(2, nums.length); i < Math.pow(2, nums.length + 1); i++) {        
            state = i.toString(2).slice(1);        
            for(j = 0; j < state.length; j++) {            
                if(state[j] == '1') {                
                    temp.push(nums[j]);            
                }        
            }        
            output.push(temp.concat([]));        
            temp = [];    
        }    
        return output;
    };