Es scheint, dass Codierungstests in Ingenieurinterviews im Ausland durchgeführt werden, und in vielen Fällen besteht die Hauptsache darin, bestimmte Funktionen und Klassen entsprechend dem Thema zu implementieren.
Anscheinend ergreifen viele Ingenieure Maßnahmen auf der Website namens LetCode.
Es ist eine Site, die die Algorithmusleistung trainiert, die dem Codierungstest standhält, der in der frühen Geschichte durchgeführt wird, und es ist ein unvermeidlicher Weg für diejenigen, die eine Karriere bei einem ausländischen Technologieunternehmen aufbauen möchten.
Ich habe es großartig geschrieben, aber ich habe im Moment keine Pläne für ein solches Interview.
Als IT-Ingenieur wäre es jedoch besser, die gleiche Algorithmusleistung wie eine Person zu haben. Daher möchte ich das Problem unregelmäßig lösen und die Methode, die ich damals dachte, als Memo aufschreiben.
Ich löse es mit Python3.
Letztes Mal Leet Code Day71 "1496. Pfadkreuzung" ab Null
Im Moment priorisiere ich das Medium der 100 beliebtesten Fragen. Easy wurde gelöst. Wenn Sie interessiert sind, gehen Sie bitte zum Tisch.
Twitter Ich mache es.
** Technischer Blog Gestartet! !! ** **. Ich denke, die Technologie wird über LetCode, Django, Nuxt usw. schreiben. ** Dies ist schneller zu aktualisieren **, vielen Dank für Ihre Mitarbeit!
1498. Number of Subsequences That Satisfy the Given Sum Condition Der Schwierigkeitsgrad ist Mittel.
Das Problem erhält ein Array von ganzen Zahlen "nums" und ein ganzzahliges "target". Gibt die Anzahl der nicht leeren Unterspalten zurück, sodass die Summe der minimalen und maximalen Werte von nums kleiner oder gleich dem Zielwert ist.
Die Antwort ist möglicherweise zu groß, sodass eine Restoperation von 10 ^ 9 + 7 zurückgegeben wird.
Example 1:
Input: nums = [3,5,6,7], target = 9 Output: 4 Explanation: There are 4 subsequences that satisfy the condition. [3] -> Min value + max value <= target (3 + 3 <= 9) [3,5] -> (3 + 5 <= 9) [3,5,6] -> (3 + 6 <= 9) [3,6] -> (3 + 6 <= 9)
Example 2:
Input: nums = [3,3,6,8], target = 10 Output: 6 Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers). [3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]
Example 3:
Input: nums = [2,3,3,4,6,7], target = 12 Output: 61 Explanation: There are 63 non-empty subsequences, two of them don't satisfy the condition ([6,7], [7]). Number of valid subsequences (63 - 2 = 61).
Example 4:
Input: nums = [5,2,4,1,7,6,8], target = 16 Output: 127 Explanation: All non-empty subset satisfy the condition (2^7 - 1) = 127
Constraints:
- 1 <= nums.length <= 10^5
class Solution:
def numSubseq(self, nums: List[int], target: int) -> int:
ans,mod = 0,10**9+7
nums.sort()
for i,j in enumerate(nums):
if target < j*2:
break
b = bisect.bisect(nums,target-j,lo=i)
ans += pow(2, b-i-1, mod)
return ans % mod
# Runtime: 888 ms, faster than 82.84% of Python3 online submissions for Number of Subsequences That Satisfy the Given Sum Condition.
# Memory Usage: 25.2 MB, less than 100.00% of Python3 online submissions for Number of Subsequences That Satisfy the Given Sum Condition.
Wie in der Problemanweisung angegeben, habe ich geschrieben, dass zuerst "mod (10 ** 9 + 7)" angegeben wurde und dann in der for-Anweisung eine Dichotomie durchgeführt wurde. Die Argumente der Halbierung sind wie folgt.
bisect(a,b,(lo,hi))
a:aufführen
b:Wert zum Einfügen
lo:Untere Grenze des Suchbereichs
hi:Obergrenze des Suchbereichs
Wie viele von Ihnen, die diesen Artikel lesen, wissen, basiert die Dichotomie auf der Sortierung, sodass die Liste am Anfang des Codes sortiert wird. Soweit das Beispiel zu sehen ist, scheint es viele Fälle gegeben zu haben, in denen es nicht sortiert wurde ...
Übrigens, 10 ** 9 + 7 kommt bei anderen Wettbewerbsprogrammen ziemlich oft heraus (nicht auf eine beschränkt, da es viele Websites gibt). Einige Leute haben leicht verständliche Erklärungsartikel darüber geschrieben. Wenn Sie also interessiert sind, tun Sie dies bitte auch.
Das war's für diese Zeit. Danke für deine harte Arbeit.
Recommended Posts