Binary Search（二分法，或者叫折半查找）
167. Two Sum II - Input array is sorted
我們來看使用二分法來解決此問題，二分法使用的前提是有序纳令。
class Solution {
public:
int BinSearch(vector<int>& numbers,int left, int right, int target)
{
while(left <= right)
{
int mid = left + (right - left) / 2;
if(numbers[mid] == target)
return mid;
else if(numbers[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
vector<int> twoSum(vector<int>& numbers, int target) {
for(int i = 0; i < numbers.size()-1; ++i)
{
int remainingTarget = target - numbers[i];
int left = i + 1;
int right = numbers.size() - 1;
int index2 = BinSearch(numbers, left, right,remainingTarget);
if(index2!=-1)
{
return {i+1, index2+1};
}
}
return {-1,-1};
}
};
以2,7,11,15為例
（1）i = 0, remainingTarget = 9-2=7, left=1, right=3, 進入函數(shù)BinSearch
（2）在7, 11, 15中利用二分查找確認7的位置
Divide and Conquer（分而治之）
快速排序qsort是分而治之技巧的典型應用柠贤，使用前提整體解題思路與部分解題思路是一致的。
例如將6 1 2 7 9 3 4 5 10 8進行快速排序
（1）選擇第一個元素（6）為基準雷滋，把小于6的元素放左邊不撑，大于6的元素放右邊，即：3 1 2 5 4 6 9 7 10 8
（2）這樣數(shù)組分為了兩部分晤斩，3 1 2 5 4與9 7 10 8
（3）在3 1 2 5 4中焕檬，依然選第一個元素3位基準，把小于3的放左邊澳泵，大于3的放右邊：2 1 3 5 4
（4）我們又得到了2 1與5 4
（5）2 1以2為基準調(diào)整实愚，變?yōu)? 2，5 4以5為基準調(diào)整兔辅，變?yōu)? 5腊敲，所以2 1 3 5 4變?yōu)榱? 2 3 4 5
（6）同理 9 7 10 8經(jīng)過處理變?yōu)? 8 9 10，最后得到的序列如下：1 2 3 4 5 6 9 7 10 8
繼續(xù)解釋下如何把數(shù)組6 1 2 7 9 3 4 5 10 8以6為基準分成兩部分（下面的partition函數(shù)操作）维苔，使得小于6的部分在左邊碰辅，大于6的部分在右邊。這里用到了上面的Tow Pointers（輔助指針）的技巧
（1）有L和R兩個指針介时，分別指向第二個元素和最后一個元素
（2）L指針一直向右掃描没宾，直到遇到第一個大于6的數(shù)字7忍法；R指針一直向左掃描，直到遇到第一個小于6的數(shù)字5, 交換這兩個數(shù)字
（3）L指針繼續(xù)向右掃描榕吼，遇到大于6的數(shù)字9饿序；R指針一直向左掃描，遇到小于6的數(shù)字4羹蚣，交換這兩個數(shù)字
（3）重復第二個步驟原探，一直到L和R指針重疊（元素3），交換基準6和重疊元素3
void Swap(int a[] ,int left,int right)
{
int tmp;
tmp=a[left];
a[left]=a[right];
a[right]=tmp;
}
int partition(int a[],int left,int right)
{
int point=a[left];
//基準點定位為第一個元素
int firstPosition = left;
while( left< right)
{
//從右往左尋找小于point的元素
while( left< right&& a[right] >= point )
right--; //移到前一個元素
//從左往右尋找大于point的元素
while( left< right&& a[left] <= point)
left++; //移到下一個元素
//交換兩個元素
Swap(a,left,right);
}
//交互基準元素與最后重疊元素位置
Swap(a,firstPosition, left);
return left;
}
void QSort(int a[],int left,int right)
{
int point;//定義變量存放基準點
if( left< right)
{
point=partition(a,left,right);//對基準點定位
//對基準點左邊進行遞歸調(diào)用
QSort(a,left,point-1);
//對基準點右邊進行遞歸調(diào)用
QSort(a,point+1,right);
}
}
215. Kth Largest Element in an Array
尋找數(shù)組的第k大元素
給出數(shù)組[3,2,1,5,6,4] 顽素，k = 2, return 5.
很多種技巧都可以解決上面的題目咽弦，例如暴力搜索（第一遍找到最大的，第二遍找到第二大胁出。型型。。）全蝶、sort（先排序闹蒜，再定位第k大）、哈希表（multiset）抑淫，最大堆（priority_queue）癌幕，在這里我們用分而治之思想來解決嫡锌。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int left = 0, right = nums.size() - 1;
while (true) {
int pos = partition(nums, left, right);
if (pos == k - 1) return nums[pos];
else if (pos > k - 1) right = pos - 1;
else left = pos + 1;
}
}
int partition(vector<int>& nums, int left, int right) {
int pivot = nums[left], l = left + 1, r = right;
while (l <= r) {
if (nums[l] < pivot && nums[r] > pivot) {
swap(nums[l++], nums[r--]);
}
if (nums[l] >= pivot) ++l;
if (nums[r] <= pivot) --r;
}
swap(nums[left], nums[r]);
return r;
}
};
從上面qsort中的partition函數(shù)我們可以受到啟發(fā)，每次partition完后比基準數(shù)小的都放右邊邊旨怠，比基準數(shù)大的都放在左邊和簸，如果基準數(shù)整好在（k-1）下標上法绵，則基準數(shù)就是第k大數(shù)徽曲。如果不在呜舒，則利用返回的下標幫我們縮小查找范圍。下面以3,2,1,5,6,4為例說明：
（1）第一次以3為基準荣月，大于3的放左邊管呵，小于3的放右邊，partition完后3的下標是3喉童，大于（k-1=1）撇寞，第二大元素肯定位于左邊顿天。
（2）第二次以5為基準堂氯，大于5的放左邊，小于5的放右邊牌废，partition完后5的下標是1咽白，等于（k-1=1）
怎樣應對IT面試與筆試-（一）
怎樣應對IT面試與筆試-（二）
怎樣應對IT面試與筆試-（三）
怎樣應對IT面試與筆試-（四）
怎樣應對IT面試與筆試-（五）
怎樣應對IT面試與筆試-（五-1）
怎樣應對IT面試與筆試-（六）
怎樣應對IT面試與筆試-（七）
怎樣應對IT面試與筆試-（八）
怎樣應對IT面試與筆試-（九）
怎樣應對IT面試與筆試-（十）
怎樣應對IT面試與筆試-（十一）
怎樣應對IT面試與筆試-（十二）
怎樣應對IT面試與筆試-（十三）
怎樣應對IT面試與筆試-（十四）
怎樣應對IT面試與筆試-（十五）
怎樣應對IT面試與筆試-（十六）
