NC112 进制转换 描述 给定一个十进制数 M ，以及需要转换的进制数 N 。将十进制数 M 转化为 N 进制数。 当 N 大于 10 以后， 应在结果中使用大写字母表示大于 10 的一位，如 'A' 表示此位为 10 ， 'B' 表示此位为 11 。 若 M 为负数，应在结果中保留负号。 数据范围： M <= 10^8, 2≤N≤16 要求：空间复杂度O(M)，时间复杂度 O(M) 思路：题目很简单，就是做除法，然后取余。M = k1N^n+k2N^(n-1)+……+kn*N+k0 M % N = k0, M = M//N = k1N^(n-1)+k2N^(n-2)+……+k(n-1...

NC106 三个数的最大乘积 描述： 给定一个长度为 nn 的无序数组 AA ，包含正数、负数和 0 ，请从中找出 3 个数，使得乘积最大，返回这个乘积。 要求时间复杂度： O(n) ，空间复杂度： O(1) 。 数据范围：3≤n≤10^4，-10^4≤A[i]≤10^4 思路：数组的情况分为全正数，全负数，正数+负数，正数+0，0+负数，正数+0+负数。如果数组长度为3，直接全部相乘， 全正数：最大的3个数相乘（3大）。 全负数：3大。 正数+负数：可能是一正n（n>=3)负，两正n(n>=2)负，三正n(n>=1)负。 一正的情况，结果为一正两负相乘（1大2小）。 两正...

NC71 旋转数组的最小数字 描述 有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。 数据范围：1≤n≤10000，数组中任意元素的值: 0≤val≤10000 要求：空间复杂度：O(1) ，时间复杂度：O(logn) 和题目“NC48 在旋转过的有序数组中寻找目标值”有点像，就是这个数组是不降序的，需要再处理一下。思路是一样的 思路：数组分成两部分，左边和右边，左右内部升序，左边值不小于右边...

二叉树中和为某一值的路径(一) 描述 给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点 2.叶子节点是指没有子节点的节点 3.路径只能从父节点到子节点，不能从子节点到父节点 4.总节点数目为n 数据范围： 1.树上的节点数满足 0≤n≤10000 2.每 个节点的值都满足 0∣val∣≤1000 要求：空间复杂度 O(n)，时间复杂度 O(n) 进阶：空间复杂度 O(树的高度)，时间复杂度 O(n) 思路：我感觉二叉树的题基本上都是递归，然后都特别简单。当然还可以遍历，深度...

链表中倒数最后k个结点 描述 输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。 如果该链表长度小于k，请返回一个长度为 0 的链表。 数据范围：0≤n≤10^5，0≤a≤10^9，0≤k≤10^9 要求：空间复杂度 O(n)，时间复杂度 O(n) 进阶：空间复杂度 O(1)，时间复杂度 O(n) 思路：双指针，链表长度为n，需要返回倒数k个节点，首先得找到这个节点的位置，节点位置在n-k处，指针fast先走k步，然后result再走，当fast走到链表结尾的时候，result刚好走到n-k处，所以一次循环搞定。fast每走一步k自减一，fast走到k处时，...

回文数字 描述 在不使用额外的内存空间的条件下判断一个整数是否是回文。 回文指逆序和正序完全相同。 数据范围：-2^31≤n≤2^31-1 进阶： 空间复杂度 O(1)，时间复杂度 O(len(n)) 提示： 负整数可以是回文吗？（比如-1） 如果你在考虑将数字转化为字符串的话，请注意一下不能使用额外空间的限制 你可以将整数翻转。但是，如果你做过题目“反转数字”，你会知道将整数翻转可能会出现溢出的情况，你怎么处理这个问题？ 思路：根据提示，如果是负数的时候，返回False，我之前是准备之间通过l = len(str(x))获取数字的长度，然后再用通过x除以10^l得到最高位，但是想了一下，之后...

求路径 描述 一个机器人在m×n大小的地图的左上角（起点）。 机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。 可以有多少种不同的路径从起点走到终点？ 备注：m和n小于等于100,并保证计算结果在int范围内 数据范围：0<n,m≤100，保证计算结果在32位整型范围内 要求：空间复杂度 O(nm)，时间复杂度 O(nm) 进阶：空间复杂度 O(1)，时间复杂度 O(min(n,m)) 思路：这是一道数学题，m*n的地图，从左上角到右下角需要往右走n-1步，往下走m-1步，总共需要走m+n-2步。要计算总的路径条数，就是C(m+n-2)中选(m-1)或者C(m+n-2)中...

数组中出现次数超过一半的数字 描述 给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。 数据范围：0n≤50000，数组中元素的值 0≤val≤10000 要求：空间复杂度：O(1)，时间复杂度 O(n) 输入描述： 保证数组输入非空，且保证有解 思路：可以排序，但是排序复杂度是O(nlogn)，空间复杂度也不会低，也可以遍历然后计数，如果次数大于数组长度的一半，则返回，时间、空间复杂度是O(n)。 最后一种解法是看评论得出的，...

NC63 扑克牌顺子 描述 现在有2副扑克牌，从扑克牌中随机五张扑克牌，我们需要来判断一下是不是顺子。 有如下规则： A为1，J为11，Q为12，K为13，A不能视为14 大、小王为 0，0可以看作任意牌 如果给出的五张牌能组成顺子（即这五张牌是连续的）就输出true，否则就输出false。 4.数据保证每组5个数字，每组最多含有4个零，数组的数取值为 [0, 13] 要求：空间复杂度 O(1)，时间复杂度 O(nlogn)，本题也有时间复杂度 O(n) 的解法 思路： 遍历数组，获取数组的最大值mx，最小值mn，0的个数zero， 如果数组有除0之外，相同的值，则返回false，如果没有...

NC13 二叉树的最大深度 描述 求给定二叉树的最大深度， 深度是指树的根节点到任一叶子节点路径上节点的数量。 最大深度是所有叶子节点的深度的最大值。 （注：叶子节点是指没有子节点的节点。） 数据范围：0≤n≤100000，树上每个节点的val满足 ∣val∣≤100 要求： 空间复杂度 O(1),时间复杂度 O(n) 思路：题目很简单，就是比左右子树的最大深度多一，然后取其中较大值，就可以了，用递归的方法，非常简单，几分钟搞定。 # class TreeNode: # def __init__(self, x): # self.val = x # se...

NC66 两个链表的第一个公共结点 描述 输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的） 数据范围： 0n≤1000 要求：空间复杂度 O(1)，时间复杂度 O(n) 思路：一、如果有公共节点，那么两链表的后面部分完全相同，所以可以从后往前遍历，直到两个不同。因为链表没法从后往前遍历，所以需要反转两个链表，之后两个反转链表从后往前遍历，用result记录当前节点，如果相等，将当前节点赋给result，如果不相等的，则result.next = None，然后再将这个公共链表反...

第一个只出现一次的字符 描述: 在一个长为 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数） 数据范围：0≤n≤10000，且字符串只有字母组成。 要求：空间复杂度 O(n)，时间复杂度 O(n) 思路：遍历字符串，把字母存入数组，并记录位置，如果字母在数组中出现过，将位置记为-1，不用再存入数组。最后遍历数组，将第一个位置不为-1的返回。如果没有，返回-1。 # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param str string字符串 # @return int整型 # c...

将升序数组转化为平衡二叉搜索树 描述 给定一个升序排序的数组，将其转化为平衡二叉搜索树（BST）. 平衡二叉搜索树指树上每个节点 node 都满足左子树中所有节点的的值都小于 node 的值，右子树中所有节点的值都大于 node 的值，并且左右子树的节点数量之差不大于1 数据范围：0≤n≤10000，数组中每个值满足 ∣val∣≤5000 进阶：空间复杂度 O(n) ，时间复杂度 O(n) 思路：题目很简单，因为这个数组是升序的，既然是升序的，那么就可以直接精准的找到中间节点设为根节点，然后用递归构建左子树和右子树即可。 # class TreeNode: # def __init__...

兑换零钱(一) 描述 给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。 如果无解，请返回-1. 数据范围：数组大小满足 0≤n≤10000 ， 数组中每个数字都满足 0<val≤10000，0≤aim≤5000 要求：时间复杂度 O(n×aim) ，空间复杂度 O(aim)。 思路：这道题我还真不太会，考察动态规划，我一开始想的是将arr数组中小于aim的取出来，然后排序得到arr_sort。之后将aim除以arr_sort中最大的，得到的余数是新的aim，最后aim等...