题目

https://oj.leetcode.com/problems/search-for-a-range/

分析

时间复杂度O(log n)， 多半便是二分查找的题目。

题目要求找出一个范围，无非就是找到一个起始点和一个终止点，通过两次二分查找找到起始点和终止点即可。

起始点的特点是，等于target，而且它左侧没有target了或者它是数组第一个数。

终止点的特点是，等于target，而且它右侧没有target了或者它是数组最后一个数。

P.S. 标准二分查找代码可以查看这里。

代码

class Solution
{
public:
	vector<int> searchRange(int A[], int n, int target)
	{
		vector<int> res;
		int l, r, m;

		l = 0;
		r = n - 1;
		while (l <= r)
		{
			m = (l + r) >> 1;
			if ((A[m]==target) && (m==0 || A[m-1]!=target))
			{
				res.push_back(m);
				break;
			}
			else if (A[m] > target || A[m-1] == target)
				r = m - 1;
			else
				l = m + 1;
		}
		if (res.size() == 0)
		{
			res.push_back(-1);
			res.push_back(-1);
			return res;
		}

		l = 0;
		r = n - 1;
		while (l <= r)
		{
			m = (l + r) >> 1;
			if ((A[m]==target) && (m==n-1 || A[m+1]!=target))
			{
				res.push_back(m);
				break;
			}
			else if (A[m] < target || A[m+1] == target)
				l = m + 1;
			else 
				r = m - 1;
		}
		return res;
	}
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40477301

题目

https://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/

分析

这道题是Search in Rotated Sorted Array的变形，因为有重复元素的存在，之前的方法就不不能直接用了，比如在{1, 3, 1, 1, 1}中寻找3， 结果就会出错。

出错的原因在于因为重复元素的存在，A[m]==A[l]时就不能确定在中点的哪一边是有序的，那就不能砍掉一半的查找范围了。

解决的办法是将左边界向右移动，直至A[m]!=A[l]，这样一来在最坏情况下时间复杂度会变为O(n)。

源码

class Solution
{
public:
	bool search(int A[], int n, int target)
	{
		int l = 0;
		int r = n - 1;
		int m;

		while (l <= r)
		{
			m = (l + r) >> 1;
			if (A[m] == target)
				return true;
			else
			{
				if (A[m] == A[l])
					l++;
				else if (A[m] > A[l])
				{
					if (target >= A[l] && target < A[m])
						r = m - 1;
					else
						l = m + 1;
				}
				else
				{
					if (target > A[m] && target <= A[r])
						l = m + 1;
					else
						r = m - 1;
				}
			}
		}
		return false;
	}
};

参考

http://blog.csdn.net/linhuanmars/article/details/20588511

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40156301

题目

https://oj.leetcode.com/problems/search-in-rotated-sorted-array/

分析

还是运用二分的思想， 每次循环判断target在中点的左侧还是右侧，每次砍掉一半的查找范围， 直到得到最终结果。

在这个过程中用到的一个重要规律是： 

一个数字序列经过rotate之后， 以中间那个数字为边界， 一定一边是有序序列， 一边是 rotated有序序列（证明略）。

如何判断哪边是有序的呢？ 如果中点大于左边界， 则左侧是有序序列， 否则右侧是有序序列。

分别用 l代表左边界， r代表右边界， m代表中间那个数，

如果A[m] == target， 则直接返回m即可。

如果A[m] >= A[l] ，说明左侧是有序序列

       如果target在左侧有序序列范围内， 则把 左边界l 设为 m+1

       否则target在右侧序列中， 则把 右边界r 设为 m-1

否则， 右侧是有序序列

       如果target在右侧有序序列范围内， 则把 左边界l 设为 m+1

       否则target在左侧有序序列范围内， 则把 右边界r 设为 m-1

 

P.S. 标准二分查找代码可以查看这里。

代码

class Solution
{
public:
	int search(int A[], int n, int target)
	{
		if (n <= 0)
			return -1;
		int l = 0;
		int r = n - 1;
		int m;

		while (l <= r)
		{
			m = (l + r) / 2;
			if (A[m] == target)
				return m;
			else if (A[l] < A[m])
			{
				if (A[l] <= target && target <= A[m-1])
					r = m - 1;
				else
					l = m + 1;
			}
			else
			{
				if (A[m+1] <= target && target <= A[r])
					l = m + 1;
				else
					r = m - 1;
			}
		}
		return -1;
	}
};

参考

http://blog.csdn.net/linhuanmars/article/details/20525681

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39860279

题目

https://oj.leetcode.com/problems/divide-two-integers/

分析

1. 题目要求实现除法运算且不能用乘除和取余运算， 一开始想用的递减计数的方式， 显然这种方法效率太低了， 从而导致超时。

不能用乘除和取余如何快速的逼近结果呢？ 答案是采用移位运算， 以指数的形式增长， 快速逼近最终的结果。

举例来说明， 137 / 7 = 19如何用移位运算来快速得到最终结果呢？

           135 - 7 × 2 ^ 4 = 23    > 7

           23   - 7 * 2 ^ 1  = 9      > 7

           9     - 7 * 2 ^ 0  = 2      <  7    停止运算

最终结果    2^4 + 2^1 + 2^0 = 19

2.  为了防止溢出， 将int型参数隐式转换为long long型参数。

代码

class Solution
{
public:
	int divide(long long dividend, long long divisor)
	{
		int res = 0;
		int sign = (dividend>0 && divisor>0) || (dividend<0 && divisor<0);
		dividend = dividend > 0 ? dividend : -dividend;
		divisor = divisor > 0 ? divisor : -divisor;

		while (dividend >= divisor)
		{
			long long res_temp = 1;
			while (res_temp * divisor <= dividend)
				res_temp <<= 1;
			res_temp >>= 1;
			res += res_temp;
			dividend -= res_temp * divisor;
		}
		return sign ? res : -res;
	}
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39558059

题目

https://oj.leetcode.com/problems/remove-duplicates-from-sorted-array/

分析

从前向后遍历， 如果该元素不和前面元素重复， 就该元素排到前面。

代码

class Solution
{
public:
	int removeDuplicates(int A[], int n)
	{
		if (n < 1) 
			return n;
		int count = 1;
		for (int i = 1; i < n; i++)
			if (A[i] != A[i-1])
				A[count++] = A[i];
		return count;
	}
};

参考

http://blog.csdn.net/xudli/article/details/8423225

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39544993

题目

https://oj.leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

分析

1. 双指针来实现， 左侧的指针指向上一个有效结点， 右侧的指针进行试探， 直到找出有效结点后和左侧的指针连接起来。

2. 由于链表第一个结点可能被删除掉， 所以左侧指针初始化为头结点的前一个指针。

代码

class Solution
{
public:
	ListNode *deleteDuplicates(ListNode *head)
	{
		if (head == NULL)
			return head;

		ListNode *pre_head = new ListNode(0);
		pre_head->next = head;

		ListNode *pl, *pr;
		pl = pre_head;
		pr = head;
		while (pr != NULL)
		{
			if (pr->next != NULL && pr->val == pr->next->val)
			{
				pl = pl->next;
				pr = pr->next;
			}
			else
			{
				while (pr->next != NULL && pr->val == pr->next->val)
				{
					ListNode *temp = pr;
					pr = pr->next;
					delete temp;
				}
				pr = pr->next;
			}
		}

		ListNode *temp = pre_head;
		pre_head = pre_head->next;
		delete temp;
		return pre_head;
	}
};

参考

http://fisherlei.blogspot.com/2013/03/leetcode-remove-duplicates-from-sorted.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39544599

题目

https://oj.leetcode.com/problems/remove-duplicates-from-sorted-list/

分析

从前向后遍历即可

代码

class Solution
{
public:
	ListNode *deleteDuplicates(ListNode *head)
	{
		if (head == NULL || head->next == NULL)
			return head;

		ListNode *p = head;
		while (p != NULL && p->next != NULL)
		{
			if (p->val == p->next->val)
			{
				ListNode *temp = p->next;
				p->next = p->next->next;
				delete temp;
			}
			else
				p = p->next;
		}
		return head;
	}
};

参考

http://www.programcreek.com/2013/01/leetcode-remove-duplicates-from-sorted-list/

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39456291