A：数组类
53 Maximum Subarray
从一个数组中找到连续的一个子数组，使得相加的和最大
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int i=0;
int max =INT_MIN;
int sum = 0;
while(i<nums.size()&&nums[i]<0){
max = max>nums[i]?max:nums[i];
sum = (sum+nums[i])>nums[i]?(sum+nums[i]):nums[i];
i++;
}
for(;i<nums.size();i++){
if(nums[i]>=0){
if(sum<0) sum = nums[i];
else sum = sum + nums[i];
max =max>sum?max:sum;
}else{
sum = sum + nums[i];
if(sum<0) sum = nums[i];
}
}
return max =max>sum?max:sum;
}
};
300. Longest Increasing Subsequence
(Given an unsorted array of integers, find the length of longest increasing subsequence)
[10, 9, 2, 5, 3, 7, 101, 18]，The longest increasing subsequence is [2, 3, 7, 101]
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> res;
for(int i=0; i<nums.size(); i++) {
auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
if(it==res.end()) res.push_back(nums[i]);
else *it = nums[i];
}
return res.size();
}
81. Search in Rotated Sorted Array II
class Solution {
public:
bool search(vector<int>& nums, int target) {
int left =0,right = nums.size()-1;
int tmp_left =0,tmp_right=0;
// 这里相对上一道问题，多了个过滤的过程，过滤后，重新设定了左右两个端点的位置
while(left+1<=right&&nums[left+1]==nums[left]) left++;
while(right-1>=left&&nums[right-1]==nums[right]) right--;
tmp_left =left;tmp_right=right;
while(left<right){
int mid = left+(right-left)/2;
if(nums[mid]>nums[right]) left=mid+1;
else right = mid;
}
int pivot = left;
if(target<nums[tmp_left]){
left = pivot;
right = tmp_right;
}else if(target>nums[tmp_left]){
left = tmp_left;
right = pivot==tmp_left?tmp_right:pivot-1;
}else if(target==nums[tmp_left]) return true;
while(left<right){
int mid = left+(right-left)/2;
if(nums[mid]==target) return true;
if(nums[mid]>target) right=mid-1;
if(nums[mid]<target) left=mid+1;
}
if(left<nums.size()&&nums[left]==target) return true;
return false;
}
};
C：二叉树类型
199. Binary Tree Right Side View
(给一棵二叉树，想像你站在右边看这课树，返回你从头结点到尾结点所能看到的所有结点的值）
class Solution {
public:
queue<TreeNode*> q1;
vector<int> res;
void help(){
while(!q1.empty()){
int size = q1.size();
for(int i=0;i<size;i++){
TreeNode* tmp = q1.front();
q1.pop();
if(tmp->left) q1.push(tmp->left);
if(tmp->right) q1.push(tmp->right);
}
if(!q1.empty()) res.push_back(q1.back()->val);
}
}
vector<int> rightSideView(TreeNode* root) {
if(!root) return res;
q1.push(root);
res.push_back(q1.back()->val);
help();
return res;
}
};
108. Convert Sorted Array to Binary Search Tree
（给你一个升序的数组，将它转换为一个高度平衡的二叉查找树）
class Solution {
public:
TreeNode* help(int left, int right, vector<int>& nums){
if(left<=right){
int mid = (left+right)/2;
TreeNode* node = new TreeNode(nums[mid]);
node->left = help(left,mid-1,nums);
node->right = help(mid+1,right,nums);
return node;
}else return nullptr;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
if(nums.size()==0) return nullptr;
return help(0,nums.size()-1,nums);
}
};
109. Convert Sorted List to Binary Search Tree
（给你一个排序好的链表，将它转换为一个高度平衡的二叉查找树）
（都是找中点，只不过，链表，用的是快慢指针来找中点）
class Solution {
public:
ListNode* findCenter(ListNode* head, ListNode* tail)
{
if(head==tail || head->next==tail) return head;
ListNode* slow = head;
ListNode* fast = head->next->next;
while(fast != tail)
{
slow = slow->next;
fast = fast->next;
if(fast != tail) fast = fast->next;
}
return slow;
}
TreeNode* helper(ListNode* head, ListNode*tail)
{
if(head == tail) return NULL;
if(head->next == tail) return new TreeNode(head->val);
ListNode* center = findCenter(head, tail);
TreeNode* t1 = helper(head, center);
TreeNode* t2 = helper(center->next, tail);
TreeNode* tree = new TreeNode(center->val);
tree->left = t1;
tree->right = t2;
return tree;
}
TreeNode* sortedListToBST(ListNode* head)
{
return helper(head, NULL);
}
};
95. Unique Binary Search Trees II
(给一个数字n，产生所有结构上唯一的二叉查找树，使得能够存储1到n的数)
(这个题要做一个动态规划，因为，当 n 相同的时候，能够产生的二叉查找树的数量也是固定的)
241. Different Ways to Add Parentheses
（给一个包含数字和操作符的字符串，返回所有通过数字和操作符所组合的可能的结果）
class Solution {
public:
vector<int> diffWaysToCompute(string input) {
if(input.size() ==0) return {};
vector<int> result;
for(int i = 0; i < input.size(); i++)
{
if(input[i]!='+' &&input[i]!= '-' &&input[i]!= '*') continue;
auto vec1 = diffWaysToCompute(input.substr(0, i));
auto vec2 = diffWaysToCompute(input.substr(i+1));
for(auto val1: vec1)
{
for(auto val2: vec2)
{
if(input[i]=='+') result.push_back(val1+ val2);
else if(input[i]=='-') result.push_back(val1 - val2);
else if(input[i]== '*') result.push_back(val1 * val2);
}
}
}
return result.empty()?vector<int>{stoi(input)}:result;
}
};
6. ZigZag Conversion
// 这个题的解决方法是逐行逐行地进行计算，并找到对应的每一个数的规律。
class Solution {
public:
string convert(string s, int numRows) {
string res="";
if(s=="") return res;
if(numRows==1||s.size()<=numRows) return s; // 单行和单列的时候都是返回原来原有的字符串。
for(int i=0;i<numRows;i++){
if(i==0||i==numRows-1){
for(int j=i;j<s.size();){
res= res + s[j];
j=j+(numRows-1)*2;
}
}else if(i!=numRows-1){
for(int j=i;j<s.size();){
res= res + s[j];
j=j+(numRows-i-1)*2;
if(j<s.size()){
res= res + s[j];
j=j+i*2;
}
}
}
}
return res;
}
};
119 Pascal's Triangle II
(给一个索引k，返回第k行的杨辉三角的数组)
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> result(rowIndex+1, 0);
result[0]=1;
for(int i=1; i<=rowIndex; i++) for(int j=i; j>=1; j--) result[j]=result[j]+result[j-1];
return result;
}
};
89. Gray Code
（格雷码是这么一组数，前后的两个数的的二进制位只相差1）
比如：n=2，return [0,1,3,2]
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> res={0};
for(int i=0;i<n;i++){
int size = res.size();
for(int j=size-1;j>=0;j--) res.push_back(res[j]+(1<<i));
}
return res;
}
};
274. H-Index
For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.
（在一维数组中进行统计，可以看出很多关系出来，比如下面的方法，通过统计的方法，可以知道，比3大的数有多少个）
[3, 0, 6, 1, 5] -> [1,1,0,1,0,2] (对于下标为3的时候，可以得出有多少个数大于等于3)
class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size();
if (n == 0) return 0;
vector<int> hindex(n+1);
for(int val: citations){
if(val >= n) hindex[n]++;
else hindex[val]++;
}
int sum = 0;
int i = n;
while (i > 0) {
sum += hindex[i];
if (i <= sum) return i;
i--;
}
return 0;
}
};
275. H-Index II
（What if the citations array is sorted in ascending order? Could you optimize your algorithm?）
（基本上，一谈到排序的数组，就想到用二分的方法，找到( size()-i） == nums[i]）；
class Solution {
public:
int hIndex(vector<int>& citations) {
if(citations.size()==0) return 0;
if(citations.size()==1) return 1<citations[0]?1:citations[0];
else{
int size = citations.size();
int left = 0,right = citations.size()-1;
while(left<right){
int mid = left + (right-left)/2;
if(citations[mid]==(size-mid)) return citations[mid];
else if(citations[mid]>(size-mid)) right = mid;
else left = mid+1;
}
return min(citations[left],(size-left));
}
}
};
289. Game of Life
（给一个 m*n 的矩阵，每一个单元格为 1 or 0 每一个单元格都会根据下面的四条规则被它的8个邻居所影响）
1、任何一个活着的单元格周围的8个单元格中活着的单元格小于2个，那么该单元格也会死掉。
2、任何一个活着的单元格周围有两个或者三个单元格活着，那么该单元格下一轮也会活着。
3、任何一个活着的单元格周围的8个单元格中有超过三个单元格或者，那么该单元格也会死掉
4、任何一个死掉的单元格周围的8个单元格中有刚好三个活着的邻居，则会变成活的单元格。
这种矩阵的变幻，又要求在原地变幻，其实就是说找到那些需要是活着的单元格就好：
void gameOfLife(vector<vector<int>>& board) {
int m = board.size(), n = m ? board[0].size() : 0;
for (int i=0; i<m; ++i) {
for (int j=0; j<n; ++j) {
int count = 0;
// 将与自己在内的所有的数都统计一遍，然后只把需要将0变为1的case 选出来。
for (int I=max(i-1, 0); I<min(i+2, m); ++I)
for (int J=max(j-1, 0); J<min(j+2, n); ++J)
count += board[I][J] & 1;
if (count == 3 || count - board[i][j] == 3)
board[i][j] |= 2;
}
}
for (int i=0; i<m; ++i)
for (int j=0; j<n; ++j)
board[i][j] >>= 1;
}
69、Sqrt(x)
class Solution {
public:
int mySqrt(int x) {
if(x==0) return 0;
int left=1,right=x;
while(left<=right){
int mid = left+(right-left)/2;
if(mid>x/mid) right=mid;
else{
if(mid+1>x/(mid+1)) return mid;
left = mid+1;
}
}
return left;
}
};
332. Reconstruct Itinerary
class Solution {
public:
vector<string> vec;
stack<string> st;
vector<string> findItinerary(vector<pair<string, string>> tickets) {
unordered_map<string,multiset<string>> record;
for(auto p: tickets){
record[p.first].insert(p.second);
}
// -----begin from "JFK"-----------
string str = "JFK";
while(str!=""){
st.push(str);
if(!record[str].empty()){
string str_ = *record[str].begin();
record[str].erase(record[str].begin()); // 需要注意的是，这个erase 最好是删除迭代器，因为里面是multiset，可以有多个相同的值
str = str_;
}else str="";
}
str = st.top();
while(str!=""){
if(record[str].empty()){
vec.push_back(str);
st.pop();
}else{
st.push(*record[str].begin());
record[str].erase(record[str].begin());
}
if(st.size()>0) str = st.top();
else str = "";
}
reverse(vec.begin(),vec.end());
return vec;
}
};
313. Super Ugly Number（这道题算是比较难的题）
写一个函数去找到第n个 super ugly number
Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.
Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
// 弄明白，如何去构造一个候选项集
int lens = primes.size();
vector<int> pos(lens,0); //候选项集的下标
vector<int> res(n,0);
res[0]=1;
for(int i=1;i<n;i++){
int tmp=INT_MAX;
for(int j=0;j<lens;j++) tmp = min(tmp,res[pos[j]]*primes[j]);
for(int j=0;j<lens;j++) if(tmp==res[pos[j]]*primes[j]) pos[j]++;
res[i] = tmp;
}
return res[n-1];
}
};
