程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式師世界 >> 編程語言 >  >> 更多編程語言 >> Python

The first wrong version of day036 (binary search method) | primary algorithm | Python

編輯:Python

Make a little progress every day , It's already great , Insist on , Don't be too tired , Refuse to roll in , Start with practice every day , Ten minutes a day , Live happily all your life ! The epidemic is still repeated , Everyone wear masks ~ Continue to continue , Come on , Today and Brother cheshen Work together to improve your Python Programming and Interview ability Well , brush ladder on high buildings ~

Put on what I took Photo Well !

Recommend a song every day : fragrance of rice ——Jay Chou

The following is my Ladder integral rule

At least one question a day : An integral +10 branch
If you do one more question ( Or one more way to answer ), Then the points of the day +20 branch (+10+10)
If you do more than three , Start with question 3 +20 branch ( Such as : If you do three questions, you will score -10+10+20=40; If you do four questions, you will score –10+10+20+20=60)


Initial classification 100 branch
If you haven't done the problem for one day , Then deduct points -10 branch ( Saturday 、 Except Sunday : rest
insist !!!


Primary algorithm

List of questions

Linked list

stem

You are the product manager , Currently leading a team to develop new products . Unfortunately , The latest version of your product doesn't pass the quality test . Because each version is based on the previous version , So all versions after the wrong version are wrong .

Suppose you have n A version [1, 2, …, n], You want to find out the first wrong version that caused all subsequent versions to go wrong .

You can call bool isBadVersion(version) Interface to determine version number version If there is an error in unit test . Implement a function to find the first wrong version . You should try to minimize calls to API The number of times .

Example 1:

Input :n = 5, bad = 4
Output :4
explain
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
therefore ,4 It's the first wrong version .

Example 2:

Input :n = 1, bad = 1
Output :1


Dichotomy search

analysis :

Is it a little silly to see this topic , It's ridiculous .
But it doesn't seem very difficult to look at it , We use dichotomy to reduce the number of test interface calls , Median . Constant temptation , Judge whether it is False, Then keep narrowing the range , Finally find the version number .

# The isBadVersion API is already defined for you.# @param version, an integer# @return an integer# def isBadVersion(version):class Solution: def firstBadVersion(self, n): """ :type n: int :rtype: int """ # Binary search  st = 0 end = n while st <= end: mid = st + (end - st)//2 if isBadVersion(mid): end = mid - 1 else: st = mid + 1 return st


It seems that there is only such an answer , Two days and two questions , Finish sorting and searching .

The next part starts tomorrow , Dynamic programming , It's a little difficult !~

come on. !!!

Reference

author : Power button (LeetCode)
link :https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnumcr/
source : Power button (LeetCode)


Score today :+10
Total score :740

come on. !!!


  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式師世界 All Rights Reserved