连接两个单增的链表，连接完依然有序，就比较两个结点值得大小，谁大就在后面。有了这个基本思路之后，可以在两个链表上分别维护一个指针，用来比较两个指针所指的结点的大小，然后按递增的方式连接。
连接将创建一个新链表，设置指针*p3，那么遍历中两个链表较小的一个连接在p3->next，然后较小链表结点上的指针后移一位，p3后移一位，这样就构成了循环体。
注意一种情况：一个链表遍历完毕，则直接把另一个链表剩余的结点接在新链表尾部即可。
一个小点：为新链表设置一个哨兵结点，结果返回此指针。
class Solution
{
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
{
ListNode *p1 = l1;
ListNode *p2 = l2;
//总是指向更小的元素
ListNode *p3 = new ListNode(0);
// 方便结果的返回
ListNode *head = p3;
while (p1 && p2)
{
if (p2->val < p1->val)
{
p3->next = p2;
p3 = p2;
p2 = p2->next;
}
else if (p2->val >= p1->val)
{
p3->next = p1;
p3 = p1;
p1 = p1->next;
}
}
// 链接剩余节点 谁还有剩余就链接谁
p3->next = p1 ? p1 : p2;
return head->next;
}
};上面的代码在堆上new了一个新链表，也可以在原链表上进行连接：
采用迭代的方式 ：
迭代参数：两个链表指针；
终止条件：其中一个链表遍历结束，结点指针为空；
迭代体：把大的接在小的上。
我对迭代的理解：就是一种功能，当我需要这种功能时，就把迭代函数调用一下，在本题中迭代函数就是比较两个链表某对结点的大小，l1比l2小了就拿后面一个l1->next比较，l2比l1->next小了就拿后面一个l2->next比较，直到一个链表遍历结束。参数很好地体现了这一思想。
//双指针，递归，谁小谁在前
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == nullptr) {
return l2;
} else if (l2 == nullptr) {
return l1;
} else if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);//再拿l1->next->val与l2->val比较
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);//再拿l2->next->val与l1->val比较
return l2;
}
}
};本质上括号的生成为排列组合问题，已知有n对括号，n个左括号，n个右括号，排列组合成有效的括号对；
排列组合，回溯算法（递归+后退一步）；
递归参数：应该有左（open）、右（close）括号的数量，存放结果的容器，当前得到的排列结果cur等；
递归结束条件：当前得到的排列结果括号数量为2*n，认为得到了一种组合结果，则把此次递归得到的排列结果放入结果容器。
递归体：如果左括号数没有到n，即还没有完成排列组合，就可以继续尾插左括号，然后open+1后再去判断数量是否达到；右括号也是一样的，但是它的条件是左括号数大于右括号数。基本逻辑就是少哪个括号就插入哪个括号。
回溯在这里就是cur尾删一个括号。
class Solution {
void backtrack(vector& ans, string& cur, int open, int close, int n) {
if (cur.size() == n * 2) {//到达数量要求
ans.push_back(cur);
return;
}
if (open < n) {
cur.push_back('(');
backtrack(ans, cur, open + 1, close, n);
cur.pop_back();//回溯
}
if (close < open) {
cur.push_back(')');
backtrack(ans, cur, open, close + 1, n);
cur.pop_back();//回溯
}
}
public:
vector generateParenthesis(int n) {
vector result;
string current;
backtrack(result, current, 0, 0, n);
return result;
}
}; 按照上面合并两个链表的方式对K个链表两两进行合并；
//方法一：设定一个初始为空的ans链表，依次与输入容器中的链表进行合并，每次ans都进行一次两链表合并
class Solution {
public:
ListNode* mergeTwoLists(ListNode *a,ListNode *b){
if((!a)||(!b)){
return a?a:b;
}
ListNode head;
ListNode *tail = &head,*aptr=a,*bptr=b;
while(aptr&&bptr){
if(aptr->valval){
tail->next=aptr;aptr=aptr->next;
}
else{
tail->next=bptr;bptr=bptr->next;
}
tail=tail->next;
}
tail->next=aptr?aptr:bptr;
return head.next;
}
ListNode* mergeKLists(vector& lists) {
ListNode* ans = nullptr;
for(int i=0;i &lists,int L,int R){
if(L==R) return lists[1];
if(L>R) return nullptr;
int mid = (L+R)>>1;//这一步使得不断二分找到相邻的每两个链表
return mergeTwoLists(merge(lists,1,mid),merge(lists,mid+1,R));
}
ListNode* mergeKLists(vector& lists){
return merge(lists,0,lists.size()-1);
}
//方法三：用队列，每次输出容器每个位置上每个链表的待比较元素
class Solution {
public:
struct Status {
int val;//值
ListNode *ptr;//结点指针
//重载<运算符
bool operator < (const Status &rhs) const {//(const Status &rhs)为参数
return val > rhs.val;
}
};
priority_queue q;//创建对象q
ListNode* mergeKLists(vector& lists) {
for (auto node: lists) {
if (node) q.push({node->val, node});
}
ListNode head, *tail = &head;//定义结点和链表的方式
while (!q.empty()) {
auto f = q.top(); q.pop();
tail->next = f.ptr;
tail = tail->next;
if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
}
return head.next;
}
}; 从后往前找，第一个下降点，即nums[i] < nums[i + 1]时的 i ，就是要交换的一个点，那么另一个点怎么找呢？就是从后往前第一个小于nums[i]的数，将这个数与nums[i]交换。
就是第一个下降点与右侧第一个小于它的点进行交换
注意到下一个排列总是比当前排列要大，除非该排列已经是最大的排列。我们希望找到一种方法，能够找到一个大于当前序列的新序列，且变大的幅度尽可能小。具体地：
我们需要将一个左边的「较小数」与一个右边的「较大数」交换，以能够让当前排列变大，从而得到下一个排列。
同时我们要让这个「较小数」尽量靠右，而「较大数」尽可能小。当交换完成后，「较大数」右边的数需要按照升序重新排列。这样可以在保证新排列大于原来排列的情况下，使变大的幅度尽可能小。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution {
public:
void nextPermutation(vector& nums) {
int i = nums.size() - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;//从右向左找到第一个下降点，即nums[i] < nums[i + 1]时的i
}
if (i >= 0) {//如果i=-1，那说明数组是从大到小排列的，直接反转即可
int j = nums.size() - 1;
while (j >= 0 && nums[i] >= nums[j]) {//再从右向左找到一个点j，j点的nums小于i点的nums
j--;
}
swap(nums[i], nums[j]);//将两个数进行交换
}
reverse(nums.begin() + i + 1, nums.end());//反转i+1后面的数，使其升序排列，以达到最小排列
}
}; 1.动态规划
首先确定动态规划dp数组的含义，本题中，dp[i] 为数组第 i 个位置以前的有效括号长度；
初始化，n个位置全为0；
递推公式：每两个字符检查一次
如果 i 处出现一对有效（），即 s[i]=), s[i-1]=( , 则dp[i]=dp[i-2]+2;
如果 i 处出现 )) ,则需要查找前面是否有((与之对应，而这个前面是已经形成有效括号窗口的头部，而））是尾部。所以就要找 i-dp[i-1]-1 的位置上是否为（ ，则有 dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2;
//动态规划
class Solution{
public:
int longestValidParentheses(string s){
int maxans = 0,n=s.length();
vector dp(n,0);
for(int i =1;i=2 ? dp[i-2] : 0 ) + 2;
}else if(i-dp[i-1]>0 && s[i-dp[i-1]-1]=='('){
dp[i]=dp[i-1]+((i-dp[i-1])>=2?dp[i-dp[i-1]-2]:0)+2;
}
maxans = max(maxans,dp[i]);
}
}
return maxans;
}
};
2.栈
这是比较常规的思路，维护一个栈，遇到左括号则把其位置放入栈，遇到右括号则与栈顶元素匹配。
注意当栈为空时，说明这一阶段匹配完毕，则存入i，即当前匹配段结束的位置，也就是最后一个没有被匹配的右括号的下标
如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」
//栈
class Solution {
public:
int longestValidParentheses(string s) {
int maxans = 0;
stack stk;
stk.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(')
{
stk.push(i);
}
else
{
stk.pop();//出栈配对
if (stk.empty()) {
stk.push(i);
} else {
maxans = max(maxans, i - stk.top());
}
}
}
return maxans;
}
};
//双计数器
class Solution {
public:
int longestValidParentheses(string s) {
int left = 0, right = 0, maxlength = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = max(maxlength, 2 * right);//2*right也太妙了
} else if (right > left) {
left = right = 0;
}
}
left = right = 0;
for (int i = (int)s.length() - 1; i >= 0; i--) {
if (s[i] == '(') {
left++;
} else {
right++;
}
if (left == right) {
maxlength = max(maxlength, 2 * left);
} else if (left > right) {
left = right = 0;
}
}
return maxlength;
}
};欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）