Home

题目链接既然不能用加减乘除，我们可以考虑位运算，对于十进制的加法来说，一般有两个步骤，一是在不产生进位的情况下将同一位的数字加在一起，二是在产生进位的情况下将进位加到相对更高的位去。对于二进制的位运算来说，我们可以用异或运算实现不带进位的加法，用和运算加上左移一位实现进位。但是，我们注意到，每次进行和运算然后左移操作时最多只能将后一位的进位处理掉，在进位过程中会产生类似一次性进两位甚至更多为的情况，循环可以用来处理这种情况，并且循环终止的条件是进位为0。另外，由于python中负数的存储机制，我们对于负数要先对32位以上的数字取反获取负数的补码才能进行运算，为了保证左移过程中不出现差错（会有位数被移动到高于32位），我们也对左移后的结果求补码。最后在输出答案时，我们也先判断数字是否...

题目链接由于题目比较严格，不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句，我们运用逻辑运算符的短路效应来完成该题。具体如下所示。 if(A && B) // 若 A 为 false ，则 B 的判断不会执行（即短路），直接判定 A && B 为 false if(A || B) // 若 A 为 true ，则 B 的判断不会执行（即短路），直接判定 A || B 为 true 因此我们可以使用 n > 1 && sumNums(n - 1) // 当 n = 1 时 n > 1 不成立，此时 “短路” ，终止后续递归来实现对递归的控制。具体实现如下所示，这...

题目链接本题就是著名的约瑟夫环问题，我们介绍两种解题方法，一种是用环形链表模拟圆圈的经典解法；第二种是分析每次被删除的数字的规律并直接计算出圆圈中最后剩下的数字。对于第一种方法，我们用一个数据结构如环形链表来模拟这个圆圈，我们可以创建一个共有n个节点的环形链表，然后每次在这个链表中删除第m个节点。如果我们用一两个例子仔细分析上述代码的运行过程，就会发现，实际上需要在环形链表里重复遍历很多遍。重复的遍历当然对时间效率有负面影响。这种方法每删除一个数字需要m步运算，共有n个数字，因此总的时间复杂度为O（MN），同时这种思路需要有一个辅助链表来模拟圆圈，其空间复杂度为O（N）。第二种方法相对更加高效。首先，我们先定义一个关于n和m的方程f(n, m)，表示每次在n个数字0，1，… ，...

题目链接改题与jz059I相同，这个算法的时间复杂度是O（N），空间复杂度是O（K）。 class Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: res, window, lnums = [], collections.deque(), len(nums) for i in range(lnums): while window and nums[i] > nums[window[-1]]: window.pop() window.append(i...

题目链接对于这个题，我们首先将数组排序，鉴于当牌中出现对子的时候就不能组成顺子，所以我们用一个集合来判断之前除了大小王之外的牌是不是唯一的。而对于出现大小王的情况，我们用一个joker变量来记录数量，并且同时记录着第一个非0的数字的位置，也是最小的牌的位置。对于是否为顺子的情况，只要满足牌中的最大值与最小值的差值小于5即可。这个算法的时间复杂度是O（NlogN）= O（5log5）= O（1），空间复杂度是O（N）= O（5）= O（1）。 class Solution: def isStraight(self, nums: List[int]) -> bool: nums.sort() repeat = set() ...

题目链接比较经典的动态规划题目，空间优化成一维矩阵。这个算法的时间复杂度是O（N^2）其中N为骰子数，空间复杂度是O（N）。 class Solution: def twoSum(self, n: int) -> List[float]: res = [0] * n * 6 for i in range(6): res[i] = 1 for i in range(1, n): for j in range((i+1)*6-1, i-1, -1): if j >= 6: res[j] = su...

题目链接https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/ 这题思想和jz059I很相似。这个算法的时间复杂度（插入，删除，求最大值）是O（1），空间复杂度是O（N）。 import queue class MaxQueue: def __init__(self): self.master, self.aux = queue.Queue(), queue.deque() def max_value(self) -> int: return self.aux[0] if self.aux else -1 def push_back(self, v...

题目链接如果用蛮力的方法，可以扫描每个滑动窗口的所有数字并找出其中的最大值，如果滑动窗口的大小为k，则需要O（K）时间才能找出滑动窗口里的最大值。对于长度为n的输入数组，这种算法的总时间复杂度为O（NK）。实际上，一个滑动窗口可以看成一个队列。当窗口滑动时，处于窗口对第一个数字先被删除，同时在窗口的末尾添加一个新的数字，这符合队列先进先出的性质。如果能从队列中找出它的最大值，那么这个问题就解决了。在jz030中我们实现了一个可以用O（1）时间得到最小值的栈，类似的我们也可以得到最大值。同时在jz009中，我们用两个栈实现了一个队列。综合这两个问题对解决方案我们发现如果把队列用两个栈实现，由于可以用O（1）的时间得到栈中的最大值，那么也就可以用O（1）时间得到队列的最大值，因此总...