44.哀家要长脑子了！

1.300. 最长递增子序列 - 力扣（LeetCode）

 

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();if(n == 0) return 0;vector<int> dp(n, 1);for(int i = 0; i < n; i++)for(int j = 0; j < i; j++)if(nums[j] < nums[i])dp[i] = max(dp[i], dp[j]+1);return *max_element(dp.begin(), dp.end());        }
};

对于数组中的每一个元素，可以假设它至少构成长度为1 的递增子序列（即自身）。当nums[j]大于nums[i]的时候，可以将nums[j] 加入到以nums[i] 为结尾的递增子序列中。

2.34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

class Solution {
public:int binsearch(vector<int> nums, int target) {int l = 0, r = nums.size() - 1;while(l <= r) {int mid = l + (r-l)/2;if(nums[mid] < target) l = mid + 1;else r = mid - 1;}return l;}vector<int> searchRange(vector<int>& nums, int target) {int st = binsearch(nums, target);if(st == nums.size() || nums[st] != target) return {-1, -1};int en = binsearch(nums, target+1) - 1;return {st, en};}
};

 二分 一看就是二分。

3.744. 寻找比目标字母大的最小字母 - 力扣（LeetCode）

 

class Solution {
public:int binsearch(vector<char> nums, char target) {int left = 0, right = nums.size() - 1;while(left <= right) {int mid = left + (right - left) / 2;if(nums[mid] <= target) left = mid + 1;else right = mid - 1;}return left;}char nextGreatestLetter(vector<char>& letters, char target) {int res = binsearch(letters, target);if(res == letters.size() || letters[res] < target)return letters[0];return letters[res];}
};

注意，binsearch函数中是nums[mid] <= target

4.2529. 正整数和负整数的最大计数 - 力扣（LeetCode）

class Solution {
public:int binsearch(vector<int> &nums, int target) {int left = 0, right = nums.size() - 1;while(left <= right) {int mid = left + (right-left) / 2;if(nums[mid] >= target) right = mid - 1;else left = mid + 1;}return left;}int maximumCount(vector<int>& nums) {int neg = binsearch(nums, 0);int pos = (int)nums.size() - binsearch(nums, 1);return pos > neg ? pos : neg;        }
};

不包括0，就从1开始找就好了啊