ເກມແຂ່ງລົດ Array ຜະລິດຕະພັນ  


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ ຕິຊົມ Adobe Amazon ຈາກຫນາກແອບເປີ asana BlackRock Bloomberg ByteDance Citadel DE Shaw eBay Evernote Expedia ເຟສບຸກ Goldman Sachs ກູໂກ Houzz Intel LinkedIn lyft Microsoft Morgan Stanley Nutanix Opera Oracle PayPal Paytm Qualtrics Salesforce SAP ServiceNow SnapChat ແຕກອອກ ຕາຕະລາງ Twitter Uber ສະແດງໃຫ້ເຫັນ VMware ຫ້ອງທົດລອງ Walmart Yahoo Yandex
Array Groupon LeetCode

ຖະແຫຼງການບັນຫາ  

ໃນສິນຄ້າ array ບັນຫາການປິດພວກເຮົາ ຈຳ ເປັນຕ້ອງສ້າງອາຄານທີ່ ith element ຈະເປັນຜົນຜະລິດຂອງທຸກໆອົງປະກອບໃນ array ທີ່ຍົກເວັ້ນແຕ່ອົງປະກອບທີ່ ith ຕໍາແຫນ່ງ.

ຍົກຕົວຢ່າງ  

ການປ້ອນຂໍ້ມູນ 

5

10 3 5 6 2

ຜົນຜະລິດ

180 600 360 300 900

ສູດການຄິດໄລ່ວິທີການແກ້ໄຂ A Array Puzzle  

ຂັ້ນຕອນທີ 1: ເອົາຜະລິດຕະພັນ vector ເພື່ອເກັບສິນຄ້າ.
a) ເລີ່ມຕົ້ນມັນໂດຍຜະລິດຕະພັນ vector

ຂັ້ນຕອນທີ 2: ກໍ່ສ້າງສອງອາຄານຊ້າຍ [] ແລະເບື້ອງຂວາ [], ຮ້ານຜະລິດຕະພັນເບື້ອງຊ້າຍຂອງສ່ວນປະກອບເຖິງເບື້ອງຊ້າຍຂອງດັດຊະນີ ith ໃນແຖວ. ຜະລິດຕະພັນທີ່ຖືກຕ້ອງຂອງຜະລິດຕະພັນຂອງສ່ວນປະກອບທີ່ຢູ່ເບື້ອງຂວາຂອງດັດຊະນີ ith.

ກ. ເລີ່ມຕົ້ນອົງປະກອບ ທຳ ອິດຂອງຊ້າຍເປັນ 1 ແລະອົງປະກອບສຸດທ້າຍຂອງຂວາຄື 1.
ຂ. ຈາກເບື້ອງຊ້າຍ, ປັບປຸງສ່ວນປະກອບຂອງ ith ຊ້າຍຂອງຜະລິດຕະພັນທີ່ມີຜະລິດຕະພັນຂອງອົງປະກອບ i-1 ຂອງອາເລທີ່ໃຫ້ກັບອົງປະກອບກ່ອນຫນ້າຂອງຂບວນຊ້າຍ. (ຢູ່ເບື້ອງຊ້າຍ [i] = ຍັງເຫຼືອ [i-1] * ອາເລ [i-1]). ໂດຍການເຮັດສິ່ງນີ້, ມັນເກັບຮັກສາຜະລິດຕະພັນຈົນເຖິງດັດຊະນີກ່ອນ ໜ້າ ນີ້ໃນແຖວຊ້າຍຈາກຂບວນທີ່ໃຫ້ໄວ້.
ຄ. ຈາກຂວາ, ປັບປຸງອົງປະກອບຂອງ ith ທີ່ຖືກຕ້ອງກັບຜະລິດຕະພັນຂອງອົງປະກອບ i + 1 ຂອງ array ທີ່ໃຫ້ກັບອົງປະກອບຕໍ່ໄປຂອງ array ທີ່ຖືກຕ້ອງ. (ຖືກຕ້ອງ [i] = ຖືກຕ້ອງ [i + 1] * ອາເລ [i + 1]). ໂດຍການເຮັດສິ່ງນີ້, ມັນເກັບຮັກສາຜະລິດຕະພັນຈົນເຖິງດັດຊະນີກ່ອນ ໜ້າ ນີ້ໃນແຖວຊ້າຍຈາກຂບວນທີ່ໃຫ້ໄວ້.

ເບິ່ງ
ປ່ຽນອາເລເປັນແຟຊັ່ນ Zig-Zag

ຂັ້ນຕອນທີ 3:  ຜະລິດຕະພັນຍົກເວັ້ນອົງປະກອບປັດຈຸບັນຈະຄືກັນກັບຜະລິດຕະພັນຂອງອົງປະກອບຂບວນຊ້າຍແລະຂວາ.
a) ແຖວຜະລິດຕະພັນຈະເປັນ, ຜະລິດຕະພັນ [i] = ຊ້າຍ [i] * ຖືກຕ້ອງ [i].

ຄໍາອະທິບາຍສໍາລັບການແກ້ໄຂປິດສະ Array ຜະລິດຕະພັນ  

ຫນ້າທໍາອິດ, ລອກເອົາອາເລໃນຕອນເລີ່ມຕົ້ນແລະເກັບຮັກສາຜະລິດຕະພັນຂອງທຸກໆອົງປະກອບທີ່ຜ່ານມາສໍາລັບແຕ່ລະ i. ຕອນນີ້ຂ້າມແຖວຈາກທາງຫລັງແລະເກັບຍອດລວມຈາກເບື້ອງສຸດແລະເກັບສິນຄ້າຂອງສ່ວນປະກອບທັງ ໝົດ ຫລັງຈາກອົງປະກອບນັ້ນ.

ປະໄວ້ [] = {10, 30, 150, 900, 1800}

ຖືກຕ້ອງ [] = {1800, 180, 60, 12, 2}

ຕອນນີ້ການ ນຳ ໃຊ້ອາເລເຫລົ່ານີ້ຊອກຫາຜະລິດຕະພັນຂອງທຸກໆອົງປະກອບໃນອາເລທີ່ຍົກເວັ້ນແຕ່ອົງປະກອບທີ່ ith ຕໍາແຫນ່ງ.

ຜະລິດຕະພັນ [] = {180, 600, 360, 300, 900}

ການປະຕິບັດ  

ໂຄງການ C ++ ສຳ ລັບການແກ້ໄຂປິດສະ Array ຜະລິດຕະພັນ

#include <bits/stdc++.h>
using namespace std;
int main()
{
  
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++)
  {
      cin>>arr[i];
  }
  int left[n],right[n];
  vector<int> product;
  left[0] = 1; //initialize the first element as 1
  for(int i=1;i<n;i++)
  {
     left[i]=left[i-1]*arr[i-1]; // store the product till just previous index
  }
  right[n-1]=1;//initialzie the first element as 1
  for(int i=n-2;i>=0;i--)
  {
     right[i]=right[i+1]*arr[i+1]; //store the product till just next index
  } 
  for(int i=0;i<n;i++)
  {
     product.push_back(left[i]*right[i]);
  }
  for(int i=0;i<n;i++)//display the product array
  {
     cout<<product[i]<<"  "; 
  }
  return 0;
}

Java Program ສຳ ລັບການແກ້ໄຂເກມ Array Puzzle

import java.util.Arrays;
import java.util.Scanner;
import java.util.Vector;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int left[] = new int [n];
        int right[] = new int [n];
        Vector<Integer> product = new Vector<Integer>(); 
        left[0] = 1; //initialize the first element as 1
        for(int i=1;i<n;i++)
        {
           left[i]=left[i-1]*arr[i-1]; // store the product till just previous index
        }
        right[n-1]=1;//initialzie the first element as 1
        for(int i=n-2;i>=0;i--)
        {
           right[i]=right[i+1]*arr[i+1]; //store the product till just next index
        } 
        for(int i=0;i<n;i++)
        {
           product.add(left[i]*right[i]);
        }
        for(int i=0;i<n;i++)//display the product array
        {
           System.out.print(product.get(i)+"  "); 
        }
    }
}
5
10 3 5 6 2
180  600  360  300  900

ການວິເຄາະຄວາມສັບສົນ  

ຄວາມສັບສົນເວລາ

ເບິ່ງ
ຂຽນລະຫັດເພື່ອ ກຳ ນົດວ່າຕົ້ນໄມ້ສອງຕົ້ນມີລັກສະນະຄືແນວໃດ

O (n) ບ່ອນທີ່ n ແມ່ນຈໍານວນຂອງອົງປະກອບທີ່ມີຢູ່ໃນອາເລ. ໃນທີ່ນີ້ພວກເຮົາພຽງແຕ່ຜ່ານ 3 ຄັ້ງແລະຊອກຫາແຖວຂອງຜະລິດຕະພັນ.

ຄວາມສັບສົນໃນອະວະກາດ

O (n) ເພາະວ່າພວກເຮົາ ນຳ ໃຊ້ອາຄານຊ້າຍແລະຂວາ ສຳ ລັບເກັບຮັກສາຜະລິດຕະພັນຂອງອົງປະກອບ.

ເອກະສານ