程序员代码面试指南（一）

用一个栈实现另一个栈的排序

只许申请一个栈,可以申请新的变量,但不能申请额外的数据结构.实现排序.

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

void sortstack(stack<int> &A){
    stack<int> tmp;
    while(!A.empty()){
        int a=A.top();
        A.pop();
        if(!tmp.empty()){
            while(!tmp.empty()&&tmp.top()<a){
                int b=tmp.top();
                tmp.pop();
                A.push(b);
            }
            tmp.push(a);
        }
        else{
            tmp.push(a);
        }
    }
    while(!tmp.empty()){
        int a=tmp.top();
        tmp.pop();
        A.push(a);
    }

}

int main(){
    stack<int> A;
    int a[]={7,1,5,3,4,2,1};
    for(int i=0;i<7;i++){
        A.push(a[i]);
    }
    sortstack(A);
    while(!A.empty()){
        cout<<A.top()<<endl;
        A.pop();
    }
}

if __name__ =="__main__":
  stack1=[6,2,1,5,3]
  stack2=[]
  while(stack1!=[]):
    a=stack1.pop(-1)
    if(stack2==[] or stack2[-1]<a):
        stack2.append(a)

    else:
        while(stack2!=[] and stack2[-1]>a):
            b=stack2.pop()
            stack1.append(b)


        stack2.append(a)
  stack2

用栈来解决汉诺塔问题

汉诺塔问题是一个经典的问题。汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？

一般的汉诺塔问题:
考虑几个状态：

1. 从左边移到中间
2. 从中间移到右边

#include <iostream>
using namespace std;

void hanoi(int n, int a, int b, int c)
{
    if(n > 0)
    {
        hanoi(n-1, a, c, b);
        cout << "move " << a << " to " << b << endl;
        hanoi(n-1, c, b, a);
    }
}

int main()
{
    int n;
    cin >> n;
    hanoi(n, 1, 2, 3);
    return 0;
}

def honi(n,stack1,stack2,stack3):
    if(n>0):
        honi(n-1,stack1,stack3,stack2)
        a=stack1.pop(-1)
        stack3.append(a)
        honi(n-1,stack2,stack1,stack3)
        return stack3
if __name__=="__main__":
  stack1=[6,5,4,3,2,1]
  stack2=[]
  stack3=[]
  result=honi(6,stack1,stack2,stack3)

构造数组的MaxTree

#include<iostream>
#include<vector>
#include<map>
using namespace std;
struct Node{
int val;
Node *left;
Node *right;
Node(int x){
    val=x;
    left=NULL;
    right=NULL;
}
};

void show(Node *head){
    if(head==NULL){
        return;
    }
    cout<<head->val<<endl;
    show(head->right);
    show(head->left);
}


int main(){
    vector<int>arr={3,4,5,1,2};
    map<Node*,Node*> Leftmax;
    map<Node*,Node*> Rightmax;
    vector<Node*> Nodelist;
    for(int i=0;i<arr.size();i++){
        Node * n=new Node(arr[i]);
        Nodelist.push_back(n);
    }
    for(int i=0;i<Nodelist.size();i++){
        if(i==0){
            Leftmax[Nodelist[i]]=NULL;
        }
        else{

            if(Nodelist[i-1]->val>Nodelist[i]->val){
                Leftmax[Nodelist[i]]=Nodelist[i-1];
            }
            else{
                Node * NN=Nodelist[i-1];

                while(NN!=NULL&&NN->val<=Nodelist[i]->val){
                    NN=Leftmax[NN];
                }

                Leftmax[Nodelist[i]]=NN;

            }

        }
    }
    for(int i=Nodelist.size()-1;i>=0;i--){
        if(i==Nodelist.size()-1){
            Rightmax[Nodelist[i]]=NULL;
        }
        else{
            if(Nodelist[i+1]->val>Nodelist[i]->val){
                Rightmax[Nodelist[i]]=Nodelist[i+1];
            }
            else{
                Node * NN=Nodelist[i+1];
                while(NN!=NULL&&NN->val<=Nodelist[i]->val){
                    NN=Rightmax[NN];
                }
                Rightmax[Nodelist[i]]=NN;
            }
        }
    }
    Node *head;



    for(int i=0;i<Nodelist.size();i++){
        if(Leftmax[Nodelist[i]]==NULL&&Rightmax[Nodelist[i]]==NULL){
            head=Nodelist[i];
        }
        else if(Leftmax[Nodelist[i]]==NULL){
            Node * father=Rightmax[Nodelist[i]];
            if(father->left!=NULL){
                father->right=Nodelist[i];
            }
            else{
                father->left=Nodelist[i];
            }
        }
        else if(Rightmax[Nodelist[i]]==NULL){
            Node * father=Leftmax[Nodelist[i]];
            if(father->left!=NULL){
                father->right=Nodelist[i];
            }
            else{
                father->left=Nodelist[i];
            }
        }
        else{
            Node * left=Leftmax[Nodelist[i]];
            Node * right=Rightmax[Nodelist[i]];
            Node * father;
            if(left->val<right->val){
                father=left;
            }
            else{
                father=right;
            }
            if(father->left!=NULL){
                father->right=Nodelist[i];
            }
            else{
                father->left=Nodelist[i];
            }
        }
    }

show(head);
}

class Node:
    def __init__(self,key):
        self.val=key
        self.left=None
        self.right=None
if __name__=="__main__":
  arr=[3,4,5,1,2]
  NodeList=[]
  for i in arr:
    NodeList.append(Node(i))
  LeftMax={}
  RightMax={}
  for (i,item) in enumerate(NodeList):
    if i==0:
        LeftMax[i]=-1
    else:
        if NodeList[i-1].val>NodeList[i].val:
            LeftMax[i]=i-1
        else:
            t=LeftMax[i-1]
            while(t!=-1 and NodeList[t].val<=NodeList[i].val):
                t=LeftMax[t]
            LeftMax[i]=t
            for i in range(len(NodeList)-1,-1,-1):
              if i==len(NodeList)-1:
                  RightMax[i]=-1
              else:
                  if NodeList[i+1].val>NodeList[i].val:
                      RightMax[i]=i+1

                  else:
                      t=RightMax[i+1]
                      while(t!=-1 and NodeList[t].val<=NodeList[i].val):
                          t=RightMax[t]
                      RightMax[i]=t
                      head
                    for i in range(len(LeftMax)):
                        if(LeftMax[i]==-1 and RightMax[i]==-1):
                            head=NodeList[i]
                        elif(LeftMax[i]==-1):
                            father=NodeList[RightMax[i]]
                            if(father.left==None):
                                father.left=NodeList[i]
                            else:
                                father.right=NodeList[i]
                        elif(RightMax[i]==-1):
                            father=NodeList[LeftMax[i]]
                            if(father.left==None):
                                father.left=NodeList[i]
                            else:
                                father.right=NodeList[i]
                        else:
                            Rf=NodeList[RightMax[i]].val
                            Lf=NodeList[LeftMax[i]].val
                            if(Rf<Lf):
                                P=NodeList[RightMax[i]]
                                if(P.left==None):
                                    P.left=NodeList[i]
                                else:
                                    P.right=NodeList[i]
                            else:
                                P=NodeList[LeftMax[i]]
                                if(P.left==None):
                                    P.left=NodeList[i]
                                else:
                                    P.right=NodeList[i]

求最大子矩阵的大小

给定一个整型矩阵map,其中的值只有0和1两种,求其中全是1的所有的矩形区域中,最大的矩形区域为1的数量
例如：
1 1 1 0
其中最大矩形区域有3个1,所以返回3
再例如:
1 0 1 1
1 1 1 1
1 1 1 0
其中最大区域有6个1返回6个1

def getheight(A):
  m=len(A)
  n=len(A[0])
  P=[]
  for k in range(m):
    M=[]
    for j in range(n):
        s=0
        for i in range(k,m):
            if(A[i][j]==0):
                break
            s=s+A[i][j]
        M.append(s)
    P.append(M)
  return P
  def getarea(p):
      minstack=[]
      zeroposition=[-1]
      maxarea=0
      for ih in range(len(p)):
          if(p[ih]==0):
              zeroposition.append(ih)    


          if(len(minstack)==0 or p[minstack[-1]]<p[ih]):
              minstack.append(ih)
              area=p[minstack[0]]*(ih-zeroposition[-1])
          else:
              if(p[ih]==0):
                  area=0
              else:
                  area=p[ih]*(ih-zeroposition[-1])
              while(len(minstack)!=0 and p[minstack[-1]]>=p[ih]):
                  minstack.pop()

              if(p[ih]!=0):
                  minstack.append(ih)
          if(area>maxarea):
              maxarea=area
          print(maxarea)

      return maxarea

if __name__=="__main__":
  A=[[1,0,1,1],[1,1,1,1],[1,1,1,0]]
  P=getheight(A)##获得从第i行到最后一行的高度,有可能被0给截断
  maxarea=0
  for p in P:
    m=getarea(p)
    if(maxarea<m):
      maxarea=m

这里采用和书上不同的方法,但也比较类似.

最大值减去最小值小于或等于num的子数组数量

给定数组 arr 和整数 num，共返回多少个字数组满足如下情况：
max(arr[i…j]) - min(arr[i…j]) <= num
max(arr[i…j]) 表示字数组 arr[i…j] 中的最大值，min(arr[i…j]) 表示子数组 arr[i…j] 中的最小值。
思路:
1、若 arr[i…j] 满足条件，那么其子数组也会满足条件；
2、若 arr[i…j] 不满组条件，那么包含arr[i…j]的数组都不满足条件；

#include<iostream>
#include<vector>
#include<deque>
using namespace std;

int getNum(vector<int> A,int num){
    int len=A.size();
    int j=0;
    int res=0;
    deque<int> maxq;
    deque<int> minq;
    for(int i=0;i<len;i++){
        while(j<len){
            while(!minq.empty()&&A[j]<=A[minq.front()]){
                minq.pop_back();
            }
            minq.push_back(j);

            while(!maxq.empty()&&A[j]>=A[maxq.front()]){
                maxq.pop_back();
            }
            maxq.push_back(j);

            if(A[maxq.front()]-A[minq.front()]>num){
                break;
            }
            j++;
        }
        if(maxq.front()==i){
            maxq.pop_front();
        }
        if(minq.front()==i){
            minq.pop_front();
        }
        res+=(j-i);
    }
    return res;
}

int main(){

     vector<int>A = {3,2,5,1,4,7,8,6};
    cout << "The number of sub arrays to meet the requirements is: " << getNum(A,4)<< endl;

}

def getNum(A,num):
    maxq=[]
    minq=[]
    res=0
    j=0
    for i in range(len(A)):
        while(j<len(A)):
            while(len(maxq)!=0 and A[maxq[0]]<A[j]):
                maxq.pop()
            maxq.append(j)

            while(len(minq)!=0 and A[minq[0]]>A[j]):
                minq.pop()
            minq.append(j)

            if(A[maxq[0]]-A[minq[0]]>num):
                break    
            j=j+1
        res=res+(j-i)
        if(i==maxq[0]):
            maxq.pop(0)
        if(i==minq[0]):
            minq.pop(0)
        i=i+1

    return res
if __name__=="__main__":
  A=[3,2,5,1,4,7,8,6]
  res=getNum(A,4)
  print(res)

Python刷题

python中栈可以用列表来代替
服从FILO：First In Last Out
其中入栈为（利用append函数）

stack = []
stack.append(<item>)

出栈为（利用pop函数）

stack.pop(-1) #stack.pop()也可

服从FIFO：First In First Out
入栈为：

stack = []
stack.append(<item>)

出栈为：

stack.pop(0)

python里的map与C++里的map不同

python里的map()是 python 内置的高阶函数，它接收一个函数 f 和一个 list，并通过把函数 f 依次作用在 list 的每个元素上，得到一个新的object并返回。（python2返回列表，Python3返回迭代对象）
这里map的使用方法形如map(f(x),Itera),它有两个参数,第一个参数为某个函数而第二个为可迭代对象.

def test(num):
  return num*num

  if __name__=="__main__":
    res=map(test,[1,23])
    print(list(res))

而在C++中的Map实际上是hashmap,要用pair的来表示.
在python中这种可以用dict字典来实现

dict

dict是python中的一个可变的数据类型，用{}表示，dict的key必须是不可变的数据类型，而value的数据类型可以任意
格式：{key:value,key:value,key:value}

注：键值对如果是字符串使用单引号，最后一个键值对没有逗号
dict的优点：

1. 查询速度快，可以二分查找
2. key是不可以重复的
   注：　　　
   不可变数据类型： 元组，bool，int , str 可以hash
   可变数据类型： dict ，list， set
   二、dict的方法：
   (1)增加的方法：dict有两种增加的方法

3. 第一种：如果没有的键值对，则进行添加，如果有，则将值进行覆盖

   dict1={'name':'jinxin','age':18,'male':'男'}
   print(dict1)
   dict1['high']=185
   print(dict1)  # {'name': 'jinxin', 'age': 18, 'male': '男', 'high': 185}
   dict1['age']=16
   print(dict1) #  {'name': 'jinxin', 'age': 16, 'male': '男', 'high': 185}

4. 第二种：如果有键值对，不做任何改变，没有键值对，才进行添加

   dict1.setdefault("weight")
   print(dict1)  #{'name': 'jinxin', 'age': 16, 'male': '男', 'high': 185, 'weight': None}
   dict1.setdefault('weight','65kg')
   print(dict1)  #{'name': 'jinxin', 'age': 16, 'male': '男', 'high': 185, 'weight': None}
   dict1.setdefault('address','北京')
   print(dict1)  #{'name': 'jinxin', 'age': 16, 'male': '男', 'high': 185, 'weight': None, 'address': '北京'}

(2)dict的删除方法

1. 使用pop()删除，如果有键，则删除，如果没有则会报错，如果不希望出现报错信息，可以在删除的后面添加信息

   delDict={'name': 'jinxin', 'age': 16, 'male': '男', 'high': 185, 'weight': None, 'address': '北京'}
   # delDict.pop('age')  #dict的删除操作是有返回值的
   print(delDict.pop('age'))  # 16
   print(delDict)  #{'name': 'jinxin', 'male': '男', 'high': 185, 'weight': None, 'address': '北京'}
   print(delDict.pop('职业','没有此键'))  #没有此键

2. 使用popitem()删除，随机删除，返回的是一个元组，元组里面存储的删除的键值，推荐使用pop()方法进行删除

   print(delDict.popitem())  # ('address', '北京') 随机删除，返回值是删除的键值对
   print(delDict)  #{'name': 'jinxin', 'male': '男', 'high': 185, 'weight': None}

3. 使用del()删除，del()可以删除整个字典，也可以删除字典的某个键，如果删除的键不存在，则会出现报错

   del delDict['name']
   print(delDict)  #{'male': '男', 'high': 185, 'weight': None}
   
   #使用del清空列表
   del delDict
   print(delDict)  #delDict已经删除,报错

4. 清空列表也可以使用clear()
   (3)dict的修改

   #直接修改
   updateDict={'name':'jinxin','age':18,'male':'男'}
   updateDict['name']='Jordan'
   print(updateDict['name']) #Jordan
   
   #调用update()修改
   dictDemo={'name':"Jordan",'age':18}
   dictDemo1={'address':'北京海淀','age':22}
   dictDemo.update(dictDemo1)
   print(dictDemo)

4）字典的查询

1. 查询字典的键：调用keys()方法
   查询字典的值：调用values()方法

   # 字典的查
   dict1={'name':'jinxin','age':18,'male':'男'}
   print(dict1.keys()) #dict_keys(['name', 'age', 'male'])
   print(dict1.values()) #dict_values(['jinxin', 18, '男'])
   print(dict1.items())# dict_items([('name', 'jinxin'), ('age', 18), ('male', '男')])
   
   #打印dict1的键
   for i in dict1.keys():
       print(i )  # name age value
   
   #打印dict的值
   for v  in dict1.values():
       print(v) #jinxin 18 男

打印字典的键值：

dict1={'name':'jinxin','age':18,'male':'男'}

for i in dict1.items():
    print(i)  # ('name', 'jinxin') ('age', 18) ('male', '男')

for k,v in dict1.items():
    print(k,v)  # name jinxin  age 18   male 男

1. 字典的get()方法：使用get()方法可以查询某个键是否存在，如果不存在此键，则会返回None，但是可以在get()方法中添加信息避免出现None

   dict1={'name':'jinxin','age':18,'male':'男'}
   print(dict1.get('name')) #jinxin
   print(dict1.get('address')) # None
   print(dict1.get('address','没有此键'))  #没有此键