Leetcode系列-Search in Rotated Sorted Array

  做Leetcode题有一段时间了,但都是断断续续的,到现在才做了30题左右,感觉对自己来说还是有点难度的。希望自己能继续坚持下去,在校招前能解决超过一百题吧。

  其实这些题就是用来训练你的解题思路的,做多了的话,才能在校招时面对编程题目,能立即有一个解题的流程,知道这是哪一种类型的题目,一般用什么样的套路,思路会很清晰,比如基础的字符串,数组操作会用到一些排序算法,还有一类是算法思想的题目,比如DP(动态规划),分治,回溯法,贪心等等,多练,多思考,多总结。

  ‘庖丁解牛,恢恢乎游刃有余’,无他,唯手熟尔!希望自己通过训练,也能在算法这一块做到手熟。。。

  言归正题。

  今天正好做到这道题,仔细一看竟然是今年参加的去哪儿网实习生招聘的第一道算法题,因此把他拿来记录一下。

具体信息如下:

Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

我的方案如下:

 class Solution {
public:
int binarySearch(int *arr,int beg,int end,int target){
if (beg <= end){
int mid = (beg+end)/;
if (arr[mid] < target)
return binarySearch(arr,mid+,end,target);
if (arr[mid] > target)
return binarySearch(arr,beg,mid-,target);
if (arr[mid] == target)
return mid;
}
return -;
} int search(int A[], int n, int target) {
if (n==)
return -;
if (n==)
if (A[] != target)
return -;
else
return ;
int down = ;
for (int i=;i<n;i++)
if (A[i]<A[i-])
down = i;
int n1 = binarySearch(A,,down-,target);
int n2 = binarySearch(A,down,n-,target);
if (n1 == -)
if (n2 == -)
return -;
else
return n2;
else
return n1;
}
};

Ac过。

上一篇:当你还在争夺移动支付的时候,我已经统一了IC卡市场


下一篇:[LeetCode] 81. Search in Rotated Sorted Array II 在旋转有序数组中搜索 II