ඉන්ටරවූ එකකදී සුදු පුවරුවේ "Jump Game II" ප්රශ්නයක් පෙනී සිටියේය. එක් අරේ එකක ප්රතිලෝම අගය එකිනෙකට උපරිම පරිධියක් දෙනවා. අරේ අගයන් අනුව අවසාන ඉන්ඩෙක්ස් එකට ළඟා වීමට අවශ්ය අඩුම පන්දම් ගණන ගණනය කිරීම මෙහි අරමුණයි.
පළමුව මම ඩයිනමික් ප්රොග්රැම්මික (DP) ආකාරය භාවිතා කරලා O(n²) කාල සීමාවකින් විසඳුමක් ලියන ලදි. එය සෑම තැනකින්ම හැම ගමන් මාර්ගයක්ත් පරීක්ෂා කර, සෑම ඉලක්කමකටම නවතම පන්දම් ගණන යාවත්කාලීන කරන ලදි. නමුත් විශාල අරේ එකකදී මෙය පරිගණක සම්පත් අධික ලෙස භාවිතා කරන බැවින් පරීක්ෂණය අසීරු විය.
එවිට මට මතකයට ආවේ පූර්ව විශ්ලේෂණ පන්තියේ ග්රීඩි (greedy) මූලධර්මය. සරලව කියන්නේ, එක් පන්දමක් ගෙන යාමේදී ඔබට දැන් පවතින පන්දම් ගණනින් ළඟා විය හැකි ඉහළම ඉන්ඩෙක්ස් එකම සලකා ගත හැකිය. එම සීමාව පිරෙන තුරු ඉදිරියට යමින්, සීමාව අවසන් වූ විට පන්දමක් තවත් එක් කර, නව සීමාව නැවත ගණනය කරයි.
ග්රීඩි ආකාරයේ මූලික අදහස – පළමු පන්දම අතින් ළඟා විය හැකි ඉහළම ස්ථානයට යාමයි. එම ස්ථානයෙන් පසු ඇති සියලු පන්දම් මාර්ගයත් එහි සිට පරික්ෂා කළ හැක. ඒ නිසා පළමු පන්දම අඩු දුරකින් යාමට වඩා, ඉහළම දුරකින් යාම වඩා හොඳ ප්රතිඵලයක් ලබා ගත හැක.
කේත උදාහරණයක් මෙසේය:
def jump_game_greedy(nums): jumps = 0 curr_end = 0 farthest = 0 for i in range(len(nums)-1): farthest = max(farthest, i + nums[i]) if i == curr_end: jumps += 1 curr_end = farthest if curr_end >= len(nums)-1: break return jumps
මෙම ක්රමය එක් වරක් පමණක් අරේ එක හරහා යන නිසා O(n) කාලයත් O(1) අතිරේක මතක භාවිතයක්ත් ලබා දෙයි. ඉන්ටරවූ වලදී කෙටි කාල සීමාවක් තිබෙන විට මේ වගේ සරල, කාර්යක්ෂම විසඳුම් ඉතා වැදගත් වේ.
ශ්රී ලංකාවට ඇති වැදගත්කම
ශ්රී ලංකාවේ තරුණ කේතකරුවන්, විශ්වවිද්යාල සිසුන්, සහ තාක්ෂණික ආයතන සඳහා මේ ග්රීඩි ආකාරය විශාල ඉගෙනුම් අවස්ථාවක්. පළමුව DP පරිදි සංකීර්ණත්වය වැඩිවූ විධිමත් විසඳුම් අත්හදා බැලීමෙන්, ග්රීඩි මූලධර්මය දැන ගැනීමෙන් කේත කුසලතා වර්ධනය වේ. එසේම, සමාගම් තාක්ෂණික සම්මුඛ පරීක්ෂණවලදී කාර්යක්ෂම ඇලගෝරිත්මයක් ඉක්මනින් ලියීමට හැකියාව ලැබේ, මෙය සංවර්ධන කාලය කෙටි කර, ව්යාපාරික ලාභය වැඩි කරයි.
අපේ දේශීය තාක්ෂණික පාඨමාලා, කේත වැඩමුළු, සහ සමාජ මාධ්ය කණ්ඩායම් මේ ග්රීඩි විධිය භාවිතා කරමින් අභ්යාස ප්රශ්න හදා, ඉදිරි පරීක්ෂණවලට සූදානම් කරගත හැක.
අවසන් වශයෙන්, Jump Game II ග්රීඩි විසඳුම පරිගණක විද්යාවේ “ඉදිරිපත් කරමින්” කාර්යක්ෂමත්වය, සරලත්වය, සහ ප්රායෝගිකත්වය යන තේමාවන් සමඟ සම්බන්ධ කරයි. ඒ නිසා ඔබත් මේ ආකාරය අත්හදා බැලුවොත්, අලූතින් පුරෝගාමී කේතකරුවෙකු බවට පත්වෙන්න.
