二叉树的镜像 描述 操作给定的二叉树，将其变换为源二叉树的镜像。 数据范围：二叉树的节点数 0≤n≤1000 ， 二叉树每个节点的值 0≤val≤1000 要求： 空间复杂度 O(n) 。本题也有原地操作，即空间复杂度 O(1) 的解法，时间复杂度 O(n) 思路：题目很简单，就左右子树交换，然后左右子树的左右子树也交换，即递归左右子树交换，非常简单 # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = Non...

对称的二叉树 描述 给定一棵二叉树，判断其是否是自身的镜像（即：是否对称） 数据范围：节点数满足 0≤n≤1000，节点上的值满足∣val∣≤1000 要求：空间复杂度 O(n)，时间复杂度 O(n) 备注： 你可以用递归和迭代两种方法解决这个问题 思路：题目挺简单的，将pRoot分成左子树leftTree和右子树rightTree，leftTree的每一个子树的左边节点left的值等于rightTree的每一个子树的右边节点right的值，leftTree的每一个的右边节点right的值等于rightTree的左边节点left的值，递归一下就行了。 # class TreeNode: # ...

判断是不是平衡二叉树 输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。 平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 思路：用递归，如果当前节点的左右层数超过1，则不是平衡二叉树，如果没有超过1，则判断左右子树是否为平衡二叉树,如果左右子树都为平衡二叉树则改数为平衡二叉树 # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None #...

调整数组顺序使奇数位于偶数前面(一) 输入一个长度为 n 整数数组，数组里面不含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。 数据范围：0≤n≤5000，数组中每个数的值 0≤val≤10000 要求：时间复杂度 O(n)，空间复杂度 O(n) 进阶：时间复杂度 O(n^2)，空间复杂度 O(1) 思路：题目很简单，方法一：定义两个数组，一个存奇数，一个存偶数，然后合并两个数组。方法二：在原数组的基础上修改，找到一个奇数就把这个奇数往前挪，所以需要记录当前有多少个奇数，如果当...

数字在升序数组中出现的次数 给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数 数据范围：0≤n≤1000,0≤k≤100，数组中每个元素的值满足 0≤val≤100 要求：空间复杂度 O(1)，时间复杂度 O(logn) 题目非常简单，用二分先找到k出现的位置middle，然后从middle的左边右边遍历，复杂度为logn+k出现的次数，空间复杂度1 # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param data int整型一维数组 # @param k int整型 # @return int整型 ...

有效括号序列 给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列 括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。 数据范围：字符串长度 0≤n≤10000 要求：空间复杂度 O(n)，时间复杂度 O(n) python没有栈，所以我用数组，当([{时，存入，当字符为)]}时取出，题目不难 # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param s string字符串 # @return bool布尔型 # class Sol...

判断一个链表是否为回文结构 描述 给定一个链表，请判断该链表是否为回文结构。 回文是指该字符串正序逆序完全一致。 数据范围： 链表节点数 0≤n≤10^7，链表中每个节点的值满足 ∣val∣≤^7 解法：快慢指针，将链表分成两部分，前半部分的长度=后半部分的长度（+1），然后后半部分逆序（之前的有做过逆序的题目，这里直接拿来用了），之后比较两部分的值是否相等。 ```# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名...

给定一个节点数为n的无序单链表，对其按升序排序。 数据范围：0<n≤100000 要求：空间复杂度 O(n)，时间复杂度O(nlogn) 解法：递归分治归并排序，递归将head切成两个列表head1和head2，到最后不能再切（即head内只有一个元素），head1和head2只有一个元素的时候合并head1和head2，合并后的head是有序的，一直往上head1和head2一直有序 上一个题目是合并两个有序链表，我直接拿上一个题目的算法直接用了 我自己写的话复杂度应该可能是n(n-1)/2，自己写的话，会新定义一个list，将head种最小的截出来，放入list结尾，复杂度为1+2+...

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。 数据范围： 0≤n≤1000，−1000≤节点值≤1000 要求：空间复杂度 O(1)，时间复杂度 O(n) # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param pHead1 ListNode类 # @param pHead2 ListNode类 # @return ListNode类 ...

题目：最长公共前缀 描述 给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。 数据范围： 0≤n≤5000， 0≤len(strs_i)≤5000 进阶：空间复杂度 O(n)，时间复杂度 O(n) 思路： 解法一：横向比较，先比较前两个字符串的相同部分，存入result，result和下一个比，相同部分作为result，一直到最后一个 解法二：纵向比较,先将第一个字符串的第一个字母拿出来和数组其它字符串第一个比，相同存入result，再取下一个，再比相同再存，不同就返回result 解法三：只需要比较差别最大的...

题目：两数之和 描述：给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。 数据范围：2≤len(numbers)≤1500，−10≤numbers≤10^9,0≤target≤10^9 要求：空间复杂度 O(n)，时间复杂度 O(nlogn) 例如： 给出的数组为 [20, 70, 110, 150] , 目标值为90 返回一个数组 [1,2] ，因为 numbers_1+numbers_2=20+70=90 思路：这个题目比较麻烦的是时间复杂度要O(nlogn)，简单的代码直接用for循环套for循环，挨个遍历，...

求平方根，向下取整 其实方法sqrta已经可以求出平方根了，min为1，max为x 不过由于我小时候我爸教过我怎么笔算平方根，所以这里写一下，大概是根据a^2=b^2+2bc+c^2计算。 因为没有办法直接得出x = a^2，所以，先算b。 比如说 1234 先得出 300^2 < 123456 < 400^2,所以用1234-300^2，再计算十位数，最后计算个位数。 sqrta计算的是结果高位第一个的值，循环次数是由1-3二分，或者4-9二分查找。 sqrtb计算的是c的值，是在x-b^2 > 2b^c+c^2 成立的基础上的c最大值 算法复杂度为log以100为底，x为...

这道题我之前想了好几种方法，但是复杂度基本都是n^2，看评论才知道的算法，而且题目提示了，考察的知识点是位运算，但是比较郁闷的是，如果要返回的结果是负数，答案还是错的，但是结果转化成二进制后每一位的01是完全一致的，所以在负数的时候还需要考虑正负转换，另外把自己写的三种解法也贴在后面吧，用jupyter写的，三种解法思路基本是一样的，贴一下，记录一下自己的代码。 题目：数组中只出现一次的数（其它数出现k次） 描述：给定一个长度为 n 的整型数组 arr 和一个整数 k(k>1) 。 已知 arr 中只有 1 个数出现一次，其他的数都出现 k 次。 请返回只出现了 1 次的数。 数据范围:...

题目：链表中环的入口结点 描述 给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。 数据范围： n≤10000 节点值范围：[1,10000] 要求：空间复杂度 O(1)，时间复杂度 O(n) 这个题目我之前有思路，但是只在环的长度大于前面链的情况下成立，看评论知道了方法，记录一下 ```# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: ...