牛客网刷题记录2021

题记录2021"/>

牛客网刷题记录2021

牛客网刷题

• 1th：反转数字

将给出的32位整数x翻转。
例1:x=123，返回321
例2:x=-123，返回-321
你有注意到翻转后的整数可能溢出吗？翻转可能会导致溢出，如果反转后的结果会溢出就返回 0。

class Solution {
public:/*** * @param x int整型 * @return int整型*/int reverse(int x) {// write code hereint res = 0;int a;while(x != 0){a = x%10;int r = res *10 + a;  //res  = 0, if((r-a)/10 != res)return 0;res = r;x = x/10;}return res;}
};

• 2th：LFU缓存结构

• 3rh：编辑距离

给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。

class Solution {
public:/*** min edit cost* @param str1 string字符串 the string* @param str2 string字符串 the string* @param ic int整型 insert cost* @param dc int整型 delete cost* @param rc int整型 replace cost* @return int整型*/int minEditCost(string str1, string str2, int ic, int dc, int rc) {// write code here//输入的三个int表示插入 删除和替换的代价权重int m = str1.size();int n = str2.size();int dp[m+1][n+1];//base case  如果s2没有，则需要是删除i个字符//如果s1没有，则需要插入j个字符for(int i = 0; i<=m; ++i) dp[i][0] = i*dc;for(int j = 0; j<=n; ++j) dp[0][j] = j*ic;for(int i = 1; i<=m; ++i){for(int j = 1; j<=n; ++j){if(str1[i-1] == str2[j-1]) dp[i][j] = dp[i-1][j-1];  //不需要操作else dp[i][j] = min(dp[i][j-1]+ic,min(dp[i-1][j]+dc,dp[i-1][j-1]+rc));}}return dp[m][n];}
};

• 4th：旋转过的有序数组中寻找目标值

给定一个整数数组nums，按升序排序，数组中的元素各不相同。
nums数组在传递给search函数之前，会在预先未知的某个下标 t（0 <= t <= nums.length-1）上进行旋转，让数组变为[nums[t], nums[t+1], …, nums[nums.length-1], nums[0], nums[1], …, nums[t-1]]。
比如，数组[0,2,4,6,8,10]在下标2处旋转之后变为[6,8,10,0,2,4]
现在给定一个旋转后的数组nums和一个整数target，请你查找这个数组是不是存在这个target，如果存在，那么返回它的下标，如果不存在，返回-1

public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param nums int整型vector * @param target int整型 * @return int整型*/int search(vector<int>& nums, int target) {// write code hereint n = nums.size();int l = 0, r = n-1;while(l<=r){int m = l + (r-l)/2;if(nums[m] == target)return m;else if(nums[m] > target){if(nums[m]>=nums[l] && target<nums[l]) l = m+1;else r = m-1;}else if(nums[m] < target){if(nums[m]<nums[l] && target>=nums[l]) r = m-1;else l = m+1;}}return  -1;}
};

• 5th：sqrt计算

实现函数 int sqrt(int x).
计算并返回x的平方根（向下取整）

class Solution {
public:/*** * @param x int整型 * @return int整型*/int sqrt(int x) {// write code here//二分法int left =1, right = x;while(left <= right){int mid = left + (right-left)/2;if(mid == x/mid)return mid;else if(mid < x/mid)left = mid+1;else right = mid -1;}return right;}
};

• 6th：合并k个有序链表

合并\ k k 个已排序的链表并将其作为一个已排序的链表返回。分析并描述其复杂度。

class Solution {
public:ListNode *mergeKLists(vector<ListNode *> &lists) {//直接合并，复杂度高/*if(lists.size() == 0) return nullptr;if(lists.size() == 1) return lists[0];ListNode *head = lists[0];for(int i = 1; i<lists.size(); ++i){head = merge(head,lists[i]);}return head;*/return merge_k(lists,0,lists.size()-1);}ListNode* merge_k(vector<ListNode*> &lists, int l, int r){if(l == r) return lists[l];if(l>r) return nullptr;int mid = l+(r-l)/2;ListNode *left = merge_k(lists,l,mid);ListNode *right = merge_k(lists,mid+1,r);ListNode* head = merge(left,right);return head;}ListNode *merge(ListNode *l1, ListNode *l2){ListNode *newhead = new ListNode(0);ListNode *cur = newhead;while(l1 != nullptr && l2 != nullptr){if(l1->val < l2->val){cur->next = l1;l1 = l1->next;}else{cur->next = l2;l2 = l2->next;}cur = cur->next;}if(l1) cur->next = l1;if(l2) cur->next = l2;cur = newhead->next;delete newhead;return cur;}
};

• 7th：容器盛水问题

给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个容器，请返回容器能装多少水。

class Solution {
public:long long maxWater(vector<int>& arr) {int n = arr.size();vector<int> left_max(n,0);left_max[0] = arr[0];for(int i = 1; i<n-1; i++)left_max[i] = max(left_max[i-1],arr[i]);vector<int> right_max(n,0);right_max[n-1] = arr[n-1];for(int i = n-2; i>=1; --i)right_max[i] = max(right_max[i+1],arr[i]);long res = 0;  //注意可能会溢出for(int i = 1; i<=n-2; ++i){res += min(left_max[i],right_max[i])-arr[i];}return res;}
};

• 8th：字符串排列问题

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba

class Solution {
public:set<string> res;  //set是有序的，可自动排序并且去重vector<string> Permutation(string str) {dfs(str,0);return vector<string>(res.begin(),res.end());}void dfs(string s, int k){if(k == s.size()-1){res.insert(s);  //交换后的字符串return;}for(int i = k; i<s.size(); ++i){swap(s[i],s[k]);  //交换值，固定某一位,做选择dfs(s,k+1); //继续固定swap(s[i],s[k]);  //撤销选择}}
};

• 9th：请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可* 求二叉树的右视图* @param xianxu int整型vector 先序遍历* @param zhongxu int整型vector 中序遍历* @return int整型vector*/vector<int> solve(vector<int>& pre, vector<int>& in) {// write code hereTreeNode *root = rebuild(pre, in);rightView(root, 0);return res;}//中序结果划分左右子树TreeNode* rebuild(vector<int> &pre, vector<int> &in){if(pre.size() == 0) return nullptr;int i;for(i = 0; i<in.size(); ++i)if(in[i] == pre[0]) break;//首先创建找到的根节点TreeNode *root = new TreeNode(pre[0]);//划分先序和中序的左子树vector<int> pre_l(pre.begin()+1,pre.begin()+i+1);vector<int> in_l(in.begin(),in.begin()+i);root->left = rebuild(pre_l,in_l);//划分先序和中序的右子树vector<int> pre_r(pre.begin()+i+1,pre.end());vector<int> in_r(in.begin()+i+1,in.end());root->right = rebuild(pre_r, in_r);return root;}vector<int> res;void rightView(TreeNode *root, int dep){if(root == nullptr) return;//记录每一层的第一个元素，当然是right先遍历的第一个元素if(res.size() == dep)res.push_back(root->val);rightView(root->right,dep+1);rightView(root->left,dep+1);}
};

• 10th：判断回文

给定一个字符串，请编写一个函数判断该字符串是否回文。如果回文请返回true，否则返回false。

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可* * @param str string字符串 待判断的字符串* @return bool布尔型*/bool judge(string str) {// write code hereint left = 0;int right = str.size()-1;while(left <= right){if(str[left++] != str[right--])return false;}return true;}
};

• 11th：单链表排序

给定一个无序单链表，实现单链表的排序(按升序排序)。

class Solution {
public:/*** * @param head ListNode类 the head node* @return ListNode类*/ListNode* sortInList(ListNode* head) {// write code herereturn sort(head,nullptr);}ListNode *sort(ListNode *head, ListNode *tail){if(head == nullptr) return head;if( head->next == tail) {/*这里一定要注意，当只有一个节点的时候，由于我们的区间是左闭右开的所以需要将head的next指针指向nullptr，否则是不对的因为我们最终是将这个链表拆分为单个节点，然后单个节点逐渐归并到一起，如果不修改next指针的指向，会超时很多*/head->next = nullptr;  //这句很重要。。。为啥return head;}//通过快慢指针找到链表的中点ListNode *slow = head;ListNode *fast = head;while(fast != tail && fast->next != tail){slow = slow->next;fast = fast->next->next;}//cout<<slow->val<<endl;ListNode *l1 = sort(head,slow);ListNode *l2 = sort(slow,tail);return merge(l1,l2);}//合并两个有序链表ListNode *merge(ListNode *l1, ListNode *l2){ListNode *head = new ListNode(-1);ListNode *cur = head;while(l1 && l2){if(l1->val < l2->val){cur->next = l1;l1 = l1->next;}else{cur->next = l2;l2 = l2->next;}cur = cur->next;}if(l1) cur->next = l1;if(l2) cur->next = l2;cur = head->next;delete head;return cur;}
};

• 12th：给定一棵二叉树，已经其中没有重复值的节点，请判断该二叉树是否为搜索二叉树和完全二叉树

class Solution {
public:vector<bool> judgeIt(TreeNode* root) {return {search(root),isFull(root)};}//判断是否是二叉搜索树：判断其中序遍历是否是递增的int pre = INT_MIN;bool search(TreeNode  *root){if(root == nullptr) return true;bool left = search(root->left);if(left == false) return false;if(root->val <= pre) return false;pre = root->val;bool right = search(root->right);if(right == false) return false;return true;}//如何判断是否为完全二叉树？这样写是错误的，不能保证前n-1层是满的/*bool isP(TreeNode *root){if(root == 0) return true;if((root->left && root->right) || (!root->right && !root->left))return true;else return false;bool left = isP(root->left);if(left == false) return false;bool right = isP(root->right);if(!right) return false;return true;}*///考虑用层序遍历的方法bool isFull(TreeNode *root){queue<TreeNode *> q;q.push(root);while(!q.empty()){int sz = q.size();int flag = 0;for(int i = 0; i<sz; ++i){TreeNode *tmp = q.front();if(tmp->left){if(flag == 1) return false;q.push(tmp->left);}else flag = 1;if(tmp->right){if(flag == 1) return false;q.push(tmp->right);}else flag = 1;q.pop();}//for}//whilereturn true;}
};

• 13th：矩阵最小路径和

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

class Solution {
public:int minPathSum(vector<vector<int> >& matrix) {// write code hereint m = matrix.size();int n = matrix[0].size();vector<vector<int>> dp(m,vector<int>(n,INT_MAX));int tmp = 0;//base casefor(int i = 0; i<m; ++i) {tmp += matrix[i][0];dp[i][0] = tmp;//cout<<dp[i][0]<<endl;}tmp = 0;for(int i = 0; i<n; ++i){//cout<<matrix[0][i]<<" ";tmp += matrix[0][i];dp[0][i] =  tmp;}for(int i = 1; i<m; ++i){for(int j = 1; j<n; ++j){dp[i][j] = min(dp[i-1][j],dp[i][j-1])+matrix[i][j];}}return dp[m-1][n-1];}
};

• 14th：字符串出现次数的topk问题

给定一个字符串数组，再给定整数k，请返回出现次数前k名的字符串和对应的次数。
返回的答案应该按字符串出现频率由高到低排序。如果不同的字符串有相同出现频率，按字典序排序。
对于两个字符串，大小关系取决于两个字符串从左到右第一个不同字符的 ASCII 值的大小关系。
比如"ah1x"小于"ahb"，“231”<”32“
字符仅包含数字和字母

struct cmp{bool operator()(pair<string,int> &a, pair<string,int> &b){if(a.second == b.second) return a.first < b.first;return a.second > b.second;}
};class Solution {
public:vector<vector<string> > topKstrings(vector<string>& strings, int k) {// write code herevector<vector<string>> res;//首先用哈希表统计每个字符串的个数unordered_map<string,int> ctr;for(auto s:strings){ctr[s] += 1;}//用小顶堆记录topk的统计信息，每次pop的都是最小的数，剩下的k个就是较大//这里要自定义比较仿函数priority_queue<pair<string,int>,vector<pair<string,int>>,cmp> q;for(auto it = ctr.begin(); it!=ctr.end(); ++it){q.push(make_pair(it->first,it->second));if(q.size() == k+1){q.pop();}}//将topk的结果保存进结果数组中while(!q.empty()){vector<string> tmp  = {q.top().first,to_string(q.top().second)};res.insert(res.begin(),tmp);q.pop();}return res;}
};

• 15th：给定一个十进制数M，以及需要转换的进制数N。将十进制数M转化为N进制数

class Solution {
public:string solve(int M, int N) {// write code herestring res;string convert = "0123456789ABCDEF"; //二进制中的某一位bool isMius = false;if(M < 1){isMius = true;M = -M;}while(M != 0){res += convert[M%N];  //查找对应的字符M = M/N;  //除}reverse(res.begin(),res.end());  //倒叙才是真正的结果if(isMius) res.insert(0,"-");  //直接插入一个负号？return res;}
};

• 16th：给定一个链表，请判断该链表是否为回文结构。

class Solution {
public:bool isPail(ListNode* head) {// write code here//递归写/*prev = head;help(head);return res;*///迭代写,首先利用快慢指针找到中点，然后反转一个链表，逐次比较ListNode *slow = head;ListNode *fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}if(fast != nullptr) slow = slow->next;slow = reverse(slow);while(slow != nullptr){if(slow->val != head->val)return false;slow = slow->next;head = head->next;}return true;}//递归写ListNode *prev;bool res = true;void help(ListNode *head){if(head == nullptr) return;help(head->next);if(prev->val != head->val){res = false;}else prev = prev->next;return;}//反转链表ListNode  *reverse(ListNode *head){ListNode *prev = 0, *next = 0;while(head != nullptr){next = head->next;head->next = prev;prev = head;head = next;}return prev;}
};

• 17th：最小编辑代价

给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。

class Solution {
public:int minEditCost(string str1, string str2, int ic, int dc, int rc) {// write code hereint m = str1.size(), n = str2.size();//dp(i,j)表示str1[0...i-1]和str2[0...j-1]的最小编辑距离vector<vector<int>> dp(m+1,vector<int>(n+1,0));//base case, 当str1为空，则需要插入，当str2为空，则需要删除for(int i = 0; i<=n; ++i) dp[0][i] = ic*i;for(int j = 0; j<=m; ++j) dp[j][0] = dc*j;for(int i = 1; i<=m; ++i){for(int j = 1; j<=n; ++j){if(str1[i-1] == str2[j-1])dp[i][j] = dp[i-1][j-1];else dp[i][j] = min(min(dp[i][j-1]+ic,dp[i-1][j]+dc),dp[i-1][j-1]+rc);}}return dp[m][n];}
};

• 18th：二叉树跟节点到叶子节点和为指定值的路径

给定一个二叉树和一个值\ sum sum，请找出所有的根节点到叶子节点的节点值之和等于\ sum sum 的路径，

class Solution {
public:vector<vector<int> > pathSum(TreeNode* root, int sum) {// write code herethis->m_sum = sum;help(root,0);return res;}int m_sum;vector<vector<int>> res;vector<int> tmp;void help(TreeNode *root,int s){if(root == nullptr) return;tmp.push_back(root->val);s += root->val;if(!root->left && !root->right){if(s == m_sum){res.push_back(tmp);}}else{help(root->left,s);help(root->right,s);}tmp.pop_back();//撤销s -= root->val;}
};

• 19th：合并区间

给出一组区间，请合并所有重叠的区间。
请保证合并后的区间按区间起点升序排列。

//按照start升序和end升序排列
bool cmp(const Interval &a, const Interval &b){if(a.start == b.start) return a.end < b.end;return a.start < b.start;
}
class Solution {
public:/*先排序按照左边升序排序，然后逐个判断*/vector<Interval> merge(vector<Interval> &intervals) {sort(intervals.begin(),intervals.end(),cmp);  //排序vector<Interval> res;if(intervals.size() <= 1) return intervals;int left = intervals[0].start, right = intervals[0].end;for(int i = 1; i<intervals.size(); ++i){Interval inter = intervals[i];if(inter.start <= right && inter.end > right){right = inter.end;}if(inter.start > right){res.push_back(Interval(left,right));left = inter.start;right = inter.end;}if(i == intervals.size()-1){res.push_back(Interval(left,right));}}return res;}
};

• 20th：链表指定区间反转

将一个链表\ m m 位置到\ n n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。

class Solution {
public:ListNode* reverseBetween(ListNode* head, int m, int n) {// write code here//找到对应的节点int i = -1;ListNode *prev = 0;ListNode *m_node = 0, *n_node = 0;ListNode *pHead = new ListNode(-1), *cur = pHead;pHead->next = head;while(pHead != nullptr){i++;if(i == m-1) prev = pHead;if(i == n+1) n_node = pHead;pHead = pHead->next;}prev->next = reverse(prev->next, n_node);return cur->next;}//迭代写法ListNode *reverse(ListNode *head, ListNode *end){ListNode *prev = end;ListNode *next = nullptr;while(head != end){next = head->next;head->next = prev;prev = head;head = next;} return prev;}  
};

• 21th：两个长度相等的排序数组找上中位数

给定两个有序数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。
上中位数：假设递增序列长度为n，若n为奇数，则上中位数为第n/2+1个数；否则为第n/2个数

class Solution {
public:int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {// write code hereint n = arr1.size();  //两个相同长度的数据，总数据个数一定为偶数，寻找的就是第n小的数return kth(arr1,0,n-1,arr2,0,n-1,n);   //第n小的数}//将中位数转换为第k小的数int kth(vector<int> &arr1, int left1, int right1, vector<int> &arr2, int left2, int right2, int k){int len1 = right1-left1+1;int len2 = right2-left2+1;//保证len是较短的数组，避免后续的判断if(len1 > len2) return kth(arr2,left2,right2,arr1,left1,right2,k);if(len1 == 0) return arr2[left2+k-1];if(k == 1) return min(arr1[left1],arr2[left2]);int cmp1 = left1 + min(k/2,len1)-1;int cmp2 = left2 + min(k/2,len2)-1;  //防止超出数组长度if(arr1[cmp1] > arr2[cmp2])return kth(arr1,left1,right1,arr2,cmp2+1,right2,k-(cmp1-left1+1));  //砍掉arr2数组的部分else return kth(arr1,cmp1+1,right1,arr2,left2,right2,k-(cmp1-left1+1));}
};

• 22th：二叉树根节点到所有叶子节点的和

class Solution {
public:/*** * @param root TreeNode类 * @return int整型*/int res = 0;int sumNumbers(TreeNode* root) {// write code hereif(root == nullptr) return 0;help(root);return res;}int sum = 0;void help(TreeNode *root){if(root == nullptr){return;}sum  = 10*sum + root->val;if(!root->left && !root->right){  //找到叶子节点res += sum;}else{help(root->left);help(root->right);}sum = (sum - root->val)/10;  //撤销选择}
};

• 23th：删除有序链表中重复出现的节点

class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {// write code hereListNode *root = new ListNode(-1);root->next   = head;ListNode *left = root;ListNode *right = head;while(right && right->next){//cout<<left->val<<endl;if(right->val == right->next->val){int val = right->val;while(right && right->val == val) right = right->next;left->next = right;//cout<<val<<" "<<right->val<<endl;}else{left = left->next;//cout<<" "<<left->val<<endl;right = right->next;}}return root->next;}
};

• 24th：矩阵元素查找

已知int一个有序矩阵mat，同时给定矩阵的大小n和m以及需要查找的元素x，且矩阵的行和列都是从小到大有序的。设计查找算法返回所查找元素的二元数组，代表该元素的行号和列号(均从零开始)。保证元素互异。

class Solution {
public:/*这一题需要注意的是： 每一行是递增的，每一列也是递增的，但是不能保证，第i行的第一个元素大于第i-1行的最后一个元素也就是说，假设找12，但是不能根据某一行的第一个元素和最后一个元素判断12一定在本行，在使用二分的时候尤其需要注意*/vector<int> findElement(vector<vector<int> > mat, int n, int m, int x) {// write code hereint nn = n-1, mm = 0;//从左下角开始找，如果小于x那么，就讲行--，否则将列++while(mm <= m-1 && nn >= 0){if(mat[nn][mm] == x) return {nn,mm};else if(mat[nn][mm] > x) nn--;else mm++;}return  {-1,-1};}
};

• 25th：数组中未出现的最小正整数

给定一个无序数组arr，找到数组中未出现的最小正整数
例如arr = [-1, 2, 3, 4]。返回1
arr = [1, 2, 3, 4]。返回5
[要求]
时间复杂度为O(n)O(n)，空间复杂度为O(1)O(1)

class Solution {
public:int minNumberdisappered(vector<int>& arr) {// write code here//n的空间复杂度，其实是不符合要求的/*unordered_map<int, int> mem;int maxv = -1;for(auto i:arr){maxv = i>maxv?i:maxv;mem[i] += 1;}for(int i  = 1; i<=maxv+1; ++i)if(mem[i] == 0) return i;return -1;*/return help(arr);}/*对于一个长度为 NN 的数组，其中没有出现的最小正整数只能在 [1, N+1][1,N+1] 中。这是因为如果 [1, N][1,N] 都出现了，那么答案是 N+1N+1，否则答案是 [1, N][1,N] 中没有出现的最小正整数。这样一来，我们将所有在 [1, N][1,N] 范围内的数放入哈希表，也可以得到最终的答案。而给定的数组恰好长度为 NN，这让我们有了一种将数组设计成哈希表的思路*/int help(vector<int> &arr){//原地标记法//首先将小于0的数，标定为len+1int len = arr.size();for(int i = 0; i<len; ++i)if(arr[i] <= 0) arr[i] = len+1;//出现过的数，下标标记为负数，主要要先取绝对值，然后比较是否是小于len+1for(int i = 0; i<len; ++i){int num = abs(arr[i]);if(arr[i] < len+1){arr[num-1] = -abs(arr[num-1]);}}//找到第一个大于0的数就是未出现的最小的正整数for(int i = 0; i<len; ++i){if(arr[i] > 0) return i+1;}return len+1;}
};

• 26th：缺失的数字

从0,1,2,…,n这n+1个数中选择n个数，找出这n个数中缺失的那个数，要求O(n)尽可能小。

public:int solve(vector<int>& a) {// write code hereint eor = 0;for(int i = 0; i<a.size(); ++i)eor ^= a[i];for(int i = 0; i<=a.size(); ++i)eor ^= i;return eor;}
};

• 27th：表达式求值

请写一个整数计算器，支持加减乘三种运算和括号

class Solution {
public://利用一个栈结构，如果是+-，那么直接入栈即可，如果是*那么需要考虑他的优先级较高，直接和栈顶的元素计算int solve(string s) {// write code herestack<int> st;int res = 0;int num = 0;int sign = '+';  //一开始默认符号为+，可看成0+for(int i  = 0; i<s.size(); ++i){//如果是数字if(s[i] >= '0' && s[i] <= '9')num = 10*num+s[i]-'0';  //计算数值，如果是大于9的数，需要计算全部的数字//如果碰到左括号 '(',我们需要=递归计算括号内的值if(s[i] == '('){int left = i, count = 1;  //记录左括号的位置和个数i++;while(count>0){if(s[i] == '(') count++;else if(s[i] == ')') count--;i++;}//找到与左括号匹配的右括号,这时候i的位置在有括号的下一个位置num = solve(s.substr(left+1,i-1-(left+1)));i--;  //这里需要将i--，放置i超出的字符串的索引范围，使得最后一个括号计算的值没有纳入计算}//如果是 加减乘,我们需要根据上一个符号来判定如何行动//同时，如果最后一个字符，也要将num纳入计算if(s[i] == '+' || s[i] == '-' || s[i] == '*' || i == s.size()-1){if(sign == '+') st.push(num);else if(sign == '-') st.push(-num);else if(sign == '*') st.top() *= num;sign = s[i];  //更改sign符号num = 0; //记录下一个num}} //for//计算之后，栈中的数，都是需要加起来的while(!st.empty()){res += st.top();st.pop();}return res;}
};

• 28th：链表的奇偶重排

给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
注意是节点的编号而非节点的数值。

class Solution {
public:ListNode* oddEvenList(ListNode* head) {// write code hereif(head == nullptr || head->next == nullptr) return head;ListNode *head1 = head, *head2 = head->next;ListNode *cur1 = head1, *cur2 = head2;//链表奇数和偶数，交替跨节点连接while(head1 && head1->next && head2 && head2->next){head1->next = head2->next;head1 = head1->next;head2->next = head1->next;head2 = head2->next;}//奇链表，指向头偶链表的头head1->next = cur2;return cur1;}
};

• 29th：二叉树的最大路径和

给定一个二叉树，请计算节点值之和最大的路径的节点值之和是多少。
这个路径的开始节点和结束节点可以是二叉树中的任意节点

class Solution {
public:int res = INT_MIN;//这里的返回值指的是，以root为根的最大和,因此返回值需要注意，要么返回自身的值，要么返回//自身的值加上较大的做或者右子树int help(TreeNode *root){if(root == nullptr) return 0;int left = help(root->left);int right = help(root->right);int val = root->val;if(left>0) val += left;if(right>0) val += right;res = max(res,val);return max(root->val,root->val+max(left,right));}//root节点下得最大节点和int maxPathSum(TreeNode* root) {help(root); return res;}
};

• 30th：括号生成

给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。
例如，给出n=3，解集为：
“((()))”, “(()())”, “(())()”, “()()()”, “()(())”,

class Solution {
public://括号生成：组合：无关顺序vector<string> res;string tmp;vector<string> generateParenthesis(int n) {// write code herehelp(n,0,0,0);return res;}//l表示左括号的个数，r表示右括号的个数 //每多一个l，那么sum++， 每多一个r，那么sum--void help(int n, int l, int r, int sum){//string tmp;if(l>n || r>n || sum<0)return;   //不合法的括号if(l == n && r == n && sum == 0){//合法的括号res.push_back(tmp);return;}for(int i = 0; i<2; ++i){if(i == 0) {tmp += '(';  //选择括号help(n,l+1,r,sum+1);}if(i == 1){tmp += ')';  //选择括号help(n,l,r+1,sum-1);} tmp = tmp.substr(0,tmp.size()-1);  //撤销选择}}
};

• 31th：将字符串转化为整数

实现函数 atoi 。函数的功能为将字符串转化为整数
提示：仔细思考所有可能的输入情况。这个问题没有给出输入的限制，你需要自己考虑所有可能的情况

class Solution {
public:/*需要考虑那些情况：1、处理空字符串2、忽略前置空格3、正负号2、不合法的字符3、溢出*/int atoi(string str) {int len = str.size();if(len == 0) return 0;  //空字符串int idx = 0;while(str[idx] == ' ') idx++;  //忽略前置空格int flag = 1;  //处理正负号if(str[idx] == '-') {flag = -1;idx++;}if(str[idx] == '+') idx++;int val = 0;for(int i = idx; i<len; ++i){if(!(str[i] >='0' && str[i] <= '9')) break;  //处理非法字符//处理溢出if(val > INT_MAX/10 || (val == INT_MAX/10 && (str[i]-'0')>INT_MAX%10)){return flag == 1? INT_MAX:INT_MIN;}val = val * 10 +str[i]-'0';  //保存整数值}return val*flag;}
};

• 32th：顺时针旋转矩

有一个NxN整数矩阵，请编写一个算法，将矩阵顺时针旋转90度。

给定一个NxN的矩阵，和矩阵的阶数N,请返回旋转后的NxN矩阵,保证N小于等于300。

class Solution {
public:vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) {// write code here//顺时针旋转之后i,j 位置的元素 跑到了 j,n-1-i的位置vector<vector<int> > res(n,vector<int>(n,0));for(int i = 0; i<n; i++){for(int j = 0; j<n; ++j){res[j][n-1-i] = mat[i][j];}}return res;}
};

• 33th：