【有书共读】《算法与数据结构题目最优解》（在线编程题总结1）

#include <iostream>
#include <vector>
#include <exception> 
using namespace std;
// 分类 ------------ 内部比较排序
// 数据结构 --------- 向量
// 最差时间复杂度 ---- 每次选取的基准都是最大（或最小）的元素，导致每次只划分出了一个分区，需要进行n-1次划分才能结束递归，时间复杂度为O(n^2)
// 最优时间复杂度 ---- 每次选取的基准都是中位数，这样每次都均匀的划分出两个分区，只需要logn次划分就能结束递归，时间复杂度为O(nlogn)
// 平均时间复杂度 ---- O(nlogn)
// 所需辅助空间 ------ 主要是递归造成的栈空间的使用(用来保存left和right等局部变量)，取决于递归树的深度，一般为O(logn)，最差为O(n)       
// 稳定性 ---------- 不稳定
 
void Swap(vector<int>& data, int i, int j)
{
    int temp = data[i];
    data[i] = data[j];
    data[j] = temp;
}
 
int RandomInRange(int min, int max)   //在min~max中随机生成一个值  
{
    int random = rand() % (max - min + 1) + min;
    return random;
}
 
int Partition(vector<int>& data, int start, int end) //Partition函数
{
    if (data.size() <= 0 || start < 0 || end >= data.size()) 
        throw new std::exception("Invalid Parameters");
 
    //int index = RandomInRange(start, end); //可以不调用RandomInRange函数
    //Swap(data, index, end);
 
    int small = start - 1;
    for (int index = start; index < end; ++index)
    {
        if (data[index] < data[end])
        {
            ++small;
            if (small != index)
                Swap(data, index, small);
        }
    }
    ++small;
    Swap(data, small, end);
    return small;
}
 
//递归快速排序  
void QuickSort(vector<int>& data, int start, int end)
{
    if (start >= end)
        return;
    int index = Partition(data, start, end); //基准的索引
    QuickSort(data, start, index - 1);
    QuickSort(data, index + 1, end);
}
 
int main()
{
    //输入不定长的待排序列
    vector<int> vec;
    int temp;
    char t;
    cout << "输入待排序列为：";
    do{
        cin >> temp;
        vec.push_back(temp);
    } while ((t = cin.get()) != '\n');
    /////////////////////////////////////////////////////////////////////////////////////
    int n = vec.size();//待排序列的长度 ，若输入为数组A，则int n = sizeof(A) / sizeof(int);
 
    cout << "排序前的结果为：";
    for (int i = 0; i < n; i++)
    {
        cout << vec[i] << " ";
    }
    cout << endl;
    /////////////////////////////////////////////////////////////////////////////////////
    QuickSort(vec, 0, n - 1); //调用快速排序算法
    /////////////////////////////////////////////////////////////////////////////////////
    cout << "排序后的结果为：";
    for (int i = 0; i < n; i++)
    {
        cout << vec[i] << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}

# 快速排序
def quick_sort(array, l, r):
    if l < r:
        q = partition(array, l, r)
        quick_sort(array, l, q - 1)
        quick_sort(array, q + 1, r)
 
def partition(array, l, r):
    x = array[r]
    i = l - 1
    for j in range(l, r):
        if array[j] <= x:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i + 1], array[r] = array[r], array[i + 1]
    return i + 1
 
if __name__=="__main__":
    arr = [int(i) for i in input().split()] # 输入待排序列
    quick_sort(arr,0,len(arr)-1)            # 快速排序
    print(" ".join(str(i) for i in arr))    # 输出排序结果

#include <iostream>
#include <vector>
using namespace std;
 
bool isRight(vector<char> &vec){
    vector<int> id(vec.size()); //用于存放左右括号的属性：左括号用1表示，右括号用-1表示
    int sum = 0;
    bool index = false;
    if (vec.size() <= 1 || vec[0]!='(' || vec.size()%2!=0){
        return index;
    }
    for (int i = 0; i < vec.size(); i++){
        if (vec[i] == '('){
            id.push_back(1);
            sum = id[i] + sum;
        }
            
        else if (vec[i] == ')'){
            id.push_back(-1);
            sum = id[i] + sum;
            if (sum <= -1)
                break;
        }
    }
    if (sum == 0)
        index = true;
    return index;
}
int main(){
    //输入不定长的括号
    vector<char> vec;
    char tmpCh;
    char t;
    cout << "输入一串括号为：";
    do{
        cin >> tmpCh;
        vec.push_back(tmpCh);
    } while ((t = cin.get()) != '\n');
 
    //调用isRight函数
    bool myRes = isRight(vec);
    cout << myRes << endl;
    system("pause");
    return 0;
}

def isRight(str1):
    index = False
    sum = 0
    tmp = []
    if(len(str1)>=2 and len(str1)%2==0 and str1[0]=='('):
        for id in range(len(str1)):
            if str1[id] == '(':
                tmp.append(1)
                sum += tmp[id]
            else:
                tmp.append(-1)
                sum += tmp[id]
                if sum<=-1:
                    break
        if sum == 0:
            index = True
    return index
 
if __name__ == "__main__":
    try:
        while True:
            str1 = [i for i in input().split()]
            print(isRight(str1))  # 返回判断结果
    except:
        pass

#include<iostream>  
#include <stack>  
#include <cassert>  
using  namespace std;
 
//方法一：  一个辅助栈，如果这个栈为空，直接将元素入这个栈，如果辅助栈中有元素，将压入的元素和辅助栈顶元素比较，  
//压入两者中较小的那个元素使得辅助栈总是维持栈顶元素为最小值。  
//class Stack  
//{  
//public:  
//  void Push(int data)  
//  {  
//      stackData.push(data);  
//      if (stackMin.empty())  
//      {  
//          stackMin.push(data);  
//      }  
//      else  
//      {  
//          int tmp = stackMin.top();  
//          int min = data > tmp ? tmp : data;  
//          stackMin.push(min);  
//      }  
//  }  
//  
//  void Pop()  
//  {  
//      assert(!stackData.empty() && !stackMin.empty());  
//      stackData.pop();  
//      stackMin.pop();  
//  }  
//  
//  int GetMin()  
//  {  
//      assert(!stackMin.empty());  
//      return stackMin.top();  
//  }  
//  
//private:  
//  stack<int> stackData;  
//  stack<int> stackMin;  
//};  
 
//方法二： 一个辅助栈，如果这个栈为空，直接将元素入这个栈，如果辅助栈中有元素，将压入的元素和辅助栈顶元素比较，  
//如果压入的元素小于等于辅助栈顶元素，者将这个元素入辅助栈，否则无操作，出栈的时候判断要出栈的元素是否等于辅助  
//栈顶元素，如果是，也将辅助栈顶元素出栈。否则无操作。  
class Stack
{
public:
    void Push(int data)
    {
        stackData.push(data);
        if (stackMin.empty())
        {
            stackMin.push(data);
        }
        else
        {
            if (data <= stackMin.top())
            {
                stackMin.push(data);
            }
        }
    }
    void Pop()
    {
        assert(!stackData.empty() && !stackMin.empty());
        if (stackData.top() == stackMin.top())
        {
            stackMin.pop();
        }
        stackData.pop();
    }
    int GetMin()
    {
        assert(!stackMin.empty());
        return stackMin.top();
    }
private:
    stack<int> stackData;
    stack<int> stackMin;
 
};
 
 
int main()
{
    Stack s;
    //s.Push(5);  
    s.Push(36);
    s.Push(15);
    s.Push(95);
    s.Push(50);
    s.Push(53);
    cout << s.GetMin() << endl;
    system("pause");
    return 0;
}//15

class Solution {
public:
    stack<int> stackData;//保存数据用的栈stackData
    stack<int> stackMin;//保存最小的数的栈stackMin，其中它的栈顶始终为最小的数
    void push(int value) {
        stackData.push(value);
        if(stackMin.empty()) 
            stackMin.push(value);//如果stackMin为空，则value是最小的值，入栈
        else{
            if(stackMin.top()>=value) 
                stackMin.push(value);//否则当value小于等于stackMin的栈顶元素时，入栈（等于的时候也入栈是因为我考虑有相同的数）
        }
  }
  void pop() {
      if(stackData.top()==stackMin.top())//如果出栈的数刚好是最小的数，那么stackMin也应该出栈
        stackMin.pop();
      stackData.pop();
  }
  int top() {
    return stackData.top();//栈顶元素应返回stackData的栈顶元素
  }
  int min() {
    return stackMin.top();//stackMin的栈顶元素即是最小的数
  }
};

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        //特殊输入测试
        if(pushV.empty() || popV.empty() || pushV.size()!=popV.size())
            return false;
        stack<int> mystack;//定义一个辅助栈
        int index=0;
        for(int i=0;i<popV.size();i++){
            //当辅助栈为空或者栈顶元素和popV当前元素不相等时，将pushV当前元素压入
            while(mystack.empty()||mystack.top()!=popV[i]){
                if(index>=pushV.size())
                    //如果需要压入的元素个数大于pushV的元素个数，说明popV不可能是pushV的弹出序列
                    return false;
                mystack.push(pushV[index++]);
            }
            //当栈顶元素与popV当前元素相等时，将栈顶元素弹出，并移至popV下一个元素
            if(mystack.top()==popV[i])
                mystack.pop();
        }
        return true;
    }
};