Ugly Number II

Ugly Number II 如何判断一个数是否是ugly数在之前一篇博客里已经提到过了。这次问题是要求出第n个ugly数。这道题目可以用动态规划来做，uglyNumber[i]表示第i个ugly数。uglyNumber[i]等于min(2*uglyNumber[a],3*ugl

Aug 20 2015

Ugly Number

Ugly Number 如果一个正整数的质因数中存在2，3，5以外的数就不是ugly数了。问题是判断一个数是否为ugly数。1认为是ugly数 我的方法是当数小于等于0的时候，返回false。接着消除2 3 5的质因数。先不断整除2得到没有质因数2的数，然后消除3和5的。最终的结

Aug 19 2015

Single Number III

Single Number III 给定一个正数数组，其中只有两个数是出现1次，其余的数都出现过2次。 我的方法和之前的方法一样，利用map来计算，键值对表示出现的数和它出现的次数。在第一次遍历的时候可以得到数和出现次数的映射，在进行第二次遍历的时候将出现次数为2次的数压入容器中

Aug 19 2015

Add Digits

Add Digits 给定一个非负整数，反复将它的各位的数加和，直到最终的和是一位数。这道题目可以用循环来做，但题目要求不能使用循环。那么我们需要从数学的角度来解这道题目。 我们需要知道一个这样的规律：任何数mod 9后的余数等于这个数的数位和 证明：该数为N = a[n-1]a

Aug 18 2015

Product of Array Except Self

Product of Array Except Self 给定一个整数数组，返回这个整数数组除了自己其他元素的乘积。我的方法是先求出所有数的乘积，接着再除以该数得到结果。需要注意的是被除数有可能是0，所以需要判断一下。

Aug 17 2015

Integer To Roman

Integer To Roman 问题是将1到3999的自然数转化为罗马数字。 我的方法是建立两个数组，分别储存”M”,”CM”,”D”,”CD”,”C”,”XC”,”L”,”XL”,”X”,”IX”,”V”,”IV”,”I”，与之对应的1000,900,500,400,100,

Aug 17 2015

Single Number II

Single Number II 问题是一个整数数组，里面只有一个元素出现了一次，其余的元素都出现了3次，现在需要找出这个只出现了一次的数。 我的方法是用map来存储出现过的数，键是数，值是出现的次数，最后遍历map找出出现次数是一个的数、

Aug 17 2015

Populating Next Right Pointers in Each Node

Populating Next Right Pointers in Each Node 问题是给定一个完美二叉树，每个树节点除了值、左右节点外，还有个next指针。如果当前结点没有右节点的话，next指向NULL，如果有的话，将指向右边的节点。 我的方法是用队列来储存节点，到节点

Aug 13 2015

Binary Tree Inorder Traversal

Binary Tree Inorder Traversal 问题是对一颗二叉树进行中序遍历。 递归版本： 先访问左子树 输出当前节点 访问右子树 这样就可以完成中序遍历的递归版本。 迭代版本： 利用栈来实现。 先压入栈中 当栈不为空时进行循环 获取栈顶元素并弹栈 如果它的左

Aug 11 2015

Binary Tree Preorder Traversal

Binary Tree Preorder Traversal 问题是对一颗二叉树进行前序遍历。 递归的方法比较简单： 先访问头节点 访问头节点的左子树 访问头节点的右子树 这样就可以实现二叉树的前序遍历了。 迭代的方法利用栈： 在栈不为空的情况下，每次访问栈顶元素并弹栈，将栈

Aug 10 2015

Search Insert Position

Search Insert Position 给定一个有序整数数组和一个整数，找出该数在这个数组中的位置。 比如：[1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0 这道题目我看到有序数组，就想到

Aug 9 2015

Linked List Cycle

Linked List Cycle 问题是从链表中查找是否存在环。我用的方法就是设置两个指针，一个慢指针，每次只指向下一个节点，另一个快指针，每次指向下一个节点的下一个节点，当两个指针指向的地址相同的时候，就能判断链表中是否存在环。 需要注意的是空指针的判断。

Aug 7 2015

Single Number

Single Number 给定一个数组，里面的数只有一个数的数量是1个，其他的数都是2个，问题是求出这个数量是单个的数。 方法1：我们可以用hash来存数组中的数出现的次数。这样的时间复杂度是O(n)，空间复杂度也是O(n)。 那么有没有方法是不需要额外的空间的呢？ 我们可以利

Aug 5 2015

VS Code 更改缩进

VS Code 更改缩进 在VS Code上编写python代码经常会出现这样的情况：有时候打开python文件使用缩进会导致直接以tab(\b)进行缩进，而编译的时候必须得用空格，那我就得手动调整空格和制表符，挺麻烦的。所以可以调整编辑器的默认缩进格式。 File->Pr

Aug 3 2015

Valid Anagram

Valid Anagram 给定两个字符串s和t，判断t是不是s的anagram。Anagram表示一个字符串中的字符是由前一个字符串中的字符组成，但顺序可以不同。 这道题目可以这样做，建立一个字母表的hash，键是26个字母（因为题目中说只能是小写字母），值是单词出现的次数。我

Aug 2 2015