class Solution {
public:
int findKthLargest(vector<int>& nums, int k)
{
return quick_sort(nums, , nums.size()-, k);
}
// 第一种快排思想
int quick_sort(vector<int>& data, int left, int right, int k)
{
int i = left;
int j = right;
int pivot = data[right];
int len = right - left + ;
if (left < right)
{
// 从大到小对数组进行快排
while(i < j)
{
while(i < j && data[i] >= pivot) // 从左往右找第一个比 pivot 小的数
{
i++;
}
if (i < j)
{
data[j--] = data[i];
}
while(i < j && data[j] <= pivot) // 从右往左找第一个比 pivot 大的数
{
j--;
}
if (i < j)
{
data[i++] = data[j];
}
}
data[i] = pivot; // 此时 i == j
// pivot 此时位于索引 i 处，i - left + 1 表示 pivot 是第几大的数
int which_max = i - left + ;
if (which_max == k) // pivot 正好是第 k 大的数
{
return pivot;
}
// 第 k 大的数在 pivot 右边，问题转化为找右边数组第 (k - which_max) 大的元素
// 比如 pivot 是第四大的数，要找第五大的数，则继续找右边数组第一大的数即可
else if(which_max < k)
{
return quick_sort(data, i + , right, k - which_max);
}
// 第 k 大的数在 pivot 左边，问题转化为找左边数组第 k 大的元素
// 比如 pivot 是第三大的数，要找第二大的数，则继续找左边数组第二大的数即可
else
{
return quick_sort(data, left, i - , k);
}
}
else
{
return pivot;
}
}
};二、相同的树
C++ Soution 1:
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q)
{
if(!p && !q) return true;
if(!p || !q) return false;
if(p->val != q->val)
return false;
else
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};三、爬楼梯
分析：
C++ Soution 1:
class Solution {
public:
int climbStairs(int n)
{
// 思路： 这是一题简单的dp问题 先写出递推表达式 dp[i] = dp[i-1] + dp [i-2] ;
vector<int> dp(n + );
dp[] = ;
dp[] = ;
dp[] = ;
for (int i = ; i <= n; i++) // 直接循环到 n ， dp[n] = dp[n-1]+ dp[n-2] ;
{
dp[i] = dp[i - ] + dp[i - ];
}
return dp[n];
}
};四、反转字符串
C++ Soution 1:
class Solution {
public:
void reverseString(vector<char>& s)
{
int i = , j =s.size()-;
while( i < j )
{
swap(s[i++], s[j--]);
}
}
};