本文共 13951 字，大约阅读时间需要 46 分钟。
- 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
解题思路：从头到尾遍历一次，如果碰到偶数，则从该偶数位置往后查找，查找到第一个奇数，将该奇数值记录下来，pop掉之后，再将该奇数插入到偶数之前的位置；
class Solution: def reOrderArray(self, array): # write code here left = 0 n = len(array) while left < n: if array[left]%2!=0: left += 1 else: for i in range(left+1,n): if array[i]%2!=0: tmp = array[i] array.insert(left,tmp) array.pop(i+1) break left += 1 return array
2.镜像二叉树：
class Solution: # 返回镜像树的根节点 def Mirror(self, root): # write code here if not root: return root node = root.left root.left = root.right root.right = node self.Mirror(root.left) self.Mirror(root.right) return root
3.输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
解题思路：二叉搜索树有一个性质，根节点的值要大于左子树所有值，小于右子树所有值。因为后序遍历最后一个值为子树的根结点，那么先得到数组最后一个值a，然后再找到第一个比a大的数，在a之前的为左子树，在a之后的为右子树，再观察右子树中是否所有值都大于a，如果不满足则return False。递归
代码：
class Solution: def VerifySquenceOfBST(self, sequence): # write code here s = sequence if s == None or len(s) == 0: return False n = len(s) root = s[n-1] for i in range(n): if s[i] > root: break for j in range(i,n): if s[j] < root: return False left = True if i > 0: left = self.VerifySquenceOfBST(s[0:i]) right = True if i < n-1: right = self.VerifySquenceOfBST(s[i:n-1]) return left and right
4.输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
解题思路：递归，回溯，找到所有组合
# -*- coding:utf-8 -*-class Solution: def dfs(self,res,n,ss,temp,book): if len(temp) == n and temp not in res: res += [temp] return for i in range(n): if book[i] == 0: book[i] = 1 self.dfs(res,n,ss,temp+ss[i],book) book[i] = 0 def Permutation(self, ss): # write code here res = [] n = len(ss) if n == 0 or n==1: return ss book = [0]*n self.dfs(res,n,ss,'',book) return res
5.输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
思路：创建两个指针，一个指向头一个指向尾。res只记录满足两数之和等于tsum的并且乘机和(muti)当前最小的两个数。
class Solution: def FindNumbersWithSum(self, array, tsum): # write code here low = 0 high = len(array)-1 res = [] muti = 10000 while low
6.汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
思路：创建一个旋转函数（逆序函数），如’abc’→’cba’，然后对字符串按k分成两块，分别调用旋转函数，再对整体调用一次旋转函数。涉及字符串换位旋转的都可以用这种方法。
# -*- coding:utf-8 -*-class Solution: def change(self,s): return s[::-1] def LeftRotateString(self, s, n): # write code here s1 = self.change(s[0:n]) s2 = self.change(s[n:]) res = self.change(s1+s2) return res
7.例如，“student. a am I”。这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
思路：与上题类似，对每个单词旋转，再对整体旋转，注意空格
# -*- coding:utf-8 -*-class Solution: def change(self,s): return s[::-1] def ReverseSentence(self, s): # write code here s = s.split(' ') s_reverse = '' for x in s: s_reverse += self.change(x) + ' ' #结尾会多个空格 return self.change(s_reverse)[1:] #结尾的空格反转到了头部，所以从1位置之后打印 8.上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。
思路：排序后，统计0的个数，如果0的个数>=4，则直接返回True，否则，遍历一次剔除0的数组，前后差距如果==1，则continue；如果 != 1 ，那么在该i位置插入numbers[i-1]+1的值，并使num_0-1，如果当num_0等于一的时候还出现前后差距>1的情况，直接返回False。
# -*- coding:utf-8 -*-class Solution: def IsContinuous(self, numbers): # write code here if not numbers: return False numbers = sorted(numbers) n = len(numbers) num_0 = numbers.count(0) numbers = numbers[num_0:] if num_0 >= 4: return True for i in range(1,n): if numbers[i] - numbers[i-1] != 1 and num_0 == 0: return False elif numbers[i] - numbers[i-1] != 1 and num_0 != 0: numbers.insert(i,numbers[i-1]+1) num_0 -= 1 return True
9.一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。
思路：hash，遍历一遍存入字典，然后对字典value值升序排序，取出前两个。
# -*- coding:utf-8 -*-class Solution: # 返回[a,b] 其中ab是出现一次的两个数字 def FindNumsAppearOnce(self, array): # write code here# res = []# for x in array:# if array.count(x) == 1:# res.append(str(x))# return res dic = {} for i in range(len(array)): if array[i] not in dic.keys(): dic[array[i]] = 1 else: dic[array[i]] += 1 dic = sorted(dic.items(),key = lambda x:x[1],reverse = False) return [dic[0][0],dic[1][0]]
对于一个有序数组arr，再给定一个整数num，请在arr中找到num这个数出现的最左边的位置。
给定一个数组arr及它的大小n，同时给定num。请返回所求位置。若该元素在数组中未出现，请返回-1。
测试样例：
[1,2,3,3,4],5,3
返回：2
# -*- coding:utf-8 -*-class LeftMostAppearance: def findPos(self, arr, n, num): # write code here res = -1 left, right = 0, n-1 while left <= right: mid = left+(right-left)/2 if arr[mid] > num: right = mid - 1 continue if arr[mid] < num: left = mid + 1 continue if arr[mid] == num: res = mid right = mid - 1 return res
对于一个有序循环数组arr，返回arr中的最小值。有序循环数组是指，有序数组左边任意长度的部分放到右边去，右边的部分拿到左边来。比如数组[1,2,3,3,4]，是有序循环数组，[4,1,2,3,3]也是。
给定数组arr及它的大小n，请返回最小值。
测试样例：
[4,1,2,3,3],5
返回：1
# -*- coding:utf-8 -*-class MinValue: def getMin(self, arr, n): low=0 high=n-1 # arr[low] >= arr[high] while low<=high:#和寻找元素最左出现的位置”这部分是一样的 mid=low+(high-low)/2 if arr[low]>arr[mid]: #左一半 high=mid elif arr[mid]>arr[high]: #右一半 low=mid+1 else: #arr[low]==arr[mid]==arr[right] 特殊情况 只能挨个遍历，之前两个if最后到了一个元素的也会到达这里进行最终的判断 cur=arr[low] while low arr[low+1]: cur=arr[low+1] low=low+1 return cur
12.动态规划割绳子：
给你一根长度为n的绳子，请把绳子剪成m段 (m和n都是整数，n>1并且m>1)每段绳子的长度记为k[0],k[1],…,k[m].请问k[0]
k[1]…*k[m]可能的最大乘积是多少？
例如，当绳子的长度为8时，我们把它剪成长度分别为2,3,3的三段，此时得到的最大乘积是18.
def cut(n): if n==1: return 0 if n==2: return 1 if n==3: return 2 dp = [0]*(n+1) dp[0] = 0 dp[1] = 1 dp[2] = 2 dp[3] = 3 for i in range(4,n+1): max0 = -1 for j in range(1,i//2+1): p = dp[j]*dp[i-j] if max0
13.给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 1:
输入: 2
输出: [0,1,1]
示例 2:
输入: 5
输出: [0,1,1,2,1,2]
class Solution: def countBits(self, num: int) -> List[int]: dp = [0] * (num + 1) dp[0] = 0 for i in range(1,num + 1): dp[i] = self.binCount(i) return dp def binCount(self, x): y = bin(x)[2:] return y.count('1') 14.输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
class Solution: def maxSubArray(self, nums: List[int]) -> int: dp = [0]*len(nums) dp[0] = nums[0] maxnum = dp[0] for i in range(1,len(nums)): dp[i] = max(dp[i-1] + nums[i],nums[i]) maxnum = max(maxnum,dp[i]) return maxnum
字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。
示例1:
输入：“aabcccccaaa”
输出：“a2b1c5a3”
示例2:
输入：“abbccd”
输出：“abbccd”
解释：“abbccd"压缩后为"a1b2c2d1”，比原字符串长度更长。
class Solution: def compressString(self, S: str) -> str: ls = len(S) res = [] cnt = 1 for i in range(ls): if i+1 == ls : res.append(S[i]+str(cnt)) else: if S[i] != S[i+1]: res.append(S[i]+str(cnt)) cnt = 1 else: cnt += 1 return ''.join(res) if len(''.join(res)) < ls else S 16.给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：“abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”
示例 2：
输入：“aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”
class Solution: def countSubstrings(self, s: str) -> int: if len(s) == 1: return 1 l = len(s) cnt = l dp = [[False if i != j else True for i in range(cnt)] for j in range(cnt)] for j in range(0,l): for i in range(0,j): if s[i] == s[j]: if j - i == 1 : dp[i][j] = True else: dp[i][j] = dp[i+1][j-1] else: False if dp[i][j]: cnt += 1 return cnt
17.给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if s == "": return 0 if len(s) == 1: return 1 dic = dict() start, res= 0, 0 #核心思想 滑动窗口 找到字串的开始位置和结束位置，然后利用max刷新纪录字串的最大长度 for end in range(len(s)): if s[end] in dic.keys(): start = max(dic[s[end]],start) res = max(res,end-start +1) dic[s[end]] = end + 1 return res
18.编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
示例 1：
输入：strs = [“flower”,“flow”,“flight”]
输出：“fl”
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: l = len(strs) if l == 0 : return '' minl = 201 pj = '' cnt = 0 flg = True for i in range(l): minl = min(minl,len(strs[i])) for x in strs: pj += x[:minl] for i in range(minl): tmp = pj[i] for j in range(1,l): if tmp != pj[j*minl+i]: flg = False if flg: cnt += 1 return pj[:cnt]
19.统计所有小于非负整数 n 的质数的数量。
示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
class Solution: def countPrimes(self, n: int) -> int: #埃式筛 将质数的倍数全部标记为合数 if n<=1: return 0 isPrime = [True] * n count = 0 for i in range(2,n): if isPrime[i]: count += 1 for j in range(i * i,n,i): isPrime[j] = False return count
20.实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def kthToLast(self, head: ListNode, k: int) -> int: #快慢指针问题 #先让快指针走k步，在同时一起走，直到快指针走到末尾，返回慢指针的值 first = head last = head i = 0 while first: if i < k: first = first.next i += 1 else: first = first.next last = last.next return last.val
21.给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。
# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def sortedArrayToBST(self, nums: List[int]) -> TreeNode:# 二分，递归# if(len(nums)) == 0: return None mid = len(nums)//2 root = TreeNode(nums[mid]) root.left = self.sortedArrayToBST(nums[:mid]) root.right = self.sortedArrayToBST(nums[mid+1:]) return root
22.给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def maxDepth(self, root: TreeNode) -> int: #深度优先遍历，递归 if not root:return 0 return max(self.maxDepth(root.left)+1,self.maxDepth(root.right)+1)
23.给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1 / \ 2 2 / \ / \3 4 4 3
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def isSymmetric(self, root: TreeNode) -> bool: # 递归调用，左子树的左节点和右子树的右节点比较，左子树的右节点和右子树的左节点比较 # 如果左右都为空，则该子树是个叶节点，为镜像的 True # 如果当前节点任意子树不为空，则不是镜像 False # 如果左右节点的值不一样，则也不为镜像 def ismirror(l,r): if not l and not r: return True elif not l or not r: return False elif l.val!=r.val: return False return ismirror(l.left,r.right) and ismirror(l.right,r.left) return ismirror(root,root)
24.将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: res = ListNode() head = res if not l1 and not l2 : return None while l1 and l2: if l1.val <= l2.val: res.next = l1 l1 = l1.next res = res.next else: res.next = l2 l2 = l2.next res = res.next while l1: res.next = l1 l1 = l1.next res = res.next while l2: res.next = l2 l2 = l2.next res = res.next return head.next
转载地址：http://mwwzb.baihongyu.com/