a***e 发帖数: 413 | 1 还是开始没想清楚,发现用2个stack要清楚很多,2个vector就搞晕了。
Sigh,贴一个终于通过的明天再看再简化。每次碰到这种开始以为简单又老是写不对的
题就很有挫折感!
vector > zigzagLevelOrder(TreeNode *root) {
vector> ret;
vector levelVals;
stack curLevel;
stack nextLevel;
if (root==NULL)
return ret;
TreeNode *r = root;
curLevel.push(r);
bool l2r = true;
while(!curLevel.empty())
{
if (!l2r)
... 阅读全帖 |
|
h****n 发帖数: 1093 | 2 第一题,随手写了DFS和BFS,请指教
TreeNode* GetDeepestNode(TreeNode* root)
{
TreeNode* res=NULL;
int curLevel=1,preLevel=0;
DFSHelper(root, res, curLevel, preLevel);
//BFSHelper(root, res);
return res;
}
//Time O(n) space 不算递归栈则O(1) 算的话 O(lgn)
void DFSHelper(TreeNode* root, TreeNode* &res, int & curLevel, int &
preLevel)
{
if(root)
{
if(curLevel>preLevel)
{
res = root;
preLevel++;
}
curLevel++;
DFSHelper(root->right, ... 阅读全帖 |
|
S*******C 发帖数: 822 | 3 the weight of a tree = sum of weight of all node in the tree. Weight of node
= value of node * level of the node in the tree。
这里的代码能计算weight
public int findWeight(TreeNode root) {
int res = 0;
if (root == null)
return res;
List curLevel = new ArrayList();
curLevel.add(root);
int level = 1;
while (!curLevel.isEmpty()) {
for (TreeNode p : curLevel)
res += p.val * level;
level... 阅读全帖 |
|
f*********d 发帖数: 140 | 4 嗯,就是打印最右边的,BST可以做,不过代码显得有些臃肿, 我上一个dfs的吧, 别
人告诉我写的!估计面试官是想要这个。。。
void GetLevelMax(vector &ret, Node* root, int &curLevel, int &
visitedLevel)
{
if(!root) return;
if(curLevel > visitedLevel) {
ret.push_back(root->val);
visitedLevel++;
//always find the first current level that great than visited level
}
curLevel++;
//always find the first current level that great than visited level
GetLevelMax(ret, root->right, curLevel, visitedLevel);
G... 阅读全帖 |
|
a***e 发帖数: 413 | 5 写了很久都过不了,15分钟哪里能写完啊?能把思路说清楚就不错了。不知道什么样的
公司和面试官会出这种题。
https://oj.leetcode.com/problems/word-ladder-ii/
vector> findLadders(string start, string end, unordered_set<
string> &dict) {
vector> res;
vector> empty;
queue curLevel;
queue nextLevel;
vector path;
path.push_back(start);
curLevel.push(start);
res.push_back(path);
string word = start;
bool find = false;
int n = word.size();
bo... 阅读全帖 |
|
a***e 发帖数: 413 | 6 写了很久都过不了,15分钟哪里能写完啊?能把思路说清楚就不错了。不知道什么样的
公司和面试官会出这种题。
https://oj.leetcode.com/problems/word-ladder-ii/
vector> findLadders(string start, string end, unordered_set<
string> &dict) {
vector> res;
vector> empty;
queue curLevel;
queue nextLevel;
vector path;
path.push_back(start);
curLevel.push(start);
res.push_back(path);
string word = start;
bool find = false;
int n = word.size();
bo... 阅读全帖 |
|
a***e 发帖数: 413 | 7 我照你说的写了一个,还是比较长,但的确要清楚了很多。请问你能share一个你的么
?多谢!
我感觉如果不是特别熟,再加上现场一紧张或者发晕,很难把这么多行程序在15分钟内
bugfree的写完,汗。
vector > zigzagLevelOrder(TreeNode *root) {
queue nextLevel;
queue curLevel;
TreeNode *r = root;
vector > ret;
if (r==NULL)
return ret;
curLevel.push(r);
bool l2r=true;
while(1)
{
vector tmpV;
wh... 阅读全帖 |
|
r****s 发帖数: 1025 | 8 public class StringPermutation {
public static void permutate(String aString, String resultString, int
curlevel)
{
if (curlevel==0)
{
System.out.println(resultString);
}
else
{
for (int i=0;i
{
String bString="";
char curChar=aString.charAt(i);
String stringToPassIn=resultString+curChar;
bString+=aString.substr |
|
f**********t 发帖数: 1001 | 9 def nestSum(a, level):
res = 0
for x in a:
if isinstance(x, list):
res += nestSum(x, level + 1)
else:
res += int(x) * level
return res
def nestSumReverse(a):
res = 0
tmpSum = 0
level = 1
for x in a:
if isinstance(x, list):
curRes, curLevel = nestSumReverse(x)
res += curRes
level = max(curLevel + 1, level)
else:
tmpSum += int(x)
res += tmpSum * level
return r... 阅读全帖 |
|
f**********t 发帖数: 1001 | 10 def nestSum(a, level):
res = 0
for x in a:
if isinstance(x, list):
res += nestSum(x, level + 1)
else:
res += int(x) * level
return res
def nestSumReverse(a):
res = 0
tmpSum = 0
level = 1
for x in a:
if isinstance(x, list):
curRes, curLevel = nestSumReverse(x)
res += curRes
level = max(curLevel + 1, level)
else:
tmpSum += int(x)
res += tmpSum * level
return r... 阅读全帖 |
|
p**t 发帖数: 157 | 11 记录到目前最深的层数 以及当前层数
然后每次当前层数超过最深层数时 sum*2?
比如{1,{4,{6}}}
先处理1 sum=1 maxlevel=1
然后4 sum=1*2+4, maxlevel = 2
然后6 sum=(1*2+4)*2+6 maxlevel = 3
如果6后面还有个2 已知maxlevel=3 curlevel = 2
所以sum=sum + 2*(3-2)*2
应该是1 pass吧- -
list
4 |
|
p**t 发帖数: 157 | 12 记录到目前最深的层数 以及当前层数
然后每次当前层数超过最深层数时 sum*2?
比如{1,{4,{6}}}
先处理1 sum=1 maxlevel=1
然后4 sum=1*2+4, maxlevel = 2
然后6 sum=(1*2+4)*2+6 maxlevel = 3
如果6后面还有个2 已知maxlevel=3 curlevel = 2
所以sum=sum + 2*(3-2)*2
应该是1 pass吧- -
list
4 |
|