# LeetCode Weekly Contest 128

https://leetcode.com/contest/weekly-contest-128

## Complement of Base 10 Integer

Every non-negative integer N has a binary representation. For example, 5 can be represented as "101" in binary, 11 as "1011" in binary, and so on. Note that except for N = 0, there are no leading zeroes in any binary representation.

The complement of a binary representation is the number in binary you get when changing every 1 to a 0 and 0 to a 1. For example, the complement of "101" in binary is "010" in binary.

For a given number N in base-10, return the complement of it’s binary representation as a base-10 integer.

Example 1:

Example 2:

Example 3:

Note:

1. 0 <= N < 10^9

## Pairs of Songs With Total Durations Divisible by 60

In a list of songs, the i-th song has a duration of time[i] seconds.

Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i < j with (time[i] + time[j]) % 60 == 0.

Example 1:

Example 2:

Note:

1. 1 <= time.length <= 60000
2. 1 <= time[i] <= 500

## Capacity To Ship Packages Within D Days

A conveyor belt has packages that must be shipped from one port to another within D days.

The i-th package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days.

Example 1:

Example 2:

Example 3:

Note:

1. 1 <= D <= weights.length <= 50000
2. 1 <= weights[i] <= 500

• dp[i][1]=sum(weights[:i]) 把前i个元素分到同一个分片，一共只有一个和，就是目前为止所有元素的和

• dp[i][k]=min(max(dp[j][k-1]+sum(weights[j+1:i])) foreach j in [k-1:i-1]) 如果到j位置为止可以划分出k-1个分片，那么从j+1i可以构成一个分片，这些分片的最大值要么在前k-1个分片中已经出现，要么在最后一个新分片中，取最大即可。而j可以>=k-1<i的任意位置来确定最后一个分片的长度。

x取值最小为max(weights)，对应k=n，最大为sum(weights)，对应k=1，那么对于1<=D<=nD对应的某个分片和的最大值k一定在max(weights)sum(weights)，可以利用二分查找对x的范围逐步缩减，测试每个范围的中点mid所对应的k是否为目标D

## Numbers With Repeated Digits

Given a positive integer N, return the number of positive integers less than or equal to N that have at least 1 repeated digit.

Example 1:

Example 2:

Example 3:

Note:

1. 1 <= N <= 10^9

1-n-1位数没有大小限制，只需要考虑无重复即可

• 如果不包含0，那么i位数可以在1-9中任选排列，共有A(9,i)个数
• 如果包含0，那么i位数有i-1位非0，在i-1位无0数中可以选择i-1位后面的位置插入一个0形成包含0i位数，共有(i-1)*A(9,i-1)个数

n位数考虑逐步扩大前缀长度，从首位开始，如果N+1在这一位上的数字是d1，那么每个小于d1的数字都可以作为前缀，后面n-1位可以取任何与d1不同的值，共有A(9,n-1)*(d1-1)个数，接下来考虑固定首位与d1一致，第二位可以比与N+1的第二位d2小的任意值，当也要求与d1不一致，然后像上面那样考虑剩下的n-2位……