ວິທີແກ້ໄຂ Leetcode ສູງສຸດ 69 ຕົວ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ HRT
ຄະນິດສາດ

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

ໃນປັນຫານີ້, ພວກເຮົາໄດ້ຮັບເລກທີ່ປະກອບດ້ວຍຕົວເລກ 6 ຫຼື 9. ພວກເຮົາສາມາດທົດແທນຕົວເລກ ໜຶ່ງ ຂອງຕົວເລກນີ້ແລະປ່ຽນເລກນີ້ໃຫ້ເປັນຕົວເລກອື່ນ. ຕົວຢ່າງ: ພວກເຮົາສາມາດທົດແທນເລກ 6 ຫາ 9 ໄດ້ຫຼືພວກເຮົາສາມາດທົດແທນເລກ 9 ເຖິງ 6. ພວກເຮົາຕ້ອງໄດ້ຜະລິດ ຈຳ ນວນສູງສຸດທີ່ພວກເຮົາສາມາດໄດ້ຮັບໂດຍສ່ວນໃຫຍ່ ໜຶ່ງ ທີ່ທົດແທນ.

ຍົກຕົວຢ່າງ

num = 9669
9969

ຄໍາອະທິບາຍ:

ປ່ຽນຜົນໄດ້ຮັບຕົວເລກ ທຳ ອິດໃນປີ 6669.
ການປ່ຽນແປງຜົນຂອງຕົວເລກທີສອງໃນປີ 9969.
ຄ້າຍຄືກັນການປ່ຽນແປງຜົນຂອງຕົວເລກທີສາມໃນປີ 9699.
ການປ່ຽນແປງຕົວເລກສີ່ຕົວເລກໃນປີ 9666.
ຈຳ ນວນສູງສຸດແມ່ນ 9969.

9996
9999

ຄໍາອະທິບາຍ:

ການປ່ຽນແປງຕົວເລກສຸດທ້າຍ 6 ຫາ 9 ຜົນໄດ້ຮັບໃນຈໍານວນສູງສຸດ.

ວິທີການ

ຍ້ອນວ່າພວກເຮົາສາມາດທົດແທນຕົວເລກ ໜຶ່ງ ເພື່ອເຮັດໃຫ້ຕົວເລກສູງສຸດ, ສິ່ງ ໜຶ່ງ ທີ່ພວກເຮົາສາມາດເຂົ້າໃຈໄດ້ທີ່ນີ້ແມ່ນ, ພວກເຮົາຄວນຈະປ່ຽນແທນ 6 ຫາ 9 ເທົ່ານັ້ນ, ເພາະວ່າຕົວແທນ 9 ເຖິງ 6 ຈະເຮັດໃຫ້ຕົວເລກນ້ອຍລົງ.
ສິ່ງອື່ນທີ່ພວກເຮົາສາມາດເຂົ້າໃຈຢູ່ທີ່ນີ້ແມ່ນ, ພວກເຮົາຄວນປ່ຽນຕົວເລກເບື້ອງຊ້າຍທີ່ເປັນໄປໄດ້. ຂໍໃຫ້ເຂົ້າໃຈສິ່ງນີ້ດ້ວຍຕົວຢ່າງ.

ສົມມຸດວ່າພວກເຮົາມີຕົວເລກທີ່ມອບໃຫ້, 6666
ພວກເຮົາຕ້ອງທົດແທນຕົວເລກ ໜຶ່ງ ຈາກ 6 ຫາ 9 ເຊັ່ນວ່າຕົວເລກທີ່ສ້າງຕັ້ງຂຶ້ນແມ່ນສູງສຸດ. ຖ້າພວກເຮົາທົດແທນທີ່ຖືກຕ້ອງທີ່ສຸດ 6 ແລ້ວພວກເຮົາຈະໄດ້ຮັບ 6669.
ຖ້າພວກເຮົາທົດແທນທີ່ຢູ່ເບື້ອງຊ້າຍ 6 ແລ້ວພວກເຮົາຈະໄດ້ຮັບ 9666 ເຊິ່ງແນ່ນອນແມ່ນ ຈຳ ນວນສູງສຸດຂອງຕົວເລກທັງ ໝົດ ທີ່ໄດ້ຮັບໂດຍການທົດແທນດັ່ງກ່າວໃສ່ ຈຳ ນວນນີ້.
ດັ່ງນັ້ນພວກເຮົາຈະພະຍາຍາມທົດແທນທີ່ຢູ່ເບື້ອງຊ້າຍ 6. ແລະຖ້າບໍ່ມີ 6 ຢູ່ໃນຕົວເລກທີ່ໄດ້ກ່າວໄວ້ເຊັ່ນ: 9999 ແລ້ວພວກເຮົາຈະບໍ່ປະຕິບັດການທົດແທນໃດໆ.

ພວກເຮົາສາມາດ ທຳ ລາຍຕົວເລກທີ່ລະບຸໄວ້ໃນຮູບແບບຂອງອາເລແລະຫຼັງຈາກນັ້ນພວກເຮົາສາມາດທົດແທນສ່ວນທີ່ເຫລືອ 6 ໂດຍ 9 ໄດ້ງ່າຍ. ຫຼັງຈາກນັ້ນພວກເຮົາຈະສ້າງເລກ ໃໝ່ ຂອງພວກເຮົາ ໃໝ່ ຈາກຂບວນແລະອອກ ຈຳ ນວນ.
ມີຂໍ້ ຈຳ ກັດທີ່ ຈຳ ນວນບໍ່ ຈຳ ກັດ 4 ຕົວເລກ. ດັ່ງນັ້ນພວກເຮົາຈະສ້າງຂະ ໜາດ 4 ເຊິ່ງຈະພໍໃຈກັບຕົວເລກທັງ ໝົດ ຂອງຄວາມຍາວນ້ອຍເກີນໄປ.

ດັ່ງນັ້ນ, ສູດການຄິດໄລ່ໂດຍພື້ນຖານແມ່ນປະກອບດ້ວຍສາມພາກສ່ວນຕົ້ນຕໍ.
i) ປ່ຽນເລກເປັນ array: ພວກເຮົາ ກຳ ລັງເຮັດແບບນີ້ໂດຍໃຊ້ loop ໃນຂະນະທີ່ມີເງື່ອນໄຂຂອງເລກ> 0. ທຸກໆຄັ້ງ, ຕົວເລກຢູ່ບ່ອນເກັບມ້ຽນ ໜ່ວຍ ງານຈະຖືກເກັບຢູ່ທີ່ດັດສະນີປະຈຸບັນຂອງອາເລແລະຕົວເລກແບ່ງອອກເປັນ 10.
ii) ການປ່ຽນແປງດ້ານຊ້າຍ 6 ຫາ 9 ໃນອາເລ.

ວິທີແກ້ໄຂ Leetcode ສູງສຸດ 69 ຕົວ

ຫຼັງຈາກການແປງດ້ານຊ້າຍ 6 ຫາ 9:

ວິທີແກ້ໄຂ Leetcode ສູງສຸດ 69 ຕົວ

iii) ປ່ຽນອາເລເປັນເລກ: ພວກເຮົາ ກຳ ລັງເຮັດແບບນີ້ໂດຍໃຊ້ loop.

ການປະຕິບັດ

ໂປແກຼມ C ++ ສຳ ລັບການແກ້ໄຂບັນຫາ Leetcode ສູງສຸດ 69 ຕົວ

#include <iostream>
using namespace std;
int maximum69Number (int num) 
{
    int arr[4];
    fill(arr,arr+4,0);
    int i=3;
    while(num!=0){
        arr[i--]=num%10;
        num/=10;
    }
    for(i=0;i<=3;i++){
        if(arr[i]==6){arr[i]=9;break;}
    }

    int ans=0,mul=1;
    for(i=3;i>=0;i--){
        ans+=(mul*arr[i]);
        mul*=10;
    }
    return ans;

}
int main()
{
    cout << maximum69Number(9669);
}
9969

Java Program ສຳ ລັບການແກ້ໄຂບັນຫາ Leetcode ສູງສຸດ 69 ຕົວ

import java.util.*;
import java.lang.*;

class Solution
{  
    public static int maximum69Number (int num) 
    {
        int[] arr=new int[4];
        int i=3;
        while(num!=0){
            arr[i--]=num%10;
            num/=10;
        }
        for(i=0;i<=3;i++){
            if(arr[i]==6){arr[i]=9;break;}
        }
        int ans=0,mul=1;
        for(i=3;i>=0;i--){
            ans+=(mul*arr[i]);
            mul*=10;
        }
        return ans;
    }
    public static void main(String args[])
    {
        System.out.println(maximum69Number(9669));
    }
}
9969

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບການແກ້ໄຂບັນຫາ Leetcode ສູງສຸດ 69 ຕົວ

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

O (1):  ພວກເຮົາ ກຳ ລັງສະແດງ 3 ວົງ ຂອງ 4 iterations ທີ່ສູງສຸດທີ່ເຄຍ. ດັ່ງນັ້ນ, ນີ້ແມ່ນເວລາທີ່ແນ່ນອນ ສຳ ລັບ ຄຳ ຖາມນີ້. ເຖິງຢ່າງໃດກໍ່ຕາມ, ຖ້າຂໍ້ ຈຳ ກັດຈະສູງ, ພວກເຮົາຈະໃຊ້ຂະ ໜາດ ທີ່ເທົ່າກັບຄວາມຍາວຂອງຕົວເລກ. ໃນເວລານັ້ນຄວາມສັບສົນຂອງເວລາຂອງພວກເຮົາແມ່ນ O (ຄວາມຍາວຂອງຕົວເລກ).

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

O (1): ພວກເຮົາໄດ້ ນຳ ໃຊ້ແຖວ 4 ຂະ ໜາດ ພິເສດເຊິ່ງຄົງທີ່. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ແມ່ນ O (1).