C++ – 要饭的银龙

leetcode 32.最长有效括号

class Solution
{
public:
    int longestValidParentheses(string &s)
    {
        stack<int> zz;
        int m = 0;
        for (auto &i : s)
        {

            if (i == '(')
            {

                zz.push(0);
            }
            else
            {
                int temp = 0;
                bool flag = false;
                while (!zz.empty())
                {
                    int temp2 = zz.top();

                    if (temp2 == 0)
                    {
                        if (flag)
                            break;
                        flag = true;
                        temp += 2;
                    }
                    else
                    {
                        temp += temp2;
                    }
                    zz.pop();
                }
                if (flag)
                {
                    zz.push(temp);
                    m = max(temp, m);
                }
                else
                {
                    // while (!zz.empty())
                    //     zz.pop();
                    zz={};                    
                }
            }
        }
        return m;
    }
};

C++清空std::stack

如存在一个

stack<int> a;

由于stack没有clear函数，可以使用以下方法进行清空

a={};

C++与Java派生类函数重载、重写、重定义一点区别

C++中无法在基类函数与派生类函数中进行重载，Java可以。

leetcode 25.K个一组翻转链表

/*
 * @lc app=leetcode.cn id=25 lang=cpp
 *
 * [25] K 个一组翻转链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution
{
private:
    static ListNode *a[5000];

public:
    ListNode *&reverseKGroup(ListNode *&head, int &k)
    {

        ListNode *temp = head;
        for (int i = 0; i < k; ++i)
        {
            if (temp != nullptr)
            {
                a[i] = temp;
                temp = temp->next;
            }
            else
                return head;
        }
        head = a[k - 1];
        a[0]->next = head->next;
        for (int i = k - 1; i > 0; --i)
        {
            a[i]->next = a[i - 1];
        }
        temp = a[0];

        reverseKGroup(temp->next, k);
        return head;
    }
};
ListNode *Solution::a[];

// @lc code=end

最开始的时候使用了

static vector<ListNode*> a(k);

运行出错，折腾了半天，后来才明白leetcode的测试程序应该是在一个程序下换不同的数组跑，导致后续的数据运行时vector越界了–

leetcode 12.整数转罗马数字无脑版代码

/*
 * @lc app=leetcode.cn id=12 lang=cpp
 *
 * [12] 整数转罗马数字
 */

// @lc code=start
#include <iostream>
using namespace std;
class Solution
{
public:
    string r;
    string intToRoman(int &num)
    {
        while (num > 0)
        {
            if (num >= 1000)
            {
                r += 'M';
                num -= 1000;
            }
            else if (num >= 900)
            {
                r += "CM";
                num -= 900;
            }
            else if (num >= 500)
            {
                r += 'D';
                num -= 500;
            }
            else if (num >= 400)
            {
                r += "CD";
                num -= 400;
            }
            else if (num >= 100)
            {
                r += 'C';
                num -= 100;
            }
            else if (num >= 90)
            {
                r += "XC";
                num -= 90;
            }
            else if (num >= 50)
            {
                r += 'L';
                num -= 50;
            }
            else if (num >= 40)
            {
                r += "XL";
                num -= 40;
            }
            else if (num >= 10)
            {
                r += 'X';
                num -= 10;
            }
            else if (num >= 9)
            {
                r += "IX";
                num -= 9;
            }
            else if (num >= 5)
            {
                r += 'V';
                num -= 5;
            }
            else if (num >= 4)
            {
                r += "IV";
                num -= 4;
            }
            else
            {
                r += 'I';
                num -= 1;
            }
        }
        return r;
    }
};
// @lc code=end

leetcode 10.正则表达式

#include <iostream>
#include <vector>
#include <functional>
using namespace std;
class Solution
{
public:
    bool isMatch(string &s, string &p)
    {
        int sSize = s.size();
        int pSize = p.size();
        vector<vector<int>> a(sSize + 1, vector(pSize + 1, 0));
        a[0][0] = 1;
        function<bool(int, int)> match = [&](int n, int m) {
            if (n < 0 || m < 0)
                return false;
            if (a[n][m] == 1)
                return true;
            if (a[n][m] == -1)
                return false;
            if (n > 0 && m > 0)
            {
                if (s[n - 1] == p[m - 1] || p[m - 1] == '.')
                    if (match(n - 1, m - 1))
                    {
                        a[n][m]=1;
                        return true;
                    }
            }
            if (m > 1)
            {
                if (p[m - 1] == '*')
                {
                    if (n > 0)
                    {
                        if (s[n - 1] == p[m - 2] || p[m - 2] == '.')
                            if (match(n - 1, m))
                                {
                        a[n][m]=1;
                        return true;
                    }
                    }
                    if (match(n, m - 2))
                        {
                        a[n][m]=1;
                        return true;
                    }
                }
            }
            a[n][m]=-1;
            return false;
        };
        return match(sSize, pSize);
    }
};

C++父类为虚函数（转）

转自https://blog.csdn.net/shltsh/article/details/45999727

C++中, 一旦某个成员函数在基类中声明为虚函数，则它在所有的子类中都会成为虚函数。换言之，如果应该在基类中声明了某个函数为虚函数，则无需在子类中使用关键字virtual再去声明函数。

可以参考: http://www.umsl.edu/~subramaniana/virtual2.html

例如，下面程序中，B::fun() 会自动成为一个虚函数

#include<iostream>
 
class A
{
public:
  virtual void fun()
  {
    std::cout << "A::fun() called \n";
  }
};
 
class B : public A
{
public:
  void fun()
  {
    std::cout << "B::fun() called \n";
  }
};
 
class C : public B
{
public:
  void fun()
  {
    std::cout << "C::fun() called \n";
  }
};
 
int main()
{
  C c;       // C的对象
  B *b = &c; // 类型为B*的一个指针，指向对象c
  b->fun();  // 这行代码会打印 "C::fun() called"
 
  A *a = &c;
  a->fun();  //这行代码会打印 "C::fun() called"
 
  return 0;
}

输出：C::fun() called
C::fun() called

C++多继承，指针问题

C++中多继承的派生类最开始的位置是第一个基类，其后才是第二三四…个基类。所以派生类对象后面的基类的地址与派生类地址不同，但在将派生类地址赋值给基类指针时会自动转换。

#include <iostream>
using namespace std;
class A
{
    public:int a;
};
class B
{
    public:int b;
};
class C : public A, public B
{
    public:int c;
};
int main()
{
    C c;
    A *pa=&c;
    B *pb=&c;
    C *pc=&c;
    cout<<pa<<endl<<pb<<endl<<pc<<endl;
    return 0;
}

以上代码的某次运行结果为

0x7ffffffedc8c
0x7ffffffedc90
0x7ffffffedc8c

C++初始化列表与类内初始化

类内初始化可使用{}，=，不可使用()，如

class test2
{
public:
    int c=6;//正确
    int d{7};//正确
    int e(8);//错误
};

初始化列表可使用{}，()，不可使用=，如

class test2
{
public:
    test2(int h, int z) : c(h), d{z}
          //不可使用 c=h
    {
        cout << h << endl;
        cout << z << endl;
    };
};

一个成员同时在类内初始化与初始化列表时，实际结果表明初始化列表生效

#include <iostream>
using namespace std;
class test2
{
public:
    int c = 6;
    int d = 7;
    test2(int h, int z) : c(h), d{z}
    {
        cout << h << endl;
        cout << z << endl;
    };
};
int main()
{
    test2 a{10, 19};
    return 0;
}

以上代码输出10 19。

B:魔兽世界之一：备战

http://cxsjsxmooc.openjudge.cn/test/B/

系统关闭，未测试

#include <iostream>
#include <iomanip>
using namespace std;
class headquarters;
extern int Time;
class warrior
{
private:
    int num;
    const int life;

public:
    friend class headquarters;
    const int id;
    const static char name[][10];
    static int lifes[];
    warrior *next;
    warrior(int _id, int _life, int _num = 0) : id(_id), num(_num), life(_life), next(NULL){};
    bool create(int &w)
    {
        if (w >= life)
        {
            w -= life;
            num++;
            return true;
        }
        else
            return false;
    }
};
class headquarters
{
private:
    int life;
    warrior *pp;
    const int *order;
    const char *color;
    bool stop;
    int num;

public:
    headquarters(int _life, const int _order[], const char *_color) : pp(NULL), life(_life), order(_order), color(_color), stop(false), num(0)
    {
    }
    ~headquarters()
    {
        while (pp != NULL && pp->next != pp)
        {
            warrior *temp;
            temp = pp->next->next;
            delete pp->next;
            pp->next = temp;
        }
        delete pp;
    }
    void add_node(int _id)
    {
        warrior *temp = new warrior(_id, warrior::lifes[_id]);
        if (pp == NULL)
        {
            pp = temp;
            pp->next = pp;
        }
        else
        {
            temp->next = pp->next;
            pp->next = temp;
            pp = temp;
        }
    }
    bool making()
    {
        if (stop)
            return false;
        pp = pp->next;
        if (pp->create(life))
        {
            num++;
            cout << setw(3) << setfill('0') << Time << ' ';
            cout << color << ' ' << warrior::name[pp->id] << ' ' <<num <<' '<<"born with strength "<<pp->life<<","<< pp->num <<" "<<warrior::name[pp->id]<<" in "<<color<<" headquarter"<< endl;
            return true;
        }
        else
        {
            warrior *temp = pp->next;
            while (temp != pp)
            {

                if (temp->create(life))
                {
                    num++;
                    cout << setw(3) << setfill('0') << Time << ' ';
                    pp = temp;
                    cout << color << ' ' << warrior::name[temp->id] << ' ' <<num<<' '<<"born with strength "<<temp->life<<"," << temp->num <<" "<<warrior::name[temp->id]<<" in "<<color<<" headquarter"<<endl;
                    return true;
                }
                temp = temp->next;
            }
            stop = true;
            cout << setw(3) << setfill('0') << Time << ' ';
            cout << color << " headquarter stops making warriors" << endl;
            return false;
        }
    }
};
const char warrior::name[][10]{"dragon", "ninja", "iceman", "lion", "wolf"};
int warrior::lifes[5]{0};
const int _order[2][5]{{2, 3, 4, 1, 0}, {3, 0, 1, 2, 4}};
const char color[][5] = {"red", "blue"};

int Time = 0;
int main()
{
    int n;
    cin >> n;
    for (int j = 1; j <= n; j++)
    {
        cout << "Case:" << j << endl;
        int h_life;
        cin >> h_life;
        for (int i = 0; i < 5; i++)
        {
            cin >> warrior::lifes[i];
        }
        headquarters red(h_life, _order[0], color[0]);
        headquarters blue(h_life, _order[1], color[1]);
        for (int k = 0; k < 5; k++)
        {
            red.add_node(_order[0][k]);
            blue.add_node(_order[1][k]);
        }
        for (Time = 0;; Time++)
        {

            bool a, b;

            a = red.making();

            b = blue.making();
            if (!(a || b))
                break;
        }
    }
    return 0;
}