C++: 基础数据结构

int countOdd(int n, int a[]) {
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] & 1) {
            ++cnt;
        }
    }
    return cnt;
}

def countOdd(n, a):
    cnt = 0
    for i in range(n):
        if a[i] & 1:
            cnt += 1
    return cnt

int countOddPair(int n, int a[]) {
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (a[i] + a[j] & 1)
                ++cnt;
        }
    }
    return cnt;
}

def countOddPair(n, a):
    cnt = 0
    for i in range(n):
        for j in range(i+1, n):
            if a[i] + a[j] & 1:
                cnt += 1
    return cnt

int countOddTriple(int n, int a[]) {
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            for (int k = j + 1; k < n; ++k) {
                if (a[i] + a[j] + a[k] & 1)
                    ++cnt;
            }
        }
    }
    return cnt;
}

def countOddTriple(n, a):
    cnt = 0
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                if a[i] + a[j] + a[k] & 1:
                    cnt += 1
    return cnt

int dfs(int n, int a[], int start, int k, int sum) {
    if (k = 0)
        return (sum & 1) ? 0 : 1;                 // (1)
    int s = 0;
    for (int i = start; i < n; ++i)
        s += dfs(n, a, i + 1, k - 1, sum + a[i]); // (2)
    return s;
}

def dfs(n, a, start, k, sum_):
    if k == 0:
        return 0 if sum_ & 1 else 1 #(1)
    s = 0
    for i in range(start, n):
        s += dfs(n, a, i+1, k-1, sum_ + a[i]) # (2)
    return s

const int MAXN = 1024;

int getMAXN() {
    return MAXN;
}

int bin(int n, int a[], int v) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = (l + r) >> 1;  // 右移一位相当于对原来的这个数除上2
        if (a[mid] == v)
            return mid;
        else if (a[mid] < v)
            r = mid + 1;
        else
            l = mid + 1;
    }
    return -1;
}

def bin(n, a, v):
    l = 0
    r = n -1
    while l <= r:
        mid = (l + r) // 2
        if a[mid] == v:
            return mid
        elif a[mid] < v:
            r  = mid + 1
        else:
            l = mid + 1
    return -1

bool isPrime(int n) {
    int i;
    if (n == 1) {
        return false;
    }
    int sqrtn = sqrt(n + 0.0);
    for (int i = 2; i <= sqrtn; ++i) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

import math

def isPrime(n):
    if n == 1:
        return False
    sqrtn = int(math.sqrt(n))
    for i in range(2, sqrtn + 1):
        if n % i == 0:
            return False
    return True

#include <iostream>
using namespace std;

#define eleType int  // 表示顺序表中所有元素都这个类型的

struct SequentialList {
    eleType* elements;
    int size;      // 元素个数
    int capacity; // 容量
};

// 实现顺序表初始化
void initializeList(SequentialList* list, int capacity) {
    list->elements = new eleType[capacity];
    list->size = 0;
    list->capacity = capacity;
}

// 实现顺序表的销毁
void destroyList(SequentialList* list) {
    delete[] list->elements;
}

// 实现获取顺序表大小接口
int size(SequentialList* list) {
    return list->size;
}

bool isEmpty(SequentialList* list) {
    return list->size == 0;
}

// 实现顺序表的插入操作
void insert(SequentialList* list, int index, eleType element) {
    if (index < 0 || index > list->size) {
        throw std::invalid_argument("Invalid index"); // 抛异常
    }
    if (list->capacity == list->size) {
        int newCapacity = list->capacity * 2;
        eleType* newElements = new eleType[newCapacity];
        for (int i = 0; i < newCapacity/2; ++i) {
            newElements[i] = list->elements[i];
        }
        delete[] list->elements;
        list->elements = newElements;
        list->capacity = newCapacity;
    }
    list->size++;
    if (list->size <= list->capacity) {
        for (int i = list->size -1; i > index; --i) {
            list->elements[i] = list->elements[i - 1];
        }
        list->elements[index] = element;
    }
}

// 顺序表的元素删除
void deleteElement(SequentialList* list, int index) {
    if (index < 0 || index >= list->size) {
        throw std::invalid_argument("Invalid index"); // 抛异常
    }
    for (int i = index; i < list->size; ++i) {
        list->elements[i] = list->elements[i + 1];
    }
    list->size--;
}

// 顺序表元素查找
int findElement(SequentialList* list, eleType element) {
    for (int i = 0; i < list->size; ++i) {
        if (list->elements[i] == element) {
            return i;
        }
    }
    return -1;
}

// 顺序表元素索引
eleType getElement(SequentialList* list, int index) {
    if (index < 0 || index > list->size) {
        throw std::invalid_argument("Invalid index"); // 抛异常
    }
    return list->elements[index];
}

// 顺序表元素修改
void updateElement(SequentialList* list, int index, eleType value) {
    if (index < 0 || index > list->size) {
        throw std::invalid_argument("Invalid index"); // 抛异常
    }
    list->elements[index] = value;
}

int main() {
    int n;
    while (cin >> n) { // 输入一个数n，表示共有n个数
        SequentialList s;
        initializeList(&s, 1);
        for (int i = 0; i < n; ++i) {// 遍历这n个数
            eleType x;
            cin >> x; // 定义一个x，并插入到顺序表中
            insert(&s, i, x);
        }
        // s.size == n 插入之后这是相等的
        int prod = 1;
        for (int i = 0; i < s.size; ++i) {
            int val = getElement(&s, i);
            if (val % 2 == 1) {
                prod = prod * val;
            }
        }
        cout << prod << endl;
    }

    return 0;
}

#include <iostream>
using namespace std;

int a[100000];

int main() {
    int n;
    while (cin >> n) { // 输入一个数n，表示共有n个数
        for (int i = 0; i < n; ++i) {// 遍历这n个数
            int x;
            cin >> x; // 定义一个x，并插入到顺序表中
            a[i] = x;
        }
        int prod = 1;
        for (int i = 0; i < n; ++i) {
            int val = a[i];
            if (val % 2 == 1) {
                prod = prod * val;
            }
        }
        cout << prod << endl;
    }

    return 0;
}

#include <iostream>
using namespace std;

#define eleType double  // 表示顺序表中所有元素都这个类型的

struct SequentialList {
    eleType* elements;
    int size;      // 元素个数
    int capacity; // 容量
};

// 实现顺序表初始化
void initializeList(SequentialList* list, int capacity) {
    list->elements = new eleType[capacity];
    list->size = 0;
    list->capacity = capacity;
}

// 实现顺序表的销毁
void destroyList(SequentialList* list) {
    delete[] list->elements;
}

// 实现获取顺序表大小接口
int size(SequentialList* list) {
    return list->size;
}

bool isEmpty(SequentialList* list) {
    return list->size == 0;
}

// 实现顺序表的插入操作
void insert(SequentialList* list, int index, eleType element) {
    if (index < 0 || index > list->size) {
        throw std::invalid_argument("Invalid index"); // 抛异常
    }
    if (list->capacity == list->size) {
        int newCapacity = list->capacity * 2;
        eleType* newElements = new eleType[newCapacity];
        for (int i = 0; i < newCapacity / 2; ++i) {
            newElements[i] = list->elements[i];
        }
        delete[] list->elements;
        list->elements = newElements;
        list->capacity = newCapacity;
    }
    list->size++;
    if (list->size <= list->capacity) {
        for (int i = list->size - 1; i > index; --i) {
            list->elements[i] = list->elements[i - 1];
        }
        list->elements[index] = element;
    }
}

// 顺序表的元素删除
void deleteElement(SequentialList* list, int index) {
    if (index < 0 || index >= list->size) {
        throw std::invalid_argument("Invalid index"); // 抛异常
    }
    for (int i = index; i < list->size; ++i) {
        list->elements[i] = list->elements[i + 1];
    }
    list->size--;
}

// 顺序表元素查找
int findElement(SequentialList* list, eleType element) {
    for (int i = 0; i < list->size; ++i) {
        if (list->elements[i] == element) {
            return i;
        }
    }
    return -1;
}

// 顺序表元素索引
eleType getElement(SequentialList* list, int index) {
    if (index < 0 || index > list->size) {
        throw std::invalid_argument("Invalid index"); // 抛异常
    }
    return list->elements[index];
}

// 顺序表元素修改
void updateElement(SequentialList* list, int index, eleType value) {
    if (index < 0 || index > list->size) {
        throw std::invalid_argument("Invalid index"); // 抛异常
    }
    list->elements[index] = value;
}

int main() {
    int n;
    while (cin >> n && n) { // 输入一个n，并且输入n等于0时跳出循环
        SequentialList s;
        initializeList(&s, 1);
        for (int i = 0; i < n; ++i) {
            eleType x;
            cin >> x;
            insert(&s, i, x);
        }
        int pcnt = 0, zcnt = 0, ncnt = 0; // 大于0 pcnt、等于0 zcnt、小于0 ncnt
        for (int i = 0; i < size(&s); ++i) {
            eleType ele = getElement(&s, i);
            if (ele > 1e-8) { // 浮点数是有误差的，所以我们不能大于0，大于一个非常小的正数我就算它大于0
                ++pcnt;
            }
            else if (ele < -1e-8) { // 小于非常大的负数，就把它定义为小于0
                ++ncnt;
            }
            else {
                ++zcnt;
            }
        }
        cout << ncnt << ' ' << zcnt << ' ' << pcnt << endl;
    }

    return 0;
}

#include <iostream>
using namespace std;

#define eleType double  // 表示顺序表中所有元素都这个类型的

struct SequentialList {
    eleType* elements;
    int size;      // 元素个数
    int capacity; // 容量
};

// 实现顺序表初始化
void initializeList(SequentialList* list, int capacity) {
    list->elements = new eleType[capacity];
    list->size = 0;
    list->capacity = capacity;
}

// 实现顺序表的销毁
void destroyList(SequentialList* list) {
    delete[] list->elements;
}

// 实现获取顺序表大小接口
int size(SequentialList* list) {
    return list->size;
}

bool isEmpty(SequentialList* list) {
    return list->size == 0;
}

// 实现顺序表的插入操作
void insert(SequentialList* list, int index, eleType element) {
    if (index < 0 || index > list->size) {
        throw std::invalid_argument("Invalid index"); // 抛异常
    }
    if (list->capacity == list->size) {
        int newCapacity = list->capacity * 2;
        eleType* newElements = new eleType[newCapacity];
        for (int i = 0; i < newCapacity / 2; ++i) {
            newElements[i] = list->elements[i];
        }
        delete[] list->elements;
        list->elements = newElements;
        list->capacity = newCapacity;
    }
    list->size++;
    if (list->size <= list->capacity) {
        for (int i = list->size - 1; i > index; --i) {
            list->elements[i] = list->elements[i - 1];
        }
        list->elements[index] = element;
    }
}

// 顺序表的元素删除
void deleteElement(SequentialList* list, int index) {
    if (index < 0 || index >= list->size) {
        throw std::invalid_argument("Invalid index"); // 抛异常
    }
    for (int i = index; i < list->size; ++i) {
        list->elements[i] = list->elements[i + 1];
    }
    list->size--;
}

// 顺序表元素查找
int findElement(SequentialList* list, eleType element) {
    for (int i = 0; i < list->size; ++i) {
        if (list->elements[i] == element) {
            return i;
        }
    }
    return -1;
}

// 顺序表元素索引
eleType getElement(SequentialList* list, int index) {
    if (index < 0 || index > list->size) {
        throw std::invalid_argument("Invalid index"); // 抛异常
    }
    return list->elements[index];
}

// 顺序表元素修改
void updateElement(SequentialList* list, int index, eleType value) {
    if (index < 0 || index > list->size) {
        throw std::invalid_argument("Invalid index"); // 抛异常
    }
    list->elements[index] = value;
}

int main() {
    int n;
    while (cin >> n) {
        SequentialList s;
        initializeList(&s, 1);
        for (int i = 0; i < n; ++i) {
            eleType ele;
            cin >> ele;
            insert(&s, i, ele);
        }
        eleType eMax = -1000000000, eMin = 10000000000;
        eleType eSum = 0; // 定义一个求和变量
        for (int i = 0; i < size(&s); ++i) {
            eleType ele = getElement(&s,i);
            if (ele > eMax) eMax = ele;
            if (ele < eMin) eMin = ele;
            eSum += ele;
        }
        eSum -= eMax;
        eSum -= eMin;
        eSum /= (n - 2);
        printf("%.2lf\n", eSum);
    }

    return 0;
}

#include <iostream>
#include <stdexcept> // 处理异常
using namespace std;

#define eleType int

// 链表结点的结构体
struct ListNode {
    eleType data;   // 数据域
    ListNode *next; // 指针域

    // c++中的struct和class是一样的，可以写构造函数
    ListNode(eleType x): data(x), next(NULL) {}
};

// 实现单向链表的类
class LinkedList {
private:
    ListNode* head; // 头结点
    int size;       // 链表元素个数
public:
    LinkedList(): head(NULL), size(0) {}
    ~LinkedList();
    void insert(int i, eleType value); // i位置插入值为value的元素
    void remove(int i);                // 删除第i个结点
    ListNode* find(eleType value);     // 查找值为value的结点，返回结点本身
    ListNode* get(int i);              // i 索引位置。获取链表的第几个结点
    void update(int i, eleType value); // 更新第i个结点的值
    void print();                      // 打印链表
    eleType sum();                     // 求链表中所有元素的和
};

// 任何一个数据结构其实都是增删改查
LinkedList::~LinkedList() {
    // 每个结点的内存空间析构掉
    ListNode* curr = head; // 头结点赋值给current
    while (curr != NULL) {
        ListNode* tmp = curr;
        curr = curr->next;
        delete tmp;
    }
}

void LinkedList::insert(int i, eleType value) {
    if (i <0 || i > size) {
        throw std::out_of_range("Invlid position");
    }
    ListNode* newNode = new ListNode(value);
    if (i == 0) { // 如果是链表头
        newNode->next = head;
        head = newNode;
    }
    else {
        ListNode* curr = head; // 定义游标结点，从head开始
        for (int j = 0; j < i - 1; ++j) { // 确定要插入位置的前一个结点
            curr = curr->next;
        }
        newNode->next = curr->next;
        curr->next = newNode;
    }
    ++size;
}

void LinkedList::remove(int i) {
    if (i < 0 || i >= size) {
        throw std::out_of_range("Invalid position");
    }
    if (i == 0) { // 删除头结点
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
    else {
        ListNode* curr = head;
        for (int j = 0; j < i - 1; ++j) { // 找到要删除结点的前一个结点
            curr = curr->next;
        }
        ListNode* temp = curr->next; // 要删除的结点存储到temp中
        curr->next = temp->next;     // 把要删除的结点的前驱结点的后继，设置为要删除结点的后继结点
        delete temp;                 // 删除要删除的结点
    }
    --size;
}

// 查找值为value的结点，返回结点本身
ListNode* LinkedList::find(eleType value) {
    ListNode* curr = head;  // 从根结点开始
    while (curr && curr->data != value) {
        curr = curr->next; // 当前结点变为它的后继
    }
    return curr; // 链表遍历完没找到返回空结点，找到返回data为value的结点
}

// 链表索引
ListNode* LinkedList::get(int i) {
    if (i < 0 || i >= size) {
        throw std::out_of_range("Invalid position");
    }
    ListNode* curr = head;         // 初始化curr，从头结点开始
    for (int j = 0; j < i; ++j) { // 迭代i次，每次操作变为它的后继
        curr = curr->next;
    }
    return curr;
}

// 链表更新。更新第i个结点的值
void LinkedList::update(int i, eleType value) {
    get(i)->data = value;
}

// 调试函数
void LinkedList::print() {
    ListNode* curr = head;
    while (curr) {
        cout << curr->data << ' ';
        curr = curr->next; // curr等于他的后继
    }
    cout << endl;
}

eleType LinkedList::sum() {
    ListNode* curr = head;
    eleType ret = 0;
    while (curr) {
        ret += curr->data;
        curr = curr->next;
    }
    return ret;
}

int main() {
    int n;
    while (cin >> n && n) {
        LinkedList l;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            l.insert(i, x);
        }
        // l.print();
        cout << l.sum() << endl;
    }

    return 0;
}

#include <iostream>
#include <stdexcept> // 处理异常
using namespace std;

#define eleType int

// 链表结点的结构体
struct ListNode {
    eleType data;   // 数据域
    ListNode *next; // 指针域

    // c++中的struct和class是一样的，可以写构造函数
    ListNode(eleType x): data(x), next(NULL) {}
};

// 实现单向链表的类
class LinkedList {
private:
    ListNode* head; // 头结点
    int size;       // 链表元素个数
public:
    LinkedList(): head(NULL), size(0) {}
    ~LinkedList();
    void insert(int i, eleType value); // i位置插入值为value的元素
    void remove(int i);                // 删除第i个结点
    ListNode* find(eleType value);     // 查找值为value的结点，返回结点本身
    ListNode* get(int i);              // i 索引位置。获取链表的第几个结点
    void update(int i, eleType value); // 更新第i个结点的值
    void print();                      // 打印链表
};

// 任何一个数据结构其实都是增删改查
LinkedList::~LinkedList() {
    // 每个结点的内存空间析构掉
    ListNode* curr = head; // 头结点赋值给current
    while (curr != NULL) {
        ListNode* tmp = curr;
        curr = curr->next;
        delete tmp;
    }
}

void LinkedList::insert(int i, eleType value) {
    if (i <0 || i > size) {
        throw std::out_of_range("Invlid position");
    }
    ListNode* newNode = new ListNode(value);
    if (i == 0) { // 如果是链表头
        newNode->next = head;
        head = newNode;
    }
    else {
        ListNode* curr = head;            // 定义游标结点，从head开始
        for (int j = 0; j < i - 1; j++) { // 确定要插入位置的前一个结点
            curr = curr->next;
        }
        newNode->next = curr->next;
        curr->next = newNode;
    }
    size++;
}

void LinkedList::remove(int i) {
    if (i < 0 || i >= size) {
        throw std::out_of_range("Invalid position");
    }
    if (i == 0) { // 删除头结点
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
    else {
        ListNode* curr = head;
        for (int j = 0; j < i - 1; j++) { // 找到要删除结点的前一个结点
            curr = curr->next;
        }
        ListNode* temp = curr->next; // 要删除的结点存储到temp中
        curr->next = temp->next;     // 把要删除的结点的前驱结点的后继，设置为要删除结点的后继结点
        delete temp;                 // 删除要删除的结点
    }
    size--;
}

// 查找值为value的结点，返回结点本身
ListNode* LinkedList::find(eleType value) {
    ListNode* curr = head;  // 从根结点开始
    while (curr && curr->data != value) {
        curr = curr->next;  // 当前结点变为它的后继
    }
    return curr; // 链表遍历完没找到返回空结点，找到返回data为value的结点
}

// 链表索引
ListNode* LinkedList::get(int i) {
    if (i < 0 || i >= size) {
        throw std::out_of_range("Invalid position");
    }
    ListNode* curr = head;         // 初始化curr，从头结点开始
    for (int j = 0; j < i; ++j) {  // 迭代i次，每次操作变为它的后继
        curr = curr->next;
    }
    return curr;
}

// 链表更新。更新第i个结点的值
void LinkedList::update(int i, eleType value) {
    if (i < 0 || i >= size) {
        throw std::out_of_range("Invalid position");
    }
    get(i)->data = value;
}

// 调试函数
void LinkedList::print() {
    ListNode* curr = head;
    while (curr != NULL) {
        cout << curr->data;
        curr = curr->next; // curr等于他的后继
        if (curr) {
            cout << " ";
        }
        else {
            cout << endl;
        }
    }
}

int main() {
    LinkedList f;
    f.insert(0, 1);
    f.insert(1, 1);
    f.insert(2, 1);
    for (int i = 3; i <= 40; ++i) {
        ListNode* a = f.get(i - 1);
        ListNode* b = f.get(i - 2);
        f.insert(i, a->data + b->data);
    }
    //f.print();
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        cout << f.get(x)->data << endl;
    }

    return 0;
}

#include <iostream>
#include <stdexcept> // 处理异常
using namespace std;

#define eleType int

// 链表结点的结构体
struct ListNode {
    eleType data;   // 数据域
    ListNode *next; // 指针域

    // c++中的struct和class是一样的，可以写构造函数
    ListNode(eleType x): data(x), next(NULL) {}
};

// 实现单向链表的类
class LinkedList {
private:
    ListNode* head; // 头结点
    int size;       // 链表元素个数
public:
    LinkedList(): head(NULL), size(0) {}
    ~LinkedList();
    void insert(int i, eleType value); // i位置插入值为value的元素
    void remove(int i);                // 删除第i个结点
    ListNode* find(eleType value);     // 查找值为value的结点，返回结点本身
    ListNode* get(int i);              // i 索引位置。获取链表的第几个结点
    void update(int i, eleType value); // 更新第i个结点的值
    void print();                      // 打印链表
    eleType sum();                     // 求链表中所有元素的和
    void append(eleType);              // 插入元素到链表的尾部
    void ascInsert(eleType value);     // 按递增顺序进行插入
};

// 任何一个数据结构其实都是增删改查
LinkedList::~LinkedList() {
    // 每个结点的内存空间析构掉
    ListNode* curr = head; // 头结点赋值给current
    while (curr != NULL) {
        ListNode* tmp = curr;
        curr = curr->next;
        delete tmp;
    }
}

void LinkedList::insert(int i, eleType value) {
    if (i <0 || i > size) {
        throw std::out_of_range("Invlid position");
    }
    ListNode* newNode = new ListNode(value);
    if (i == 0) { // 如果是链表头
        newNode->next = head;
        head = newNode;
    }
    else {
        ListNode* curr = head;            // 定义游标结点，从head开始
        for (int j = 0; j < i - 1; j++) { // 确定要插入位置的前一个结点
            curr = curr->next;
        }
        newNode->next = curr->next;
        curr->next = newNode;
    }
    size++;
}

void LinkedList::remove(int i) {
    if (i < 0 || i >= size) {
        throw std::out_of_range("Invalid position");
    }
    if (i == 0) { // 删除头结点
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
    else {
        ListNode* curr = head;
        for (int j = 0; j < i - 1; j++) { // 找到要删除结点的前一个结点
            curr = curr->next;
        }
        ListNode* temp = curr->next; // 要删除的结点存储到temp中
        curr->next = temp->next;     // 把要删除的结点的前驱结点的后继，设置为要删除结点的后继结点
        delete temp;                 // 删除要删除的结点
    }
    size--;
}

// 查找值为value的结点，返回结点本身
ListNode* LinkedList::find(eleType value) {
    ListNode* curr = head;  // 从根结点开始
    while (curr && curr->data != value) {
        curr = curr->next;  // 当前结点变为它的后继
    }
    return curr; // 链表遍历完没找到返回空结点，找到返回data为value的结点
}

// 链表索引
ListNode* LinkedList::get(int i) {
    if (i < 0 || i >= size) {
        throw std::out_of_range("Invalid position");
    }
    ListNode* curr = head;         // 初始化curr，从头结点开始
    for (int j = 0; j < i; ++j) {  // 迭代i次，每次操作变为它的后继
        curr = curr->next;
    }
    return curr;
}

// 链表更新。更新第i个结点的值
void LinkedList::update(int i, eleType value) {
    if (i < 0 || i >= size) {
        throw std::out_of_range("Invalid position");
    }
    get(i)->data = value;
}

// 调试函数
void LinkedList::print() {
    ListNode* curr = head;
    while (curr != NULL) {
        cout << curr->data;
        curr = curr->next; // curr等于他的后继
        if (curr) {
            cout << " ";
        }
        else {
            cout << endl;
        }
    }
}

eleType LinkedList::sum() {
    ListNode* curr = head;
    eleType ret = 0;
    while (curr) {
        ret += curr->data;
        curr = curr->next;
    }
    return ret;
}

void LinkedList::append(eleType v) {
    insert(size, v);
}
void LinkedList::ascInsert(eleType value) {
    if (size = 0) {
        insert(0, value);
        return;
    }
    ListNode* curr = head;
    for (int i = 0; i < size; ++i) {
        if (value <= curr->data) {
            insert(i, value);
            return;
        }
        curr = curr->next;
    }
    insert(size, value);
}


int main() {
    int n, x;
    while (cin >> n >> x) {
        if (!n && !x) {
            break;
        }
        LinkedList l;
        while (n--) {
            int v;
            cin >> v;
            l.append(v);
        }
        l.ascInsert(x);
        l.print();
    }

    return 0;
}

#include <iostream>
#include <stdexcept>

using namespace std;

template<typename T> // 这样栈中的每个元素都可以是自定义的
class Stack {
private:
    // 实现结点的结构体
    struct Node {
        T data;
        Node* next;
        Node(T d) : data(d), next(NULL) {}
    };
    Node* head; // 链表头，也是栈顶元素指针
    int size;   // 栈中元素个数

public:
    Stack() :head(NULL), size(0) {}
    ~Stack();
    void push(T element); // 入栈
    T pop();              // 出栈
    T top() const;         // 获取栈顶
    int getSize() const;  // 栈中元素个数
};

template<typename T>
Stack<T>::~Stack() {
    // 遍历链表，如果发现当前结点不为空时，把栈顶元素取出并存储在temp中
    while (head) {
        Node* temp = head;
        head = head->next; // 删除栈顶元素，但内存还在，需要清理
        delete temp;
    }
}

template<typename T>
void Stack<T>::push(T element) {
    Node* newNode = new Node(element);
    newNode->next = head;
    head = newNode;
    ++size;
}

template<typename T>
T Stack<T>::pop() {
    if (head == NULL) {
        throw std::underflow_error("Stack is empty");
    }
    T result = head->data;
    Node* temp = head;
    head = head->next;
    delete temp;
    --size;
    return result;
}

template<typename T>
T Stack<T>::top() const {
    if (head == NULL) {
        throw std::underflow_error("Stack is empty");
    }
    return head->data;
}

template<typename T>
int Stack<T>::getSize() const {
    return size;
}

int main() {
    int N, x;
    while (cin >> N >> x) {
        if (N == 0) {
            cout << 0 << endl;
            continue;
        }
        if (N < 0) {
            cout << '-';
            N = -N; // 这样，只需要处理N为正数的情况
        }
        Stack<int> stk;
        while (N) {
            stk.push(N % x);
            N /= x;
        }
        while (stk.getSize()) {
            int x = stk.pop();
            if (x > 10) {
                printf("%c", 'A' + x - 10);
            }
            else {
                printf("%d", x);
            }
        }
        cout << endl;
    }

    return 0;
}

#include <iostream>
#include <stdexcept>

using namespace std;

template<typename T> // 这样栈中的每个元素都可以是自定义的
class Stack {
private:
    // 实现结点的结构体
    struct Node {
        T data;
        Node* next;
        Node(T d) : data(d), next(NULL) {}
    };
    Node* head; // 链表头，也是栈顶元素指针
    int size;   // 栈中元素个数

public:
    Stack() :head(NULL), size(0) {}
    ~Stack();
    void push(T element); // 入栈
    T pop();              // 出栈
    T top() const;         // 获取栈顶
    int getSize() const;  // 栈中元素个数
};

template<typename T>
Stack<T>::~Stack() {
    // 遍历链表，如果发现当前结点不为空时，把栈顶元素取出并存储在temp中
    while (head) {
        Node* temp = head;
        head = head->next; // 删除栈顶元素，但内存还在，需要清理
        delete temp;
    }
}

template<typename T>
void Stack<T>::push(T element) {
    Node* newNode = new Node(element);
    newNode->next = head;
    head = newNode;
    ++size;
}

template<typename T>
T Stack<T>::pop() {
    if (head == NULL) {
        throw std::underflow_error("Stack is empty");
    }
    T result = head->data;
    Node* temp = head;
    head = head->next;
    delete temp;
    --size;
    return result;
}

template<typename T>
T Stack<T>::top() const {
    if (head == NULL) {
        throw std::underflow_error("Stack is empty");
    }
    return head->data;
}

template<typename T>
int Stack<T>::getSize() const {
    return size;
}

int main() {
    int n;
    while (cin >> n) {
        Stack<int> stk;
        while (n) {
            stk.push(n % 2);
            n /= 2;
        }
        while (stk.getSize()) {
            cout << stk.pop();
        }
        cout << endl;
    }

    return 0;
}

书店店员有一张链表形式的书单，每个节点代表一本书，节点中的值表示书的编号。
为更方便整理书架，店员需要将书单倒过来排列，就可以从最后一本书开始整理，逐一将书放回到书架上。请倒序返回这个书单链表。

示例 1：
输入：head = [3,6,4,1]
输出：[1,4,6,3]

提示：
0 <= 链表长度 <= 10000

/**
 * 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 {
public:
    vector<int> reverseBookList(ListNode* head) {
        // 其实上是对链表做逆序，存储到顺序表中进行返回。
        // 凡是涉及到逆序，都可以和栈联系起来，因为它是先进后出的；
        // 把链表中的元素放入栈中，利用弹栈的方式将弹出的元素逐次放入顺序列中

        // 1.遍历链表，逐个压栈
        stack<int> stk;
        while(head) {
            stk.push(head->val);
            head = head->next;
        }
        // 2.生成顺序表ans，将栈内元素一个个弹出存入顺序表中
        vector<int> ans;
        while(!stk.empty()){
            ans.push_back(stk.top());
            stk.pop();
        }
        return ans;
    }
};

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

示例 1：
输入: head = [1,2,3,3,2,1]
输出: true

示例 2：
输入: head = [1,2]
输出: false

提示：
链表 L 的长度范围为 [1, 105]
0 <= node.val <= 9

/**
 * 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 {
public:
    bool isPalindrome(ListNode* head) {
        // 如果这个链表逆序后，和原来链表元素一一对应，这个链表必然是个回文链表
        // 可以把链表的元素不断地压入栈，然后弹出栈顶元素和链表元素比较，不相等就不是回文。
        stack<ListNode*> stk;
        ListNode* tmp = head;
        while (tmp) {
            stk.push(tmp);
            tmp = tmp->next;
        }
        while(head){
            if(head->val != stk.top()->val) {
                return false;
            }
            stk.pop();
            head = head->next;
        }
        return true;
    }
};

给定 有效括号字符串 s，返回 s 的 嵌套深度。嵌套深度是嵌套括号的 最大 数量。

示例 1：
输入：s = "(1+(2*3)+((8)/4))+1"
输出：3
解释：数字 8 在嵌套的 3 层括号中。

示例 2：
输入：s = "(1)+((2))+(((3)))"
输出：3
解释：数字 3 在嵌套的 3 层括号中。

示例 3：
输入：s = "()(())((()()))"
输出：3

提示：
1 <= s.length <= 100
s 由数字 0-9 和字符 '+'、'-'、'*'、'/'、'('、')' 组成
题目数据保证括号字符串 s 是 有效的括号字符串

class Solution {
public:
    int maxDepth(string s) {
        // 给定一个带括号的字符串，括号都是匹配的，括号支持嵌套，求嵌套的最深的括号层数？
        // 遍历字符串x，如果遇到左括号入栈，如果遇到右括号就弹出栈顶左括号，这个过程中栈的大小的最大值就是s的嵌套深度

        int ret = 0, top = 0; // top 栈元素个数，ret括号层数
        for(int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') {
                ++top;
                ret = max(ret, top); // 记录最大值到ret中
            }else if (s[i] == ')') {
                --top;
            }
        }
        return ret;

    }
};

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：
输入：s = "()"
输出：true

示例 2：
输入：s = "()[]{}"
输出：true

示例 3：
输入：s = "(]"
输出：false

示例 4：
输入：s = "([])"
输出：true

示例 5：
输入：s = "([)]"
输出：false

提示：
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

class Solution {
    bool isLeft(char c) {
        return c == '(' || c == '[' || c == '{';
    }

    bool isMatch(char l, char r) {
        return l == '(' && r == ')' ||
        l == '[' && r == ']' ||
        l == '{' && r == '}';
    }
public:
    bool isValid(string s) {
        // 所有的左括号都有右括号闭合
        stack<char> stk;
        for (int i = 0; i < s.size(); ++i) {
            if (isLeft(s[i])) {
                stk.push(s[i]);
            }else {
                // 如果栈中没有元素，必然缺少和它匹配的左括号，直接返回false
                if (stk.empty()) { 
                    return false;
                }
                // 和右括号匹配，不能匹配返回false
                if (!isMatch(stk.top(), s[i])) {
                    return false;
                }
                stk.pop();
            }
        }
        return stk.empty(); // 栈为空时才算匹配完毕
    }
};

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，
其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。


示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        // 对于栈用vector来模拟
        vector<int> stk;
        vector<int> ans;
        // 如果所有数字都单调递减，那么可以先把ans所有元素初始化为0
        for(int i = 0; i < temperatures.size(); ++i) {
            ans.push_back(0);
        }
        for(int i = 0; i < temperatures.size(); ++i) {
            if(stk.size() == 0) {
                stk.push_back(i);  // 如果栈大小为0，把下标压入栈中
            }else {
                // 如果栈顶有元素，存储的是温度下标; 如果温度值小于当前温度, 说明下一个更高的温度就是i
                while(stk.size() && temperatures[ stk.back() ] < temperatures[i]) {
                    ans[stk.back()] = i - stk.back();
                    stk.pop_back();
                }
                stk.push_back(i); 
            }
        }
        return ans;

    }
};

/*
对于任意一个数，向右找第1个比它大的数，向右找几位
1 2 3 4 5
1 1 1 1 0

9 8 7 6 5
0 0 0 0 0
*/

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        // 对于栈用vector来模拟
        vector<int> stk;
        vector<int> ans;
        // 如果所有数字都单调递减，那么可以先把ans所有元素初始化为0
        for(int i = 0; i < temperatures.size(); ++i) {
            ans.push_back(0);
        }
        for(int i = 0; i < temperatures.size(); ++i) {
            // 如果栈顶有元素，存储的是温度下标; 如果温度值小于当前温度, 说明下一个更高的温度就是i
            while(stk.size() && temperatures[ stk.back() ] < temperatures[i]) {
                ans[stk.back()] = i - stk.back();
                stk.pop_back();
            }  
            stk.push_back(i); 
        }
        return ans;    
    }
};

/*
对于任意一个数，向右找第1个比它大的数，向右找几位
1 2 3 4 5
1 1 1 1 0

9 8 7 6 5
0 0 0 0 0
*/

给你一个链表的头节点 head 。

移除每个右侧有一个更大数值的节点。

返回修改后链表的头节点 head 。

示例 1：
输入：head = [5,2,13,3,8]
输出：[13,8]
解释：需要移除的节点是 5 ，2 和 3 。
- 节点 13 在节点 5 右侧。
- 节点 13 在节点 2 右侧。
- 节点 8 在节点 3 右侧。

示例 2：
输入：head = [1,1,1,1]
输出：[1,1,1,1]
解释：每个节点的值都是 1 ，所以没有需要移除的节点。

提示：
给定列表中的节点数目在范围 [1, 105] 内
1 <= Node.val <= 105

/**
 * 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 {
public:
    ListNode* removeNodes(ListNode* head) {
        // 递归(深搜)就是和栈联系起来的; 广搜和队列联系起来
        // 用vector数组来模拟栈
        vector<ListNode*> stk;
        ListNode* dummy = new ListNode(100000, head); // 定义虚拟头结点
        ListNode* now = head;                         // 定义游标结点，从head开始
        // 每次把栈顶元素和当前遍历到的这个链表结点比较，如果小于，把栈顶元素给pop出来
        stk.push_back(dummy);
        while(now) {
            while(stk.back()->val < now->val) { // 单调不增的栈
                stk.pop_back();
            }
            stk.push_back(now);
            now = now->next;
        }
        for(int i = 0; i < stk.size(); ++i) {
            stk[i]->next = stk[i+1];
        }
        stk.back()->next = NULL;
        return dummy->next;
    }
};

#include <iostream>
#include <stdexcept>
using namespace std;

// 实现队列的类
template<typename T> // 用模板的方式，这样每个元素都是自定义的
class Queue {
private:
    struct Node {
        T data;     // 数据域
        Node* next; // 指针域
        Node(T d) : data(d), next(NULL) {} // 结点的构造
    };
    Node* front;  // 队首指针
    Node* rear;   // 队尾指针
    int size;     // 队列中元素个数
public:
    Queue() : front(NULL), rear(NULL), size(0) {}
    ~Queue();
    void enqueue(T element); // 入队
    T dequeue();             // 出队
    T getFront() const;      // 获取队首元素
    int getSize() const;     // 获取队列的元素个数
};

template<typename T> // 代表每个函数都有这个类型
Queue<T>::~Queue() {
    // 从头开始遍历整个链表，获取到当前的头，然后把链表头删除
    while (front) {
        Node* temp = front;
        front = front->next;
        delete temp;
    }
}

template<typename T>
void Queue<T>::enqueue(T element) {
    if (rear == NULL) {
        rear = new Node(element);
        front = rear;
    }
    else {
        rear->next = new Node(element);
        rear = rear->next;  // 新加进来的结点作为队尾指针
    }
    ++size;
}

template<typename T>
T Queue<T>::dequeue() {
    if (front == NULL) { // 空队列，抛异常
        throw std::underflow_error("Queue is empty");
    }
    // 获取队首元素，并且把队首指针存储到temp中,删除队首结点，返回element，即出队完成
    T element = front->data;
    Node* temp = front;
    front = front->next;
    delete temp;
    --size;
    if (size == 0) {
        rear = NULL;  // 当队列为空时，把rear指针置为NULL。如果不这样，rear就变成野指针了，在下次入队时会报错
    }
    return element;
}

template<typename T>
T Queue<T>::getFront() const {
    if (front == NULL) { // 空队列，抛异常
        throw std::underflow_error("Queue is empty");
    }
    return front->data;
}

template<typename T>
int Queue<T>::getSize() const {
    return size;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        Queue<int> q1, q2;
        // 将元素插入q1中
        for (int i = 1; i <= n; ++i) {
            q1.enqueue(i);
        }
        while (q1.getSize() > 3) {
            int cnt = 0;
            while (q1.getSize()) {
                int v = q1.dequeue();
                ++cnt;
                if (cnt % 2 == 1) {
                    q2.enqueue(v);
                }
            }
            if (q2.getSize() <= 3) {
                while (q2.getSize()) q1.enqueue(q2.dequeue());
                break;
            }
            cnt = 0;
            while (q2.getSize()) {
                int v = q2.dequeue();
                ++cnt;
                if (cnt % 3 == 1 || cnt % 3 == 2) {
                    q1.enqueue(v);
                }
            }
        }
        int flag = 0;
        while (q1.getSize()) {
            if (flag) {
                cout << ' ';
            }
            cout << q1.dequeue();
            flag++;
        }
        cout << endl;
    }

    return 0;
}

#include <iostream>
#include <string>
#include <cstring>
#include <stdexcept>
using namespace std;

// 实现队列的类
template<typename T> // 用模板的方式，这样每个元素都是自定义的
class Queue {
private:
    struct Node {
        T data;     // 数据域
        Node* next; // 指针域
        Node(T d) : data(d), next(NULL) {} // 结点的构造
    };
    Node* front;  // 队首指针
    Node* rear;   // 队尾指针
    int size;     // 队列中元素个数
public:
    Queue() : front(NULL), rear(NULL), size(0) {}
    ~Queue();
    void enqueue(T element); // 入队
    T dequeue();             // 出队
    T getFront() const;      // 获取队首元素
    int getSize() const;     // 获取队列的元素个数
};

template<typename T> // 代表每个函数都有这个类型
Queue<T>::~Queue() {
    // 从头开始遍历整个链表，获取到当前的头，然后把链表头删除
    while (front) {
        Node* temp = front;
        front = front->next;
        delete temp;
    }
}

template<typename T>
void Queue<T>::enqueue(T element) {
    if (rear == NULL) {
        rear = new Node(element);
        front = rear;
    }
    else {
        rear->next = new Node(element);
        rear = rear->next;  // 新加进来的结点作为队尾指针
    }
    ++size;
}

template<typename T>
T Queue<T>::dequeue() {
    if (front == NULL) { // 空队列，抛异常
        throw std::underflow_error("Queue is empty");
    }
    // 获取队首元素，并且把队首指针存储到temp中,删除队首结点，返回element，即出队完成
    T element = front->data;
    Node* temp = front;
    front = front->next;
    delete temp;
    --size;
    if (size == 0) {
        rear = NULL;  // 当队列为空时，把rear指针置为NULL。如果不这样，rear就变成野指针了，在下次入队时会报错
    }
    return element;
}

template<typename T>
T Queue<T>::getFront() const {
    if (front == NULL) { // 空队列，抛异常
        throw std::underflow_error("Queue is empty");
    }
    return front->data;
}

template<typename T>
int Queue<T>::getSize() const {
    return size;
}

int team[1000000]; // 存放每个人的队伍
int main() {
    // 有一个队列，如果发现队列里有一个人和我的队伍是在同一个队里，我就排在他的后面。
    // 如果在这个队列中没找到，则排在整个队列的后面。
    // 第一维代表先插入的人；第二维代表同一个队列里的不同的人并且按先后时间顺序
    // 出队就是第一维的那个队列里的元素出队。
    // 每个人都有编号，0~99999
    int t; // t 个队伍
    int cases = 0;
    while (cin >> t && t) {
        ++cases;
        // 1.队伍数据
        memset(team, 0, sizeof(team)); // 初始化team
        for (int i = 1; i <= t; ++i) {
            int n;
            cin >> n;
            while (n--) { // 表示每个队伍有多少人
                int x; // x 表示编号
                cin >> x;
                team[x] = i;
            }
        }
        // 2.入队出队操作
        Queue<int> q[1001];
        int s = 0, e = 0; // start end
        string str;
        cout << "Scenario #" << cases << endl;
        while (cin >> str) {
            if (str == "STOP") break;
            if (str == "ENQUEUE") {
                int x, i;
                cin >> x;
                for (i = s; i < e; ++i) {
                    if (team[q[i].getFront()] == team[x]) { // 说明有个队友在第i个队伍里
                        break;
                    }
                }
                q[i].enqueue(x);
                if (i == e) { // 表示队列不存在
                    ++e;
                }
            }
            else {
                int val = q[s].dequeue();
                if (q[s].getSize() == 0) {
                    ++s;
                }
                cout << val << endl;
            }
        }
        cout << endl;

    }
    return 0;
}

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请你实现 RecentCounter 类：

RecentCounter() 初始化计数器，请求数为 0 。
int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。

示例 1：
输入：
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
输出：
[null, 1, 2, 3, 3]

解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1]，范围是 [-2999,1]，返回 1
recentCounter.ping(100);   // requests = [1, 100]，范围是 [-2900,100]，返回 2
recentCounter.ping(3001);  // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3

提示：
1 <= t <= 109
保证每次对 ping 调用所使用的 t 值都 严格递增
至多调用 ping 方法 104 次

class RecentCounter {
    queue<int> q;
public:
    RecentCounter() {

    }

    int ping(int t) {
        q.push(t);
        while(t - q.front() > 3000 ) { // 队尾元素减队首元素超过3000毫秒，就清理队首元素
            q.pop();
        }
        return q.size();
    }
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */

#include <iostream>

using namespace std;

int main() {
    char s[500];
    int n;
    cin >> n;
    getchar(); // 把回车给吃掉
    while (n--) {
        fgets(s, 500, stdin);
        int cnt = 0;
        int len = strlen(s);
        for (int i = 0; i < len; ++i) {
            // 对于汉字，补码最高位是1
            if (s[i] < 0) {
                ++cnt;
            }
        }
        cout << cnt / 2 << endl;
    }
    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    // 判断当前位置不是空格并且前一个位置是空格，或者前一个位置是-1，就把当前字母变大写
    // AScii码的转换
    char s[110];
    while (fgets(s, 110, stdin)) {
        int len = strlen(s);
        for (int i = 0; i < len; ++i) {
            if (i == 0 || s[i - 1] == ' ') {
                if (s[i] != ' ') {
                    if (s[i] >= 'a' && s[i] <= 'z') { // 是否是小写字母，是则小写转大写
                        s[i] -= 'a';
                        s[i] += 'A';
                    }
                }
            }
        }
        printf("%s\n", s);
    }

    return 0;
}

#include <iostream>
#include <string>
using namespace std;

int main() {
    // 找到最大字符，可以利用枚举
    string s;
    while (cin >> s) {
        string ret = "";
        char maxc = 'a';
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] > maxc) {
                maxc = s[i];
            }
        }
        for (int i = 0; i < s.size(); ++i) {
            ret = ret + s[i];        // 字符串的连接
            if (s[i] == maxc) {
                ret = ret + "(max)"; // 字符串的连接
            }
        }
        cout << ret << endl;
    }

    return 0;
}

给你一个坐标 coordinates ，它是一个字符串，表示国际象棋棋盘中一个格子的坐标。下图是国际象棋棋盘示意图。

如果所给格子的颜色是白色，请你返回 true，如果是黑色，请返回 false 。

给定坐标一定代表国际象棋棋盘上一个存在的格子。坐标第一个字符是字母，第二个字符是数字。


示例 1：
输入：coordinates = "a1"
输出：false
解释：如上图棋盘所示，"a1" 坐标的格子是黑色的，所以返回 false 。

示例 2：
输入：coordinates = "h3"
输出：true
解释：如上图棋盘所示，"h3" 坐标的格子是白色的，所以返回 true 。

示例 3：
输入：coordinates = "c7"
输出：false

提示：
coordinates.length == 2
'a' <= coordinates[0] <= 'h'
'1' <= coordinates[1] <= '8'

class Solution {
public:
    bool squareIsWhite(string coordinates) {
        // a b c d e f g h 是横坐标，12345678是纵坐标
        // 把abcdefgh变成01234567; 12345678变成01234567
        int x = coordinates[0] - 'a';
        int y = coordinates[1] - '1';
        // x + y 是奇数时，是白色
        return (x + y) % 2 == 1;
    }
};

假定一段路径记作字符串 path，其中以 "." 作为分隔符。现需将路径加密，
加密方法为将 path 中的分隔符替换为空格 " "，请返回加密后的字符串。

示例 1：
输入：path = "a.aef.qerf.bb"
输出："a aef qerf bb"

限制：
0 <= path.length <= 10000

class Solution {
public:
    string pathEncryption(string path) {
        int len = path.size();
        for (int i = 0; i <len; ++i) {
            if(path[i] == '.') {
                path[i] = ' ';
            }
        }
        return path;
    }
};

如果一个字符串不含有任何重复字符，我们称这个字符串为 好 字符串。

给你一个字符串 s ，请你返回 s 中长度为 3 的 好子字符串 的数量。

注意，如果相同的好子字符串出现多次，每一次都应该被记入答案之中。

子字符串 是一个字符串中连续的字符序列。

示例 1：
输入：s = "xyzzaz"
输出：1
解释：总共有 4 个长度为 3 的子字符串："xyz"，"yzz"，"zza" 和 "zaz" 。
唯一的长度为 3 的好子字符串是 "xyz" 。

示例 2：
输入：s = "aababcabc"
输出：4
解释：总共有 7 个长度为 3 的子字符串："aab"，"aba"，"bab"，"abc"，"bca"，"cab" 和 "abc" 。
好子字符串包括 "abc"，"bca"，"cab" 和 "abc" 。

提示：
1 <= s.length <= 100
s 只包含小写英文字母。

class Solution {
public:
    int countGoodSubstrings(string s) {
        int cnt = 0;
        int len = s.size();
        for (int i = 0; i < len - 2; ++i) {
            int a = s[i];
            int b = s[i + 1];
            int c = s[i + 2];
            if(a != b && b != c & a != c) {
                ++cnt;
            }
        }
        return cnt;
    }
};

小扣在秋日市集发现了一款速算机器人。店家对机器人说出两个数字（记作 x 和 y），请小扣说出计算指令：

"A" 运算：使 x = 2 * x + y；
"B" 运算：使 y = 2 * y + x。
在本次游戏中，店家说出的数字为 x = 1 和 y = 0，小扣说出的计算指令记作仅由大写字母 A、B 组成的字符串 s，字符串中字符的顺序表示计算顺序，请返回最终 x 与 y 的和为多少。

示例 1：
输入：s = "AB"

输出：4
解释： 经过一次 A 运算后，x = 2, y = 0。 再经过一次 B 运算，x = 2, y = 2。 最终 x 与 y 之和为 4。

提示：
0 <= s.length <= 10
s 由 'A' 和 'B' 组成

class Solution {
public:
    int calculate(string s) {
        int x = 1, y = 0;
        int len = s.size();
        for(int i = 0; i < len; ++i) {
            if(s[i] == 'A'){
                x = 2 * x + y;
            } else {
                y = 2 * y + x;
            }
        }
        return x + y;
    }
};

存在一种仅支持 4 种操作和 1 个变量 X 的编程语言：

++X 和 X++ 使变量 X 的值 加 1
--X 和 X-- 使变量 X 的值 减 1
最初，X 的值是 0

给你一个字符串数组 operations ，这是由操作组成的一个列表，返回执行所有操作后， X 的 最终值 。

示例 1：
输入：operations = ["--X","X++","X++"]
输出：1
解释：操作按下述步骤执行：
最初，X = 0
--X：X 减 1 ，X =  0 - 1 = -1
X++：X 加 1 ，X = -1 + 1 =  0
X++：X 加 1 ，X =  0 + 1 =  1

示例 2：
输入：operations = ["++X","++X","X++"]
输出：3
解释：操作按下述步骤执行： 
最初，X = 0
++X：X 加 1 ，X = 0 + 1 = 1
++X：X 加 1 ，X = 1 + 1 = 2
X++：X 加 1 ，X = 2 + 1 = 3

示例 3：
输入：operations = ["X++","++X","--X","X--"]
输出：0
解释：操作按下述步骤执行：
最初，X = 0
X++：X 加 1 ，X = 0 + 1 = 1
++X：X 加 1 ，X = 1 + 1 = 2
--X：X 减 1 ，X = 2 - 1 = 1
X--：X 减 1 ，X = 1 - 1 = 0


提示：
1 <= operations.length <= 100
operations[i] 将会是 "++X"、"X++"、"--X" 或 "X--"

class Solution {
public:
    int finalValueAfterOperations(vector<string>& operations) {
        int X = 0;
        for(int i = 0; i < operations.size(); ++i) {
            string s = operations[i];
            // 判断s的第一个位置是加号还是减号
            if(s[1] == '+') {
                X++;
            }else {
                X--;
            }
        }
        return X;
    }
};

给你一个有效的 IPv4 地址 address，返回这个 IP 地址的无效化版本。

所谓无效化 IP 地址，其实就是用 "[.]" 代替了每个 "."。

示例 1：
输入：address = "1.1.1.1"
输出："1[.]1[.]1[.]1"

示例 2：
输入：address = "255.100.50.0"
输出："255[.]100[.]50[.]0"

提示：
给出的 address 是一个有效的 IPv4 地址

class Solution {
public:
    string defangIPaddr(string address) {
        // 遇到.点变为[.]
        string s = "";
        for(int i = 0; i < address.size(); ++i) {
            if(address[i] == '.') {
                s = s + "[.]";
            }else {
                s += address[i];
            }
        }
        return s;
    }
};

给你一个字符串 s ，每 两个 连续竖线 '|' 为 一对 。
换言之，第一个和第二个 '|' 为一对，第三个和第四个 '|' 为一对，以此类推。

请你返回 不在 竖线对之间，s 中 '*' 的数目。

注意，每个竖线 '|' 都会 恰好 属于一个对。

示例 1：
输入：s = "l|*e*et|c**o|*de|"
输出：2
解释：不在竖线对之间的字符加粗加斜体后，得到字符串："l|*e*et|c**o|*de|" 。
第一和第二条竖线 '|' 之间的字符不计入答案。
同时，第三条和第四条竖线 '|' 之间的字符也不计入答案。
不在竖线对之间总共有 2 个星号，所以我们返回 2 。

示例 2：
输入：s = "iamprogrammer"
输出：0
解释：在这个例子中，s 中没有星号。所以返回 0 。

示例 3：
输入：s = "yo|uar|e**|b|e***au|tifu|l"
输出：5
解释：需要考虑的字符加粗加斜体后："yo|uar|e**|b|e***au|tifu|l" 。不在竖线对之间总共有 5 个星号。所以我们返回 5 。


提示：
1 <= s.length <= 1000
s 只包含小写英文字母，竖线 '|' 和星号 '*' 。
s 包含 偶数 个竖线 '|' 。

class Solution {
public:
    int countAsterisks(string s) {
        // 遍历字符串对|进行入栈和出栈，可以用+-来表示。或者一直加再判断奇偶性
        int sh = 0; // 表示竖线出现奇数次还是偶数次
        int ret = 0;
        for (int i = 0; i < s.size(); ++i) {
            if(s[i] == '|') {
                sh = sh + 1;
            }else if(s[i] == '*') {
                if(sh % 2 == 0) { // 偶数时，星号加进来
                    ret++;
                }
            }
        }
        return ret;
    }
};

平衡字符串 中，'L' 和 'R' 字符的数量是相同的。

给你一个平衡字符串 s，请你将它分割成尽可能多的子字符串，并满足：

每个子字符串都是平衡字符串。
返回可以通过分割得到的平衡字符串的 最大数量 。

示例 1：
输入：s = "RLRRLLRLRL"
输出：4
解释：s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。

示例 2：
输入：s = "RLRRRLLRLL"
输出：2
解释：s 可以分割为 "RL"、"RRRLLRLL"，每个子字符串中都包含相同数量的 'L' 和 'R' 。
注意，s 无法分割为 "RL"、"RR"、"RL"、"LR"、"LL" 因为第 2 个和第 5 个子字符串不是平衡字符串。

示例 3：
输入：s = "LLLLRRRR"
输出：1
解释：s 只能保持原样 "LLLLRRRR" 。

提示：
2 <= s.length <= 1000
s[i] = 'L' 或 'R'
s 是一个 平衡 字符串

class Solution {
public:
    int balancedStringSplit(string s) {
        // 贪心思路
        // 遇到L计数器加1，遇到R计数器减1
        // 当计数器为0时，说明前面遍历的部分，L和R的数量是相等的，这时分割
        int cnt = 0;  // 计数器，表示L和R数量的差值
        int ret = 0;
        for(int i = 0; i < s.size(); ++i) {
            if (s[i] == 'L'){
                ++cnt;
            }else if (s[i] == 'R') {
                --cnt;
            }
            if(cnt == 0) {
                ++ret;
            }
        }
        return ret;
    }
};

某公司门禁密码使用动态口令技术。初始密码为字符串 password，密码更新均遵循以下步骤：

设定一个正整数目标值 target
将 password 前 target 个字符按原顺序移动至字符串末尾
请返回更新后的密码字符串。

示例 1：
输入: password = "s3cur1tyC0d3", target = 4
输出: "r1tyC0d3s3cu"

示例 2：
输入: password = "lrloseumgh", target = 6
输出: "umghlrlose"

提示：
1 <= target < password.length <= 10000

class Solution {
public:
    string dynamicPassword(string password, int target) {
        // 把字符串password想象成一个环. 循环可以用取模解决
        string ret;
        int n = password.size();
        for (int i = 0; i < n; ++i){
            ret = ret + password[(i + target) % n];
        }
        return ret;
    }
};

// 12345 将1个字符移动到末尾23451
// 将2个字符移动到末尾34512
// 45123
// 51234
// 12345

请你设计一个可以解释字符串 command 的 Goal 解析器 。command 由 "G"、"()" 和/或 "(al)" 按某种顺序组成。
Goal 解析器会将 "G" 解释为字符串 "G"、"()" 解释为字符串 "o" ，
"(al)" 解释为字符串 "al" 。然后，按原顺序将经解释得到的字符串连接成一个字符串。

给你字符串 command ，返回 Goal 解析器 对 command 的解释结果。


示例 1：
输入：command = "G()(al)"
输出："Goal"
解释：Goal 解析器解释命令的步骤如下所示：
G -> G
() -> o
(al) -> al
最后连接得到的结果是 "Goal"

示例 2：
输入：command = "G()()()()(al)"
输出："Gooooal"

示例 3：
输入：command = "(al)G(al)()()G"
输出："alGalooG"

提示：
1 <= command.length <= 100
command 由 "G"、"()" 和/或 "(al)" 按某种顺序组成

class Solution {
public:
    string interpret(string command) {
        string ret;
        for(int i = 0; i < command.size(); ++i) {
            if (command[i] == 'G') {
                ret = ret + 'G';
            }else if ( command[i] == '(' ) {
                if ( command[i+1] == ')' ) {
                    ret = ret + 'o';
                    i++;
                }else {
                    ret = ret + "al";
                    i += 3;
                }
            }else {
                ret = ret + '/';
            }
        }
        return ret;
    }
};

一个 句子 由一些 单词 以及它们之间的单个空格组成，句子的开头和结尾不会有多余空格。

给你一个字符串数组 sentences ，其中 sentences[i] 表示单个 句子 。

请你返回单个句子里 单词的最多数目 。

示例 1：
输入：sentences = ["alice and bob love leetcode", "i think so too", "this is great thanks very much"]
输出：6
解释：
- 第一个句子 "alice and bob love leetcode" 总共有 5 个单词。
- 第二个句子 "i think so too" 总共有 4 个单词。
- 第三个句子 "this is great thanks very much" 总共有 6 个单词。
所以，单个句子中有最多单词数的是第三个句子，总共有 6 个单词。

示例 2：
输入：sentences = ["please wait", "continue to fight", "continue to win"]
输出：3
解释：可能有多个句子有相同单词数。
这个例子中，第二个句子和第三个句子（加粗斜体）有相同数目的单词数。

提示：
1 <= sentences.length <= 100
1 <= sentences[i].length <= 100
sentences[i] 只包含小写英文字母和 ' ' 。
sentences[i] 的开头和结尾都没有空格。
sentences[i] 中所有单词由单个空格隔开。

class Solution {
public:
    int mostWordsFound(vector<string>& sentences) {
        // 句子的开头和结尾不会有多余空格。只要统计空格数就可以了，空格数是n，单词数n+1
        int ret = 0;
        for(int i = 0; i < sentences.size(); ++i) {
            int k = 1;
            for(int j = 0; j < sentences[i].size(); ++j) {
                if(sentences[i][j] == ' ') {
                    ++k;
                }
            }
            ret = max(ret, k);
        }
        return ret;
    }
};

给你一个由不同字符组成的字符串 allowed 和一个字符串数组 words 。
如果一个字符串的每一个字符都在 allowed 中，就称这个字符串是 一致字符串 。

请你返回 words 数组中 一致字符串 的数目。

示例 1：
输入：allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
输出：2
解释：字符串 "aaab" 和 "baa" 都是一致字符串，因为它们只包含字符 'a' 和 'b' 。

示例 2：
输入：allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
输出：7
解释：所有字符串都是一致的。

示例 3：
输入：allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]
输出：4
解释：字符串 "cc"，"acd"，"ac" 和 "d" 是一致字符串。

提示：
1 <= words.length <= 104
1 <= allowed.length <= 26
1 <= words[i].length <= 10
allowed 中的字符 互不相同 。
words[i] 和 allowed 只包含小写英文字母。

class Solution {
public:
    int countConsistentStrings(string allowed, vector<string>& words) {
        // 标记allowed
        int has[256] = {0};
        for(int i = 0; i < allowed.size(); ++i) {
            has[allowed[i]] = 1;
        }

        int sum = 0;
        for(int i = 0; i < words.size(); ++i) {
            bool bfind = true;
            for(int j = 0; j < words[i].size(); ++j) {
                char c = words[i][j];
                if(has[c] == 0) { // 如果没有出现过
                    bfind = false;
                    break;
                }
            }
            if(bfind) { // 说明allowed都在words[i]中
                ++sum;
            }
        }
        return sum;
    }
};

给你一个字符串 s 。一个字符串的 分数 定义为相邻字符 ASCII 码差值绝对值的和。

请你返回 s 的 分数 。

示例 1：
输入：s = "hello"
输出：13
解释：
s 中字符的 ASCII 码分别为：'h' = 104 ，'e' = 101 ，'l' = 108 ，'o' = 111 。
所以 s 的分数为 |104 - 101| + |101 - 108| + |108 - 108| + |108 - 111| = 3 + 7 + 0 + 3 = 13 。

示例 2：
输入：s = "zaz"
输出：50
解释：
s 中字符的 ASCII 码分别为：'z' = 122 ，'a' = 97 。
所以 s 的分数为 |122 - 97| + |97 - 122| = 25 + 25 = 50 。


提示：
2 <= s.length <= 100
s 只包含小写英文字母。

class Solution {
public:
    int scoreOfString(string s) {
        int ans = 0;
        for(int i = 1; i <s.size(); ++i){
            ans += abs(s[i] - s[i-1]); 
        }
        return ans;
    }
};

TinyURL 是一种 URL 简化服务， 比如：当你输入一个 URL https://leetcode.com/problems/design-tinyurl 时，
它将返回一个简化的URL http://tinyurl.com/4e9iAk 。请你设计一个类来加密与解密 TinyURL 。

加密和解密算法如何设计和运作是没有限制的，你只需要保证一个 URL 可以被加密成一个 TinyURL ，
并且这个 TinyURL 可以用解密方法恢复成原本的 URL 。

实现 Solution 类：
Solution() 初始化 TinyURL 系统对象。
String encode(String longUrl) 返回 longUrl 对应的 TinyURL 。
String decode(String shortUrl) 返回 shortUrl 原本的 URL 。题目数据保证给定的 shortUrl 是由同一个系统对象加密的。


示例：
输入：url = "https://leetcode.com/problems/design-tinyurl"
输出："https://leetcode.com/problems/design-tinyurl"
解释：
Solution obj = new Solution();
string tiny = obj.encode(url); // 返回加密后得到的 TinyURL 。
string ans = obj.decode(tiny); // 返回解密后得到的原本的 URL 。


提示：
1 <= url.length <= 104
题目数据保证 url 是一个有效的 URL

class Solution {
public:

    // Encodes a URL to a shortened URL.
    string encode(string longUrl) {
        // 异或
        for(int i = 0; i < longUrl.size(); ++i) {
            longUrl[i] ^= 5201314;
        }
        return longUrl;
    }

    // Decodes a shortened URL to its original URL.
    string decode(string shortUrl) {
        for(int i = 0; i < shortUrl.size(); ++i) {
            shortUrl[i] ^= 5201314;
        }
        return shortUrl;
    }
};

// Your Solution object will be instantiated and called as such:
// Solution solution;
// solution.decode(solution.encode(url));

给你一个下标从 0 开始的字符串数组 words 和一个字符 x 。

请你返回一个 下标数组 ，表示下标在数组中对应的单词包含字符 x 。

注意 ，返回的数组可以是 任意 顺序。

示例 1：
输入：words = ["leet","code"], x = "e"
输出：[0,1]
解释："e" 在两个单词中都出现了："leet" 和 "code" 。所以我们返回下标 0 和 1 。

示例 2：
输入：words = ["abc","bcd","aaaa","cbc"], x = "a"
输出：[0,2]
解释："a" 在 "abc" 和 "aaaa" 中出现了，所以我们返回下标 0 和 2 。

示例 3：
输入：words = ["abc","bcd","aaaa","cbc"], x = "z"
输出：[]
解释："z" 没有在任何单词中出现。所以我们返回空数组。


提示：
1 <= words.length <= 50
1 <= words[i].length <= 50
x 是一个小写英文字母。
words[i] 只包含小写英文字母。

class Solution {
public:
    vector<int> findWordsContaining(vector<string>& words, char x) {
        vector<int> ans;
        for(int i = 0; i < words.size(); ++i) {
            for(int j = 0; j < words[i].size(); ++j) {
                if(words[i][j] == x) {
                    ans.push_back(i);
                    break;
                }
            }
        }
        return ans;
    }
};

给你一个字符串数组 words 和一个字符串 s ，请你判断 s 是不是 words 的 首字母缩略词 。

如果可以按顺序串联 words 中每个字符串的第一个字符形成字符串 s ，则认为 s 是 words 的首字母缩略词。
例如，"ab" 可以由 ["apple", "banana"] 形成，但是无法从 ["bear", "aardvark"] 形成。

如果 s 是 words 的首字母缩略词，返回 true ；否则，返回 false 。


示例 1：
输入：words = ["alice","bob","charlie"], s = "abc"
输出：true
解释：words 中 "alice"、"bob" 和 "charlie" 的第一个字符分别是 'a'、'b' 和 'c'。
因此，s = "abc" 是首字母缩略词。 

示例 2：
输入：words = ["an","apple"], s = "a"
输出：false
解释：words 中 "an" 和 "apple" 的第一个字符分别是 'a' 和 'a'。
串联这些字符形成的首字母缩略词是 "aa" 。
因此，s = "a" 不是首字母缩略词。

示例 3：
输入：words = ["never","gonna","give","up","on","you"], s = "ngguoy"
输出：true
解释：串联数组 words 中每个字符串的第一个字符，得到字符串 "ngguoy" 。
因此，s = "ngguoy" 是首字母缩略词。 

提示：
1 <= words.length <= 100
1 <= words[i].length <= 10
1 <= s.length <= 100
words[i] 和 s 由小写英文字母组成

class Solution {
public:
    bool isAcronym(vector<string>& words, string s) {
       string t  = "";
       for(int i = 0; i <words.size(); ++i) {
        t += words[i][0];
       }
       return t == s;
    }
};

给你一个包含若干星号 * 的字符串 s 。

在一步操作中，你可以：

选中 s 中的一个星号。
移除星号 左侧 最近的那个 非星号 字符，并移除该星号自身。
返回移除 所有 星号之后的字符串。

注意：
生成的输入保证总是可以执行题面中描述的操作。
可以证明结果字符串是唯一的。

示例 1：
输入：s = "leet**cod*e"
输出："lecoe"
解释：从左到右执行移除操作：
- 距离第 1 个星号最近的字符是 "leet**cod*e" 中的 't' ，s 变为 "lee*cod*e" 。
- 距离第 2 个星号最近的字符是 "lee*cod*e" 中的 'e' ，s 变为 "lecod*e" 。
- 距离第 3 个星号最近的字符是 "lecod*e" 中的 'd' ，s 变为 "lecoe" 。
不存在其他星号，返回 "lecoe" 。

示例 2：
输入：s = "erase*****"
输出：""
解释：整个字符串都会被移除，所以返回空字符串。


提示：
1 <= s.length <= 105
s 由小写英文字母和星号 * 组成
s 可以执行上述操作

class Solution {
public:
    string removeStars(string s) {
        // 经典的栈。回溯就要想到递归，递归就要想到栈
        string t = "";
        for(int i = 0; i < s.size(); ++i) {
            if(s[i] == '*'){
                t.pop_back(); // string中pop_back 将最后一个字符清掉
            }else {
                t += s[i];
            }
        }
        return t;
    }
}

给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 s 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。


示例：
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，
这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，
其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：
1 <= s.length <= 105
s 仅由小写英文字母组成。

class Solution {
public:
    string removeDuplicates(string s) {
        string t = "";
        for(int i = 0; i < s.size(); ++i) {
            if(t.size() > 0 && t.back() == s[i]) { // 如果t的最后一个字符和s[i]相等，则一直删除
                t.pop_back();
            } else {
                t += s[i];
            }
        }
        return t;
    }
};