1237. 找出给定方程的正整数解
给出一个函数 f(x, y) 和一个目标结果 z，请你计算方程 f(x,y) == z 所有可能的正整数 数对 x 和 y。
给定函数是严格单调的，也就是说：
f(x, y) < f(x + 1, y)
f(x, y) < f(x, y + 1)
函数接口定义如下：
interface CustomFunction {
public:
// Returns positive integer f(x, y) for any given positive integer x and y.
int f(int x, int y);
};
示例 1：
输入：function_id = 1, z = 5
输出：[[1,4],[2,3],[3,2],[4,1]]
解释：function_id = 1 表示 f(x, y) = x + y
示例 2：
输入：function_id = 2, z = 5
输出：[[1,5],[5,1]]
解释：function_id = 2 表示 f(x, y) = x * y
提示：
1 <= function_id <= 9
1 <= z <= 100
题目保证 f(x, y) == z 的解处于 1 <= x, y <= 1000 的范围内。
在 1 <= x, y <= 1000 的前提下，题目保证 f(x, y) 是一个 32 位有符号整数。
比较暴力的方法是 进行两层循环处理可行解
class Solution(object):
def findSolution(self, customfunction, z):
"""
:type num: int
:type z: int
:rtype: List[List[int]]
"""
ans = []
for i in range(1, 1001):
for j in range(i, 1001):
tmp = customfunction.f(i, j)
if tmp == z:
ans.append([i, j])
break
if tmp > z:
break
return ans
有了上面的解法后,由于题目给出严格的递增性,所以随着i的增加,j的解范围是在不断缩小的.
所以我们设定j的初始范围是1-1000,从1000逐步缩小到1,这样的复杂度只有
class Solution(object):
def findSolution(self, customfunction, z):
"""
:type num: int
:type z: int
:rtype: List[List[int]]
"""
ans = []
i,j = 1,1000
while i<=1000:
tmp = customfunction.f(i, j)
while tmp>z and j>1:
j-=1
tmp = customfunction.f(i, j)
if tmp == z:
ans.append([i,j])
i+=1
return ans
1238. 循环码排列
给你两个整数 n 和 start。你的任务是返回任意 (0,1,2,...,2^n-1) 的排列 p，并且满足：
* p[0] = start
* p[i] 和 p[i+1] 的二进制表示形式只有一位不同
* p[0] 和 p[2^n -1] 的二进制表示形式也只有一位不同
示例 1：
输入：n = 2, start = 3
输出：[3,2,0,1]
解释：这个排列的二进制表示是 (11,10,00,01)
所有的相邻元素都有一位是不同的，另一个有效的排列是 [3,1,0,2]
示例 2：
输出：n = 3, start = 2
输出：[2,6,7,5,4,0,1,3]
解释：这个排列的二进制表示是 (010,110,111,101,100,000,001,011)
提示：
1 <= n <= 16
0 <= start < 2^n
很暴力的解法,通过初始化构造所有答案,然后对start做处理调整,即可输出
class Solution(object):
arr = []
def circularPermutation(self, n, start):
if not self.arr:
self.init()
return self.handle(self.arr[n],start)
def handle(self,array,start):
l = []
r = []
mk = True
for i in array:
if i == start:
mk = False
if mk:
r.append(i)
else:
l.append(i)
return l+r
def init(self):
self.arr.append([0])
def calc(array,x):
array = array[::-1]
tmp = 2**x
ans = []
for k,v in enumerate(array):
ans.append(v+tmp)
return ans
for i in range(1,17):
self.arr.append(self.arr[i-1]+calc(self.arr[i-1],i-1))
1239. 串联字符串的最大长度
给定一个字符串数组 arr，
字符串 s 是将 arr 某一子序列字符串连接所得的字符串，
如果 s 中的每一个字符都只出现过一次，
那么它就是一个可行解。
请返回所有可行解 s 中最长长度。
示例 1：
输入：arr = ["un","iq","ue"]
输出：4
解释：所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique"，最大长度为 4。
示例 2：
输入：arr = ["cha","r","act","ers"]
输出：6
解释：可能的解答有 "chaers" 和 "acters"。
示例 3：
输入：arr = ["abcdefghijklmnopqrstuvwxyz"]
输出：26
提示：
1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i] 中只含有小写英文字母
初始化处理掉不合法的状态,然后进行dp
class Solution(object):
def maxLength(self, arr):
arr = self.init(arr)
print arr
dp = []
length = len(arr)
for i in range(length+1):
dp.append([])
dp[0].append("")
def check(arrx,arry):
s = set()
for i in arrx:
s.add(i)
for i in arry:
if i in s:
return False
return True
for k,v in enumerate(arr):
print dp[k]
dp[k+1].append(v)
for i in dp[k]:
if check(i,v):
dp[k+1].append(i+v)
dp[k+1].append(i)
ans = 0
for i in dp[length]:
ans = max(ans,len(i))
return ans
def init(self,arr):
ans = []
def test(array):
for k,v in enumerate(array):
if k>0 and v == array[k-1]:
return False
return True
for i in arr:
i = "".join((lambda x:(x.sort(),x)[1])(list(i)))
if test(i):
if i in ans:
continue
else:
ans.append(i)
return ans
1240. 铺瓷砖
你是一位施工队的工长，根据设计师的要求准备为一套设计风格独特的房子进行室内装修。
房子的客厅大小为 n x m，为保持极简的风格，需要使用尽可能少的 正方形 瓷砖来铺盖地面。
假设正方形瓷砖的规格不限，边长都是整数。
请你帮设计师计算一下，最少需要用到多少块方形瓷砖？
没有思路
