题目描述 在不使用额外的内存空间的条件下判断一个整数是否是回文。 回文指逆序和正序完全相同。（负数不是回文） 例1 输入：121 返回值：true 题目分析 对于判断数字是否是回文有两种方式： ①数字转字符串，双指针判断：可以将数字转换成字符串，然后再采用判断字符串是否是回文的方式进行判断。 ②反转数字：主要是将数字的高位数字与低位数字调换，计算反转后的数字是否与之前相等。对于反转数字来说，可能会导致溢出的情况，需要进行溢出判断。 解题思路 方法1：数字转字符串，双指针判断是否回文 判断字符串是否是回文的方式比较简单，使用双指针，一个指向字符串头部，一个指向字符串尾部，两隔指针指向的字符相同...

题目描述 给你一个大小为n的字符串数组strs，其中包含n个字符串，编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。 数据范围：0<=n<=5000, 0<=len(strs[i])<=5000 例1 输入：["abca","abc","abca","abc","abcc"] 返回值："abc" 题目分析 想要获取数组中所有字符串的最长公共前缀，需要遍历每个字符串的字符，进行比较，比较的方法主要有两种： ①横向比较：先比较两个字符串的...

题目描述 给出一个有n个元素的数组S，S中是否有元素a,b,c 满足 a+b+c=0? 找出数组S中所有满足条件的三元组。 数据范围：0<= n <= 1000 ，数组中各个元素满足 |val|<= 100 注意：三元组(a,b,c)中的元素必须按非降序排列。解集中不能包含重复的三元组。 例： S= {-10 0 10 20 -10 -40}， 解集为(-10, -10, 20), (-10, 0, 10) 题目分析 获取三元组的思路可以借鉴二元组（两个数之和为0），区别是需要先确定一个数，然后找和等于它的相反数的另两个数，其实就是多了一层循环，不断更改确定的数，主要思路代...

题目描述 合并k个升序的链表并将结果作为一个升序的链表返回其头节点。 数据范围：节点总数 0<=n<=5000，每个节点的val 满足 |val|<=1000 要求：空间复杂度O(1)，时间复杂度O(nlogn) 例如： 输入：[{1,2,3},{4,5,6,7}] 返回值：{1,2,3,4,5,6,7} 题目分析 合并k个链表，因为链表是升序的，使用k个节点记录每个链表当前节点位置，每次只需要在这k个节点中选择一个最小的作为结果节点，且选择的链表也相应往后推，直到所有的链表都遍历完。如图： 解题思路 方法1：先获得链表的所有节点，然后对节点进行整体排序 最简单的做法就...

题目描述 将给出的链表中的节点每k个一组翻转，返回翻转后的链表。如果链表中的节点数不是k的倍数，将最后剩下的节点保持原样，你不能更改节点中的值，只能更改节点本身。 例如： 给定的链表是1->2->3->4->5 对于k=2，你应该返回 2->1->4->3->5 对于k=3，你应该返回 3->2->1->4->5 题目分析 题目是在链表的翻转基础上，增加了一个长度的限制k，每k个进行一次翻转，首先我们要知道如何翻转一个链表，然后需要将这些翻转的部分连接起来，链表的翻转可以使用头插法，如图： 因为每次要把翻转的节点换到头...

题目描述 请编写一个程序，给数独中剩余的空格填写上数字，空格用字符'.'来表示，假设给定的数独只有唯一的解法。 示例1： 输入： [[.,.,9,7,4,8,.,.,.],[7,.,.,.,.,.,.,.,.],[.,2,.,1,.,9,.,.,.],[.,.,7,.,.,.,2,4,.],[.,6,4,.,1,.,5,9,.],[.,9,8,.,.,.,3,.,.],[.,.,.,8,.,3,.,2,.],[.,.,.,.,.,.,.,.,6],[.,.,.,2,7,5,9,.,.]] 返回值： [[5,1,9,7,4,8,6,3,2],[7,8,3,6,5,2,4,1,9],[4,2,6,...

题目描述 给出一组候选数 c和一个目标数 t，找出候选数中和等于t的所有组合。 c中每个数字在一个组合中只能使用一次。 注意： 1.题目中所有的数字都是正整数。 2.组合中数字（a1,a2...ak）要按非递减排序。 3.结果中不能包含重复的组合。 4.组合之间的排序按照索引从小到大依次比较，小的排在前面，如果索引相同的情况下数值相同，则比较下一个索引。 示例： 侯选数：[10,20,60,10], 目标数：80 组合结果：[[10,10,60], [20,60]] 题目分析 数字的组合是指从候选数中选出若干个数的数字，当它们的和等于目标值时是一个结果，与选择数字的顺序无关。 对于数字的组合情...

题目描述 给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。 数据范围： 0<n≤80 < n \le 80<n≤8 ，数组中的值满足 −1≤val≤5-1 \le val \le 5−1≤val≤5 题目分析 题目时在NC43 “没有重复项数字的所有排列” 基础上增加了有重复数字这个条件，因为有重复数字，排列的n!种情况也会有重复的排列，直观地想，可以在排列结果中，若是遇到相同的排列，则不加入结果中，如图： 在判断是否已经存在排列时，需要对已有的排列都遍历一遍，时间复杂度为O(n2)O(n^2)O(n2)，而这个判断判断是在dfs方法中的，dfs...

题目描述 给出一组数字，返回该组数字的所有排列 例如： [1,2,3]的所有排列如下 [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1]. （以数字在数组中的位置靠前为优先级，按字典序排列输出。） 数据范围：数字个数 0<n≤60 < n \le 60<n≤6 题目分析 获取数字的所有排列是一个典型的dfs问题，使用一个列表记录排列的数字，获取排列的过程就是不断在数组中选择数字的过程，从第一个数字开始直到最后一个数字被选择完后，列表即为排列结果，因为数字的排列一共有n!种情况，如图： 因为数字是不能被重复选择的，所以需要记录下之...

题目描述 N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后， 要求：任何两个皇后不同行，不同列也不再同一条斜线上， 求给一个整数 n ，返回 n 皇后的摆法数。 题目分析 对于n皇后的放置，主要有三个放置要求（不同行、不同列、不同斜线），可以先考虑不同行的情况，即在每一行只选择一个位置，记录上前面的位置，后面选择位置只需要判断另外的两个方向，对于排列枚举的情况，一共有n!种。 可以遍历枚举的所有情况，当满足三个条件的结果出现时，方法数加1。 解题思路 遍历枚举的情况的过程就是dfs的过程，从第1行开始，每行可以从1~n列中选择一个作为放置位置，只要不和前面冲突，可以继续下一行的选择，直...

题目描述 n个节点n-1条边的无向连通图，两个点a，b，a位于1，b位于x，两点移动速度相同，求a和b移动到同一节点所需的最多节点数。输入第一个参数为 n ，(1≤n≤100,000)第二个参数为 x ，(1≤x≤n)第三个参数为大小为 n−1 的点对 的集合，其中 表示结点ui与结点vi之间有一条边，1≤ui,vi≤n返回最多需要经过的节点数（包括 1 号节点在内）示例1输入：5,2,[(1,2),(2,3),(3,4),(2,5)]返回值：4 题目分析 连通图的概念是图中的任意两点之间都能有路径到达，当n个结点只有n-1条边形成的连通图一定是树状的，题目设定两个点a,b，a点固定从1出...

题目描述 给出一颗以1为根的树，树上节点的值只为1或者0，在最多经过两个值为1的节点的情况下，有多少条到达叶节点的路径？输入第一个参数为 n ，(1≤n≤100,000)第二个参数为大小为 n-1 的点对 的集合，其中 表示结点 ui 与结点 vi之间有一条边， , 第三个参数为大小为 n 的 0/1 序列 f ， 为i-1结点的值。返回一个整数，表示路径数示例1输入：7,[(7,2),(6,1),(5,2),(1,2),(4,6),(6,3)],[0,0,1,0,1,0,0]返回值：4说明：样例中的四条路径分别为: (1 - 2 - 7), (1 - 2 - 5) , (1 - 6 -...

题目描述 给定一颗节点编号为1~n的，且以1为根的树，给出n组询问，每次询问给定一个数对(x,y)，求i为x到根路径上的点(包括x和根) (y+2i)xor(y+i)，对于这n组询问的答案，不需要依次输出n个数，你只需要输出他们的和对998244353的取模即可。树的信息以及询问不会直接给出，输入数据只包含随机种子，具体生成方式请仔细阅读备注内容。示例1输入：3,1,1,1,1返回值：7备注：输入数据包含5个整数，n,seed1,seed2,seed3,x.树的信息生成伪代码如下//////////////////////1/////////////////////定义边集数组u[],v[] ...

题目描述 在一颗有 n 个结点且以 1 为根节点树上，起初每个结点的初始权值为 0 。现在有 q 次操作，每次操作选择将以 为根节点的子树上的所有结点权值增加 。求 q 次操作后从 1 到 n 每个结点的权值。输入:第一个参数为 n，1≤n≤100,000第二个参数为边 的集合，其中 表示结点 与结点 之间有一条边，1≤ui,vi≤n第三个参数为 q，1≤q≤100,000第四个参数为 q 次询问的 的集合，1≤ri≤n,0≤∣vi∣≤1000,000返回:从 1 到 n 每个结点的权值。示例1输入：5,[(2,5),(5,3),(5,4),(5,1)],2,[(1, 3), (2, -...