三颗猫饼干算法 leetcode: 2 pointers

Showing posts with label 2 pointers. Show all posts

Wednesday, October 2, 2013

3 Sum Closest@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

3Sum Closest

AC Rate: 545/1778

My Submissions

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

和3 sum几乎一样，用一个variable来record target - sum的绝对值，一直变动。但要注意的是：一旦遇到sum == target的，要break!

Sunday, September 8, 2013

Valid Palindrome@leetcode

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

» Solve this problem

This problem reminds me of quicksort. There is one quicksort algorithm is start searching in both ends. Pick a pivot, if list[i]<pivot, i++, if(list[j]>pivot) j--. Until we found a pair of elements that they should swap. In this problem, it's the same. We set two pointers, to filter those elements that are not numbers or characters. Then compare.

PS: I learned the code from 水中的鱼

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的情况。最后记得删掉。第二，就是平时可以先用自己复杂的逻辑把代码写出来，再对比别人的看如何把逻辑简化，这样就可以把代码简化，多做几次会形成一种直觉，下一次设计会快很多。

Tuesday, July 2, 2013

remove duplicates from sorted lists@leetcode

Given a sorted linked list, delete all duplicates such that each element appear only once.

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

» Solve this problem

Remove Duplicates from Sorted Array II@leetcode

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

» Solve this problem

此题的基本思路还是和remove duplicates from sorted array一样，就是双指针，i and j，i 指向当前已经去掉了duplicate的subarray，j就一直往后搜寻，一直遇到和i指向的不同的，就做A[++i]=A[j].

此题多设了一个counter来看是否是两个了，有一些细节需要注意，但总体不难。看代码可知。