g********E
发帖数: 178 | 1 main function格式是按leetcode给的格式来得。如果我用new,写出来是这样吗？
void doinorder(TreeNode *root, vector * res){
...
*res.push_back(root->val);
}
vector* inorderTraversal(TreeNode *root){
vector *res = new vector;
...
return res;
} |
|
w***y
发帖数: 6251 | 2 要怎么做才能不超时？
我就是按照传统的N queens写法， 但是大集合到12就超时了
public class Solution {
int res=0;
public int totalNQueens(int n) {
int[] row = new int[n];
res=0;
_solveNQueens(row,0);
return res;
}
public void _solveNQueens(int[] row, int idx){
//when it finishes the last row, output the valid result
if(idx==row.length){
res++;
return;
}
... 阅读全帖 |
|
d******l
发帖数: 175 | 3 大家好，我纠结这道题目一些时间了。期间用Java写了3个算法，在Judge Large的时候
都说超时。请教高人帮忙分析一下我的一个算法的复杂度（基于TwoSum的一个解法）。
非常感谢。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
public class Solution {
public ArrayList> twoSum(int[] numbers, int target) {
ArrayList> twoSumList = new ArrayList
Integer>>();
Map map = new HashMap();
for (in... 阅读全帖 |
|
e*******i
发帖数: 56 | 4 No map is needed. Source is as following:
///////////////
#include
using namespace std;
int findLongest(char *s, char **start)
{
if(!s) return 0;
char first, second;
char *beginOfPreviousChar;
int currMax=0;
char *curr=s;
first=*s;
*start=s;
while(*curr)
{
if(*curr!=first) break;
currMax++;
curr++;
}
if( !*curr ) return currMax; //end of string
else
{
second=*curr;
beginOfPreviousChar=curr... 阅读全帖 |
|
g***j
发帖数: 1275 | 5 Given an unsorted array of integers, find the length of the longest
consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length
Your algorithm should run in O(n) complexity.
我在网上看到了几段code，用到了set或者map，每次要在set或者map里面找到，然后删
掉，我想问，这样的code时间是n么？find in a set难道不是logn么？当然也有用到
map的，我觉得找元素都是logn啊，那么最终的时间就是nlogn啊，比如如下code
class Solution {
public:
int longestConsecutive(vector &num) {
// Start typing... 阅读全帖 |
|
a*****a
发帖数: 46 | 6 呀，是我眼花了，但是romantoint也不需要recursion或者那么多if啊。我的意思是，
一般面试题本身不是特别难的，考察的就是细节了。
这是我写的，yuren贴的那个更简洁些。
public int romanToInt(String s) {
HashMap map = new HashMap();
map.put('M', 1000);
map.put('D', 500);
map.put('C', 100);
map.put('L', 50);
map.put('X', 10);
map.put('V', 5);
map.put('I', 1);
int res = 0;
for (int i=0; i
char c = s.charAt(i);
if ((c == 'C' || c == 'X' || c == 'I')
&... 阅读全帖 |
|
L*******e
发帖数: 114 | 7 综合楼上的解答，我试着写了一个。
/**
* find all the prime up to n(including n)
*/
public static List findPrimes(int n){
List res = new ArrayList();
if (n <= 1) return res;
// create a boolean array to track whether a number
// is a prime or not
boolean[] primeTrack = new boolean[n+1];
for (int i = 2; i <= n; i++){
primeTrack[i] = true;
}
int upper = (int)Math.sqrt(n);
for (int i = 2; i <= upper; i++){
for (int j = i * i; j <= n; j +=... 阅读全帖 |
|
W**********i
发帖数: 136 | 8 请问一下这里， if(temp.size==k)
{
res.add(new ArrayList(temp));
return;
}
为啥要 res.add(new ArrayList(temp));？ 为什么不是res.add(temp);?
我试过res.add(tem)，输出的都是空的了 |
|
a*****a
发帖数: 46 | 9 光用DP还不行，必须得等结束后回溯找所有路径才过了测试。。。
我在DP里存的是可能路径的所有节点（也可以只存上一个节点，但是那样回溯不好写）
，这样的话和仅DP的区别在于每次拷贝的只是节点，省掉的时间就是拷贝生成字符串的
时间。
呵呵，这测试真严格啊。C++的有没有可能不回溯也能过测试？
贴出code来，欢迎各位牛人指正~
private ArrayList getPath(String s, int n, ArrayList
Integer>> pres) {
ArrayList res = new ArrayList();
for (int pre : pres.get(n-1)) {
if (pre == 0) {
res.add(s.substring(0, n));
} else {
ArrayList preres = getPath(s,... 阅读全帖 |
|
g*********e
发帖数: 14401 | 10 我的也很长，但不用每个recursion都寻找中间node的位置。
class Solution {
public:
ListNode *merge(ListNode *a, ListNode *b, ListNode *&last) {
ListNode *res=NULL;
ListNode *prev=NULL;
while(a && b) {
if(res==NULL)
res=(a->val < b->val) ? a:b;
if(a->val < b->val) {
if(prev)
prev->next=a;
prev=a;
a=a->next;
} else {
if(prev)
prev->next=b;... 阅读全帖 |
|
S******6
发帖数: 55 | 11 探讨下，我觉得这道题目是为了找每个id下面链接id的weight和，要避免死循环。
所以我在您code基础上做了点修改：
void PrintSubTreeSum(vector > &Input)
{
int size = Input.size();
if(size == 0) return;
vector res(size, 0);
for(int i = 0; i < size; i++)
{
map mp;
res[i] += Input[i][2];
mp.push_back(Input[i][0]);
int p = Input[i][1];
while(mp.find(p) == mp.end())
{
mp.push_back(p);
res[i] += Input[p][2];
p = Input[p][1];
}
}... 阅读全帖 |
|
b*********s
发帖数: 115 | 12
You are right. deque is much better. Below is the implementation using deque
def solve2(s, k):
from collections import deque
d = deque(maxlen=k + 1)
n = len(s)
if n <= k:
return ''
for i in xrange(k + 1):
while d and ord(d[-1][1]) > ord(s[i]):
if s[i] == '0':
break
d.pop()
d.append((i, s[i]))
res = []
for i in xrange(k + 1, n):
res.append(d.popleft()[1])
while d and d[0][0] < i - k:
... 阅读全帖 |
|
h*****7
发帖数: 60 | 13 试了 也过不了 如下：
class Solution:
# @return a list of lists of length 3, [[val1,val2,val3]]
def threeSum(self, num):
num.sort()
n = len(num)
res= []
if n<3:
return res
for i in range(n-2):
j = n-1
if i > 0 and num[i] == num[i-1]:
continue
k = i + 1
while k < j:
sum = num[i] + num[j] + num[k]
if sum < 0:
k += 1
el... 阅读全帖 |
|
l****r
发帖数: 118 | 14 Anagrams 那道题，谢谢大家帮忙review。
public ArrayList anagrams(String[] strs) {
ArrayList res = new ArrayList();
boolean[] added = new boolean[strs.length];
for(int i = 0; i< added.length; i++)
added[i] = false;
if (strs == null)
return null;
if (strs.length <=1)
return res;
Hashtable map = new Hashtable();
for(int i = 0; ... 阅读全帖 |
|
a********e
发帖数: 53 | 15 class Solution {
public:
Write a function to find the longest common prefix string amongst an array
of strings.
The Time complexity is O(logM * N), while M is the size of strs, N is the
shortest length of the str in the strs
而我觉得这个时间复杂度应该是O(MN). 因为isEqual（）的复杂度应该是O(M), as T(M
) = 2T(M/2) + O(1). 谢谢。
============================
bool isEqual(vector &strs, int index, int start, int end) {
if(end < start) return true;
if(end == start) {
if(strs[start].size() > index) return ... 阅读全帖 |
|
h*******r
发帖数: 3 | 16 就字符串转化为数组那个题，其实我之前也碰到过，当时店面对方还加入了back slash
的可能性，当时这个题做得挺糟糕的。
后来我仔细想了一下，发现这类转化条件很多，分化很细很杂的程序统一可以用state
machine来辅助解决。
下面贴个针对该题的代码，画图3分钟，实现10分钟，当然自己还调试了5分钟让它能跑。
希望这种解法能对楼主有点用。
vector stringToStringArray(string s){
vector res;
int state = 0;
string e;
for (int i = 0; i < s.length(); i++){
switch(state){
case 0:
switch(s[i]){
case ' ':
break;
case '"':
... 阅读全帖 |
|
x******0
发帖数: 178 | 17 虽然是老题，但是写起来还是很费劲，唉。。
public static ArrayList SlidingWindowMax(int[] arr, int windowSize){
//edge case
ArrayList res = new ArrayList();
ArrayDeque indexQ = new ArrayDeque();
for (int i = 0; i < windowSize; i++){
while (!indexQ.isEmpty() && arr[i] > indexQ.getLast()){
indexQ.pollLast();//only keep possible max
}
indexQ.add(i);
}
for (int i... 阅读全帖 |
|
j********8
发帖数: 10 | 18 //Best first search, time complexity O(klog(n)). The size of heap is at most
2*n. Every time an element is popped from the heap or inserted to the heap,
O(log(n)). We need to do the pop and insert operations k times. So the time
complexity is O(klog(n)).
//Space complexity O(n), because there are at most 2*n nodes in the priority
queue.
struct node
{
int index;
int val;
node(int index_, int val_): index(index_), val(val_){}
bool operator > (const node& other) const
{
... 阅读全帖 |
|
j********8
发帖数: 10 | 19 //Best first search, time complexity O(klog(n)). The size of heap is at most
2*n. Every time an element is popped from the heap or inserted to the heap,
O(log(n)). We need to do the pop and insert operations k times. So the time
complexity is O(klog(n)).
//Space complexity O(n), because there are at most 2*n nodes in the priority
queue.
struct node
{
int index;
int val;
node(int index_, int val_): index(index_), val(val_){}
bool operator > (const node& other) const
{
... 阅读全帖 |
|
T*******e
发帖数: 4928 | 20 算了，给你贴一个: http://www.itint5.com/oj/#26
int getNumber(const string &expr, int &pos){
int num=0;
while(expr[pos]&&expr[pos]<='9'&&expr[pos]>='0'){
num=num*10+expr[pos++]-'0';
}
return num;
}
//返回表达式expr的值
int evaluate(const string& expr) {
int res=0;
int size=expr.size();
if(size==0) return res;
vector v;
int pos=0;
v.push_back(getNumber(expr, pos));
while(pos
char op=expr[pos++];
int num=getNumber(expr, pos);
... 阅读全帖 |
|
r*******k
发帖数: 1423 | 21 果然，赞
public class Solution {
public int[] twoSum(int[] numbers, int target) {
int[] res = new int[2];
HashMap scannedList = new HashMap
>();
for(int i = 0; i
int tmp = numbers[i];
if (scannedList.get(target - tmp)!=null){
res[0] = scannedList.get(target - tmp);
res[1] = i+1;
} else {
scannedList.put(numbers[i], i+1);
... 阅读全帖 |
|
p****6
发帖数: 724 | 22 先遍历, 边遍历边给每个节点一个index, 比如root为0, 做left减1, right加1. 然后
建立一个HashMap, key是index, value是list
贴个java版本的
public List> printVertical1(TreeNode root){
List> res = new ArrayList>();
if(root == null)
return res;
Map> map = new HashMap
TreeNode>>();
getVertical(root, map, 0);
Set keys = new TreeSet(map.keySet());
... 阅读全帖 |
|
f**********t
发帖数: 1001 | 23 写个暴力的，要求状态DP的地方高攀不起
void NumOfBoardLayouts(vector> &board, size_t x, size_t y, int
*res) {
//for 1 * 2 board
size_t row = board.size();
size_t col = board[0].size();
if (x == row) {
++*res;
return;
}
for (size_t i = x; i < row; ++i) {
for (size_t k = y; k < col; ++k) {
if (board[i][k] == true) {
continue;
} else {
if (k + 1 < col && board[i][k + 1] == false) {
board[i][k] = true;
board[i][k + 1] = true;
... 阅读全帖 |
|
f**********t
发帖数: 1001 | 24 来自主题: JobHunting版 - 一道面试题 bool UniqueBTrees(Node *root, vector &res, unordered_set &us) {
unordered_set lus;
unordered_set rus;
if ((!root->left || UniqueBTrees(root->left, res)) &&
(!root->right || UniqueBTrees(root->right, res)) &&
lus.find(root->val) == lus.end() &&
rus.find(root->val) == rus.end()) {
res.push_back(root);
for (int x : lus) {
us.insert(x);
}
for (int y : lus) {
us.insert(y);
}
us.insert(root->val);
return true;
} el... 阅读全帖 |
|
s******6
发帖数: 57 | 25 两个指针
int longestSubstr(string s) {
int count[256];
memset(count, 0, sizeof(count));
int cnt = 0;
int i = 0;
int res = 0;
for(int j=0; j
count[s[j]] ++;
if(count[s[j]] == 1) cnt ++;
while(cnt > 2) {
count[s[i]] --;
if(count[s[i]] == 0) cnt --;
i ++;
}
res = max(res, j-i+1);
}
return res;
} |
|
s******6
发帖数: 57 | 26 就是两个指针+一个计数的，假设是string是 acsii
int longestSubstr(string s) {
int count[256];
memset(count, 0, sizeof(count));
int cnt = 0;
int i = 0;
int res = 0;
for(int j=0; j
count[s[j]] ++;
if(count[s[j]] == 1) cnt ++;
while(cnt > 2) {
count[s[i]] --;
if(count[s[i]] == 0) cnt --;
i ++;
}
res = max(res, j-i+1);
}
return res;
} |
|
f**********t
发帖数: 1001 | 27 // Given an int array A[], define: distance=A[i]+A[j]+(j-i), j>=i. Find max
distance in A[]?
int maxDistance(int A[], int n) {
if (n < 1)
return INT_MIN;
int res = A[0];
int idx = 0;
for (int i = 1; i < n; ++i) {
res = max(A[i] + A[idx] + (i - idx), res);
if (A[idx] + (i - idx) < A[i]) {
idx = i;
}
}
return res;
} |
|
b*********s
发帖数: 115 | 28 def maxProduct(self, a):
if not a:
return 1
res = max_e = min_e = a[0]
for x in a[1:]:
candidates = [max_e * x, min_e * x, x]
max_e = max(candidates)
min_e = min(candidates)
res = max(res, max_e)
return res |
|
k****r
发帖数: 807 | 29 这道题当时c＋＋时简单的就实现了，但是类似的，我用java就不对，具体代码是这样的
public class Solution {
public int sumNumbers(TreeNode root) {
int result = 0;
int tmp = 0;
sumHelp(root, tmp, result);
return result;
}
private void sumHelp(TreeNode root, int tmp, int sum){
if (root == null) return;
if (root.left == null && root.right == null){
int newone = tmp + root.val;
sum = sum + newone;
}
if (root.right != null) sumHelp(root.right,... 阅读全帖 |
|
f*******w
发帖数: 1243 | 30 写了一下第二题，O(k)，用hash来实现swap..
vector randomPick(vector > &input, int k) {
int n = input[0].size(), total = input.size() * n;
unordered_map visited;
vector res; int start = 0;
for (int i = 0; i < k; ++i) {
int pos = rand() % (total - start) + start;
int x = pos / n, y = pos % n;
if (visited.find(pos) != visited.end()) {
res.push_back(visited[pos]);
int tmp = visited[pos];
visited[pos] = (visi... 阅读全帖 |
|
H******7
发帖数: 1728 | 31 class Solution {
public:
int res;
bool isValid(int A[], int r){
for (int i=0;i
if ( (A[i]==A[r])||(abs(A[i]-A[r])==(r-i))){
return false;
}
}
return true;
}
void nqueens(int A[], int cur, int n){
if (cur==n){ res++;return;}
else{
for (int i=0;i
A[cur]=i;
if (isValid(A,cur)){
nqueens(A,cur+1,n);
}
... 阅读全帖 |
|
S*******C
发帖数: 822 | 32 public List inorderTraversal(TreeNode root) {
List res = new ArrayList();
if (root == null)
return res;
Stack stack = new Stack();
TreeNode p = root;
while (!stack.isEmpty() || p != null) {
// if it is not null, push to stack
//and go down the tree to left
if (p != null) {
stack.add(p);//stack.push(p);
p = p.left;
} els... 阅读全帖 |
|
x*******6
发帖数: 262 | 33 贡献一个code，由于没有乘除，只需要记录括号内是否要根据加减改变数字的符号，不
需要使用reverse polish notation解法。
public static int eval(String s, int x) {
String[] exp = s.split("=");
int[] left = helper(exp[0],x);
int[] right = helper(exp[1],x);
return (left[0] - right[0])/(right[1]-right[0]);
}
private static int[] helper(String s, int x) {
boolean positive = true;
Stack re = new Stack();
re.push(false);
int num = 0;
int y = 0;
... 阅读全帖 |
|
a***e
发帖数: 413 | 34 平时几乎不用c++，有没有哪位同学帮看看怎么能让这段程序通过编译？我觉得自己思
路是对了的，不知道如果面试中碰到这种情况是否影响？没觉得哪里template用错了啊
？多谢
主要是在
Point x(a,b);
std::map::iterator it=mp.find(x);
if (it==mp.end())
mp.insert(std::pair(x,1));
else
mp[x]++;
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
int maxPoints(vec... 阅读全帖 |
|
a***e
发帖数: 413 | 35 多谢。
改了改，还是通不过，看来得VS里面debug去了
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
int maxPoints(vector &points) {
int n=points.size();
if (n==0) return 0;
double a=0,b=0;
map, int> mp;
int x1,x2,y1,y2;
for (int i=0; i
{
for (int j=i+1;j
{
... 阅读全帖 |
|
t*******y
发帖数: 22 | 36 int zero_one_multiple(int k){
vector > reminder;
for(int i=1;; i *= 10){
if(i%k==0) return i;
int pre_size=reminder.size();
vector r_i;
r_i.push_back(i);
r_i.push_back(i%k);
reminder.push_back(r_i);
for(int j=0;j
vector r = reminder[j];
int sum = i%k+r.back();
if(sum == k){
int res = 0;
for(int m=0;m
... 阅读全帖 |
|
g*******e
发帖数: 107 | 37 public zero_one_multiple(int N){
HashMap> map=new HashMap
Integer>> ();
int jj=0;
ArrayList remain=new ArrayList();
remain.add(0);
long resD=1;
while (resD
int residue=(int) (resD%N);
if (residue==0) return resD;
jj++;
int size=remain.size();
for (int i=0; i
int tmp=remain.get(i)+residue;
if ((tmp%N)==0) {
ArrayList res... 阅读全帖 |
|
f**********t
发帖数: 1001 | 38 // Given a dictionary of words, how can we efficiently find a pair words s.t
. they don't have characters in common and sum of their length is maximum?
size_t MaxLengthSumOfDistinctPairs(vector vs) {
vector char2str[26];
for (size_t i = 0; i < vs.size(); ++i) {
for (char c : vs[i]) {
char2str[c - 'a'].push_back(i);
}
}
size_t res = 0;
for (size_t i = 0; i < vs.size(); ++i) {
unordered_set dups;
for (char c : vs[i]) {
for (size_t k : char... 阅读全帖 |
|
d****n
发帖数: 397 | 39 DP
python solution
class Solution:
"""
@param A: A positive integer which has N digits, A is a string.
@param k: Remove k digits.
@return: A string
"""
def DeleteDigits(self, A, k):
# write you code here
l = len(A)
S = [['' for j in range(k + 1)] for i in range(l + 1)]
T = ''
for j in range(0, k + 1):
S[j][j] = ''
for i in range(1, l + 1):
T += A[i - 1]
S[i][0] = T
for j in range(1... 阅读全帖 |
|
d****n
发帖数: 397 | 40 DP
python solution
class Solution:
"""
@param A: A positive integer which has N digits, A is a string.
@param k: Remove k digits.
@return: A string
"""
def DeleteDigits(self, A, k):
# write you code here
l = len(A)
S = [['' for j in range(k + 1)] for i in range(l + 1)]
T = ''
for j in range(0, k + 1):
S[j][j] = ''
for i in range(1, l + 1):
T += A[i - 1]
S[i][0] = T
for j in range(1... 阅读全帖 |
|
a*********0
发帖数: 2727 | 41 vector> 2sumSum(vector& a)
{
vector> res;
size_t n=a.size();
if(n<4) return res;
unordered_map>> umap;
for(size_t i=0;i
for(size_t j=i+1;j
int sum=a[i]+a[j];
if(umap.find(sum)!=umap.end()) {
for(auto e: umap[sum]){
res.push_back({i,j, e.first, e.second});
}
}
umap[sum].push_back(mak... 阅读全帖 |
|
t**r
发帖数: 3428 | 42 贴个答案
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
|
|
x*******9
发帖数: 138 | 43 nested_list = [[1,2], 1, [2, [2,1]]]
def revSum(nlist):
(depth, res) = dfs(nlist)
return res
def dfs(nlist):
nlist_sum = 0
s = 0
max_lv = 1
for item in nlist:
if isinstance(item, list):
(depth, res) = dfs(item)
nlist_sum += res
max_lv = max(max_lv, depth + 1)
else:
s += item
nlist_sum += s * max_lv
return (max_lv, nlist_sum)
print revSum(nested_list)
(已加入肯德基豪华午餐 |
|
x*******9
发帖数: 138 | 44 nested_list = [[1,2], 1, [2, [2,1]]]
def revSum(nlist):
(depth, res) = dfs(nlist)
return res
def dfs(nlist):
nlist_sum = 0
s = 0
max_lv = 1
for item in nlist:
if isinstance(item, list):
(depth, res) = dfs(item)
nlist_sum += res
max_lv = max(max_lv, depth + 1)
else:
s += item
nlist_sum += s * max_lv
return (max_lv, nlist_sum)
print revSum(nested_list)
(已加入肯德基豪华午餐 |
|
c******h
发帖数: 46 | 45 就是说 {1,2} 的weight 是1了对吧 因为nlist_sum没有乘max_lv
我觉得是对的
2L说{1,2} weight是2不知道为啥
nested_list = [[1,2], 1, [2, [2,1]]]
def revSum(nlist):
(depth, res) = dfs(nlist)
return res
def dfs(nlist):
nlist_sum = 0
s = 0
max_lv = 1
for item in nlist:
if isinstance(item, list):
(depth, res) = dfs(item)
nlist_sum += res
max_lv = max(max_lv, depth + 1)
else:
s += item
nlist_sum += s * max_lv
return (max_lv, nlist_sum)
p... 阅读全帖 |
|
a*********0
发帖数: 2727 | 46 class Solution {
public:
vector findRepeatedDnaSequences(string s) {
int map[4];
std::fill(map, map+4, 0);
vector res;
set keySet;
multimap mmap;
if(s.size()<10) return res;
for(int i=0;i
map[toInt(s[i])]++;
if(i>=9){
if(i>=10){
map[toInt(s[i-10])]--;
}
string ss=toString(map);
... 阅读全帖 |
|
C****t
发帖数: 53 | 47 一个hashtable就好， key为元素，value为两个数【重复次数，visited的状态】
def total(nums, tar):
maps = {}
res = 0
for ele in nums:
if ele not in maps:
maps[ele] = [1,0]
else:
maps[ele][0] += 1
for ele in nums:
if maps[ele][1] = 1: continue
diff = tar - ele
if diff not in maps: continue
rep1, rep2 = maps[ele][0], maps[diff][0]
if ele == diff and rep1 > 1:
res += rep1*(rep1-1)//2
elif ele != diff:
... 阅读全帖 |
|
S*******C
发帖数: 822 | 48 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*******5
发帖数: 52 | 49 多谢楼主回复！我的代码确实没考虑到a或者b是lca的情况。找到a或者b之后应该继续
递归，在递归左右子树的过程中保存path，因为当前节点的path取决于左右子树中是否
找到另一个b。下面是代码，假设a或b其中一个为空时候返回空path
很羡慕楼主拿到G的offer，能去G是我一直的梦想，衣带渐宽终不悔，为伊消得人憔悴
，hehe
int lca_p(TreeNode* root, TreeNode* a, TreeNode* b, vector& path){
if(!root) return 0;
vector l_path;
vector r_path;
int l = lca_p(root->left, a, b, l_path);
int r = lca_p(root->right, a, b, r_path);
vector temp;
if(l == 2) path = l_path;
else if(r == 2) path = r_path;
else{
... 阅读全帖 |
|
h*********8
发帖数: 73 | 50 public int[] findRange(int[] arr, int target) {
int[] res = new int[2];
int l = 0;
int r = arr.length - 1;
while (l <= r) {
int m = (l+r)/2;
if (arr[m] < target) l = m + 1;
else r = m - 1;
}
if (l >= arr.length) return new int[] {-1, -1};
res[0] = l;
l = 0;
r = arr.length - 1;
while (l <= r) {
int m = (l+r)/2;
if (arr[m] > target) r = m - 1;
else l = m + 1;
}
res[1] = r;
return res;
} |
|
