实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1 思路：参考
class Solution { public: void nextPermutation(vector<int>& nums) { int pos=nums.size()-2; while(pos>=0 &&nums[pos]>=nums[pos+1]){ pos--; } reverse(nums.begin()+pos+1,nums.end()); if(pos>=0){ int start=pos; for(;start<=nums.size()-1;start++){ if(nums[start]>nums[pos]){ swap(nums[start],nums[pos]); break; } } } } };给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 思路：参考
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode *dummy=new ListNode(0); //针对只有[1]的情况做的下面的处理 dummy->next=head; ListNode *first; ListNode *second; ListNode *prevNode=dummy; while(head!=NULL && head->next!=NULL){ first=head; second=head->next; prevNode->next=second; first->next=second->next; second->next=first; prevNode=first; head=first->next; } return dummy->next; } };将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下： L C I R E T O E S I I G E D H N 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“LCIRETOESIIGEDHN” 思路：参考
class Solution { public: string convert(string s, int numRows) { if(numRows<2)return s; string res; vector<string>temp(numRows,""); int i=0,flag=-1; for(auto x:s){ temp[i]+=x; if(i==numRows-1||i==0)flag=-flag; i+=flag; } for(int i=0;i<temp.size();i++){ res+=temp[i]; } return res; } };给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。 思路：参考
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map <int,int> mymap; for(int i=0;i<nums.size();i++){ int component =target-nums[i]; if(mymap.find(component)!=mymap.end()){ return {mymap[component],i}; } mymap[nums[i]]=i; } return {}; } };罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况： I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。 X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。 给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。 思路：参考
class Solution { public: string intToRoman(int num) { string res=""; vector<int>values={1000,900,500,400,100,90,50,40,10,9,5,4,1}; vector<string> reps={"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}; for(int i=0;i<values.size();i++){ while(num>=values[i]){ num-=values[i]; res+=reps[i]; } } return res; } };给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。 注意：答案中不可以包含重复的三元组。 思路：参考
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>>res; sort(nums.begin(),nums.end()); int n=nums.size(); for(int first=0;first<n;first++){ if(first>0&& nums[first]==nums[first-1])continue; int third=n-1; for(int second=first+1;second<n;second++){ if(second>first+1 && nums[second]==nums[second-1])continue; while(second<third && nums[second]+nums[third]+nums[first]>0){ third--; } if(second==third)break; if(nums[first]+nums[third]+nums[second]==0){ res.push_back({nums[first],nums[second],nums[third]}); } } } return res; } };给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。 思路：参考3数之和
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { int n=nums.size(); vector<vector<int>>res; sort(nums.begin(),nums.end()); for(int first=0;first<n;first++){ if(first>0&&nums[first]==nums[first-1])continue; for(int second=first+1;second<n;second++){ if(second>first+1 && nums[second]==nums[second-1])continue; int forth=n-1; for(int third=second+1;third<n;third++){ if(third>second+1 &&nums[third]==nums[third-1])continue; while(third<forth && nums[first]+nums[second]+nums[third]+nums[forth]>target){ forth--; } if(third==forth)break; if(nums[first]+nums[second]+nums[third]+nums[forth]==target){ res.push_back({nums[first],nums[second],nums[third],nums[forth]}); } } } } return res; } };给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 说明： 所有数字（包括 target）都是正整数。 解集不能包含重复的组合。 思路：参考
class Solution { public: void DFS(int start ,int target){ if(target==0){ res.push_back(path); return; } for(int i=start;i<candidates.size();i++){ if(target-candidates[i]>=0){ path.push_back(candidates[i]); DFS(i,target-candidates[i]); path.pop_back(); } } } vector<vector<int>> combinationSum(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end()); this->candidates=candidates; DFS(0,target); return res; } private: vector<vector<int>>res; vector<int>candidates; vector<int>path; };给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 你的算法时间复杂度必须是 O(log n) 级别。 如果数组中不存在目标值，返回 [-1, -1]。 思路：二分法
class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int left=0; int right=nums.size()-1; while(left<=right){ int mid=(left+right)/2; if(nums[mid]==target){ left=mid; right=mid; while(left>=0 &&nums[left]==target)left--; while(right<=nums.size()-1 && nums[right]==target)right++; return {left+1,right-1}; } else if(nums[mid]<target){ left=mid+1; } else{ right=mid-1; } } return {-1,-1}; } };给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 思路：参考
class Solution { public: bool canJump(vector<int>& nums) { int n=nums.size(); int rightmost=0; for(int i=0;i<n;i++){ if(i<=rightmost){ rightmost=max(rightmost,i+nums[i]); if(rightmost>=n-1){ return true; } } } return false; } };假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。 你可以假设数组中不存在重复的元素。 你的算法时间复杂度必须是 O(log n) 级别。 思路：二分法
class Solution { public: int search(vector<int>& nums, int target) { int n=nums.size(); if(!n)return -1; if(n==1)return nums[0]==target ? 0:-1; int l=0; int r=n-1; while(l<=r){ int mid=(l+r)/2; if (nums[mid]==target)return mid; if(nums[l]<=nums[mid]){ if(nums[l]<=target && target<nums[mid] ){ r=mid-1; } else{ l=mid+1; } } else{ if(nums[mid]<target && target<=nums[n-1] ){ l=mid+1; } else{ r=mid-1; } } } return -1; } };给出一个区间的集合，请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 思路：参考
class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { if(intervals.size()==0)return {}; sort(intervals.begin(),intervals.end()); for(int i=0;i<intervals.size();i++){ int L=intervals[i][0],R=intervals[i][1]; if(res.size()==0||res.back()[1]<L){ res.push_back({L,R}); } else{ res.back()[1]=max(res.back()[1],R); } } return res; } private: vector<vector<int>>res; };给定一个 n × n 的二维矩阵表示一个图像。 将图像顺时针旋转 90 度。 说明： 你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。 思路：参考
class Solution { public: void rotate(vector<vector<int>> & matrix) { int n = matrix.size(); for(int i=0;i<n;i++){ for(int j=i;j<n;j++){ int tmp=matrix[i][j]; matrix[i][j]=matrix[j][i]; matrix[j][i]=tmp; } } for(int i=0;i<n;i++){ for(int j=0;j<n/2;j++){ int tmp=matrix[i][j]; matrix[i][j]=matrix[i][n-1-j]; matrix[i][n-1-j]=tmp; } } } };给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 说明：解集不能包含重复的子集。 思路：参考
class Solution { public: void backtrack(vector<int> & nums,int pos){ res.push_back(cur); for(int i=pos;i<nums.size();i++){ cur.push_back(nums[i]); backtrack(nums,i+1); cur.pop_back(); } } vector<vector<int>> subsets(vector<int>& nums) { backtrack(nums,0); return res; } private: vector<vector<int>>res; vector<int>cur; };给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。 有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 ‘.’ 分隔。 思路：参考
class Solution { public: bool isValid(const string ip){ int val=stoi(ip); if(val>255)return false; if(ip.size()>=2 &&ip[0]=='0')return false; return true; } void backtrack(const string &s,int pos,vector<string> &path){ int maxLen=(4-path.size())*3; if(s.size()-pos>maxLen)return; if(path.size()==4 && pos==s.size()){ string ans=""; for(int i=0;i<4;i++){ ans+=path[i]; if(i!=3) ans+="."; } res.push_back(ans); return; } for (int i=pos;i<s.size()&& i<=pos+2;i++){ string ip=s.substr(pos,i-pos+1); if(!isValid(ip))continue; path.push_back(ip); backtrack(s,i+1,path); path.pop_back(); } } vector<string> restoreIpAddresses(string s) { vector<string>path; backtrack(s,0,path); return res; } private: vector<string>res; };给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。 思路：参考
class Solution { public: string multiply(string num1, string num2) { int n1=num1.size(); int n2=num2.size(); string res(n1+n2,'0'); for(int i=n2-1;i>=0;i--){ for(int j=n1-1;j>=0;j--){ int temp=(res[i+j+1]-'0')+(num2[i]-'0')*(num1[j]-'0'); res[i+j+1]=temp%10+'0'; res[i+j]+=temp/10; } } for(int i=0;i<n1+n2;i++){ if(res[i]!='0') return res.substr(i); } return "0"; } };给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。 思路：动态规划
class Solution { public: int minPathSum(vector<vector<int>>& grid) { int row =grid.size(); int colum=grid[0].size(); vector<vector<int>> dp(row,vector<int>(colum,0)); dp[0][0]=grid[0][0]; for(int i=1;i<row;i++){ dp[i][0]=dp[i-1][0]+grid[i][0]; } for(int i=1;i<colum;i++){ dp[0][i]=dp[0][i-1]+grid[0][i]; } for(int i=1;i<row;i++){ for (int j=1;j<colum;j++){ dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]; } } return dp[row-1][colum-1]; } };给定一个二叉树，原地将它展开为一个单链表。 思路：参考解法一
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: void flatten(TreeNode* root) { while(root!=NULL){ if(root->left==NULL){ root=root->right; } else{ TreeNode *pre=root->left; while(pre->right!=NULL){ pre=pre->right; } pre->right=root->right; root->right=root->left; root->left=NULL; root=root->right; } } } };给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。 思路：参考
class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { vector<vector<string>>res; unordered_map<string ,vector<string>> mymap; for (auto s:strs){ string temp=s; sort(temp.begin(),temp.end()); mymap[temp].push_back(s); } for(auto p=mymap.begin();p!=mymap.end();p++){ res.push_back(p->second); } return res; } };数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 思路：参考
class Solution { public: void backtrack(string path,int n,int left,int right){ if(left==n &&right==n){ res.push_back(path); return; } if(left>n ||right>n|| right>left )return; backtrack(path+'(',n,left+1,right); backtrack(path+')',n,left,right+1); } vector<string> generateParenthesis(int n) { string path=""; backtrack(path,n,0,0); return res; } private: vector<string>res; };给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。 思路：参考
class Solution { public: void dfs(vector<vector<char>> & grid,int init_x,int init_y ){ grid[init_x][init_y]='0'; if(init_x>=1 && grid[init_x-1][init_y]=='1')dfs(grid,init_x-1,init_y); if( init_x+1<grid.size() && grid[init_x+1][init_y]=='1')dfs(grid,init_x+1,init_y); if(init_y>=1 && grid[init_x][init_y-1]=='1')dfs(grid,init_x,init_y-1); if(init_y+1<grid[0].size() && grid[init_x][init_y+1]=='1')dfs(grid,init_x,init_y+1); } int numIslands(vector<vector<char>>& grid) { if(grid.size()==0) return 0; int row=grid.size(); int col=grid[0].size(); int res=0; for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ if(grid[i][j]=='1'){ res++; dfs(grid,i,j); } } } return res; } };给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 注意: 不能使用代码库中的排序函数来解决这道题。 思路：参考
class Solution { public: void sortColors(vector<int>& nums) { int p0=0; int p2=nums.size()-1; int curr=p0; while(curr<=p2){ if(nums[curr]==0){ swap(nums[curr++],nums[p0++]); } else if(nums[curr]==2){ swap(nums[curr],nums[p2--]); } else curr++; } } };在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。 示例: 输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 输出: 4
class Solution { public: int maximalSquare(vector<vector<char>>& matrix) { if(matrix.size()==0|| matrix[0].size()==0)return 0; int col=matrix[0].size(); int row=matrix.size(); vector<vector<int>>dp(row,vector<int>(col,0)); int res=0; for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ if(matrix[i][j]=='1'){ if(i==0||j==0){ dp[i][j]=1; } else{ dp[i][j]=min(min(dp[i-1][j],dp[i-1][j-1]),dp[i][j-1])+1; } res=max(dp[i][j],res); } } } return res*res; } };给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。 注意: 字符串长度 和 k 不会超过 10^4。 思路：滑动窗口
class Solution { public: string minWindow_1(string s, string t) { //最小字串的开始位置和最小长度 int start=0,minLength=INT_MAX; unordered_map<char,int> needs; unordered_map<char,int> window; //建立字符串t的字符表 for(char c:t)needs[c]++; //初始化窗口区间和记录窗口中满足的字符个数 int left=0,right=0,match=0; //开始滑动窗口 while(right<s.size()) { char c1=s[right]; if(needs.count(c1)){//字符c1存在于t的字符表中 window[c1]++;//加入window if(window[c1]==needs[c1])//字符c1的个数已经满足字符表中的个数了 match++; } right++; while(match==needs.size()) { if(right-left<minLength){//窗口的大小小于最小长度，更新字符串 start=left; minLength=right-left; } char c2=s[left]; if(needs.count(c2)){//c2在needs中，主要用来去除window中多余的字符数的 window[c2]--;//字符c2的个数减1 if(window[c2]<needs[c2])//字符c2出现次数不再符合要求 match--; } left++;//不管c2在不在needs中，都需要将left右移，因为此时的window的字符个数必然多于needs的字符个数 } } return minLength==INT_MAX?"":s.substr(start,minLength); } };给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。 注意: num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。 参考：地址
#include<iostream> #include<bits/stdc++.h> using namespace std; class Solution { public: string removeKdigits(string num, int k) { string res; for(int i=0;i<num.size();i++){ while(res.size() && k && res.back()>num[i]){ res.pop_back(); k--; } if(res.size()==0 && num[i]=='0'){ continue;//跳过前置0 } res+=num[i]; } while(k>0 && !res.empty()){//当还要再移除数字的时候：从此时单调递增栈的top部删去数字 res.pop_back(); k--; } return res==""? "0":res; } }; int main(){ Solution sol; string str="1432219"; string str1="123456"; string str2="10001001"; string res=sol.removeKdigits(str2,3); int c=1; }