第 k 大的數(shù)
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

class Solution {
public:   
    inline int left(int idx) {
        return (idx << 1) + 1;
    }
    inline int right(int idx) {
        return (idx << 1) + 2;
    }
    void max_heapify(vector<int>& nums, int idx) {
        int largest = idx;
        int l = left(idx), r = right(idx);
        if (l < heap_size && nums[l] > nums[largest]) largest = l;
        if (r < heap_size && nums[r] > nums[largest]) largest = r;
        if (largest != idx) {
            swap(nums[idx], nums[largest]);
            max_heapify(nums, largest);
        }
    }
    void build_max_heap(vector<int>& nums) {
        heap_size = nums.size();
        for (int i = (heap_size >> 1) - 1; i >= 0; i--)
            max_heapify(nums, i);
    }
    int findKthLargest(vector<int>& nums, int k) {
        build_max_heap(nums);
        for (int i = 0; i < k; i++) {
            swap(nums[0], nums[heap_size - 1]);
            heap_size--;
            max_heapify(nums, 0);
        }
        return nums[heap_size];
    }
private:
    int heap_size;
}

找數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字04.14
數(shù)組中有一個數(shù)字出現(xiàn)次數(shù)超過數(shù)組長度的一半碌燕，請找出這個數(shù)字。例如輸入一個長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}继薛。
由于數(shù)字2在數(shù)組中出現(xiàn)了5次修壕，超過數(shù)組長度一半，因此輸出2

int findNumber(std::vector<int> v){  
    std::stack<int> stack = std::stack<int>();
    for (int i = 0; i < v.size(); ++i) {
        if (stack.empty() || stack.top() == v[i]) {
            stack.push(v[i]);
        }
        else{
            stack.pop();
        }
    }
    return stack.top();
}

旋轉(zhuǎn)數(shù)組求查找某個值是否存在04.12
Suppose an array sorted in ascending order 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.

public static int search(int n,int[] array){  
        int low = 0;          
        int high = array.length-1;  
        while(low<=high){  
            int middle = (low+high)/2;  
            if(array[middle]==n) return middle;  
            if(array[middle]>array[low]){  //left is order  
                if(n<=array[middle]&&n>=array[low]){  
                    high = middle-1;  
                }else {  
                    low = middle+1;  
                }  
            }else {           
                if(n>=array[middle]&&n<=array[high]){  
                    low = middle+1;  
                }else {  
                    high = middle-1;  
                }  
            }  
        }  
        return -1;    
    } 

旋轉(zhuǎn)數(shù)組求最小值04.10
Suppose an array sorted in ascending order 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).
Find the minimum element.
You may assume no duplicate exists in the array.

int findMin(vector<int> &num) {
        int start=0,end=num.size()-1;
        while (start<end) {
            if (num[start]<num[end])
                return num[start];
            
            int mid = (start+end)/2;
            
            if (num[mid]>=num[start]) {
                start = mid+1;
            } else {
                end = mid;
            }
        }
        return num[start];
    }

求兩個不等長遏考、有序數(shù)組的中位數(shù)04.09
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int N1 = nums1.size();
    int N2 = nums2.size();
    if (N1 < N2) return findMedianSortedArrays(nums2, nums1);   // Make sure A2 is the shorter one.
    
    if (N2 == 0) return ((double)nums1[(N1-1)/2] + (double)nums1[N1/2])/2;  // If A2 is empty
    
    int lo = 0, hi = N2 * 2;
    while (lo <= hi) {
        int mid2 = (lo + hi) / 2;   // Try Cut 2 
        int mid1 = N1 + N2 - mid2;  // Calculate Cut 1 accordingly
        
        double L1 = (mid1 == 0) ? INT_MIN : nums1[(mid1-1)/2];  // Get L1, R1, L2, R2 respectively
        double L2 = (mid2 == 0) ? INT_MIN : nums2[(mid2-1)/2];
        double R1 = (mid1 == N1 * 2) ? INT_MAX : nums1[(mid1)/2];
        double R2 = (mid2 == N2 * 2) ? INT_MAX : nums2[(mid2)/2];
        
        if (L1 > R2) lo = mid2 + 1;     // A1's lower half is too big; need to move C1 left (C2 right)
        else if (L2 > R1) hi = mid2 - 1;    // A2's lower half too big; need to move C2 left.
        else return (max(L1,L2) + min(R1, R2)) / 2; // Otherwise, that's the right cut.
    }
    return -1;
} 

實現(xiàn)簡單的正則表達式匹配04.08
Implement regular expression matching with support for '.' and ''.
'.' Matches any single character.
'' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length(); 
        vector<vector<bool> > dp(m + 1, vector<bool> (n + 1, false));
        dp[0][0] = true;
        for (int i = 0; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (p[j - 1] == '*')
                    dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);
                else dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
        return dp[m][n];
    }
};

連續(xù)子數(shù)組的最大和04.07
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

public int maxSubArray(int[] A) {
        int n = A.length;
        int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
        dp[0] = A[0];
        int max = dp[0];
        
        for(int i = 1; i < n; i++){
            dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
            max = Math.max(max, dp[i]);
        }
        return max;
}

解題思路慈鸠，從前往后的順序，并不知道后面新加入的部分和是否會 >0灌具，可以把這道動態(tài)規(guī)劃的子問題的格式更改為：maxSubArray（int A []青团，int i）），這意味著A [0：i]的maxSubArray必須具有A [i]作為結(jié)束元素咖楣。我們可以判斷知道A [i]之前連續(xù)元素的和的最大值壶冒。從而解決整個數(shù)組的連續(xù)子數(shù)組的最大和問題。

翻轉(zhuǎn)字符串04.06
Given an input string, reverse the string word by word.
For example,Given s = "the sky is blue",return "blue is sky the".

void reverseWords(string &s) {
    reverse(s.begin(), s.end());
    int storeIndex = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] != ' ') {
            if (storeIndex != 0) s[storeIndex++] = ' ';
            int j = i;
            while (j < s.size() && s[j] != ' ') { s[storeIndex++] = s[j++]; }
            reverse(s.begin() + storeIndex - (j - i), s.begin() + storeIndex);
            i = j;
        }
    }
    s.erase(s.begin() + storeIndex, s.end());
}

字符串全排列04.05
Implement atoi to convert a string to an integer.consider all possible input cases.
用C++寫一個函數(shù), 如 Foo(const char *str), 打印出 str 的全排列, 如 abc 的全排列: abc, acb, bca, dac, cab, cab
思路：全排列就是從第一個數(shù)字起每個數(shù)分別與它后面的數(shù)字交換
#include <stdio.h>
#include <string.h>
void Swap(char *a, char *b)
{
char t = *a;
*a = *b;
*b = t;
}
//k表示當前選取到第幾個數(shù),m表示共有多少數(shù).
void AllRange(char *pszStr, int k, int m)
{
if (k == m)
{
static int s_i = 1;
printf(" 第%3d個排列\(zhòng)t%s\n", s_i++, pszStr);
}
else {
for (int i = k; i <= m; i++) //第i個數(shù)分別與它后面的數(shù)字交換就能得到新的排列
{
Swap(pszStr + k, pszStr + i);
AllRange(pszStr, k + 1, m);
Swap(pszStr + k, pszStr + i);
}
}
}
void Foo(char *pszStr)
{
AllRange(pszStr, 0, strlen(pszStr) - 1);
}
int main()
{
printf(" 全排列的遞歸實現(xiàn)\n");
printf(" --by MoreWindows( http://blog.csdn.net/MoreWindows )--\n\n");
char szTextStr[] = "123";
printf("%s的全排列如下:\n", szTextStr);
Foo(szTextStr);
return 0;
}
輸出：
123的全排列如下:
第 1個排列 123
第 2個排列 132
第 3個排列 213
第 4個排列 231
第 5個排列 321
第 6個排列 312

去掉重復(fù)的全排列的遞歸實現(xiàn)
思路：去重的全排列就是從第一個數(shù)字起每個數(shù)分別與它后面非重復(fù)出現(xiàn)的數(shù)字交換

//去重全排列的遞歸實現(xiàn)  
 #include <stdio.h>  
 #include <string.h>  
 void Swap(char *a, char *b)  
{  
    char t = *a;  
    *a = *b;  
    *b = t;  
}  
//在pszStr數(shù)組中截歉，[nBegin,nEnd)中是否有數(shù)字與下標為nEnd的數(shù)字相等  
bool IsSwap(char *pszStr, int nBegin, int nEnd)  
{  
    for (int i = nBegin; i < nEnd; i++)  
        if (pszStr[i] == pszStr[nEnd])  
            return false;  
    return true;  
}  
//k表示當前選取到第幾個數(shù),m表示共有多少數(shù).  
void AllRange(char *pszStr, int k, int m)  
{  
    if (k == m)  
    {  
        static int s_i = 1;  
        printf("  第%3d個排列\(zhòng)t%s\n", s_i++, pszStr);  
    }  
    else  
    {  
        for (int i = k; i <= m; i++) //第i個數(shù)分別與它后面的數(shù)字交換就能得到新的排列  
        {  
            if (IsSwap(pszStr, k, i))  
            {  
                Swap(pszStr + k, pszStr + i);  
                AllRange(pszStr, k + 1, m);  
                Swap(pszStr + k, pszStr + i);  
            }  
        }  
    }  
}  
void Foo(char *pszStr)  
{  
    AllRange(pszStr, 0, strlen(pszStr) - 1);  
}  
int main()  
{  
    printf("         去重全排列的遞歸實現(xiàn)\n");  
    printf("  --by MoreWindows( http://blog.csdn.net/MoreWindows )--\n\n");  
    char szTextStr[] = "122";  
    printf("%s的全排列如下:\n", szTextStr);  
    Foo(szTextStr);  
    return 0;  
}  

[字符串轉(zhuǎn)數(shù)字04.04]胖腾？(https://leetcode.com/problems/string-to-integer-atoi/#/description)
Implement atoi to convert a string to an integer.consider all possible input cases.

int myAtoi(string str) {
  long result = 0;
  int indicator = 1;
  for(int i = 0; i<str.size();)
  {
      i = str.find_first_not_of(' ');
      if(str[i] == '-' || str[i] == '+')
        indicator = (str[i++] == '-')? -1 : 1;
      while('0'<= str[i] && str[i] <= '9') 
      {
        result = result*10 + (str[i++]-'0');
        if(result*indicator >= INT_MAX) return INT_MAX;
        if(result*indicator <= INT_MIN) return INT_MIN;                
      }
      return result*indicator;
  }
}

最長無重復(fù)子串04.03
Given a string, find the length of the longest substring without repeating characters.

int lengthOfLongestSubstring(string s) {  
    vector<int> dict(256, -1);  
    int maxLen = 0, start = -1;  
    for (int i = 0; i != s.length(); i++) {  
        if (dict[s[i]] > start)  
            start = dict[s[i]];  
        dict[s[i]] = i;  
        maxLen = max(maxLen, i - start);  
    }  
    return maxLen;  
}

最長回文字符串04.02
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.Example:Input: "babad" Output: "bab"

string longestPalindrome(string s) {
   if (s.empty()) return "";
   if (s.size() == 1) return s;
   int min_start = 0, max_len = 1;
   for (int i = 0; i < s.size();) {
       if (s.size() - i <= max_len / 2) break;
       int j = i, k = i;
       while (k < s.size()-1 && s[k+1] == s[k]) ++k;
       i = k+1;
       while (k < s.size()-1 && j > 0 && s[k + 1] == s[j - 1]) { ++k; --j; } 
       int new_len = k - j + 1;
       if (new_len > max_len) { min_start = j; max_len = new_len; }
    }
    return s.substr(min_start, max_len);
}