당신이 훌륭한 부모이고 자녀에게 쿠키를 주고 싶다고 가정해 보겠습니다. 단, 쿠키는 각 어린이에게 최대 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;
}
`
흔들기 시퀀스는 연속된 숫자 간의 차이가 양수와 음수 사이에서 엄격하게 교대로 나타나는 시퀀스입니다. 첫 번째 차이(존재하는 경우)는 양수일 수도 있고 음수일 수도 있습니다. 하나의 요소가 있는 시퀀스와 두 개의 같지 않은 요소가 있는 시퀀스는 사소하게 흔들리는 시퀀스입니다.
예를 들어 [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;
}
`
정수 배열 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
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 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
