解题思路数字1与数字相位与运算，最后一位为1就是1，最后一位为0就是0。遍历二进制的32位，通过移位0-31次实现。将移位后的1与数字进行位与运算，结果为1就计数器加一。返回计数器。复杂度时间复杂度为O(1)；空间复杂度为O(1)。代码python class Solution: def NumberOf1(self , n: int) -> int: res = 0 for i in range(32): if (n & (1<<i)): res += 1 return res C++ class Solution { public: int NumberOf1(i...

解题思路可以线从简单的情况进行分析：当绳子长度为2和3的时候，不切分的乘积是最大的；当绳子长度为4的时候，对半切分的乘积是最大的。而继续往后计算的话，有一个规律：假设一段长为i的绳子，其后j段不能切分，那么我们知道它前面i-j长的绳子切分乘积最大值，则我们可以知道最终的乘积，一个一个去比较大小，取大值。复杂度时间复杂度为O(N）；空间复杂度为O(N)。代码Python class Solution: def cutRope(self , n: int) -> int: # write code here if n < 4: return n dp = [0 for _ in ran...

解题思路先写一个dfs函数：当索引值超过边界，或当前的矩阵值与字符串相对应的符号不匹配，或者是当前元素已经被遍历过了，则返回False；如果当前已经遍历完目标字符串了，则说明匹配上一条路径了。则直接返回True。否则，给当前值赋值True，代表已经遍历过了。如果这上下左右这四个方向至少有一个方向能找到路径，则返回True。否则将该值的状态改为False，并将函数返回False。 2. 求路径的函数内：遍历矩阵的每一个元素，判断从某个元素开始是否有可行的路径。代码Python class Solution: def dfs(self, matrix, n, m, i, j, word, k, f...

解题思路先向前寻找，直至找到根节点；中序遍历数；在遍历后的结果内查找是否有目标节点，如果有则返回其下一个节点；否则，返回空。复杂度时间复杂度为O（n）；空间复杂度为O（n）。代码Python class Solution: node = [] def inOrder(self, root): if root is None: return self.inOrder(root.left) self.node.append(root) self.inOrder(root.right) def GetNext(self, pNode): root = pNode # 从后往前找，直到根节点 whil...

解题思路二分法。如果中点处的值大于右边界的值，则最小值在中点右边，更新左边的边界；如果中点处的值小于右边界的值，则最小值在中点的左边或者是中点，更新右边界的值；如果相等的话，则逐步向左减少右边界的值。最终返回结果即可。复杂度时间复杂度为O（logn）；空间复杂度为O（1）。代码Python class Solution: def minNumberInRotateArray(self , nums: List[int]) -> int: left = 0 right = len(nums) - 1 while left < right: mid = (right+left) // ...

解题思路先顺序遍历一遍，并将每个元素添加到数组中；之后，将数组进行反转，并返回该结果。Python class Solution: def printListFromTailToHead(self , listNode: ListNode) -> List[int]: res = [] while listNode != None: res.append(listNode.val) listNode = listNode.next return res[::-1] C++技术点：运用到了reverse函数。reverse函数可以反转一个容器中的内容，包含在<algorithm&gt...

解题思路Python可以利用split函数和join函数。先将字符串以空格为间隔进行切分，获得一个list；之后将list以‘%20’为分隔符将其连接成一个字符串。 class Solution: def replaceSpace(self , s: str) -> str: return '%20'.join(s.split(' ')) C++拼接字符串。如果当前字符不为空格，则将其连接；否则，连接"%20"。 class Solution { public: string replaceSpace(string s) { string res = "&q...

解题思路这个题很简单，利用了哈希表的性质，判断当前的元素是否在哈希表内，如果在的话，就说明该数是重复的元素，就返回该数。复杂度时间复杂度：O(n)；空间复杂度：O(n)。代码C++ // 写法一 #include <unordered_map> class Solution { public: int duplicate(vector<int>& numbers) { unordered_map<int, int> mp; for(int i = 0; i<numbers.size(); i++) { if(mp.find(numbers[i]...

方法一：迭代先创建一个pre和一个cur的ListNode变量；然后迭代遍历链表，然后反转指针指向。复杂度时间复杂度为O（N）；空间复杂度为O（1）。 /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: ListNode* ReverseList(ListNode* head) { ListNode* pre = NULL; ListNode* cur = head; wh...

class Solution: def match(self , str: str, pattern: str) -> bool: if not pattern: return not str firstMatch = str and pattern[0] in {str[0], '.'} if len(pattern) >= 2 and pattern[1] == '*': return (self.match(str, pattern[2:]) or firstMatch and self.match(str[1:], pattern)) else: return firstM...

class Solution: def LCS(self , s1: str, s2: str) -> str: # 获取最长公共子序列长度 dp = [[0]*(len(s2)+1) for _ in range(len(s1)+1)] for i in range(1, len(s1)+1): for j in range(1, len(s2)+1): if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i][j-1], dp[i-1][j]) # 获取字符串 res = "&...

class Solution: def longestValidParentheses(self , s: str) -> int: stack = [] flag = [0]*len(s) for i in range(len(s)): if not stack and s[i] == ')': continue if s[i] == '(': stack.append(i) else: j = stack.pop() flag[i] = 1 flag[j] = 1 res = 0 tmp = 0 for i in flag: if i == 1: tmp += 1 res = max...

1 买股票最好时机（一） class Solution: def maxProfit(self , prices: List[int]) -> int: dp = [[0]*2 for _ in range(len(prices) )] dp[0][0] = 0 dp[0][1] = -prices[0] for i in range(1, len(prices)): dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]) # 当天不持股 dp[i][1] = max(dp[i-1][1], -prices[i]) # 当天持股 return d...

class Solution: def rob(self , nums: List[int]) -> int: dp = [0 for _ in range(len(nums))] dp[1] = nums[0] for i in range(1, len(nums)): dp[i] = max(dp[i-1], dp[i-2]+nums[i-1]) maxNum = dp[-1] dp = [0 for _ in range(len(nums)+1)] dp[1] = 0 for i in range(2, len(nums)+1): dp[i] = max(dp[i-1], dp[i...