Leetcode刷题第004天

 1 class Solution {
 2 public:
 3     int findKthLargest(vector<int>& nums, int k) 
 4     {
 5     
 6         return quick_sort(nums, 0, nums.size()-1, k);
 7     }
 8     
 9     // 第一种快排思想
10     int quick_sort(vector<int>& data, int left, int right, int k)
11     {
12         int i = left;
13         int j = right;
14         int pivot = data[right];
15         int len = right - left + 1;
16 
17         if (left < right)
18         {  
19             // 从大到小对数组进行快排
20             while(i < j)
21             {
22                 while(i < j && data[i] >= pivot) // 从左往右找第一个比 pivot 小的数
23                 {
24                     i++;
25                 }
26                 if (i < j)
27                 {
28                     data[j--] = data[i];
29                 }
30 
31                 while(i < j && data[j] <= pivot) // 从右往左找第一个比 pivot 大的数
32                 {
33                     j--;
34                 }
35                 if (i < j)
36                 {
37                     data[i++] = data[j];
38                 }
39             }
40             
41             data[i] = pivot; // 此时 i == j
42 
43             // pivot 此时位于索引 i 处，i - left + 1 表示 pivot 是第几大的数
44             int which_max = i - left + 1;
45             if (which_max == k) // pivot 正好是第 k 大的数
46             {
47                 return pivot;
48             }
49   
50             // 第 k 大的数在 pivot 右边，问题转化为找右边数组第 (k - which_max) 大的元素
51             // 比如 pivot 是第四大的数，要找第五大的数，则继续找右边数组第一大的数即可
52             else if(which_max < k)
53             {
54                 return quick_sort(data, i + 1, right, k - which_max);
55             }
56             
57             // 第 k 大的数在 pivot 左边，问题转化为找左边数组第 k 大的元素
58             // 比如 pivot 是第三大的数，要找第二大的数，则继续找左边数组第二大的数即可
59             else
60             {
61                 return quick_sort(data, left, i - 1, k);
62             }
63         }
64         else
65         {
66             return pivot;
67         }
68     }
69 };

二、相同的树

题目：100. Same Tree

C++ Soution 1:

 1 class Solution {
 2 public:
 3     bool isSameTree(TreeNode* p, TreeNode* q) 
 4     {
 5         if(!p && !q) return true;
 6         if(!p || !q) return false;
 7         if(p->val != q->val)
 8             return false;
 9         else
10             return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);      
11     }
12 };

三、爬楼梯

题目：70. Climbing Stairs

分析：

C++ Soution 1:

 1 class Solution {
 2 public:
 3     int climbStairs(int n)
 4     {
 5         // 思路：  这是一题简单的dp问题  先写出递推表达式 dp[i] = dp[i-1] + dp [i-2] ; 
 6         vector<int> dp(n + 1);
 7         dp[0] = 0;
 8         dp[1] = 1;
 9         dp[2] = 2;
10         for (int i = 3; i <= n; i++)  // 直接循环到 n    ，  dp[n] = dp[n-1]+ dp[n-2] ;
11         {
12             dp[i] = dp[i - 1] + dp[i - 2];
13         }
14         return dp[n];
15     }
16 };

四、反转字符串

题目：344. Reverse String

C++ Soution 1:

 1 class Solution {
 2 public:
 3     void reverseString(vector<char>& s) 
 4     {        
 5         int i = 0, j =s.size()-1;  
 6         while( i < j )
 7         {
 8             swap(s[i++], s[j--]);
 9         }
10     }
11 };