三颗猫饼干算法 leetcode: single linked list

Showing posts with label single linked list. Show all posts

Thursday, November 14, 2013

reorder list@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Basic idea,

1. get length of the linked list

2. go to the middle node of the list

3. reverse the bottom part of the list, set NULL to last node of upper part list, and NULL to the first node of bottom part list

4. insert one by one

Pay attention to the corner case. One is when we have odd number of elements in list, we have one node more in bottom part. The other case is we have only one node in bottom part when reversing.

Thursday, October 17, 2013

Copy List with random pointer@leetcode

Copy List with Random Pointer

AC Rate: 1399/7131
My Submissions

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

利用一个hashtable，在一边查找random和next的时候一边建立。

Sunday, October 13, 2013

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
两种办法，第一种很straight forward，直接merge two sorted lists，然后对于每一个lists，都如此合并，但时间复杂度消耗比较高。e.g, n lists, every list has k nodes. O(knn). 因为每次合并之后的lists长度都会变长。
第二种用min-heap来动态地给minimun node in all lists. time complexity is O(knlogk). (介个我不太会。。因为没咋建过堆)
第三种是我最稀饭的，用multiset来动态地保存当前最小的元素，然后比较完一个就把那个list的后面那个扔到multiset里面去。

Multisets are containers that store elements following a specific order, and where multiple elements can have equivalent values.

In a multiset, the value of an element also identifies it (the value is itself the key, of type T). The value of the elements in a multiset cannot be modified once in the container (the elements are always const), but they can be inserted or removed from the container.

Internally, the elements in a multiset are always sorted following a specific strict weak ordering criterion indicated by its internal comparison object (of type Compare).

multiset containers are generally slower than unordered_multiset containers to access individual elements by their key, but they allow the direct iteration on subsets based on their order.

Multisets are typically implemented as binary search trees.

Tuesday, September 10, 2013

Add two numbers@leetcode

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

» Solve this problem

这题思路很简单，这个算法里很巧妙地用了当l1 or l2是null的时候用0来代替的做法，很简洁。

另外还要注意c＋＋里面指针的运算，要新开辟node呢。

Monday, July 22, 2013

Flatten binary tree to linked list@leetcode

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

The flattened tree should look like:

click to show hints.

» Solve this problem

这道题思路很清晰，就是递归，然后分别flat右和左，刚开始以为flat哪个先都无所谓，但实际是要先flatten右边的，不然flatten完左边，把左边的连上右边去，右边的已经不是bst了。这是第一点。

第二点，难点，也是我卡住的地方，就是如何把点连接起来。我的思路会，但就是连点连错了，导致出不来。之前我写的是

build(root->right);
build(root->left);

root->right->left=root->right;
root->right=root->left;

这样看上去是对的，但是对于完成了一颗子树，换到另一颗子树的连接就出了问题。这个时候我们要用一个treenode来保存之前跑过的node的root，以便下一次连接，于是就有了下面的代码，多了一个tmp.

Sunday, July 21, 2013

Convert linked list to bst@leetcode

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

» Solve this problem

下面两种方法，第一种更快。因为不用做循环什么的。

Saturday, July 6, 2013

Partition lists@leetcode

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal tox.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

» Solve this problem

自己写的时候很多小问题，借鉴了别人的方法，逻辑设计比我简洁很多，而且也避免了判断head的情况，很值得学习，少定义了太多变量。

在改一个bug的时候有一个判断while(p->val<x&&p!=NULL) 改成了 while(p!=NULL&&p->val<x)就通过了。。这到底是为什么？内部是怎么实现的？会导致什么区别？

此题没啥太多算法，细心就行了。

Wednesday, July 3, 2013

Remove Duplicates from Sorted Lists II @leetcode

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

这道题做了好久逻辑还是没对，总是漏掉一些东西，考虑得很复杂，看了别人的代码后有了一些启发。第一，用safeguard，就是在head前面加上一个头结点，避免处理head的情况。最后记得删掉。第二，就是平时可以先用自己复杂的逻辑把代码写出来，再对比别人的看如何把逻辑简化，这样就可以把代码简化，多做几次会形成一种直觉，下一次设计会快很多。

三颗猫饼干算法 leetcode