2021-10-28
题目
1.2的幂
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
示例 1：
输入：n = 1
输出：true
解释：20 = 1
示例 2：
输入：n = 16
输出：true
解释：24 = 16
示例 3：
输入：n = 3
输出：false
示例 4：
输入：n = 4
输出：true
示例 5：
输入：n = 5
输出：false
提示：
-231 <= n <= 231 - 1
2.全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
提示：
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同
3.全排列||
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
4.组合两个表
5.重新排序得到 2 的幂
给定正整数 N ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。
如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。
示例 1：
输入：1
输出：true
示例 2：
输入：10
输出：false
示例 3：
输入：16
输出：true
示例 4：
输入：24
输出：false
示例 5：
输入：46
输出：true
题解
1.2的幂
这个题我们直接可以用与运算来写出如果n&（n-1）==0返回true就证明这是是2的幂数，明天我可能就会更新一些运算符的使用，有一些运算符在写踢的时候是很方便的，还要注意一点这个是要大于0的！
2.全排列
本题就是一个简单的回溯加剪枝，我们在回溯的条件上添加一个剪枝，判断每一个排序中是否已经有了该元素，如果有了就直接跳过此次循环，每次回溯的终止条件就是子元素的长度是否等于给定的长度，我们来借鉴一下官方的图：
看图是能比较好理解的，如果大家懂了这个图的原理，还有回溯的原理就可以直接下手本题了！！
3.全排列||
本题是上一题的一个进阶问题，本题多出了两个条件，给的数组里面的元素是可以重复的，但是排序的结果是不能重复的。
我们还是用回溯加剪枝，我们还需要把每个重复的元素给经行一个标记，我们可以创建一个新的全为0等长的列表，然后判断如果有重复的，则对应新列表重复的下标转化为1，在回溯的时候判断，如果新列表的哪个下标为1就直接跳过此次循环，这样就去重了一些，然后回溯在进行排序。
4.组合两个表
本题考的就是两个表的如何合并，在MySQL中我们可以先用outer join合并这两个表，然后在在合并的表中进行查询，这个是一个基本的思路，我最后测试了一下效率不是很高但是没有什么问题。
5.重新排序得到 2 的幂
本题是今天的每日一题，本题有一种解法就是用回溯加对2幂数经行判断，我最开始写的几道题就是为这个题做铺垫，但是呢我并没有用那种方法去写嘿嘿嘿嘿，我看到了一个新的思路。就是我们可以把2的31个幂数列举出来，然后在给这些幂函数转化为二进制的数，并放在列表中，我们也把目标数转化为二进制数放在列表中，然后经行a和b两个数组进行对比如果相等就返回true，反之返回false。
6.买股票的最佳时机
代码
1.2的幂
class Solution: def isPowerOfTwo(self, n: int) -> bool: return n>0 and n&(n-1)== 0
2.全排列
class Solution: def permute(self, nums: List[int]) -> List[List[int]]: res = [] def trace (nums,path): if len(path) == len(nums): res.append(list(path)) return for i in nums: if i in path: continue path.append(i) trace(nums,path) path.pop() trace(nums,[]) return res
3.全排列||
class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: nums.sort() res = [] check =[0 for i in range(len(nums))] def trace (nums,path,check): if len(path) == len(nums): res.append(list(path)) return for i in range(len(nums)): if check[i] == 1: continue if i>0 and nums[i]==nums[i-1] and check[i-1] ==0: continue check[i]=1 trace(nums,path+[nums[i]], check) check[i]=0 trace(nums,[],check) return res class Solution1: def permuteUnique(self, nums: List[int]) -> List[List[int]]: nums.sort() res = [] check = [0 for i in range(len(nums))] def backtrack(sol, nums, check): if len(sol) == len(nums): res.append(list(sol)) return for i in range(len(nums)): if check[i] == 1: continue if i > 0 and nums[i] == nums[i-1] and check[i-1] == 0: continue check[i] = 1 backtrack(sol+[nums[i]], nums, check) check[i] = 0 backtrack([], nums, check) return res
4.组合两个表
select FirstName, LastName, City, State from Person left join Address on Person.PersonId = Address.PersonId ;
5.重新排序得到 2 的幂
class Solution: def reorderedPowerOf2(self, n: int) -> bool: def check(targ: int, num: int) -> bool: a = [0 for _ in range(10)] b = [0 for _ in range(10)] while targ: x = targ % 10 a[x] += 1 targ //= 10 while num: x = num % 10 b[x] += 1 num //= 10 return a == b for i in range(31): targ = 2 ** i if check(targ, n) == True: return True return False
6.买卖股票的最佳时机
class Solution: def maxProfit(self, prices: List[int]) -> int: n = len(prices) if n == 0: return 0 # 边界条件 dp = [0] * n minprice = prices[0] for i in range(1, n): minprice = min(minprice, prices[i]) dp[i] = max(dp[i - 1], prices[i] - minprice) return dp[-1]
