Problem
You are given an n x n 2D matrix representing an image.Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?
Thursday, August 21, 2014
3Sum
Problem
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
Idea
- 先排序，然后假定第一个元素，让这个元素start从num[0]到num[n-2]遍历。
- 采用两边夹逼的方法，定义两个变量，mid 和 end. 比较start+mid+end和0的关系，若小于0则mid++，大于0则end--
Note
- vector<vector<int> > a的用法 首先这个多维的数组被写做
- Sort the vector by STL
Solution
Tuesday, August 19, 2014
Permutation Sequence
Problem
The set [1,2,3,…,n] contains a total of n! unique permutations.By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3):
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
Idea
- 这个题目的思路就是对于这个n位数的排列组合，从最高位到最低位分别确定第kth个数的每一位分别是多少，然后将每一位整合起来。得到那个kth数。可是如何判断每一位是多少呢？
- 以最高位（第n位）为例，最高位有n种情况，每一种情况中，从1到n-1位有（n-1)!种情况，这样，这个n位数的排列组合就被分成了n份，每一份包含了（n-1)!种组合。依次类推若第n位和第n-1都确定，则剩下的排列组合被分成了（n-2)!种情况。
- 若n=6 [1,2,3...,6] k=250, 首先确定最高位，此时排列组合可被分为6份，每份有5!=120. k/120= 250/120 = 2, 所以k在第三组，我们可以得出最高位为3.剩下的set为[1,2,4,5,6]，这时我们要更新k，因为剩下的数是在[1-120]之间了， k=k%5!＝10. 接下来确定第5位，每份有4!=24个组合，则10/24=0，所以k在第1组，这时set中第一个元素为1，所以第5位为1.接下来更新k然后继续上面的步骤，直到确定所有位。
Note
- How to add a digit number into string
Solution
Two Sum
Problem
Given an array of integers, find two numbers such that they add up to a specific target number.The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
Idea
- Hash Table
- Use a hashtable to record the index for each element in numbers[]
- For each element number[i] check if target-number[i] is in the hashtable
- Must be sure number[i] appear twice in numbers[] when number[i] == target-number[i]
- Sort
Solution
Special Cases
- [0,4,3,0], target = 0
- [3,2,4], target = 6 （3 must be checked if another 3 is in numbers[])
Sunday, August 17, 2014
Remove Element
Problem
Given an array and a value, remove all instances of that value in place and return the new length.The order of elements can be changed. It doesn't matter what you leave beyond the new length
Ideas
The problem is a little difficult to understand (my poor English - -!). if A[]={1,2,2,3} elem:2, you should return 2 and A[] = {1,3}.Solution
Longest Consecutive Sequence
Problem
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
Idea
- Use a hash map
- If the element is checked, then continue.
- For each unchecked element in hash map, we change any consecutive elements (both > num[i] and < num[i]) as checked.
- Use local and global parameter to record the longest consecutive sequence
Notes
- A method to traverse the array
- A similar method to traverse the vector
Solution
Thursday, August 14, 2014
Search in Rotated Sorted Array II
Problem
Follow up for "Search in Rotated Sorted Array":What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
Idea
允许重复元素,则上一题中如果 A[m]>=A[l], 那么 [l,m] 为递增序列的假设就不能成立了,比如 [1,3,1,1,1]。如果 A[m]>=A[l] 不能确定递增,那就把它拆分成两个条件:
- 若 A[m]>A[l],则区间 [l,m] 一定递增
- 若 A[m]==A[l] 确定不了,那就 l++,往下看一步即可。
Solution
Special Cases
- {1,3,1,1,1} 3
- {1} 0
Subscribe to:
Posts (Atom)