likesky3
- 浏览: 130687 次
-
最新评论
-
likesky3：
看了数据结构书得知并不是迭代和递归的区别，yb君的写法的效果是 ...
Leetcode - Graph Valid Tree -
likesky3：
迭代和递归的区别吧~
Leetcode - Graph Valid Tree -
qb_2008：
还有一种find写法：int find(int p) { i ...
Leetcode - Graph Valid Tree -
qb_2008：
要看懂这些技巧的代码确实比较困难。我是这么看懂的：1. 明白这 ...
Leetcode - Single Num II -
qb_2008：
public int singleNumber2(int[] ...
Leetcode - Single Num II
文章列表
[分析]
思路1：和Number of Islands类似，但是此题用DFS会栈溢出，因此使用BFS。从四个边缘的元素开始BFS, 遇到 O 改成特殊字符M,最后没有被修改的O就是被X包围的，应当改为X, 并且把M恢复成O即可。 BFS搜索时队列中维护的是所有未展开BFS的 O，队列记录这些 O的位置。
思路2：利用union find算法，将所有边界可达的O union在一起。设置一个根节点oRoot，边界上的所有O同其union上，非边界的O同其上下左右的O进行union。扫描完board后，那些最终没有和oRoot union在一起的O是需要翻转的。实现时特别注意要将oRoot的秩设得足 ...
[分析]
BFS & DFS法详见实现。
这里阐述下union-find思路，思路很直接，我们需要把相连在一起的1union起来，最后数下union了多少个集合1。输入时一个m*n矩阵，union-find相应地需要一个二维数组保存信息，采用按秩求并方法，初始时每个1元素的秩为-1,0元素不参与union，记为0。扫描数组，对于(i,j)元素，查看其是否需要同右边和下边相邻元素合并，其上边和左边不需要，因为按这种扫描顺序已经查看过。一个相邻的1集合合并完，只有根节点的秩为负数，而其余节点均指向相应根节点的下标为正数，因此扫描完整个集合，通过检查秩数组中负数的个数即可知道grid中的岛屿数 ...
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
For example:
Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given n = 5 and edges = [[0, 1], [1, 2], [2, ...
Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.
Note:
Given target value is a floating point.
You may assume k is always valid, that is: k ≤ total nodes.
You are guaranteed to have only one unique set of k values in the BST that are c ...
[分析]
迭代实现后序遍历比迭代实现先序和中序都要稍微复杂，对其一直有恐惧心理，总觉得自己不看答案做不出来……这次竟然做出来了，很开心，练习还是有效果的~
思路1：遍历到curr节点，不管三七二十一，入栈，继续访问左节点，因为后序遍历中root最后访问。问题是栈中的节点何时出栈？答案是其左右节点均被访问之后。怎么判断其左右节点均被访问过了呢？或者换个问题，怎么判断右节点没有被访问过（一路向左，左节点必然先被访问了）？答案是如果栈顶元素有右节点且右节点没有出现在结果列表的最后。
思路2：先序遍历是root->left->right,后序遍历是left->right->roo ...
Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.
For example:
Given a binary tree {1 ...
[分析]
思路1：暴力法，遍历当前待检查数组，找到第一个大于数组起始位置的位置i，则 i 为右子树根节点，然后递归判断左右子树。对于根节点，最坏情况下要遍历整个数组，时间为O（N），因为要递归检查每个节点，因此总的时间复杂度是O（N^2）。
思路2：参考StefanPochmann大神的作品https://leetcode.com/discuss/51543/java-o-n-and-o-1-extra-space, 时间复杂度是O（N），空间复杂度是O（h）。
public class Solution {
// Method 2
public boolean ver ...
Leetcode - Min Stack
- 博客分类：
- Stack
[分析]
这题属于简单题，之所以要记录下是因为遇到了个不理解的Java语法问题。
在pop（）时如果判断条件写成if (minStack.peek() == stack.peek())是要吃WA的，
原因是在表达式中比较的是引用本身，而不是值，奇怪的是在main中我认为一 ...
Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.
For example:
Given s = "aabb", return ["abba", "baab"].
Given s = "abc", return [].
[分析]
先按照Palindrome Pe ...
Numbers can be regarded as product of its factors. For example,
8 = 2 x 2 x 2;
= 2 x 4.
Write a function that takes an integer n and return all possible combinations of its factors.
Note:
Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, ...
The API: int read4(char *buf) reads 4 characters at a time from a file.
The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.
By using the read4 API, implement the function int read(char *buf, int n) that reads n characte ...
The API: int read4(char *buf) reads 4 characters at a time from a file.
The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.
By using the read4 API, implement the function int read(char *buf, int n) that reads n characte ...
[分析]
两字符串相同或者长度差异大于等于2都不符合要求，只需要检查那些长度相同或者相差为1的情况。逐个字符检查，发现第一个差异字符，若s和t长度相等将s中字符替换为t中字符，若不等则在s中插入t当前字符，然后跳出检查循环。若检查过程无差异字符（说明长度差1）或者消除发现的第一个差异后两字符串相等说明两字符串编辑距离为1.
这个思路和实现参考https://leetcode.com/discuss/42379/4ms-11-lines-c-solution-with-explanations，自己写的丑代码就不粘贴了
public class Solution {
public ...
mplement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:
"3+ ...
[思路]
数乘积结果的后缀0，其实就是数结果中有多少个因子10,10=2*5，易知因子2是充裕的，因此只要数因子5的个数，暴力的方法是统计并加和1到n每个数含有因子5的个数，会超时。
能贡献因子5的数是5,10,15,20,25,30……，其中所有5的倍数会至少贡献1个因子5，所有25的倍数会至少贡献两个因子5，所有5*5*5=125的倍数会至少贡献三个因子5，依次类推，因此n中5的因子个数=n/5 + n/25 + n/125……，实现时写成循环即可。
实现这个思路没有一次bug free，忽视了溢出问题，再次强调涉及整数运算是要牢记处理运算溢出问题，省事的方案就是使用long类型。
p ...