i*******6
发帖数: 107 | 1 #5.输入一个linkedlist和一个数字例如：9->7->8->6->1->2 和 3，输出还是一个
linkedlist但是每三个数reverse一下，例如8->7->9->2->1->6。
扩展了这道题，写成可以自己设置每几个数reverse一下。
思路大概是这样,一个原始链表为
0->1->2->3->4->5->6
如果每3个数反转一下的话，那么先把5指向0,6指向3,2指向null （换言之则是把第kn
个节点指向(k-2)*n+1个节点，再把第n个节点指向null），可以得到
6->3->4->5->0->1->2
然后把整个链表反转就是我们要的结果：
2->1->0->5->4->3->6
附上java代码和数据结构，以及测试用例，在netbeans5.5测试通过：
class ListElement{
public ListElement next;
public int data;
public ListElement(){
}
public ListElement(int data){
th... 阅读全帖 |
|
i****1
发帖数: 445 | 2 Node * Merge(Node * head1, Node * head2)
{
Node * head3, *tail;
head3 = tail = new Node;
while(head1 && head2)
{
if (head1 -> data < head2 -> data)
{
tail -> next = head1;
tail = head1;
head1 = head1 -> next;
}
else
{
tail -> next = head2;
tail = head2;
head2 = head2 -> next;
}
}
if (head1)
{
tail -> next = head1;
}
else
{
... 阅读全帖 |
|
b******7
发帖数: 92 | 3 注意左移右移就行了
第一个栈[0...capacity0 - 1)
第二、三个栈[capacity0,...,N)分别一个从头开始++，一个从尾开始--
当第一个栈满而第二、三个栈不满时，做右移操作
反过来，但第二、三个栈满，而第一个栈伟满时，做左移操作
template
class TripleStack{
public:
TripleStack()
{
head0 = 0;
head1 = capacity0 = N/3;
head2 = N-1;
}
void push0(const T & e)
{
if(!isSubStackFull(0))
arr[head0++] = e;
else if(!isSubStackFull(1))
{
shiftRight();
arr[head0++] = e;
}
... 阅读全帖 |
|
f****e
发帖数: 923 | 4 刚刚学习链表， 请问 head = dummy 是把dummy的值赋给 head吗？ 还是其他含义？
为什么最后返回dummy.next 就是返回合并之后的整个链表？貌似 循环过程没dummy 啥
事？
private ListNode merge(ListNode head1, ListNode head2) {
ListNode dummy = new ListNode(-1);
ListNode head = dummy;
while (head1 != null && head2 != null ) {
if (head1.val < head2.val) {
head.next = head1;
head1 = head1.next;
}else {
head.next = head2;
head2 = head2.next;
... 阅读全帖 |
|
f****e
发帖数: 923 | 5 public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
刚刚学习java，请问 head = dummy 是把dummy的值赋给 head吗？
为什么最后返回dummy.next 就是返回合并之后的整个链表？貌似 循环过程没dummy 啥
事？
private ListNode merge(ListNode head1, ListNode head2) {
ListNode dummy = new ListNode(-1);
ListNode head = dummy;
while (head1 != null && head2 != null ) {
if (head1.val < head2.val) {
head.next =... 阅读全帖 |
|
P*******U
发帖数: 203 | 6 不用转的，可以直接搞
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
// Start typing your Java solution below
// DO NOT write main() function
if(head == null)
return null;
if(head.next == null)
return new TreeNode(head.val);
ListNode head1, head2;
head1 = head;
head2 = head;
while(head2!=null && head2.next!=null){
head1 = head1.next;
head2... 阅读全帖 |
|
j**7
发帖数: 143 | 7 /**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode mergeTwoLists(ListNode head1, ListNode head2) {
if(head1==null &&head2==null)
{
return null;
}
if(head1==null)
return head2;
if(head2==null)
return head1;
ListNode head=null;
ListNode result... 阅读全帖 |
|
J******t
发帖数: 1945 | 8 typedef struct node
{
int data;
struct node * next;
}Node;
/* O(n) solution */
Node * findCommonNodes(Node * head1, Node * head2)
{
while(head1)
{
if (head1 == head2)
{
return head1;
}
else
{
head1 = head1->next;
head2 = head2->next;
}
}
return NULL;
} |
|
g*****k
发帖数: 623 | 9 This is wrong, suppose the same node appears 2nd in the first list
and 3rd in the second list.
So your code only solves the problem when the same node is at the same rank
in
each list.
typedef struct node
{
int data;
struct node * next;
}Node;
/* O(n) solution */
Node * findCommonNodes(Node * head1, Node * head2)
{
while(head1)
{
if (head1 == head2)
{
return head1;
}
else
{
head1 = head1->next;
head2 = head2->next;
}
}
return NULL;
} |
|
a**********2
发帖数: 340 | 10 修修补补好几次才过了测试，写的又臭又长，谁能帮我改一下啊？
class Solution {
public:
ListNode *reverseBetween(ListNode *head, int m, int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if( m > n || !head) return NULL;
ListNode* tail1 = (m>1?head:NULL);
ListNode* head2 = NULL;
ListNode* tail2 = NULL;
int i;
for( i = 1; i < m-1; i++)
{
if(!tail1)return NULL;
tail1=tail1->next;
}
ListN... 阅读全帖 |
|
c****r
发帖数: 576 | 11 多谢。顺便问一个Matlab语句
>> seed = [seed,repmat(head2(1+length(seed)),(~isempty(strfind(head2(2+
length(seed):
length(head2)),[seed,head2(1+length(seed))]))),1)]
是否过于复杂？这是个递归语句，用于实现我帖子里的算法。写成函数＋if - else结
构更好？ |
|
y**i
发帖数: 1112 | 12 我尝试了两个解法的代码，测试过了：
// copy a linked list with random pointer
struct NodeR
{
int val;
NodeR* next;
NodeR* random;
};
NodeR* CopyList(NodeR* head)
{
const int method = 0;
if (method == 0)
{
NodeR* head2 = NULL, *p = head, *p2 = head2;
while (p)
{
p2 = new NodeR;
p2->val = p->val;
p2->next = p->random;
p->random = p2;
p = p->next;
}
head2 = head->random;
p = head;
|
|
i**********e
发帖数: 1145 | 13 1）要是我的话会给个简单的递归思路，如果面试官要求的话再转换成非递归。
string part(string A) {
int n = A.length();
if (n <= 2) return A;
string prefix;
prefix += A[0];
prefix += A[n-1];
return prefix + part(A.substr(1, n-2));
}
2）in place merge two lists 可能有点 tricky，但我加了个 prev 指针可以稍微简
洁些。不知道还有没有更简洁的方法。
Node *mergeTwoLists(Node *head1, Node *head2) {
Node *p1 = head1, *p2 = head2;
Node *head = NULL;
Node *prev = NULL;
while (p1 || p2) {
int n1 = (p1 ? p1->data : INT_MAX);
int n2 = (p2 ? p2->data : INT_M... 阅读全帖 |
|
d******i
发帖数: 7160 | 14 NODE *head1, *head2, *p=head1;
if(!p) cout<<"list 1 ends";
p=head2;
if(!p) cout<<"list 2 ends";
在这里，p不需要清楚自己在指向1还是2.但NULL足够判断either list的尾了。
所以你说的1不成立。 |
|
f*****h
发帖数: 228 | 15 给你贴了吧，大家想用都可以
#!/usr/bin/perl -w
#############################################
#Author: Jiang Li
#email: r**********[email protected]
#Creat Time: Tue 23 Oct 2012 01:37:54 PM CDT
#Vanderbilt Center for Quantitative Sciences
#############################################
use strict;
use warnings;
=pod
=head1 SYNOPSIS
Given a genbank format file (.gb), parse its feature parts (mRNA feature to
get exon regions) to get information like transcript id, gene name, etc.,
and store the result in gtf format
=he... 阅读全帖 |
|
s*******e
发帖数: 93 | 16 I saw this problem earlier here. The answer is:
(imagine you have a->b->c->d, lets call the other pointer as "other"
1. duplicate each node and insert after itself. Now you get a->a->b->b->c->c->d->d
2. node n=head
while(n!=null)
n->next->other = n->other->next
n=n->next->next
3. separate the two lists
head2 = head->next
node n=head
while(n->next->next !=null)
n->next->next = n->next->next->next
n->next = n->next->next
n=n->next
... 阅读全帖 |
|
f*******y
发帖数: 1148 | 17 一上来就甩出一题关于树的，两人坐那里一下子我就不知道代码该怎么写了，脑子乱乱
的，第一题基本就是在他们的提示下完成的，果然我找编程的工作还是难啊。感觉平时
看的一些书，别人的解法都看得懂，但写的不够多，不是很熟练的话，现场写代码真是
有难度。
人生第一次次interview就这样收场了，也算见识面试是这么回事了...
我是EE的，面financial software engineer职位
1，比较两个普通binary tree 是否完全一样，根指针head1，head2已知。
2，一个魔方似的cube，每一边有n个小cube，这个cube浮在水上，最下面的2层没入水
里，问有多少个小cube是没有与水接触的？
n*n*n-(n*n*2-(n-2)^2) ? |
|
i****1
发帖数: 445 | 18 明天微软的电面，题目已经提前发给我了，不知道是什么意思，难道微软让我在电话里
讲代码？。
merge two already sorted list.
list 节点是
class Node{
public:
int data;
Node * next;
};
这个题目我觉得不是很难。
Node * merge (Node * head1, Node * head2)
{
//让我填写这个函数。
}
请教各位大牛，这个题目会不会有什么陷阱？ |
|
v*****y
发帖数: 68 | 19 就这个例子而言，我们最终返回的那个head刚开始还未确定，他可能是head1或head2中
的一个，因此我们先假设有了head，遇到真head之后直接像处理普通node一样加在后面
就可以了。这样有一个很大的好处是clean code。 |
|
p******o
发帖数: 4 | 20 面试官： 口头叙述的 Merge two sorted list
Me：接口是LinkedList还是Array?
面试官： 每种接口有什么优缺点
Me: 回答这是需求问题，LinkedList不需要临时存储空间
面试官：分析空间复杂度
Me: O（1） and O(n), 继续问需要用什么写Code
面试官：随便
Me: 写了标准实现with class Node {int val, Node next}, merge(Node head1, Node
head2)
面试官：为什么自定义Node class, 不用java.util.LinkedList?
Me: ... (这个真没仔细想过，胡乱答的)
面试官：纠缠各种java code 细节 of Node class: public, private, constructor等
Me: 回答以为是主要写算法，可以重写Node class to production ready.
面试官: 不用了，如何实现Merge K sorted list
Me: 可以递归调用Merge two sorted list, 或heap
面试官：... 阅读全帖 |
|
|
l*****g
发帖数: 2087 | 22 中国科学院院士李家洋
生平简介
李家洋（1956.7-）安徽肥西人。植物分子遗传学家，中国科学院院士，研究员。
中国
科学院副院长、党组成员。1982年毕业于安徽农学院（现安徽农业大学），1991年获美国
布兰代斯（Brandeis）大学博士学位，1991—1994年在美国康乃尔大学汤普逊（Boyce
Th
ompson）植物研究所进行博士后研究工作。历任中国科学院遗传研究所所长助理、所长，
遗传与发育生物学研究所所长。
李家洋主要从事植物分子遗传学研究，他利用模式植物拟南芥与重要粮食作物水稻探
索植物生长发育的调控机理。近年来的主要研究工作包括：采用图位法克隆了水稻分蘖控
制基因MOC1，开拓了水稻分蘖控制分子机理研究的新领域；利用水稻脆秆突变体分离了
B
C1基因，阐述了水稻机械强度的控制机理；通过获得的拟南芥胆碱生物合成突变体，初步
明确了胆碱合成与植物温度敏感雄性不育性的关系；通过图位克隆法分离出导致细胞死亡
的基因MOD1，明确了初级代谢途径的缺陷会导致植物细胞凋亡；利用转基因技术，创制出
色氨酸与吲哚乙酸合成量改变的转基因植物，从而提出植物生长素吲哚乙酸生物合成途径
的新模... 阅读全帖 |
|
