指尖的舞曲_个人页
指尖的舞曲
文章
915
问答
0
视频
0
个人介绍
目前在阿里巴巴搬砖
擅长的技术
- 容器
- 数据库
-
发表了文章 2014-12-08
careercup-递归和动态规划 9.9
9.9 设计一种算法，打印八皇后在8*8棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。 类似leetcode：N-Queens 回溯法的实现代码： #include #include #includ...
-
发表了文章 2014-12-08
careercup-递归和动态规划 9.8
9.8 给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码就是n分有几种表示法。 解法： 使用回溯法进行解决，实际上就是一个类似枚举的过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
-
发表了文章 2014-12-08
careercup-递归和动态规划 9.7
9.7 编写函数，实现许多图片编辑软件都支持的“填充颜色”功能。给定一个屏幕（以二维数组表示，元素为颜色值）、一个点和一个新的颜色值，将新颜色值填入这个点的周围区域，直到原来的颜色值全部改变。 类似leetcode：Surrounded Regions 解法：首先，想象一下这个方法是怎么回事。
-
发表了文章 2014-12-08
careercup-递归和动态规划 9.6
9.6 实现一种算法，打印n对括号的全部有效组合（即左右括号正确配对）。 类似leetcode：Generate Parentheses 解法： 从头开始构造字符串，从而避免出现重复字符串。在这个解法中，逐一加入左括号和右括号，只有字符串仍然有效。
-
发表了文章 2014-12-07
careercup-递归和动态规划 9.5
9.5 编写一个方法，确定某字符串的所有排列组合。 类似leetcode：Permutations 解法： 跟许多递归问题一样，简单构造法非常管用。假设有个字符串S，以字符序列a1a2a...an表示。
-
发表了文章 2014-12-07
careercup-递归和动态规划 9.4
9.4 编写一个方法，返回某集合的所有子集。 类似leetcode：Subsets 解法： 解决这个问题之前，我们先要对时间和空间复杂度有个合理的评估。一个集合会有多少子集？我们可以这么计算，生成了一个子集时，每个元素都可以“选择”在或者不在这个子集中。
-
发表了文章 2014-12-07
careercup-递归和动态规划 9.3
9.3 在数组A[0...n-1]中，有所谓的魔术索引，满足条件A[i]=i。给定一个有序整数数组，元素值给不相同，编写一个方法，在数组A中找出一个魔术索引，若存在的话。 进阶： 如果数组元素有重复值，又该如何处理。
-
发表了文章 2014-12-07
careercup-递归和动态规划 9.2
9.2 设想有个机器人坐在X*Y网格的左上角，只能向右、向下移动。机器人从(0,0)到(X,Y)有多少种走法？ 进阶： 假设有些点为“禁区”，机器人不能踏足。设计一种算法，找到一条路径，让机器人从左上角移动到右下角。
-
发表了文章 2014-12-07
careercup-递归和动态规划 9.1
9.1 有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一个方法，计算小孩有多少种上楼梯的方法。 解法： 我们可以采用自上而下的方式来解决这个问题。小孩上楼梯的最后一步，也就是抵达第n阶的那一步，可能走1阶、2阶或3阶。
-
发表了文章 2014-12-07
careercup-数学与概率 7.7
7.7 有些数的素因子只有3、5、7，请设计一个算法，找出其中第k个数。 解法： 首先，我们可以将满足条件的前几个数列出来，以此寻找解题思路。 一种简单的思路就是对于已经列出的数，我们依次去乘以3，5，7得到一组数 然后找出最小且还没有列出的数，加入到这个列表。
-
发表了文章 2014-12-07
careercup-数学与概率 7.6
7.6 在二维平面上，有一些点，请找出经过点数最多的那条线。 解法： 类似于leetcode：Max Points on a Line 我们只需在任意两点之间“画”一条无限长的直线（也即不是线段），并利用散列表追踪哪条直线出现的次数最多。
-
发表了文章 2014-12-07
careercup-数学与概率 7.5
7.5 在二维平面上，有两个正方形，请找出一条直线，能够将这两个正方形对半分。假定正方形的上下两条边与x轴平行。 解法： 要将两个正方形对半分，这条线必须连接两个正方形的中心点。利用slope=(y1-y2)/(x1-x2)就能算出斜率。
-
发表了文章 2014-12-06
careercup-数学与概率
7.3 给定直角坐标系上的两条线，确定这两条线会不会相交。 解法： 此题有很多不确定的地方：两条线的格式是什么？两条线实为同一条怎么处理？这些含糊不清的地方最好跟面试官讨论一下。 下面将做出以下假设： 若两条线是相同的（斜率和y轴截距相等），则认为这两条线相交； 两条线若不平行则必相交。
-
发表了文章 2014-12-06
careercup-位操作5.1
5.1 写程序使整数N中第i位到第j位的值与整数M中的相同。 题目 给定两个32位的数，N和M，还有两个指示位的数，i和j。 写程序使得N中第i位到第j位的值与M中的相同(即：M变成N的子串且位于N的第i位和第j位之间) 例子： 输入: N = 10000000000, M = 10101, i = 2, j = 6 输出: N = 10001010100 解答 方案1：先将N中第0位到第i位保存下来(左闭右开：[0, i))，记作ret， 然后将N中第0位到第j位全清0([0, j])，通过向右移动j+1位然后再向左移动j+1位得到。
-
发表了文章 2014-12-06
careercup-树与图 4.9
4.9 给定一颗二叉树，其中每个结点都含有一个数值。设计一个算法，打印结点数值总和等于某个给定值的所有路径。注意，路径不一定非得从二叉树的根节点或叶子节点开始或结束。 类似于leetcode：Path Sum II C++实现代码：（使用了双重的递归）对于不含有parent指针域时。
-
发表了文章 2014-12-06
careercup-树与图 4.8
4.8 你有两棵非常大的二叉树：T1，有几百万个结点；T2，有几百个结点。设计一个算法，判断T2是否为T1的子树。 如果T1有这么一个结点n，其子树与T2一模一样，则T2C++实现代码： #include #include using namespace std; //Defi...
-
发表了文章 2014-12-06
careercup-树与图 4.7
4.7 设计并实现一个算法，找出二叉树中某两个结点的第一个共同祖先。不得将额外的结点储存在另外的数据结构中。注意：这不一定是二叉查找树。 解答 本题的关键应当是在Avoid storing additional nodes in a data structure 这句话上。
-
发表了文章 2014-12-06
careercup-树与图 4.6
4.6 设计一个算法，找出二叉查找树中指定结点的“下一个”结点（也即中序后继）。可以假定每个结点都含有指向父节点的连接。 思路： 有两种情况：1）如果该结点存在右子树，则中序后继即为右子树中最小的结点。
-
发表了文章 2014-12-06
careercup-树与图 4.5
4.5 实现一个函数，检查一棵二叉树是否为二叉查找树。 参考：http://blog.csdn.net/sgbfblog/article/details/7771096 C++实现代码： #include #include #include using namespace st...
-
发表了文章 2014-12-06
careercup-树与图 4.4
4.4 给定一棵二叉树，设计一个算法，创建含有某一深度上所有结点的链表（比如，若一棵树的深度为D，则会创建D个链表）。 类似于leetcode：Populating Next Right Pointers in Each Node II 解答 这道题目本质上是个BFS，也就是说，如果已经构建了第i层结点的链表， 那么将此链表中每个结点的左右孩子结点取出，即可构建第i+1层结点的链表。
-
发表了文章 2014-12-06
careercup-树与图 4.3
4.3 给定一个有序整数数组，元素各不相同按升序排列，编写一个算法，创建一棵高度最小的二叉查找树。 解答 想要使构建出来的二叉树高度最小，那么对于任意结点， 它的左子树和右子树的结点数量应该相当。比如，当我们将一个数放在根结点， 那么理想情况是，我们把数组中剩下的数对半分，一半放在根结点的左子树， 另一半放在根结点的右子树。
-
发表了文章 2014-12-06
careercup-树与图 4.2
4.2 给定有向图，设计一个算法，找出两个结点之间是否存在一条路径。 解答 根据题意，给定一个有向图和起点终点，判断从起点开始，是否存在一条路径可以到达终点。 考查的就是图的遍历，从起点开始遍历该图，如果能访问到终点， 则说明起点与终点间存在路径。
-
发表了文章 2014-12-05
careercup-树与图 4.1
4.1 实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个结点，其两颗子树的高度差不超过1. C++实现代码： #include #include #include using namespace std; //Definition for bina...
-
发表了文章 2014-12-05
迪杰斯特拉算法介绍
迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。 基本思想 通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。
-
发表了文章 2014-12-05
普里姆算法介绍
普里姆(Prim)算法，和克鲁斯卡尔算法一样，是用来求加权连通图的最小生成树的算法。 基本思想 对于图G而言，V是所有顶点的集合；现在，设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。
-
发表了文章 2014-12-05
Kruskal算法(一)之 C语言详解
最小生成树 在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。 例如，对于如上图G4所示的连通网可以有多棵权值总和不相同的生成树。
-
发表了文章 2014-12-05
拓扑排序介绍
拓扑排序介绍 拓扑排序(Topological Order)是指，将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。 这样说，可能理解起来比较抽象。
-
发表了文章 2014-12-05
广度优先搜索的图文介绍
1. 广度优先搜索介绍 广度优先搜索算法(Breadth First Search)，又称为"宽度优先搜索"或"横向优先搜索"，简称BFS。 它的思想是：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。
-
发表了文章 2014-12-05
深度优先搜索的图文介绍
1. 深度优先搜索介绍 图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似。 它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。
-
发表了文章 2014-12-05
邻接表有向图的介绍
邻接表有向图是指通过邻接表表示的有向图。 上面的图G2包含了"A,B,C,D,E,F,G"共7个顶点，而且包含了",,,,,,,,"共9条边。 上图右边的矩阵是G2在内存中的邻接表示意图。每一个顶点都包含一条链表，该链表记录了"该顶点所对应的出边的另一个顶点的序号"。
-
发表了文章 2014-12-05
邻接矩阵有向图的介绍
邻接矩阵有向图的介绍 邻接矩阵有向图是指通过邻接矩阵表示的有向图。 上面的图G2包含了"A,B,C,D,E,F,G"共7个顶点，而且包含了",,,,,,,,"共9条边。 上图右边的矩阵是G2在内存中的邻接矩阵示意图。
-
发表了文章 2014-12-05
C/C++语法知识：typedef struct 用法详解
第一篇：typedef struct与struct的区别 1. 基本解释 typedef为C语言的关键字，作用是为一种数据类型定义一个新名字。这里的数据类型包括内部数据类型（int,char等）和自定义的数据类型（struct等）。
-
发表了文章 2014-12-05
邻接表无向图的介绍
邻接表无向图是指通过邻接表表示的无向图。 上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点，而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边。
-
发表了文章 2014-12-04
邻接矩阵无向图的介绍
邻接矩阵无向图是指通过邻接矩阵表示的无向图。 上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点，而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边。
-
发表了文章 2014-12-04
图的基本概念
1. 图的定义 定义：图(graph)是由一些点(vertex)和这些点之间的连线(edge)所组成的；其中，点通常被成为"顶点(vertex)"，而点与点之间的连线则被成为"边或弧"(edege)。
-
发表了文章 2014-12-04
careercup-栈与队列 3.6
3.6 编写程序，按升序对栈进行排序（即最大元素位于栈顶）。最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中（如数组）。该栈支持如下操作：push、pop、peek和isEmpty。
-
发表了文章 2014-12-04
careercup-栈与队列 3.5
3.5 实现一个MyQueue类，该类用两个栈来实现一个队列。 解答 队列是先进先出的数据结构(FIFO)，栈是先进后出的数据结构(FILO)， 用两个栈来实现队列的最简单方式是：进入队列则往第一个栈压栈， 出队列如果第二个栈不为空，则直接从第二个栈出队列，否则将第一个栈的数据依次压入第二个栈，然后出栈。
-
发表了文章 2014-12-04
careercup-栈与队列 3.4
3.4 在经典问题汉诺塔中，有3根柱子及N个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自底向上从大到小依次套在第一根柱子上（即每一个盘子只能放在更大的盘子上面）。移动圆盘时有以下限制： 每次只能移动一个盘子； 盘子只能从柱子顶端滑出移到下一根柱子； 盘子只能叠在比它大的盘子上。
-
发表了文章 2014-12-04
careercup-栈与队列 3.3
3.3 栈就像叠盘子，当盘子叠得太高时，就会倾斜倒下。因此，在真实的世界中，当一叠盘子 (栈)超过了一定的高度时，我们就会另起一堆，再从头叠起。实现数据结构SetOfStacks 来模拟这种情况。SetOfStacks由几个栈组成，当前一栈超出容量时，需要创建一个新的栈 来存放数据。
-
发表了文章 2014-12-04
careercup-栈与队列 3.2
3.2 请设计一个栈，除pop与push方法，还支持min方法，可返回栈元素中的最小值。push、pop和min三个方法的时间复杂度必须为O(1)。 我们假设除了用一个栈s1来保存数据，还用另一个栈s2来保存这些非冗余最小值。
-
发表了文章 2014-12-04
careercup-栈与队列 3.1
3.1 描述如何只用一个数组来实现三个栈。 解答 我们可以很容易地用一个数组来实现一个栈，压栈就往数组里插入值，栈顶指针加1； 出栈就直接将栈顶指针减1；取栈顶值就把栈顶指针指向的单元的值返回； 判断是否为空就直接看栈顶指针是否为-1。
-
发表了文章 2014-12-04
careercup-链表 2.7
2.7 编写一个函数，检查链表是否为回文。 思路：1）可以利用链表中的元素采用头插法创建一个新的链表，然后比较两个链表的元素是否相等。 2）利用快慢指针，将链表后半部分逆转之后，比较前半部分与后半部分是否相等。
-
发表了文章 2014-12-03
careercup-链表 2.6
2.6 给定一个有环链表，实现一个算法返回环路的开头结点。 类似leetcode中 Linked List Cycle II C++实现代码： #include #include using namespace std; struct ListNode { int v...
-
发表了文章 2014-12-03
careercup-链表 2.5
2.5 给定两个用链表表示的整数，每个结点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。 示例： 输入： (7->1->6)+(5->9->2)，即617+295.
-
发表了文章 2014-12-03
careercup-链表 2.4
2.4 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。 思路：将小于的结点还是保存在原来的链表中，将大于等于x的结点加入一个新的链表，最后将这两个链表链接起来。
-
发表了文章 2014-12-03
careercup-链表 2.3
2.3 实现一个算法，删除单向链表中间的某个结点，假设你只能访问该结点。（即你不知道头结点） 这个问题的关键是你只有一个指向要删除结点的指针，如果直接删除它，这条链表就断了。 但你又没办法得到该结点之前结点的指针，是的，它连头结点也不提供。
-
发表了文章 2014-12-03
careercup-链表 2.2
2.2 实现一个算法，找到单链表中倒数第k个节点。 这道题的考点在于我们怎么在一个单链表中找到倒数第n个元素？ 由于是单链表，所以我们没办法从最后一个元素数起，然后数n个得到答案。 但这种最直观的思路显然是没错的，那我们有没有办法通过别的方式，从最后的元素数起数 n个来得到我们想要的答案呢。
-
发表了文章 2014-12-03
careercup-链表 2.1
2.1 编写代码，移除未排序链表中的重复节点。 不使用临时缓存： 如果不允许使用临时的缓存(即不能使用额外的存储空间)，那需要两个指针， 当第一个指针指向某个元素时，第二个指针把该元素后面与它相同的元素删除， 时间复杂度O(n2 )。
-
发表了文章 2014-12-03
careercup-数组和字符串1.8
1.8 假定有一个方法isSubstring，可检查一个单词是否为其他字符串的子串。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成，要求只能调用一次isSubstring。旋转字符串：”waterbottle”是”erbottlewat”的旋转字符串。
-
发表了文章 2014-12-03
careercup-数组和字符串1.7
1.7 编写一个算法，若M*N矩阵中某个元素为0，则将其所在的行与列清零。 类似于leetcode中的 Set Matrix Zeroes C++实现代码： #include #include using namespace std; void setMatricZero(vector &matrix) { if(matrix.
暂无更多信息
-
发表了文章
2017-12-19
我的博客即将入驻“云栖社区”，诚邀技术同仁一同入驻。
-
发表了文章
2017-12-06
Trie树（字典树）
-
发表了文章
2017-11-01
如何使用jstack分析线程状态
-
发表了文章
2017-09-24
2PC AND 3PC
-
发表了文章
2017-09-18
设计模式- 观察者模式
-
发表了文章
2017-05-21
数据库索引原理及优化
-
发表了文章
2017-05-20
避免写慢SQL
-
发表了文章
2017-04-05
Elasticsearch 简介
-
发表了文章
2017-04-04
Elasticsearch
-
发表了文章
2017-03-11
Java注释@interface的用法【转】
-
发表了文章
2017-03-11
OSS介绍
-
发表了文章
2017-03-10
谈谈动态规划的思想
-
发表了文章
2017-02-27
Java中Synchronized的用法
-
发表了文章
2017-02-20
mac下载、破解、安装webstorm编辑器
-
发表了文章
2017-02-08
Java是如何读到hbase-site.xml 的内容的
-
发表了文章
2016-05-15
如果你遇到，在IntelliJ IDEA里Ctrl+Alt+方向键用不了
-
发表了文章
2016-05-05
Unitils集成DBUnit的问题-解决方案
-
发表了文章
2016-05-05
Unitils集成DBUnit、Spring-单元测试
-
发表了文章
2016-04-25
用对 gitignore
-
发表了文章
2016-04-25
对已经add的文件不在跟踪
滑动查看更多
暂无更多信息
暂无更多信息