劍指offer43
題目描述：
輸入一個整數 n ，求1～n這n個整數的十進制表示中1出現的次數，
例如，輸入12，1～12這些整數中包含1 的數字有1、10、11和12，1一共出現了5次，
示例：
解答：
class Solution:
def countDigitOne(self, n: int) -> int:
a, b, one_count = 1, 10, 0
while n >= a:
x, y = divmod(n, b)
if y >= a * 2:
one_count += (x + 1) * a
elif y >= a:
one_count += y + 1 + (x - 1) * a
else:
one_count += x * a
a, b = b, b*10
return one_count
劍指offer45
題目描述：
輸入一個非負整數陣列，把陣列里所有數字拼接起來排成一個數，列印能拼接出的所有數字中最小的一個，
示例：
解答：
class cmpSmaller(str):
def __lt__(self, y):
return self + y < y + self # 字串拼接比較(兩兩比較)
# 按由小到大來排列
class Solution:
def minNumber(self, nums: List[int]) -> str:
res=sorted(map(str, nums),key=cmpSmaller)
smallest = ''.join(res)
return smallest
劍指offer49
題目描述：
我們把只包含質因子 2、3 和 5 的數稱作丑數（Ugly Number），求按從小到大的順序的第 n 個丑數，
示例：
解答：
class Solution:
def nthUglyNumber(self, n: int) -> int:
#記錄上一個時刻乘以（2/3/5）的最小時刻，下個丑數及對應的每個時刻乘以2/3/5的最小數
ugly = [1] # 利用陣列記錄
i2 = i3 = i5 =0
while n>1:
u2, u3, u5 = ugly[i2]*2, ugly[i3]*3, ugly[i5]*5
umin = min(u2, u3, u5)
if umin == u2:
i2 += 1
if umin == u3:
i3 += 1
if umin == u5:
i5 += 1
n -= 1
ugly.append(umin)
return ugly[-1]
劍指offer51
題目描述：
在陣列中的兩個數字，如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對，輸入一個陣列，求出這個陣列中的逆序對的總數，
示例：
解答：
class Solution:
def reversePairs(self, nums: List[int]) -> int:
if len(nums) <2:
return 0
res = []
def mergesort(nums,res):
size = len(nums)
if size <2:
return nums
middle = size //2
left = mergesort(nums[:middle],res)
right = mergesort(nums[middle:],res)
j = 0
count = 0
for i in range(len(left)):
while j < len(right):
if left[i] > right[j]:
count += len(right) - j
break
else:
j += 1
if j >= len(right):
break
res.append(count)
left += right
left.sort(reverse = True)
return left
mergesort(nums,res)
return sum(res)
劍指offer52
題目描述：
示例：
解答：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
node1, node2 = headA, headB
while node1 != node2:
node1 = node1.next if node1 else headB
node2 = node2.next if node2 else headA
return node1
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/257805.html
標籤：python