今日はケビンのアルゴリズムの旅の14日目です。LeetCode問題78を説明し、中々難しい問題で金曜日を締めくくります。
日々の笑い
嗜好品に2,000ドルも使ったのですから、それだけの価値はあります。
日用品に200ドルも使って、破産しそうです。
問題
重複要素のない整数の配列 nums が与えられた場合、その配列のすべての部分集合を返します。
注意：解集合に重複する部分集合を含めることはできません。
例
入力： nums = [1,2,3] 出力： [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]。
問題解決のためのアイデア
再帰的
配列を直接反復処理し、数値が発生したときにすべてのサブセットを新しいサブセットに追加します。
注意 空の集合 [] も部分集合であることを忘れないでください。
図は以下の通りです。
コードの実装
//go
func subsets(nums []int) [][]int {
arr := make([][]int, 0) // 結果を記録する
arr = append(arr, []int{}) // 最初に空のセットを加える
for i := 0; i < len(nums); i++ { // 配列をトラバースする
tempArr := make([][]int, 0) // 一時保管
for _, c := range arr { // 既存のサブセットを反復する
temp := make([]int, 0) // 一時保管
temp = append(temp, c...) // サブセットを追加する
temp = append(temp, nums[i]) // 新しい要素を加える
tempArr = append(tempArr, temp) // 一時記憶装置に追加する
}
for _, c := range tempArr { // 反復して結果を預ける
arr = append(arr, c)
}
}
return arr
}
//java
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> output = new ArrayList();
output.add(new ArrayList<Integer>());
for (int num : nums) {
List<List<Integer>> newSubsets = new ArrayList();
for (List<Integer> curr : output) {
newSubsets.add(new ArrayList<Integer>(curr){{add(num);}});
}
for (List<Integer> curr : newSubsets) {
output.add(curr);
}
}
return output;
}
}
念のため：
ここに示されたコードはLeetCodeを通して実行されました！
ちょっとおしゃべりをしているところです。
多くの人が良い習慣を身につけたいと願っていますが、ほとんどの人は3分間人間です。そのため、次のような計画を立てることにしました。
一緒にアルゴリズムを学び、ボーナスを受け取ってください！
参加様式：
また、多くの友人と「会う」こともできます。
団結し、共に学び、共に向上すること！
パンチカードのルールは
"Clock in XXX Days" にコメントを残す 友達と共有する.
報酬
連続出勤1日につき $6.60の レッドパケットを私にご連絡ください！
連続出勤1日ごとに $16.60の レッドパケットをお渡しします！
66.60ドルの レッドパケットをご希望の方はご連絡ください！
