LeetCode DayGreedy 알고리즘 1부

455. 쿠키 할당

당신이 훌륭한 부모이고 자녀에게 쿠키를 주고 싶다고 가정해 보겠습니다. 단, 쿠키는 각 어린이에게 최대 1개씩 주어야 합니다.

각 어린이 i는 탐욕 계수 g[i]를 갖고 있는데, 이는 어린이가 만족할 쿠키의 최소 크기입니다. 각 쿠키 j의 크기는 s[j]입니다. s[j] >= g[i]이면 쿠키 j를 자식 i에 할당할 수 있고 자식 i는 만족할 것입니다. 귀하의 목표는 콘텐츠 하위 항목 수를 최대화하고 최대 수를 출력하는 것입니다.

예 1:

입력: g = [1,2,3], s = [1,1]
출력: 1
설명: 귀하에게는 3명의 자녀와 2개의 쿠키가 있습니다. 세 아이의 탐욕지수는 1, 2, 3 입니다.
그리고 쿠키가 2개 있더라도 크기가 모두 1이므로 욕심 지수가 1인 아이만 콘텐츠로 만들 수 있습니다.
1을 출력해야 합니다.
예시 2:

입력: g = [1,2], s = [1,2,3]
출력: 2
설명: 귀하에게는 2명의 자녀와 3개의 쿠키가 있습니다. 두 아이의 욕심 요인은 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) {
// 널 포인터를 피하세요
if(g.길이 == 0 || s.길이 ==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, 7, 4, 9, 2, 5]는 차이(6, -3, 5, -7, 3)가 양수와 음수를 번갈아 표시하므로 흔들기 시퀀스입니다.
대조적으로, [1, 4, 7, 2, 5] 및 [1, 7, 4, 5, 5]는 흔들기 시퀀스가 ​​아닙니다. 첫 번째는 처음 두 차이가 양수이기 때문이 아니며, 두 번째는 마지막 차이가 0이기 때문이 아닙니다.
하위 시퀀스는 원래 시퀀스에서 일부 요소(0일 수도 있음)를 삭제하고 나머지 요소는 원래 순서대로 유지하여 얻습니다.

정수 배열 nums가 주어지면 nums의 가장 긴 흔들기 하위 시퀀스의 길이를 반환합니다.

예 1:

입력: 숫자 = [1,7,4,9,2,5]
출력: 6
설명: 전체 시퀀스는 차이(6, -3, 5, -7, 3)가 있는 흔들기 시퀀스입니다.
예시 2:

입력: 숫자 = [1,17,5,10,13,15,10,5,16,8]
출력: 7
설명: 이 길이를 달성하는 하위 시퀀스가 ​​여러 개 있습니다.
하나는 차이(16, -7, 3, -3, 6, -8)가 있는 [1, 17, 10, 13, 10, 16, 8]입니다.
예시 3:

입력: 숫자 = [1,2,3,4,5,6,7,8,9]
출력: 2

제약사항:

1 <= nums.length <= 1000
0

후속 조치: O(n) 시간 안에 이 문제를 해결할 수 있나요?

`
공개 int wiggleMaxLength(int[] nums) {
if(nums.length == 0){
0을 반환합니다;
}
정수 개수 = 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:

입력: 숫자 = [-2,1,-3,4,-1,2,1,-5,4]
출력: 6
설명: 하위 배열 [4,-1,2,1]의 합이 가장 큰 값은 6입니다.
예시 2:

입력: 숫자 = [1]
출력: 1
설명: 하위 배열 [1]에 가장 큰 합계 1이 있습니다.
예시 3:

입력: 숫자 = [5,4,-1,7,8]
출력: 23
설명: 하위 배열 [5,4,-1,7,8]의 합이 가장 큰 값은 23입니다.

제약사항:

1 <= nums.length <= 105
-104

후속 작업: O(n) 해법을 알아냈다면 더 미묘한 분할 정복 접근 방식을 사용하여 다른 해법을 코딩해 보세요.

`
공개 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(합 합계 = 숫자[i];
}그밖에{
합계 += 숫자[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 DayGreedy 알고리즘 1부의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!