LeetCode Day貪欲なアルゴリズム パート 1

455. クッキーの割り当て

あなたは素晴らしい親で、子供たちにクッキーをあげたいと考えているとします。ただし、各子供に与えるクッキーは最大でも 1 つまでにしてください。

各子 i には貪欲係数 g[i] があり、これは子が満足する Cookie の最小サイズです。各クッキー j のサイズは s[j] です。 s[j] >= g[i] の場合、クッキー j を子 i に割り当てることができ、子 i は満足します。あなたの目標は、コンテンツの子の数を最大化し、最大数を出力することです。

例 1:

入力: g = [1,2,3]、s = [1,1]
出力: 1
説明: あなたには 3 人の子供と 2 つのクッキーがいます。 3 人の子供の貪欲因子は 1、2、3 です。
また、クッキーが 2 つありますが、サイズは両方とも 1 なので、貪欲係数が 1 のコンテンツを持つ子しか作成できません。
1 を出力する必要があります。
例 2:

入力: g = [1,2]、s = [1,2,3]
出力: 2
説明: あなたには 2 人の子供と 3 つのクッキーがあります。 2 人の子供の貪欲係数は 1、2 です。
クッキーが 3 つあり、そのサイズは子供たち全員を満足させるのに十分な大きさです。
2 を出力する必要があります。

制約:

1 0 1

    public int findContentChildren(int[] g, int[] s) {
        // avoid null pointer
        if(g.length == 0 || s.length ==0){
            return 0;
        }
        // 2 * nlogn
        Arrays.sort(g);
        Arrays.sort(s);

        int i = 0;
        int j = 0;
        int count = 0;
        while(i < g.length && j < s.length){
            if(g[i] <= s[j]){
                i++;
                j++;
                count++;
            } else{
                j++;
            }
        }
        return count;   
    }

時刻: n`logn

ループの別のバージョン
`
public int findContentChildren(int[] g, int[] s) {
// null ポインタを回避します
if(g.length == 0 || s.length ==0){
0 を返す;
}
// 2 * nlogn
Arrays.sort(g);
Arrays.sort(s);

    int j = 0;
    int count = 0;
    for(int i=0; i<s.length && j<g.length; i++){
        if(s[i] >= g[j]){
            j++;
            count++;
        }
    }
    return count;   
}

`

376. ウィグルサブシーケンス

ウィグル シーケンスは、連続する数値の差が正と負の間で厳密に交互になるシーケンスです。最初の違い (存在する場合) は、正または負のいずれかになります。 1 つの要素を持つシーケンスと 2 つの等しくない要素を持つシーケンスは、自明のことながらウィグル シーケンスです。

たとえば、[1, 7, 4, 9, 2, 5] は、差分 (6、-3、5、-7、3) が正と負を交互に繰り返すため、小刻みなシーケンスです。
対照的に、[1, 4, 7, 2, 5] と [1, 7, 4, 5, 5] はウィグル シーケンスではありません。 1 つ目は、最初の 2 つの差が正であるためではありません。2 つ目は、最後の差がゼロであるためではありません。
サブシーケンスは、元のシーケンスからいくつかの要素 (おそらくゼロ) を削除し、残りの要素を元の順序のままにすることによって取得されます。

整数配列 nums を指定すると、nums の最長のウィグル サブシーケンスの長さを返します。

例 1:

入力: nums = [1,7,4,9,2,5]
出力: 6
説明: シーケンス全体は、差異 (6、-3、5、-7、3) のあるウィグル シーケンスです。
例 2:

入力: nums = [1,17,5,10,13,15,10,5,16,8]
出力: 7
説明: この長さに達するサブシーケンスがいくつかあります。
1 つは [1, 17, 10, 13, 10, 16, 8] で、差分 (16、-7、3、-3、6、-8) があります。
例 3:

入力: nums = [1,2,3,4,5,6,7,8,9]
出力: 2

制約:

1 0

フォローアップ: O(n) 時間以内に解決できますか?

`
public int wggleMaxLength(int[] nums) {
if(nums.length == 0){
0 を返す;
}
int カウント = 1;
int preFlag = 0;
int pre = nums[0];

    for(int i=1; i<nums.length; i++){
        if(nums[i]-nums[i-1] != 0){
            int flag = (nums[i]-nums[i-1])/Math.abs(nums[i]-nums[i-1]);

            if(flag == -preFlag || preFlag == 0){
                preFlag = flag;
                count++;
            }
        }
    }
    return count;
}

`

53. 最大サブアレイ

整数配列 nums を指定して、
を見つけます 部分配列
最大の合計を求め、その合計を返します。

例 1:

入力: nums = [-2,1,-3,4,-1,2,1,-5,4]
出力: 6
説明: 部分配列 [4,-1,2,1] の合計は最大の 6 です。
例 2:

入力: nums = [1]
出力: 1
説明: 部分配列 [1] の合計は最大の 1 です。
例 3:

入力: nums = [5,4,-1,7,8]
出力: 23
説明: 部分配列 [5,4,-1,7,8] の合計は最大の 23 です。

制約:

1 -104

フォローアップ: O(n) ソリューションを見つけたら、より巧妙な分割統治アプローチを使用して別のソリューションをコーディングしてみてください。

`
public int maxSubArray(int[] nums) {
if(nums.length == 0){
0 を返す;
}
int max = Integer.MIN_VALUE;
int sum = Integer.MIN_VALUE;
for(int i=0; i if(数値[i] > 0){
if(合計 sum = nums[i];
}その他{
合計 += nums[i];

            }
            max = Math.max(max, sum);
        }else{
            if(sum<0){
                sum = nums[i];
            }else{
            sum += nums[i];
            }
            max = Math.max(max, sum);
        }
    }
    return max;

}

`

improve code
`
public int maxSubArray(int[] nums) {
if(nums.length == 0){
return 0;
}
int max = Integer.MIN_VALUE;
int sum = Integer.MIN_VALUE;
for(int i=0; i if(sum < 0){
sum = nums[i];
}else{
sum += nums[i];

            }
            max = Math.max(max, sum);
    }
    return max;

}

`

Another way for greedy
`
public int maxSubArray(int[] nums) {
if(nums.length == 0){
return 0;
}
int max = Integer.MIN_VALUE;
// int sum = Integer.MIN_VALUE;

    int sum = 0;
    for(int i=0; i<nums.length; i++){
        sum+= nums[i];
        if(max < sum){
            max = sum;
        }
        if(sum <0){
            sum = 0;
        }
            // if(sum < 0){
            //     sum = nums[i];
            // }else{
            //     sum += nums[i];

            // }
            // max = Math.max(max, sum);

    }
    return max;

}

`

以上がLeetCode Day貪欲なアルゴリズム パート 1の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。