LeetCode DayGreedy 알고리즘 2부

122. 주식을 사고 파는 가장 좋은 시기 II

price[i]가 i번째 날 특정 주식의 가격인 정수 배열 가격이 제공됩니다.

매일 주식을 매수 및/또는 매도하기로 결정할 수 있습니다. 귀하는 언제든지 주식을 최대 1주만 보유할 수 있습니다. 단, 구매 후 당일 바로 판매도 가능합니다.

당신이 달성할 수 있는 최대 수익을 찾아 돌려보세요.

예 1:

입력: 가격 = [7,1,5,3,6,4]
출력: 7
설명: 2일차 매수(가격 = 1), 3일차 매도(가격 = 5), 이익 = 5-1 = 4.
그런 다음 4일차에 매수(가격 = 3)하고 5일차에 매도(가격 = 6), 이익 = 6-3 = 3.
총 이익은 4 + 3 = 7입니다.
예시 2:

입력: 가격 = [1,2,3,4,5]
출력: 4
설명: 1일차 매수(가격 = 1), 5일차 매도(가격 = 5), 이익 = 5-1 = 4.
총 수익은 4입니다.
예시 3:

입력: 가격 = [7,6,4,3,1]
출력: 0
설명: 긍정적인 수익을 낼 수 있는 방법이 없으므로 최대 수익 0을 달성하기 위해 주식을 구매하지 않습니다.

제약사항:

1 <= 가격.길이 <= 3 * 104
0 <= 가격[i] <= 104
원본페이지

잘못된 코드

    public int maxProfit(int[] prices) {
        int profit = 0;
        int buy = Integer.MAX_VALUE;
        int sum = 0;
        int peek = 0;

        for(int i=0; i<prices.length; i++){
            int num = prices[i];
            if(num > buy && num > peek){
                profit = num - buy;
                peek = num;
            }
            else if((num>buy && num<peek) || num < buy){
                sum += profit;
                profit = 0;
                buy = num;
                peek = num;
            }

        }

        return sum+profit;
    }

int MAX_VALUE로 구매를 초기화했는데 업데이트하는 것을 잊어버리면 일부 오류가 발생할 수 있습니다.

이 문제를 수정하고 코드를 자릅니다

미세한 코드

    public int maxProfit(int[] prices) {
        if(prices.length <1){
            return 0;
        }
        int profit = 0;
        int buy = prices[0];
        int sum = 0;
        int peek = prices[0];

        for(int i=0; i<prices.length; i++){
            int num = prices[i];
            if( num > peek){
                profit = num - buy;
                peek = num;
            }
            else if(num<peek){
                sum += profit;
                profit = 0;
                buy = num;
                peek = num;
            }

        }
        sum += profit;
        return sum;
    }

1005. K 부정 후 배열의 합 최대화

정수 배열 nums와 정수 k가 주어지면 다음과 같은 방법으로 배열을 수정합니다.

인덱스 i를 선택하고 nums[i]를 -nums[i]로 바꾸세요.
이 프로세스를 정확히 k번 적용해야 합니다. 동일한 색인을 여러 번 선택할 수 있습니다.

이런 식으로 수정한 후 배열의 가능한 가장 큰 합계를 반환합니다.

예 1:

입력: nums = [4,2,3], k = 1
출력: 5
설명: 인덱스 1을 선택하면 숫자는 [4,-2,3]이 됩니다.
예시 2:

입력: nums = [3,-1,0,2], k = 3
출력: 6
설명: 인덱스(1, 2, 2)를 선택하면 숫자는 [3,1,0,2]가 됩니다.
예시 3:

입력: nums = [2,-3,-1,5,-4], k = 2
출력: 13
설명: 인덱스(1, 4)를 선택하면 숫자는 [2,3,-1,5,4]가 됩니다.

제약사항:

1 <= nums.length <= 10^4
-100 <= 숫자[i] <= 100
1 <= k <= 10^4
원본페이지

    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int change = nums[nums.length-1] >=0?0:nums.length-1;
        int sum = 0;
        for(int i=0; i<nums.length; i++){
            if(nums[i] < 0 && k>0){

                sum  -= nums[i];
                k--;
            }else{
                sum += nums[i];
            }
            // find the cross over 
            if(i>0 && nums[i-1]<=0 && nums[i]>0){
                if(-nums[i-1]>nums[i]){
                    change = i;
                }else{
                    change = i-1;
                }    
            }  
        }
        // k>nums.length so we need to run out of these k
        if(k>0){
            if(k%2!=0){
                //find the min abs value
                sum -= 2*Math.abs(nums[change]);
            }
        }
        return sum;
    }




</p>
<h2>
  
  
  55. 점프 게임
</h2>

<p>정수 배열 nums가 제공됩니다. 처음에는 배열의 첫 번째 인덱스에 위치하며 배열의 각 요소는 해당 위치에서의 최대 점프 길이를 나타냅니다.</p>

<p>마지막 인덱스에 도달할 수 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.</p>

<p>예 1:</p>

<p>입력: 숫자 = [2,3,1,1,4]<br>
출력: true<br>
설명: 인덱스 0에서 1로 1단계 점프한 다음 마지막 인덱스로 3단계 점프합니다.<br>
예시 2:</p>

<p>입력: 숫자 = [3,2,1,0,4]<br>
출력: 거짓<br>
설명: 무슨 일이 있어도 항상 인덱스 3에 도착합니다. 최대 점프 길이는 0이므로 마지막 인덱스에 도달할 수 없습니다.</p>

<p>제약사항:</p>

<p>1 <= nums.length <= 10^4<br>
0 <= 숫자[i] <= 10^5</p>
<h2>
  
  
  잘못된 코드
</h2>


<pre class="brush:php;toolbar:false">    public boolean canJump(int[] nums) {
        //find whether achive the last element so that we only can see whether can reach the second last element 
        for(int i=0; i<nums.length-1;){
            int size = nums[i];
            int next = 0;
            int nextVal = 0;
            if(size == 0){
                return false;
            }
            if(i+size >= nums.length){
                return true;
            }
            //find the max steps among the current step
            for(int j=0; j<=size; j++){
                // calculate max for both index and value
                if(i+j+nums[i+j]>next){
                    next = i+j+nums[i+j];
                }
            }
            i = next;
        }
        return true;
    }


</p>
<h2>
  
  
  잘못된 코드 2
</h2>


<pre class="brush:php;toolbar:false">    public boolean canJump(int[] nums) {
        if(nums.length==1){

            return true;
        }

        if(nums[0] == 0){
            return false;
        }

        for(int i=0; i<nums.length-1; i++){
            if(i+nums[i]>=nums.length-1){
                return true;
            }
        }

        return false;
    }

    public boolean canJump(int[] nums) {
        if(nums.length==1){      
            return true;
        }

        int range = 0;

        for(int i=0; i<=range; i++){
            range = Math.max(range, i+nums[i]);
            if(range >= nums.length-1){
                return true;
            }
        }

        return false;
    }

45. 점프 게임 II

길이가 n이고 인덱스가 0인 정수 배열이 제공됩니다. 처음에는 nums[0]에 위치합니다.

각 요소 nums[i]는 인덱스 i에서 앞으로 점프하는 최대 길이를 나타냅니다. 즉, nums[i]에 있는 경우 임의의 nums[i + j]로 이동할 수 있습니다. 여기서:

0 <= j <= nums[i] 및
i + j < ㄴ
nums[n - 1]에 도달하기 위한 최소 점프 횟수를 반환합니다. 테스트 사례는 nums[n - 1]에 도달할 수 있도록 생성됩니다.

예 1:

입력: 숫자 = [2,3,1,1,4]
출력: 2
설명: 마지막 인덱스에 도달하기 위한 최소 점프 횟수는 2입니다. 인덱스 0에서 1로 1단계 점프한 다음 마지막 인덱스까지 3단계 점프합니다.
예시 2:

입력: 숫자 = [2,3,0,1,4]
출력: 2

제약사항:

1 <= nums.length <= 104
0 <= 숫자[i] <= 1000
숫자[n - 1]에 도달할 수 있다는 것이 보장됩니다.

    public int jump(int[] nums) {
        if(nums.length == 1){
            return 0;
        }
        int step = 0;
        int range = 0;
        int preRange = 0;
        for(int i=0; i= nums.length-1){
                step++;
                break;
            }
            if(i == preRange){
                preRange = range;
                step++;
            }

        }
        return step;

    }





          

            
        
위 내용은 LeetCode DayGreedy 알고리즘 2부의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!