ពង្រីកផលបូកនៃអារេបន្ទាប់ពីដំណោះស្រាយ K កិច្ចចរចា Leetcode


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon
អារេ LeetCode

ការប្រកាសនេះមានលើផលបូកអតិបរិមានៃអារេបន្ទាប់ពីការចរចា K ដំណោះស្រាយឡេឡេលេខកូដ

សេចក្តីថ្លែងការណ៍បញ្ហា

ក្នុងបញ្ហា "បង្កើនផលបូកនៃអារេបន្ទាប់ពីខេ ការចរចា"យើងត្រូវបានផ្តល់អារេមកដល់និងតម្លៃឃ។ អារេមានតំលៃចំនួនគត់។ យើងអាចផ្លាស់ប្តូរតម្លៃនៃការមកដល់ [អាយ] ទៅ -arr [i] K ដង។ យើងអាចធ្វើម្តងទៀតនូវតម្លៃរបស់ i ។ ភារកិច្ចរបស់យើងគឺបង្កើនផលបូកអារេដោយអនុវត្តវិធីនេះ K ដងនិងប្រគល់ផលបូកអារេសរុបបន្ទាប់ពីការកែប្រែ។

ឧទាហរណ៍

arr = [2,-3,-1,5,-4], k=2
13

ការពន្យល់:

ពង្រីកផលបូកនៃអារេបន្ទាប់ពីការចរចារ K ដំណោះស្រាយឡេឡេលេខកូដ

នៅក្នុងអារេដែលបានផ្តល់ឱ្យនៅពេលយើងនឹងជំនួស -3 ទៅ 3 និង -4 ទៅ 4 បន្ទាប់មកចំនួនសរុបនៃអារេក្លាយជា 13 ។

វិធីសាស្រ្ត

ភារកិច្ចរបស់យើងគឺ ពង្រីកផលបូកអារេ និងអារេមានទាំងធាតុវិជ្ជមាននិងអវិជ្ជមានដូច្នេះយើងនឹងអនុវត្តតាមជំហានទាំងនេះ៖

  1. ដំបូងយើងនឹងតម្រៀបអារេពីព្រោះយើងចង់ផ្លាស់ប្តូរសញ្ញានៃតម្លៃតូចបំផុត។ វានឹងមានប្រយោជន៍ក្នុងការពង្រីកឯកសារ អារេបូក.
  2.  ឥឡូវនេះយើងនឹងផ្លាស់ប្តូរសញ្ញាភាគច្រើននៅ K លេខអវិជ្ជមាន.
  3. ទន្ទឹមនឹងនេះយើងក៏នឹងតាមដានប្រសិនបើសូន្យមានវត្តមាននៅក្នុងអារេរឺអត់។
  4. ស្វែងរក អារេបូក.
  5. ចម្លើយចុងក្រោយរបស់យើងគឺ អារេបូក ប្រសិនបើ:
    1. តម្លៃរបស់ K ក្លាយជាលេខសូន្យ។
    2. សូន្យមានវត្តមាននៅក្នុងអារេ។ វិធីនេះយើងនឹងបន្តផ្លាស់ប្តូរសញ្ញាសូន្យ។
    3. តម្លៃដែលនៅសេសសល់របស់ K បន្ទាប់ពីផ្លាស់ប្តូរសញ្ញានៃតម្លៃអវិជ្ជមានគឺ។ វិធីនេះយើងនឹងធ្វើលេខវិជ្ជមានទៅលេខអវិជ្ជមានហើយបន្ទាប់មកវានឹងធ្វើឱ្យវាវិជ្ជមានម្តងទៀត។
  6. នៅទីនេះតម្លៃរបស់ K គឺអវិជ្ជមានដូច្នេះយើងនឹងផ្លាស់ប្តូរសញ្ញានៃ លេខវិជ្ជមានតូចបំផុត ដង K ។ នេះនឹងធ្វើឱ្យវាអវិជ្ជមាន។ ឥឡូវនេះយើងនឹងប្រគល់ផលបូកអារេថ្មី។

លេខកូដសំរាប់ផលបូកនៃអារេបន្ទាប់ពីការចរចារ K ដំណោះស្រាយឡេឡេលេខកូដ

លេខកូដ C ++

#include <bits/stdc++.h> 
using namespace std; 
    int largestSumAfterKNegations(vector<int>& A, int K) {
        sort(A.begin(),A.end());
        int sum=0,neg=0,zero=0;
        for(int i=0;i<A.size();i++)
        {
            if(A[i]==0)
                zero=1;
            if(A[i]<0&&K>0)
            {  A[i]=-A[i];K--;}
            sum+=A[i];
        }
        if(zero||K==0||K%2==0)
         return sum;
        else
            return sum-2*(*min_element(A.begin(),A.end()));       
    }
int main() 
{ 
 vector<int> arr = {2,-3,-1,5,-4}; 
 int k=2;
 cout<<largestSumAfterKNegations(arr,k)<<endl; 
 return 0;
}
13

កូដចាវ៉ា

import java.util.Arrays; 
public class Tutorialcup {
    public static int largestSumAfterKNegations(int[] A, int K) {
        Arrays.sort(A);
        int sum=0,neg=0,zero=0;
        for(int i=0;i<A.length;i++)
        {
            if(A[i]==0)
                zero=1;
            if(A[i]<0&&K>0)
            {  A[i]=-A[i];K--;}
            sum+=A[i];
        }
        if(zero==1||K==0||K%2==0)
         return sum;
        else
            return sum-2*(Arrays.stream(A).min().getAsInt());      
    }
  public static void main(String[] args) {
    int [] arr = {2,-3,-1,5,-4}; 
    int k=2;
    int ans=  largestSumAfterKNegations(arr,k);
    System.out.println(ans);
  }
}
13

ការវិភាគស្មុគស្មាញនៃផលបូកនៃអារេអតិបរមាបន្ទាប់ពីការចរចា K ដំណោះស្រាយឡេឡេកូដ

ភាពស្មុគស្មាញពេលវេលា

ពេលវេលាស្មុគស្មាញនៃលេខកូដខាងលើគឺ អូរ (n) ពីព្រោះយើងកំពុងឆ្លងកាត់អារេដែលបានផ្តល់អោយតែម្តង។

ភាពស្មុគស្មាញនៃលំហ

ភាពស្មុគស្មាញចន្លោះនៃលេខកូដខាងលើគឺ ឱ (១) ពីព្រោះយើងកំពុងប្រើតែអថេរដើម្បីរក្សាទុកចម្លើយ។

ឯកសារយោង