logo
Redian新闻
>未名空间
>PDA - 掌中宝
>
软软被人告歧视了
avatar
软软被人告歧视了# PDA - 掌中宝
p*u
1 楼
两个单链表（singly linked list），每一个节点里面一个0-9的数字，输入就相当于
两个大数了。然后返回这两个数的和（一个新list）。这两个输入的list长度相等。
要求是：1. 不用递归。2. 要求算法只遍历两个list一次。
1，算法没想到，在别的地方看到的。
2，第一次写挫了，第二次写用了15分钟，用了15分钟写case调试通过
https://gist.github.com/pdu/8083cd76da5976eac5ac
avatar
M*y
2 楼
不建议交易打印胖子；胖子是免费的，收费的是服务:
出售/交换物品的名称:
E家奶票，7/31过期，有三张$3和一张$5check，另外可以附送一张6/30过期的$1check,
收过期奶票的地方或许可以用。
物品类别（coupon：mfc等；血糖仪等）:
奶票
物品来源（报纸夹页，厂家邮寄等）:
厂家邮寄
可接受的价格（必须明码标价，必填）:
半价+0.5邮费
邮寄损失方式哪方承担（若需邮寄，必填）:
买方
付款方式说明:
paypal non-cc
本贴有效期（必填）:
till gone
联系方式（例： 站内）:
站内。由于奶票很快过期，需要的同学可以考虑就近购买，邮编94706。
avatar
G*s
3 楼
【 以下文字转载自 WaterWorld 讨论区 】
发信人: OutsiderBB (有点笨), 信区: WaterWorld
标 题: 帮忙解惑，夫妻间的问题
发信站: BBS 未名空间站 (Fri Jul 12 17:01:44 2013, 美东)
顶了个马甲
我跟老公的第一次痛得我撕心裂肺，老公看我可怜的样子，就草草完事。
之后也是很紧，不enjoy。
现在的疑问是，我已经生了娃了，顺产。老公跟我都很期待。
结果，这都试了好多回了，老公说比生娃前还紧，他也很疑惑，我更是，不会是他弟弟
变大了吧？到底怎么回事啊？
有没有过来人，给点希望吧！
avatar
f*l
5 楼
Thanks
avatar
m*8
6 楼
博嫂，博导外面有人啦！
avatar
f*w
7 楼
所以一开始指向的是位数最高的？
走一遍的时候把sum存到一个新的list，不考虑进位，然后再走一遍新的list，然后翻
转？
avatar
a*s
8 楼
博嫂已经习惯了，没见最近双方都在找下家吗？

【在 m*******8 的大作中提到】
: 博嫂，博导外面有人啦！
avatar
B*g
9 楼
走到下一位时存上一位的到新list

【在 f*******w 的大作中提到】
: 所以一开始指向的是位数最高的？
: 走一遍的时候把sum存到一个新的list，不考虑进位，然后再走一遍新的list，然后翻
: 转？
avatar
f*w
10 楼

不行吧
比如 88888 + 11112

【在 B*****g 的大作中提到】
: 走到下一位时存上一位的到新list
avatar
g*o
11 楼
head存高位还是低位
低位的话,leetcode有这题啊

【在 p*u 的大作中提到】
: 两个单链表（singly linked list），每一个节点里面一个0-9的数字，输入就相当于
: 两个大数了。然后返回这两个数的和（一个新list）。这两个输入的list长度相等。
: 要求是：1. 不用递归。2. 要求算法只遍历两个list一次。
: 1，算法没想到，在别的地方看到的。
: 2，第一次写挫了，第二次写用了15分钟，用了15分钟写case调试通过
: https://gist.github.com/pdu/8083cd76da5976eac5ac
avatar
p*u
12 楼
题目要求存低位，存高位就太简单了。
关键点是：
1，只遍历一次，不能递归
2，比较容易漏掉corner case
3，白板写有点困难~~

【在 g****o 的大作中提到】
: head存高位还是低位
: 低位的话,leetcode有这题啊
avatar
z*8
13 楼
head存高位比较难吧 或者说不可能一次遍历就搞定

【在 p*u 的大作中提到】
: 题目要求存低位，存高位就太简单了。
: 关键点是：
: 1，只遍历一次，不能递归
: 2，比较容易漏掉corner case
: 3，白板写有点困难~~
avatar
B*g
14 楼
有道理，我再想想

【在 f*******w 的大作中提到】
:
: 不行吧
: 比如 88888 + 11112
avatar
B*g
15 楼
要不，只要是9就不加到新list，count一共多少个9，到第一个，不是9的再决定往上放
10000...还是就放9999...

【在 f*******w 的大作中提到】
:
: 不行吧
: 比如 88888 + 11112
avatar
f*w
16 楼

所以最坏的情况需要O(n)额外空间？
我也不知道怎样做毕竟好……

【在 B*****g 的大作中提到】
: 要不，只要是9就不加到新list，count一共多少个9，到第一个，不是9的再决定往上放
: 10000...还是就放9999...
avatar
d*n
17 楼
A Java version
public static Node add(Node n1, Node n2) {
Node head = new Node(0);
Node back = head;
Node front = head;
while(n1 != null) {
int v = n1.m_value + n2.m_value;
front.next = new Node(v%10);
if (v > 9) {
back.m_value++;
while(back != front){
back = back.next;
back.m_value = 0;
}
back = front = front.next;
}
else if (v < 9){
back = front = front.next;
}
else
front = front.next;
n1 = n1.next;
n2 = n2.next;
}

return head.m_value != 0? head : head.next;
}

【在 B*****g 的大作中提到】
: 要不，只要是9就不加到新list，count一共多少个9，到第一个，不是9的再决定往上放
: 10000...还是就放9999...
avatar
p*u
18 楼
赞，你这样写比较巧妙，比我的版本要好看多了。
指正一个小错误：
while(back != front.next){ //这里改为front.next
back = back.next;
back.m_value = 0;
}
你试试这个例子：
445 + 555 = 1000
但是你的代码结果是：1090

【在 d****n 的大作中提到】
: A Java version
: public static Node add(Node n1, Node n2) {
: Node head = new Node(0);
: Node back = head;
: Node front = head;
: while(n1 != null) {
: int v = n1.m_value + n2.m_value;
: front.next = new Node(v%10);
: if (v > 9) {
: back.m_value++;
avatar
d*n
19 楼
试了一下， 好像我是对的。

【在 p*u 的大作中提到】
: 赞，你这样写比较巧妙，比我的版本要好看多了。
: 指正一个小错误：
: while(back != front.next){ //这里改为front.next
: back = back.next;
: back.m_value = 0;
: }
: 你试试这个例子：
: 445 + 555 = 1000
: 但是你的代码结果是：1090
avatar
p*u
20 楼
嗯，刚看了下你是对的。不好意思看错了

【在 d****n 的大作中提到】
: 试了一下， 好像我是对的。
avatar
B*g
21 楼
??O(1)呀

【在 f*******w 的大作中提到】
:
: 所以最坏的情况需要O(n)额外空间？
: 我也不知道怎样做毕竟好……
avatar
p*2
22 楼
mark
关键是找到每次进位链开始和结束的位置吧？
avatar
c*w
23 楼
双指针
一个curr就指向当前的加的结果
一个before指向“9”之前的listnode

【在 p*******2 的大作中提到】
: mark
: 关键是找到每次进位链开始和结束的位置吧？
avatar
l*1
24 楼
貌似这个可以:
S=0
C=0
while (not end) {
if (a + b >= 10) {
curr = a + b - 10;
C += 1
} else {
curr = a + b;
}
S = 10 * S + curr;
C = 10 * C;
}
S = S + C;
avatar
s*e
25 楼
首先问题是这两个数的长度是否相同？
avatar
l*1
26 楼
来个C版本的:
static void add_two(struct list *sum, const struct list *a,
const struct list *b)
{
struct list *n1, *n2;
struct list *curr, *last, *end = sum;
char res;
/* reseve one node for carry bit */
curr = alloc_node();
curr->val = 0;
add_node(sum, curr);
end = curr;
last = curr;
n1 = a->next;
n2 = b->next;
while (n1) {
res = n1->val + n2->val;
if (res >= 10) {
last->val++;
res -= 10;
if (last != end) {
for (last = last->next; last != NULL;
last = last->next)
last->val = 0;
last = end;
}
}
curr = alloc_node();
curr->val = res;
add_node(end, curr);
if (res != 9)
last = curr;
n1 = n1->next;
n2 = n2->next;
end = curr;
}
}
avatar
l*n
27 楼
只能遍历两个输入list一次，没说不能遍历新list多次。把新list逆序记录，有进位就
处理进位，最后再反转。

【在 p*u 的大作中提到】
: 两个单链表（singly linked list），每一个节点里面一个0-9的数字，输入就相当于
: 两个大数了。然后返回这两个数的和（一个新list）。这两个输入的list长度相等。
: 要求是：1. 不用递归。2. 要求算法只遍历两个list一次。
: 1，算法没想到，在别的地方看到的。
: 2，第一次写挫了，第二次写用了15分钟，用了15分钟写case调试通过
: https://gist.github.com/pdu/8083cd76da5976eac5ac
相关阅读
美国消费者起诉ATT对其3G限速措施 获赔850美元Fascinate刷cm7出现assert错误(status 7)谁有WEBOS的TP3.05百度输入法纯净版？cm9 alpha2 刷完以后,自带的email不能用？upnplay怎么调节播放视频的进度？有没有语音输入来发短信的？你们在drobox/box上放什么文件？有多少人用2-step verification来保护gmail密码呢？用国内中国电信的SIM卡, 应该在这里买什么iphone 4s?华为自己出cpu了。TP CM7 进不去了rooted DroidX要装RootKeeper才能OTA 621!!!Nitro HD is getting CM9 (soon) !!有人能给推荐一个kindle dx的套子吗？android帐号开box.net现在有50GCM7下TP没有反应了，有谁指点一下怎么关机iPhone的email里的eml附件怎么看不到Touchpad CM9的奇怪问题谁给科普一下为什么国内android普遍是2.2？samsung dart
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。