കെ നെഗേഷൻസ് ലീറ്റ്കോഡ് പരിഹാരത്തിന് ശേഷം അറേയുടെ എണ്ണം വർദ്ധിപ്പിക്കുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ
അറേ ലീട്ട് കോഡ്

കെ നെഗറ്റീവ് ലീഗ്‌കോഡ് പരിഹാരത്തിനുശേഷം ഈ ശ്രേണി വിപുലീകരിക്കുക എന്നതിലാണ് ഈ കുറിപ്പ്

പ്രശ്നം പ്രസ്താവന

പ്രശ്‌നത്തിൽ ”കെക്ക് ശേഷം അറേയുടെ എണ്ണം വർദ്ധിപ്പിക്കുക നിർദേശങ്ങൾ”ഞങ്ങൾക്ക് ഒരു അറേ അറയും ഒരു മൂല്യവും നൽകിയിരിക്കുന്നു. അറേയിൽ പൂർണ്ണസംഖ്യകൾ അടങ്ങിയിരിക്കുന്നു. നമുക്ക് arr [i] ന്റെ മൂല്യം -arr [i] K തവണയിലേക്ക് മാറ്റാൻ കഴിയും. I ന്റെ മൂല്യം നമുക്ക് ആവർത്തിക്കാം. ഈ രീതി കെ തവണ പ്രയോഗിച്ചുകൊണ്ട് അറേ തുക പരമാവധി വർദ്ധിപ്പിക്കുകയും പരിഷ്‌ക്കരിച്ചതിന് ശേഷം മൊത്തം അറേ തുക തിരികെ നൽകുകയും ചെയ്യുക എന്നതാണ് ഞങ്ങളുടെ ചുമതല.

ഉദാഹരണം

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

വിശദീകരണം:

കെ നെഗേഷൻസ് ലീറ്റ്കോഡ് പരിഹാരത്തിന് ശേഷം അറേയുടെ എണ്ണം വർദ്ധിപ്പിക്കുക

തന്നിരിക്കുന്ന അറേയിൽ ഞങ്ങൾ -3 മുതൽ 3 വരെയും -4 മുതൽ 4 വരെയും മാറ്റിസ്ഥാപിക്കുമ്പോൾ അറേയുടെ ആകെ തുക 13 ആയി മാറുന്നു.

സമീപനം

ഞങ്ങളുടെ ചുമതല അറേ തുക പരമാവധി വർദ്ധിപ്പിക്കുക ഒപ്പം നിരയിൽ പോസിറ്റീവ്, നെഗറ്റീവ് ഘടകങ്ങൾ അടങ്ങിയിരിക്കുന്നു, അതിനാൽ ഞങ്ങൾ ഈ ഘട്ടങ്ങൾ പിന്തുടരും:

  1. ഏറ്റവും ചെറിയ മൂല്യത്തിന്റെ ചിഹ്നം മാറ്റാൻ ആഗ്രഹിക്കുന്നതിനാൽ ആദ്യം നമ്മൾ അറേ അടുക്കും. ഇത് വർദ്ധിപ്പിക്കുന്നതിന് ഉപയോഗപ്രദമാകും അറേ തുക.
  2.  ഇപ്പോൾ നമ്മൾ പരമാവധി കെ യുടെ ചിഹ്നം മാറ്റും നെഗറ്റീവ് സംഖ്യകൾ.
  3. അതേസമയം, അറേയിൽ പൂജ്യം ഉണ്ടോ ഇല്ലയോ എന്നും ഞങ്ങൾ ട്രാക്ക് ചെയ്യും.
  4. ഇത് കണ്ടെത്തു അറേ തുക.
  5. ഞങ്ങളുടെ അവസാന ഉത്തരം ആയിരിക്കും അറേ തുക എങ്കിൽ:
    1. കെ യുടെ മൂല്യം പൂജ്യമായിത്തീരുന്നു.
    2. അറേയിൽ പൂജ്യം ഉണ്ട്. ഇതുവഴി പൂജ്യത്തിന്റെ അടയാളം മാറ്റിക്കൊണ്ടിരിക്കും.
    3. നെഗറ്റീവ് മൂല്യങ്ങളുടെ അടയാളം മാറ്റിയതിന് ശേഷം കെ യുടെ മൂല്യം റീമയിംഗ് ചെയ്യുന്നത് തുല്യമാണ്. ഇതുവഴി നമ്മൾ നെഗറ്റീവ് നമ്പറിലേക്ക് ഒരു പോസിറ്റീവ് സംഖ്യ ഉണ്ടാക്കുകയും അത് വീണ്ടും പോസിറ്റീവ് ആക്കുകയും ചെയ്യും.
  6. ഇവിടെ K യുടെ മൂല്യം നെഗറ്റീവ് ആയതിനാൽ‌ ഞങ്ങൾ‌ അതിന്റെ ചിഹ്നം മാറ്റും ഏറ്റവും ചെറിയ പോസിറ്റീവ് നമ്പർ കെ തവണ. ഇത് നെഗറ്റീവ് ആക്കും. ഇപ്പോൾ ഞങ്ങൾ പുതിയ അറേ തുക നൽകും.

കെ നെഗേഷൻസ് ലീറ്റ്കോഡ് പരിഹാരത്തിന് ശേഷം അറേ തുക വർദ്ധിപ്പിക്കുന്നതിനുള്ള കോഡ്

സി ++ കോഡ്

#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

കെ നെഗേഷൻസ് ലീറ്റ്കോഡ് പരിഹാരത്തിന് ശേഷം അറേയുടെ പരമാവധി തുകയുടെ സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

മുകളിലുള്ള കോഡിന്റെ സമയ സങ്കീർണ്ണതയാണ് O (n) കാരണം ഞങ്ങൾ നൽകിയ അറേയിൽ ഒരു തവണ മാത്രമേ സഞ്ചരിക്കുകയുള്ളൂ.

സ്ഥല സങ്കീർണ്ണത

മുകളിലുള്ള കോഡിന്റെ സ്ഥല സങ്കീർണ്ണത O (1) കാരണം ഉത്തരങ്ങൾ‌ സംഭരിക്കുന്നതിന് ഞങ്ങൾ‌ ഒരു വേരിയബിൾ‌ മാത്രം ഉപയോഗിക്കുന്നു.

അവലംബം