this_is_qiqi-CSDN博客

原创主元素 III-LintCode

描述：给定一个整型数组，找到主元素，它在数组中的出现次数严格大于数组元素个数的1/k。注意事项数组中只有唯一的主元素样例：给出数组 [3,1,2,3,2,3,3,4,4,4] ，和 k = 3，返回 3思路：用哈希的方法建立一一对应，即对于给出的数组中的数m及其个数n，有a[m+500000]=n；（m+500000)是防止

2018-02-07 17:04:48 213

原创翻转链表 II-LintCode

描述：翻转链表中第m个节点到第n个节点的部分注意事项m，n满足1 ≤ m ≤ n ≤ 链表长度样例：给出链表1->2->3->4->5->null， m = 2 和n = 4，返回1->4->3->2->5->null思路：1.先建立四个指针分别指向第m-1、m、n、n+1个节点的位置；2.将第m到n个节点的链表拿出做翻转处理为

2018-02-07 16:50:49 214

原创算法分析与设计课程总结

算法分析与设计课程总结经过8周的学习，我对算法有了更深入的理解。代码水平也有了显著的提高。我们学习的算法有：递归与分治策略，贪心算法，回溯算法，分支限界算法和动态规划算法。一、递归与分治策略（一）递归程序调用自身的编程技巧称为递归。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量

2017-11-02 23:04:14 10747

原创不同的路径 II-LintCode

描述： “不同的路径” 的跟进问题：现在考虑网格中有障碍物，那样将会有多少条不同的路径？网格中的障碍和空位置分别用 1 和 0 来表示。注意事项：m 和 n 均不超过100样例：如下所示在3x3的网格中有一个障碍物： [ [0,0,0], [0,1,0], [0,0,0] ] 一共有2条不同的路径从左上角到右下角。思路：与不同路径思路大体相同，不过需要添

2017-10-29 23:02:18 287

原创不同路径-LintCode

描述：有一个机器人的位于一个 m × n 个网格左上角。机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。问有多少条不同的路径？注意事项：n和m均不超过100样例：给出 m = 3 和 n = 3, 返回 6. 给出 m = 4 和 n = 5, 返回 35.思路: 建立二维数组，表示第i行第j列的路径个数，f[i][j]=f[i-1][j]+f[i][j-

2017-10-29 22:55:41 178

原创数字三角形-LintCode

描述：给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。注意事项：如果你只用额外空间复杂度O(n)的条件下完成可以获得加分，其中n是数字三角形的总行数。样例：比如，给出下列数字三角形：[ [2], [3,4], [6,5,7],[4,1,8,3]] 从顶到底部的最小路径和为11 ( 2 + 3 + 5 + 1 = 11)。思路：通过思

2017-10-29 22:44:50 258

原创栅栏染色-LintCode

描述：我们有一个栅栏，它有n个柱子，现在要给柱子染色，有k种颜色可以染。必须保证不存在超过2个相邻的柱子颜色相同，求有多少种染色方案。注意事项：n和k都是非负整数样例： n = 3, k = 2, return 6 post1， post2， post3way1 0， 0， 1 way2 0， 1，

2017-10-29 22:11:03 290

原创最小路径和-LintCode

描述：给定一个只含非负整数的m*n网格，找到一条从左上角到右下角的可以使数字和最小的路径。注意事项：你在同一时间只能向下或者向右移动一步。思路：建立一个二维数组 ,f[i][j]用来表示以A[i][j]为终点时的最小路径，对于每一个A[i][j]来说，能走到它的方法有两种，即从A[i-1][j]到A[i][j]或者从A[i][j-1]到A[i][j],我们取和较小的赋值给f[i][j]；

2017-10-29 21:39:28 237

原创最长上升连续子序列-LintCode

描述：给定一个整数数组（下标从 0 到 n-1， n 表示整个数组的规模），请找出该数组中的最长上升连续子序列。（最长上升连续子序列可以定义为从右到左或从左到右的序列。）注意事项：time样例：给定 [5, 4, 2, 1, 3], 其最长上升连续子序列（LICS）为 [5, 4, 2, 1], 返回 4. 给定 [5, 1, 2, 3, 4], 其最长上升连续子序列（LICS）为 [

2017-10-29 21:26:17 329

原创爬楼梯-LintCode

描述：假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？样例：比如n=3，1+1+1=1+2=2+1=3，共有3种不同的方法返回 3思路：这个题显然用动态规划比较好处理，设爬到第n层楼梯，它的爬法与它的前两层爬法有关，即可以由n-2层爬两层或由n-1层爬一层。即f(n)=f(n-1)+f(n-2) 这里我们用记忆搜索的方式来

2017-10-29 20:44:41 215

原创验证二叉查找树—LintCode

描述: 给定一个二叉树，判断它是否是合法的二叉查找树(BST)一棵BST定义为：节点的左子树中的值要严格小于该节点的值。节点的右子树中的值要严格大于该节点的值。左右子树也必须是二叉查找树。一个节点的树也是二叉查找树。ac代码：/** * Definition of TreeNode: * class TreeNode { * public: * int val; *

2017-10-12 17:22:15 194

原创快速幂—LintCode

描述：计算a^n % b，其中a，b和n都是32位的整数。样例：例如 2^31 % 3 = 2例如 100^1000 % 1000 = 0思路：二分求幂。ac代码：class Solution {public: /* * @param a, b, n: 32bit integers * @return: An integer */ int m

2017-10-12 17:21:04 174

原创最大间距—LintCode

描述：给定一个未经排序的数组，请找出其排序表中连续两个要素的最大间距。如果数组中的要素少于 2 个，请返回 0.样例：给定数组 [1, 9, 2, 5]，其排序表为 [1, 2, 5, 9]，其最大的间距是在 5 和 9 之间，= 4.思路：利用sort对数组进行排序。找出最大的间距即可。ac代码：class Solution {public: /** * @para

2017-10-12 17:14:24 247

原创寻找缺失的数—LintCode

描述：给出一个包含 0 .. N 中 N 个数的序列，找出0 .. N 中没有出现在序列中的那个数。样例： N = 4 且序列为 [0, 1, 3] 时，缺失的数为2。思路：首先对数组进行排序。再判断nums[i]是否等于i。不等于即缺少的数为i。ac代码：class Solution {public: /** * @param nums: a vector

2017-10-12 17:11:39 209

原创硬币排成线—LintCode

描述：有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。样例： n = 1, 返回 true.n = 2, 返回 true.n = 3, 返回 false.n = 4, 返回 true.n = 5, 返回 true.思路：博弈。为3的倍数必胜。ac代码：class Solution {public: /**

2017-10-12 17:09:35 273

原创买卖股票的最佳时机 —LintCode

描述：假设有一个数组，它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。样例：给出一个数组样例 [3,2,3,1,2], 返回 1 思路：当我们遍历到第i天的时候，我们需要知道前i-1天的最小值。那么就可得出在第i天卖出股票的利润，每一步更新利润的最大值即可。ac代码：class Solution {public:

2017-10-12 17:08:06 218

原创落单的数—LintCode

描述：给出2*n + 1 个的数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。样例：给出 [1,2,2,1,3,4,3]，返回 4思路：从头开始遍历数组，遍历到没有被标记的数时，就遍历后面的数组找到与这个数相同的标记上。最后没有被标记的数就是答案。也可以将所有的数按位异或，最后的值即为答案。ac代码1：class Solution {public: /* *

2017-10-12 17:00:42 461

原创最小子数组—LintCode

描述：给定一个整数数组，找到一个具有最小和的子数组。返回其最小和。样例：给出数组[1, -1, -2, 1]，返回 -3思路：和最大数组思路一致。ac代码：class Solution {public: /* * @param nums: a list of integers * @return: A integer indicate the sum of

2017-10-12 16:54:39 186

原创最大子数组—Lintcode

描述：给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。样例：给出数组[−2,2,−3,4,−1,2,1,−5,3]，符合要求的子数组为[4,−1,2,1]，其最大和为6思路：从头开始遍历，每次添加新元素进行两步操作： 1.比较maxx与sum的大小，使maxx始终为最大的值。 2.判断sum的大小，如果sum小于0，就将sum的值置为0；也就是说舍去前面所有的元素，重新选择子

2017-10-12 16:52:31 155

原创主元素-LintCode

描述：给定一个整型数组，找出主元素，它在数组中的出现次数严格大于数组元素个数的二分之一。样例：给出数组[1,1,1,1,2,2,2]，返回 1思路：创建一个数组a[i]=j; 代表i数字出现了j次。遍历一遍a数组，找出a数组中大于nums.size()/2的值即为答案。ac代码：class Solution {public: /* * @param nums: a li

2017-10-12 16:36:03 330

原创排序列表转换为二分查找树-LintCode

描述：给出一个所有元素以升序排序的单链表，将它转换成一棵高度平衡的二分查找树样例： 21->2->3 => / \ 1 3思路：折半取链表中的元素作为其根节点，左半部分作为其左子树，右半部份作为其右子树。不断递归。相比于数组转换二叉查找树，多了些链表的遍历而已。AC代码：/** * Defi

2017-09-05 23:24:09 206

原创二叉树中的最大路径和-LintCode

描述：给出一棵二叉树，寻找一条路径使其路径和最大，路径可以在任一节点中开始和结束（路径和为两个节点之间所在路径上的节点权值之和）样例：给出一棵二叉树： 1 / \ 2 3返回 6思路：首先要考虑到二叉树中的节点存在正数也存在负数，且最大路径和所在路径是任意两个节点的通路或者是一个节点自己。所以不能直接使用之前根

2017-09-05 23:17:22 2589

原创全排列-LintCode

描述：给定一个数字列表，返回其所有可能的排列。注意事项你可以假设没有重复数字。样例：给出一个列表[1,2,3]，其全排列为：[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]思路：1.当只有一个数时，全排列为其本身。2.当有两个数时，选

2017-09-04 22:45:29 726

原创平面列表-LintCode

描述：给定一个列表，该列表中的每个要素要么是个列表，要么是整数。将其变成一个只包含整数的简单列表。注意事项如果给定的列表中的要素本身也是一个列表，那么它也可以包含列表。样例：给定 [1,2,[1,2]]，返回 [1,2,1,2]。给定 [4,[3,[2,[1]]]]，返回 [4,3,2,1]。思路：我

2017-08-31 22:33:41 680 2

原创平衡二叉树-LintCode

描述：给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是：一棵二叉树中每个节点的两个子树的深度相差不会超过1。样例：给出二叉树 A={3,9,20,#,#,15,7}, B={3,#,20,15,7}A) 3 B) 3 / \ \ 9 20

2017-08-31 22:23:31 440

原创合并区间-LintCode

描述：给出若干闭合区间，合并所有重叠的部分。样例：给出的区间列表 => 合并后的区间列表：[ [ [1, 3], [1, 6], [2, 6], => [8, 10], [8, 10], [15, 18] [15, 18]

2017-06-14 23:54:57 241

原创两数组的交 II -LintCode

描述：计算两个数组的交注意事项每个元素出现次数得和在数组里一样答案可以以任意顺序给出样例：nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].思路：这道题的思路与两组数的交一样是建立哈希表，区别在于将a[x]的值改为i+1，最后输出a[x]的值个x。class Solution {p

2017-06-14 23:49:13 166

原创两组数的交-LintCode

描述：返回两个数组的交注意事项Each element in the result must be unique.The result can be in any order.样例：nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2].思路：这道题建立了一个哈希函数，建立数组a[ ]=0，令a

2017-06-14 23:39:12 285

原创整数排序-LintCode

描述：给一组整数，按照升序排序，使用选择排序，冒泡排序，插入排序或者任何 O(n2) 的排序算法。样例：对于数组 [3, 2, 1, 4, 5], 排序后为：[1, 2, 3, 4, 5]。思路：无论是冒泡排序、选择排序、插入排序都是O（n^2）的算法。AC代码：冒泡排序：class Solution {public: /**

2017-06-14 23:35:12 240

原创 Convert BST to Greater Tree-LintCode

描述：Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST

2017-05-21 21:57:43 159

原创在二叉查找树中插入节点-LintCode

描述：给定一棵二叉查找树和一个新的树节点，将节点插入到树中。你需要保证该树仍然是一棵二叉查找树。注意事项You can assume there is no duplicate values in this tree + node.样例：给出如下一棵二叉查找树，在插入节点6之后这棵二叉查找树可以是这样的： 2

2017-05-21 21:32:02 258

原创子树-LintCode

描述：有两个不同大小的二进制树： T1 有上百万的节点； T2 有好几百的节点。请设计一种算法，判定 T2 是否为 T1的子树。注意事项若 T1 中存在从节点 n 开始的子树与 T2 相同，我们称 T2 是 T1 的子树。也就是说，如果在 T1 节点 n 处将树砍断，砍断的部分将与 T2 完全相同。样例：下面的例子中 T

2017-04-11 17:46:48 244

原创二叉树的最小深度-LintCode

描述：给定一个二叉树，找出其最小深度。二叉树的最小深度为根节点到最近叶子节点的距离。样例：给出一棵如下的二叉树: 1 / \ 2 3 / \ 4 5 这个二叉树的最小深度为 2思路：一开始想偷懒直接将求二叉树最大深度中的大于号

2017-04-11 17:45:33 221

原创二叉树的最大深度-LintCode

描述：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的距离。样例：给出一棵如下的二叉树: 1 / \ 2 3 / \ 4 5这个二叉树的最大深度为3.思路：这个题就是递归，不断返回左右子树中较大的高度。代码：/** * Definition of TreeNode: * c

2017-04-11 17:30:01 382

原创翻转二叉树-LintCode

描述：翻转一棵二叉树样例： 1 1 / \ / \2 3 => 3 2 / \ 4 4思路：这个题就是递归调用 swap( , ) 函数，交换一个根节点的左右子树。代码：/** * Definition of TreeNode:

2017-04-11 17:22:02 156

原创等价二叉树-LintCode

描述：检查两棵二叉树是否等价。等价的意思是说，首先两棵二叉树必须拥有相同的结构，并且每个对应位置上的节点上的数都相等。样例： 1 1 / \ / \ 2 2 and 2 2 / /4 4就是两棵等价的二叉树。 1

2017-04-11 17:16:07 154

原创将二叉树拆成链表-LintCode

描述：将一棵二叉树按照前序遍历拆解成为一个假链表。所谓的假链表是说，用二叉树的 right指针，来表示链表中的 next 指针。注意事项不要忘记将左儿子标记为 null，否则你可能会得到空间溢出或是时间溢出。样例： 1 \ 1 2 / \

2017-04-11 16:51:31 239

原创把排序数组转换为高度最小的二叉搜索树-LintCode

描述：给一个排序数组（从小到大），将其转换为一棵高度最小的排序二叉树。注意事项There may exist multiple valid solutions, return any of them.样例：给出数组 [1,2,3,4,5,6,7], 返回 4 / \ 2 6 / \ / \

2017-04-11 16:34:25 249

原创克隆二叉树-LintCode

描述：深度复制一个二叉树。给定一个二叉树，返回一个他的克隆品。样例：给定一个二叉树： 1 / \ 2 3 / \4 5返回其相同结构相同数值的克隆二叉树： 1 / \ 2 3 / \4 5思路：这个题还是利用递归思想，对

2017-04-11 16:27:45 215

原创二叉树的所有路径-LintCode

描述：给一棵二叉树，找出从根节点到叶子节点的所有路径。样例：给出下面这棵二叉树： 1 / \2 3 \ 5所有根到叶子的路径为：[ "1->2->5", "1->3"]思路：这道题与二叉树的路径和的思想是一样的，只是换了一种存储和输出方式。基本思想还是递归，访问从根节点到叶子节点的路径，

2017-04-11 15:35:28 224

空空如也

空空如也