1300. Sum of Mutated Array Closest to Target 链接到标题

对 arr 进行降序排序,将 arr 中的最小值乘以 arr 长度与 target比较,若比 target 小,则将其丢弃,并将其从 target 中减去。 若 arr 为空,则表示 arr 中最大值乘以 arr 长度仍比 target 小,则返回 arr 中的最大值。 若 arr 不为空,则表示 arr 中存在大于目标值的数值,取 target 除以此时 arr 长度(arr 中所有数值均大于目标值),最终值四舍五入得到目标值。

class Solution(object):
    def findBestValue(self, arr, target):
        """
        :type arr: List[int]
        :type target: int
        :rtype: int
        """
        arr.sort(reverse = True)
        
        while arr and target >= arr[-1]*len(arr):
            temp = arr[-1]
            target -= arr.pop()
        
        if not arr:
            return temp
        res = target/float(len(arr))
        
        if res % 1 > 0.5:
            return int(res)+1
        else:
            return int(res)

也可用二分方式做,取 [0, max(arr)] 中间值为 mid,对 arr 求和:若数值大于 mid则取 mid,求和结果与 target 比较。 记录最小差值和最小差值时 mid 值,若求和数值大于 target,则将上限置为 mid-1,否则将下限置为 mid+1,如果求和数值与 target 相等,则直接返回 mid。

class Solution(object):
    def findBestValue(self, arr, target):
        """
        :type arr: List[int]
        :type target: int
        :rtype: int
        """
        left, right = 0, max(arr)
        sub, ans = float("inf"), float("inf")
        
        while left <= right:
            mid = (left + right) // 2
            
            tmp = 0 
            for num in arr:
                if num > mid:
                    tmp += mid
                else:
                    tmp += num
            
            cur_sub = abs(tmp - target)
 
            if cur_sub < sub:
                sub = cur_sub
                ans = mid
            elif cur_sub == sub:
                ans = min(ans, mid)
 
            if tmp > target:
                right = mid - 1
            elif tmp < target:
                left = mid + 1
            elif tmp == target:
                return mid
                
        return ans

1299. Replace Elements with Greatest Element on Right Side 链接到标题

按照题意暴力解法,时间接近5s。

class Solution(object):
    def replaceElements(self, arr):
        """
        :type arr: List[int]
        :rtype: List[int]
        """
        for i in range(len(arr)):
            if i == len(arr)-1:
                arr[i] = -1
                return arr
            arr[i] = max(arr[i+1:])
        return arr

正确姿势为从后向前比较,每次比较最大值与 arr[i] 即可。

class Solution(object):
    def replaceElements(self, arr):
        """
        :type arr: List[int]
        :rtype: List[int]
        """
        greatest = -1
        for i in range(len(arr)-1, -1, -1):
            if arr[i] < greatest:
                arr[i] = greatest
            else:
                arr[i], greatest = greatest, arr[i]
        return arr

1363. Largest Multiple of Three 链接到标题

这是一道数学题,当一个数字可以被 3 整除时,那么这个数字每一位相加之和也可被 3 整除。

倒序排序,计算所有数字之和,如果可以被 3 整除,那么直接返回; 如果余数为1,则从数组中尝试删除 1,4,7 其中一个; 如果余数为2,则从数组中尝试删除 2,5,8 其中一个; 若仍不满足条件,且余数为 2 ,则从数组中尝试删除 1,4,7 其中两个; 若仍不满足条件,且余数为 1 ,则从数组中尝试删除 2,5,8 其中两个;

class Solution(object):
    def largestMultipleOfThree(self, A):
        """
        :type digits: List[int]
        :rtype: str
        """
        total = sum(A)
        count = collections.Counter(A)
        A.sort(reverse=1)

        def f(i):
            if count[i]:
                A.remove(i)
                count[i] -= 1
            if not A: return ''
            if not any(A): return '0'
            if sum(A) % 3 == 0: return ''.join(map(str, A))

        if total % 3 == 0:
            return f(-1)
        if total % 3 == 1 and count[1] + count[4] + count[7]:
            return f(1) or f(4) or f(7)
        if total % 3 == 2 and count[2] + count[5] + count[8]:
            return f(2) or f(5) or f(8)
        if total % 3 == 2:
            return f(1) or f(1) or f(4) or f(4) or f(7) or f(7)
        return f(2) or f(2) or f(5) or f(5) or f(8) or f(8)

1362. Closest Divisors 链接到标题

求 num 的平方根,倒序排序后,依次遍历检测是否被 (num + 1) 或 (num + 2) 整除,若整除则为所求结果。

class Solution(object):
    def closestDivisors(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        for i in reversed(range(1, int((num + 2) ** 0.5) + 1)):
            if not (num + 1) % i:
                return [i, (num + 1) // i]
            if not (num + 2) % i:
                return [i, (num + 2) // i]

228. Summary Ranges 链接到标题

这道题我在实际应用中遇到过,具体问题可以看这篇记录 《记一次 libcgroup 配置失败》

记录当前连续数字的 start 和 end,并遍历数组进行判断,如果 num = end + 1 ,那么更新 end 数值,如果不等于,那么将这段数字转换为字符串并添加到结果中,并重置 start & end。

class Solution(object):
    def summaryRanges(self, nums):
        """
        :type nums: List[int]
        :rtype: List[str]
        """
        ranges = []
        if not nums:
            return ranges

        start, end = nums[0], nums[0]
        for i in xrange(1, len(nums) + 1):
            if i < len(nums) and nums[i] == end + 1:
                end = nums[i]
            else:
                interval = str(start)
                if start != end:
                    interval += "->" + str(end)
                ranges.append(interval)
                if i < len(nums):
                    start = end = nums[i]

        return ranges

p.s. 贴一下自己用 shell 写的,写完就看不懂了。。

function format_qemu_processors {
    # cgconfig.service could not be active when libcgroup <= libcgroup-0.41-20.el7 and config field >= 100 char
    # use `-` format qemu_processors
    # example:
    # qemu_processors input (6,7,8,9,10),  output is "6-10"
    # qemu_processors input (10,9,8,7,6),  output is "6-10"
    # qemu_processors input (6,7,8,10,11), output is "6-8,10-11"
    # qemu_processors input (1,3,5,7,9),   output is "1,3,5,7,9"

    IFS=$'\n' sorted=($(sort -n <<<"${qemu_processors[*]}"))
    unset IFS

    QEMU_CPUS=""
    TAG=""
    for i in "${!sorted[@]}";do
        if [[ "${sorted[(i+1)]}" == `expr ${sorted[i]} + 1` ]];then
            if [[ ${sorted[(i-1)]} == $TAG ]];then
                TAG=${sorted[i]}
                continue
            fi
            QEMU_CPUS=$QEMU_CPUS"${sorted[i]}"
            QEMU_CPUS=$QEMU_CPUS"-"
            TAG="${sorted[i]}"
        else
            QEMU_CPUS=$QEMU_CPUS"${sorted[i]}"
            if [[ ${sorted[i]}  != ${sorted[-1]} ]];then
                QEMU_CPUS=$QEMU_CPUS","
            fi
        fi
    done
    echo ${QEMU_CPUS}
}