h*********o
发帖数: 230 | 1 Rverse Nodes in k-Group：
看了好久，没发现问题在哪儿，求大牛们过目~~
谢了！
public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// Start typing your Java solution below
// DO NOT write main() function
if(head==null)
return null;
ListNode begin=head;
ListNode pre=null;
ListNode end=null;
while(begin!=null){
ListNode cur=begin;
for(int i=0;i
cur=cur.next;
... 阅读全帖 |
|
x*****0
发帖数: 452 | 2 按照leetcode的建议，用先变再查的方法来判断相邻的word。对大数据还是超时了。
下面是我的code，大家可不可以帮忙看看。
class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
unordered_set visited;
queue q;
q.push(start);
int curLevelLen = 1;
int nextLevelLen = 0;
int level = 1;
while (dict.size() > 0 && !q.empty()) {
... 阅读全帖 |
|
m***p
发帖数: 86 | 3 single linked list版本:
void reverse(Node head){
Node cur = head;
Node prev = null;
while(cur != null){
Node nextNode = cur.next;
cur.next = prev;
prev = cur;
cur = nextNode;
}
return prev;
}
double linked list版本:
void reverse(Node head){
Node cur = head;
Node prev = null;
while(cur != null){
Node nextNode = cur.next;
cur.next = prev;
cur.prev = nextNode;
prev = cur;
cur = nextNode;
}
re... 阅读全帖 |
|
l*****g
发帖数: 685 | 4 Good question!
I was wrong. It's not really a BST, but rather a BT.
The nodes don't have explicit keys, and line numbers are implied by the in-
order traveral of the tree. Each node holds prevCount, number of all lines
before it, and nextCount, number of all lines after it.
Here is a rough implementation of this idea.
class Line
{
public:
//char * text;
Line * prev;
Line * next;
int prevCount;
int nextCount;
Line(char * text)
{
// clone text data
prev ... 阅读全帖 |
|
d****o
发帖数: 1055 | 5 复制链表
/*
先插入一个节点，
原始LL:
1 2 3 4
新LL
1 1 2 2 3 3 4 4
然后
pre->next->rand=pre->rand->next
最后去掉
*/
node* copyLL(node* head){
if(head==NULL) return NULL;
node* cur = head;
while(cur){
node* newNode = new node(cur->data);
newNode->next=cur->next;
cur->next=newNode;
cur=cur->next->next;
}
node* pre = head;
while(pre){
pre->next->rand=pre->rand->next;
pre=pre->next->next;
}
/*
1 1 2 2 3 3
p
c
*/
node* newHead = head->next;
... 阅读全帖 |
|
p********2
发帖数: 123 | 6 感觉不复杂，就bfs完了
java版过了OJ
public class Solution {
public void connect(TreeLinkNode root) {
if(root==null) return;
TreeLinkNode cur=root;
Queue q=new LinkedList();
q.add(cur);
while(!q.isEmpty()){
cur=q.remove();
if(cur.left!=null){
q.add(cur.left);
cur.left.next=cur.right;
}
if(cur.right!=null){
q.add(cur.right);
... 阅读全帖 |
|
h****n
发帖数: 1093 | 7 写了三个方法，一个是递归，一个是naive方法，一个是用指向指针的指针来构建
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
ListNode* res;
//Method using pointer to pointer
res = P2PMethod(l1,l2);
//res = recursive(l... 阅读全帖 |
|
Y********f
发帖数: 410 | 8 学习了，今天花时间仔细看了一下morris traversal，同时练习了一下，测试了一个
case。
Node *getNext(Node* &bst)
{
Node *cur = bst;
while(cur)
{
if (cur->lch == NULL)
{
bst = cur->rch;
return cur;
}
Node *prev = cur->lch;
while(prev->rch && prev->rch != cur)
prev = prev->rch;
if (!prev->rch)
{
prev->rch = cur;
cur = cur->lch;
}
else
{
prev->rch = NULL;
bst ... 阅读全帖 |
|
r**h
发帖数: 1288 | 9 class Solution {
public:
int maxDepth(TreeNode *root) {
if(root == NULL) return 0;
stack st;
st.push(root);
TreeNode *prev=NULL, *cur;
int maxHeight = 0;
while(st.size()>0){
cur = st.top();
if(prev==NULL || prev->left==cur || prev->right==cur){
if(cur->left != NULL){
st.push(cur->left);
}
else if(cur->right != NULL){
... 阅读全帖 |
|
a******e
发帖数: 710 | 10 题目如下：
Given a 2D array of black and white entries representing a maze with
designated entrance and exit points, find a path from the entrance to the
exit, if one exists.
答案是
class Coordinate {
public:
int x, y;
const bool operator==(const Coordinate &that) const {
return (x == that.x && y == that.y);
}
};
bool is_feasible(const Coordinate &cur, const vector> &maze) {
return cur.x >= 0 && cur.x < maze.size() &&
cur.y >= 0 && cur.y < maze[cur.x].size() &&... 阅读全帖 |
|
r********7
发帖数: 102 | 11 之前面试 遇到过LRU 这道题，面试之前准备过，就直接说了 用hashmap 和
linkedlist。 但是实现起来发现很不好处理 删除命令。 由于是最后一题时间有限就
没在写下去。不过最后一再追问下，知道使用Doublelinkedlist。。。
不过感谢国人面试官，还是给过了。 再次鸣谢下。
然后看到leetcode有这道题（稍微有点不一样）就又做了下，还是问题重重，不得不感
叹自己实力的差距, 不过最后还是通过了，代码如下：
1.由于是菜鸟，代码很丑很啰嗦，希望大神们指点要怎么改进。
2.小弟有一事不明，为啥LRU 还要有（key,value）查询？ 现实中，不就只有一个
value吗？然后HashMap 存。 现实中的LRU 每个内存有key
这个值吗？
希望帮忙讲解下LRU。
public class LRUCache {
public HashMap table = new
HashMap阅读全帖 |
|
j******d
发帖数: 2 | 12 class ListNode {
public:
int val;
ListNode *next; // point to the next of self list
ListNode *down; // point to the head of nested list
};
class DeepIterator {
public:
DeepIterator(ListNode *head) : cur(head) {}
bool hasNext(){
return cur != NULL;
}
int next(){
int val = cur->val;
if (cur->down) {
stk.push(cur);
cur = cur->down;
} else {
while (cur->next == NULL && stk.empty() == false) {... 阅读全帖 |
|
j******d
发帖数: 2 | 13 class ListNode {
public:
int val;
ListNode *next; // point to the next of self list
ListNode *down; // point to the head of nested list
};
class DeepIterator {
public:
DeepIterator(ListNode *head) : cur(head) {}
bool hasNext(){
return cur != NULL;
}
int next(){
int val = cur->val;
if (cur->down) {
stk.push(cur);
cur = cur->down;
} else {
while (cur->next == NULL && stk.empty() == false) {... 阅读全帖 |
|
s********x
发帖数: 81 | 14 大家好，最近做了两题leetcode, 但是都遇到了run time error. 但是我遇到run time
error 的例子在别的c++编译器上都顺利通过了，请大家帮我看一下是什么问题. 谢谢
大家!
问题一：next permutation:
class Solution {
public:
int findSecondMax(vector &num, int cur){
int max1=-1, max2=-2;
int index1=-1, index2=-2;
for(int i=cur; i
if(max1
max2=max1;
index2=index1;
max1=num[i];
index1=i;
}
}
if(max2!=-2 || max2!=-1) return index2;
else return index1;
}
... 阅读全帖 |
|
e********3
发帖数: 229 | 15 抛个砖.有错哪里可以优化请吃出.
public class IntegerToEnglishWord {
public static void main(String[] args) {
IntegerToEnglishWord itew = new IntegerToEnglishWord();
System.out.println(itew.integerToEnglishWord(123456789));
}
public String integerToEnglishWord(long num) {
String res = "";
if (num == 0) {
return "zero";
}
boolean neg = false;
if (num < 0) {
num = -num;
neg = true;
}
Map阅读全帖 |
|
b*****1
发帖数: 52 | 16 rotate from the current searched element to the found position in the 2nd
half element. The total number of rotation will be no more than n. The
search is logn. So the total complexity is O(nlogn)
1,3,6,8,-5,-2,3,8
#1 search a[0]=1 between i=4 to 7: found 1 before i=6, rotate the array
before i=6:
-5 -2 1 3 6 8 3 8
#2 search a[3]=3 between i=6 to 7: found 3 before i=7, roate the array
between i=3 (current search position) and i=7 (found position)
-5 -2 1 3 3 6 8 8
#3 search a[5]=6 between i=7 to... 阅读全帖 |
|
d**********x
发帖数: 4083 | 17 那题目貌似就没卡复杂度。。。枉我昨天下班后还捏着鼻子写了个treap。。。结果证
明是输出格式错了，只过了两三个case的可以考虑检查一下输出格式
思路大致就是用order statistics tree。每次查询都是O(logn)。手写最大问题在于没
法定制容器的行为。。。
好吧，然后想了一下，如果用两个heap加一个map的话也是可以的，因为只是查询
median，没有要求随机查询kth元素，所以还是写复杂了
附上代码，treap是个随机平衡树，可以拿去用。
#include
#include
#include
#include
using namespace std;
template
class Treap {
public:
class Node {
public:
Node(const T& value)
: value_(value),
left_(NULL),
right_(NULL),... 阅读全帖 |
|
b******7
发帖数: 92 | 18 实现得复杂了，stack中存pair简单点
bool isSymmetric(TreeNode *root) {
if(root == NULL) return true;
stack > s;
s.push(make_pair(root->left,root->right));
while(!s.empty())
{
pair cur = s.top();
s.pop();
if(cur.first == NULL && cur.second == NULL)
continue;
else if(cur.first == NULL || cur.second == NULL || cur.first->
val != cur.second... 阅读全帖 |
|
s*****4
发帖数: 25 | 19 第四题encode, 请问要如何把code写得干净一点呢, 我的code真丑:
void encode(string &str, int n) {
for (int i = 0; i < str.size(); i++) {
char cur = str[i];
if (cur >= 'a' && cur <= 'z') {
if (cur > 'z' - n)
str[i] = 'a' + cur + n - 'z' - 1;
else
str[i] = cur + n;
} else if (cur >= 'A' && cur <= 'Z') {
if (cur > 'Z' - n)
str[i] = 'A' + cur + n - 'Z' - 1;
else
str[i] = cur + n;
... 阅读全帖 |
|
c*****e
发帖数: 3226 | 20 public class Solution {
class Record {
Record prev;
String cur;
public Record(Record prev, String cur) {
this.prev = prev;
this.cur = cur;
}
}
public List> findLadders(String start, String end, Set<
String> dict) {
List> r = new LinkedList>();
if (start == null || end == null || dict == null || start.length() =
= 0 || start.length() != end.len... 阅读全帖 |
|
f***c
发帖数: 338 | 21 在网上看到，基本都是遍历都给定节点，然后将下一个节点指向当前的前一个节点。
大多数的例子，都是对int的链表，所以memory不是问题。如果链表的内容是一个很大
的数据结构，是否需要释放该节点的内存？如何释放？
请专家指点。
谢谢。
这里是我的一个实现。
"delete cur"试图释放节点内存，似乎多此一举，因为这里cur是个auto变量，函数返
回时自动释放内存。
void del(Node *&head, int n) {
Node *cur = head, *pre=NULL;
while (cur) {
if (n == cur->val) {
if (cur == head) {
/* if the node is the head*/
head = head->next;
return;
}
pre->next = cur->next; //next -> pre
... 阅读全帖 |
|
k***t
发帖数: 276 | 22 来自主题: JobHunting版 - 问个算法题 也来凑个热闹。主要是练练trie。
花了些时间才调通:( 谁帮忙给Review一下？谢了。
运行结果：
ad: 5
bc: 3
bb: 2
aaa: 1
aa: 1
源码：
#include
#include
using namespace std;
struct Node {
int cnt;
char c;
struct Node *n[26];
char *p; // to the 1st occurrence in the original input string
};
#define idx(x) (x-'a')
void add2trie (Node *r, char *p1, char *p2) {
char *p; Node *cur=r; Node *n;
p=p1;
cur=r;
while (p!=p2 && cur->n[idx(*p)]) {cur=cur->n[idx(*p)]; ++p;}
if (p==p2) { cur->cnt++;... 阅读全帖 |
|
S*******e
发帖数: 379 | 23 多谢两位，大概写了一下，能帮们确认一下吗?
Node *findInOrderSuccessor(Node *root, Node *target){
Stack s;
Node *cur = root;
Node *prev = NULL;
while(true){
while(cur) {
s.push(cur);
cur = cur->left;
}
if (s.empty()){
break;
} else {
cur = s.pop();
}
if (prev == target) {
return cur;
}
prev = cur;
cur = cur->right;
}
return NULL;
} |
|
h****n
发帖数: 1093 | 24 一个的stack只会写改动TreeNode的结构体的post traversal版本呵呵
假设允许改动treenode，加个bool标志位visited，初始都初始化为false
够简洁吧。。
void PostOrder(TreeNode * root)
{
TreeNode* cur;
if(root)
{
stack st;
st.push(root);
while(!st.empty())
{
cur = st.top();
st.pop();
if(cur->visited)
cout<val<
else
{
cur->visited = true;
st.push(cur);
if(cur->right) st.push(cur->r... 阅读全帖 |
|
x******0
发帖数: 1025 | 25 这个和我上学期考试题目一样啊
//recursively remove ALL nodes with value
PINTLISTNODE RemoveAll1(PINTLISTNODE pHead, int iRemoveValue)
{
if (pHead == NULL)
{
return NULL;
}
if (pHead->iValue == iRemoveValue)
{
PINTLISTNODE pToDelete = pHead;
pHead = pHead->pNext;
delete pToDelete;
return RemoveAll1(pHead, iRemoveValue);
}
else
{
pHead->pNext = RemoveAll1(pHead->pNext, iRemoveValue);
return pHead;
}
}
//use a dummyHead
PI... 阅读全帖 |
|
x*****0
发帖数: 452 | 26 Given a linked list where in addition to the next pointer, each node has a
child pointer, which may or may not point to a separate list. These child
lists may have one or more children of their own, and so on, to produce a
multilevel data structure, as shown in below figure.You are given the head
of the first level of the list. Flatten the list so that all the nodes
appear in a single-level linked list. You need to flatten the list in way
that all nodes at first level should come first, then nod... 阅读全帖 |
|
j*****y
发帖数: 1071 | 27 不错。 thanks. 简单多了.
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) {
TreeLinkNode dummyCur(0), dummyNext(0);
TreeLinkNode *cur = &dummyCur, *p = &dummyNext;
dummyCur.next = root;
while(cur->next)
{
while(cur->next)
{
... 阅读全帖 |
|
h*****a
发帖数: 1718 | 28 不错，不过值得注意的是这样build的tree和递归建的树形状可能是不同的。但都是
balanced。
public TreeNode buildIteratively(int[] a) {
int n = a.length;
TreeNode root = createTreeOfN(n);
Stack s = new Stack();
TreeNode cur = root;
int i=0;
while (cur != null || !s.isEmpty()) {
if (cur == null) {
cur = s.pop();
cur.val = a[i++];
cur = cur.right;
} else {
s.push(cur);
... 阅读全帖 |
|
f**********t
发帖数: 1001 | 29 Well, my code is complex and sigfault. Let me go back if I have time.
This is too hard for a 45 minutes interview.
void skipSpace(const char **s) {
while (isspace(**s)) {
++(*s);
}
}
int getNum(const char **s) {
bool neg = false;
if (**s == '-') {
neg = true;
++(*s);
}
int cur = 0;
while (isdigit(**s)) {
cur = cur * 10 + (**s - '0');
++(*s);
}
--(*s);
return neg ? -cur : cur;
}
int opNum(int x, int y, char op) {
switch (op) {
case '+':
return x + y... 阅读全帖 |
|
l******s
发帖数: 3045 | 30 像word ladder ii类似的一开始预处理所有近似点的做法，建一个大的依赖map先。
C#测试了几个，单连通图的，多独立连通图的正面反面用例，都通过了。
//directions = {{"A", "N", "C"}, {"B", "NE", "C"}, {"C", "NE", "D"}, {"A", "
S", "D"}, {"B", "W", "A"}}
// AB
// C
// D
// A <- false
private static bool validDirections(IList> directions)
{
int[,] depend = new int[26, 8]; //8 directions 0:N; 1:NE; 2:E; 3:SE; 4:S
; 5:SW; 6:W; 7:NW
for (int i = 0; i < depend.GetLength(0); i++)
for (int j = 0; j < depend.GetLength(1); j++)
de... 阅读全帖 |
|
l******s
发帖数: 3045 | 31 It's the way of finding the earliest joint of 2 linked list.
private Node LCA(Node p, Node q){
int countP = 0, countQ = 0;
Node cur = p;
while(cur != null) { cur = cur.parent; countP++; }
cur = q;
while(cur != null) { cur = cur.parent; countQ++; }
if(countP < countQ) {
cur = p; p = q; q = cur;
countP = countP ^ countQ ^ (countQ = countP);
}
while(countP > countQ) { p = p.parent; countP--; }
while(p != q) { p = p.parent; q = q.parent; }
retu... 阅读全帖 |
|
f***g
发帖数: 214 | 32 来自主题: JobHunting版 - 一到电面题 我给贡献一个非递归的, 请指正
void rev() {
Node** cur = &head;
while( *cur!=0 && (*cur)->next!=0 ) {
Node* second = (*cur)->next;
(*cur)->next = second->next;
second->next = (*cur);
(*cur) = second;
cur = &((*cur)->next->next);
}
} |
|
s******n
发帖数: 226 | 33 可能我没说清楚，不只是看pop什么值
比如 inorder
while(cur || !s.empty()){
if(cur){
1// s.push(cur); cur = cur.left;
}else{
2// cur = s.pop();
visit(cur);
cur = cur.right;
}
}
1和2 check两个地方，就是push和pop都检查，也看分支，这样就没有问题了 |
|
d*******d
发帖数: 2050 | 34 好,写点code攒人品:
return 第k个.和原题要求稍微不一样一点.
int findkth(int p, int q, int r, int k){
queue q1, q2, q3;
q1.push(p);
q2.push(q);
q3.push(r);
int cur = p;
for(int i =1; i<=k; i++){
int h1 = q1.front();
int h2 = q2.front();
int h3 = q3.front();
int min = h1 < h2 ? h1 : h2;
min = min
cur = min;
if( min == h1){
q1.pop();
q1.push(cur*p);
q2.push(cur*q);
q3.push(cur*r);
}else if( min == h2){
q2.pop();
q2.push(cur... 阅读全帖 |
|
l*********y
发帖数: 142 | 35 #include
#include
#include
using namespace std;
struct Segment {
Segment(int l, int r) : left(l), right(r) {};
int left;
int right;
};
vector input;
vector output;
void MergeInput(vector& input, Segment& cand)
{
int left = cand.left;
int right = cand.right;
// 处理边界情况
if (input.size() == 0 || cand.right < input.front().left || cand.left >
input.back().right) {
output.push_back(Segment(cand.left, cand.right... 阅读全帖 |
|
n*******w
发帖数: 687 | 36 1. binary search tree
first（） 从左子树一直往下，到左子树为null，返回node。
next（） 没有parent指针，找中序遍历successor挺麻烦。写个递归都感觉繁琐。
思路是，先top-down，找到当前node，再bottom-up，找到successor。
下面用Java写的。假设没有duplicate keys。不然会更麻烦。
tmp = null；//tmp存储结果辅助用的。cur是当前node。
Node next(Node cur, Node root){
//find cur node, and check its right child is null or not
//if null, return null
if(root == cur){
if(root.right != null)
return first(root.right);
else
return null;
}
//tmp stores the result, if tmp is null, root... 阅读全帖 |
|
l*********8
发帖数: 4642 | 37 Node * DeleteDuplicates(Node * head)
{
if (!head) return head;
Node tmpHead;
tmpHead.next = head;
Node *prev, *cur, *p;
prev = &tmpHead;
do {
bool isUnique = true;
cur = prev->next；
p = cur->next；
while(p && p->val == cur->val) {
isUnique = false;
cur->next = p->next;
delete p;
p = cur->next;
}
if (isUnique) {
prev = cur;
} else {
prev->next ... 阅读全帖 |
|
d****o
发帖数: 1055 | 38 int decode(vector in, int begin, int end){
if(begin>end) return 1;
if(begin==end&&in[begin]==0) return 0;
if(begin==end) return 1;
int cur = in[begin]*10+in[begin+1];
if(cur>=0&&cur<=9){
return 0;
}else if(cur==10||cur==20){
return begin+2<=end?decode(in,begin+2,end):1;
}else if((cur>=11&&cur<=19)||(cur>=21&&cur<=26)){
return decode(in,begin+1,end)+decode(in,begin+2,end);
}else{
return decode(in,begin+1,end);
}
}
int... 阅读全帖 |
|
h**u
发帖数: 35 | 39 BFS is OK, but traverse from the farthest kid first when visiting a node
class Solution {
public:
int jump(int A[], int n)
{
if ( !A || n <=1)
return 0;
queue Q;
vector min_jump(n, -1);
Q.push(0);
min_jump[0] = 0;
while (!Q.empty()) {
int cur = Q.front();
Q.pop();
if ( A[cur] + cur >= n - 1)
return min_jump[cur] + 1;
for (int i=A[cur]; i... 阅读全帖 |
|
p*g
发帖数: 141 | 40 pass OJ
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode preHead = new ListNode(1), cur=head;
preHead.next = head;
for ( int i=0; i
cur = cur.next;
preHead = preHead.next;
}
ListNode tail = cur;
for ( int i=m; i<=n; i++) {
ListNode t = cur.next;
cur.next = preHead.next;
preHead.next = cur;
cur = t;
}
tail.next = cur;
... 阅读全帖 |
|
d*******3
发帖数: 58 | 41 C++ version
void LevelTraverse(Node* root)
{
if(root == NULL)return;
vector v;
v.push_back(root);
int cur = 0;
int last =0;
while(cur < v.size())
{
last = v.size();
while(cur < last)
{
cout<data<
if(v[cur]->left !=NULL)v.push_back(v[cur]->left);
if(v[cur]->right != NULL)v.push_back(v[cur]->right);
cur++;
}
cout<
}
} |
|
s********u
发帖数: 1109 | 42 就利用merge two sorted lists那题的函数啊
ListNode *sortList(ListNode *head, int size){
if(size<=1) return head;
ListNode *prev = NULL, *cur = head;
for(int i = 0; i < size/2; i++){
prev = cur;
cur = cur->next;
}
if(prev) prev->next = NULL;
return mergeTwoLists( sortList(head,size/2), sortList(cur,size -
size/2) );
}
ListNode *sortList(ListNode *head) {
int ... 阅读全帖 |
|
g*****g
发帖数: 212 | 43 BST相当于给了你中序。
所以，你只需按前序来serialize。
Node* deserialize(int* A, int n)
{
int cur = 0;
return deserialize(A, n, cur, INT_MIN, INT_MAX);
}
Node* deserialize(int* A, int n, int &cur, int min, int max)
{
if (cur >= n)
{
return NULL;
}
if (A[cur]max)
{
return NULL;
}
Node* node = new Node(A[cur++]);
node->left = deserialize(A, n, cur, min, min(max, node->val));
node->right = deserialize(A, n, cur, max(min, node->val), max);
... 阅读全帖 |
|
f**********t
发帖数: 1001 | 44 class Component {
public:
virtual char next() = 0;
virtual bool hasNext() = 0;
virtual void traverse() = 0;
};
class Leaf : public Component {
char val;
bool _hasNext;
public:
Leaf(char v) : val(v), _hasNext(true) { }
char next() {
_hasNext = false;
return val;
}
bool hasNext() {
return _hasNext;
}
void traverse() {
cout << val << ' ';
}
};
class Composite : public Component {
vector children;
size_t _idx = 0;
void goNext() {
while (_... 阅读全帖 |
|
s**x
发帖数: 7506 | 45 这个怎么样？the idea is remove each node and add it to a new list.
// assume not circular doubly linked list.
void reverse2(Node * &head, Node * &tail)
{
if (head == tail)
return;
Node *newHead = NULL;
Node *newTail = NULL;
Node *cur = head;
while(cur) {
Node *tmp = cur->next;
cur->next = newHead;
cur->prev = NULL;
if (newHead == NULL} newTail = cur;
else newHead->prev = cur;
newHead = cur;
cur = tmp;
}
head = ... 阅读全帖 |
|
x*******6
发帖数: 262 | 46 贡献一个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*********8
发帖数: 140 | 47 用recursion和post order的stack，做第一题：
class TreeNode2 {
char val;
TreeNode2 left;
TreeNode2 right;
TreeNode2(char val){
this.val = val;
}
}
public class Exercise2 {
public List pathRootToLeaf(TreeNode2 root){
List list = new ArrayList();
if (root == null){
return list;
}
List left = pathRootToLeaf(root.left);
List right = pathRootToLeaf(root.right);
i... 阅读全帖 |
|
l******s
发帖数: 3045 | 48 两个Queue也可以吧，Queue 和 Queue，保持两个Queue同步就行了
。
It's accepted by leetcode.
private IList allPath(TreeNode root){
Queue queue = new Queue();
Queue qStr = new Queue();
IList result = new List();
if(root == null) return result;
queue.Enqueue(root); qStr.Enqueue(root.val.ToString());
while(queue.Count != 0){
TreeNode cur = queue.Dequeue();
string curStr = qStr.Dequeue();
if(cur.le... 阅读全帖 |
|
发帖数: 1 | 49 简化版只输出一个答案可以用counter做。
如果是301原题输出所有解那就要dfs了，dfs比bfs省空间，并且不需要set来去重，看
起来更elegant。DFS之前要先count一下需要删除多少个。时间复杂度是O(N^k), k是需
要删除的括号数。当然是需要删除的越多，解就越多，复杂度就越高。上code：
class Solution {
public List removeInvalidParentheses(String s) {
int leftRemove = 0;
int rightRemove = 0;
int open = 0;
for (int i = 0; i < s.length(); ++i) {
char cur = s.charAt(i);
if (cur == '(') {
open++;
} else if (cur == ')') {
... 阅读全帖 |
|
d******u
发帖数: 397 | 50 Thank you for the reply and the code.
Maybe I misunderstood and please correct me if I am wrong.
Keeping the two counters on each node up-to-date requires linear
complexity (in the following two loops), right? So the insertion is
still linear...
do
{
cur->nextCount++;
cur = cur->next;
}
while (cur->next);
do
{
cur->prevCount++;
cur = cur->prev;
}
whil... 阅读全帖 |
|
