程序员面试金典，牛课网在线编程题目答案（1）

程序员面试金典，牛课网在线编程题目答案（1）题目地址点击打开链接

//请实现一个算法，确定一个字符串的所有字符是否全都不同。
//这里我们要求不允许使用额外的存储结构。
bool checkDifferent(string iniString) {
    // write code here
    int len = iniString.length();
    int vis[256];
    memset(vis,0,sizeof(vis));
    for(int i = 0 ; i < len ; i++)
    {
        if(vis[iniString[i]-'0'])return false;
        vis[iniString[i]-'0']=1;
    }
    return true;
}

//请实现一个算法，在不使用额外数据结构和储存空间的情况下，
//翻转一个给定的字符串(可以使用单个过程变量)。
string reverseString(string iniString) {
    // write code here
    int len = iniString.size();
    for(int i = 0 ; i < (len+1)/2 ; i++ )
    {
        swap(iniString[i],iniString[len-i-1]);
    }
    return iniString;
}

//给定两个字符串，请编写程序，确定其中一个字符串的字符重新排列后，
//能否变成另一个字符串。这里规定大小写为不同字符，且考虑字符串重点空格。
bool checkSam(string stringA, string stringB) {
    // write code here
    int lenA = stringA.size();
    int lenB = stringB.size();
    if(lenA!=lenB)return false;
    sort(stringA.begin(),stringA.end());
    sort(stringB.begin(),stringB.end());
    for(int i = 0 ; i < lenA ; i++)
    {
        if(stringA[i]!=stringB[i])return false;
    }
    return true;
}

//请编写一个方法，将字符串中的空格全部替换为“%20”。假定该字符串有足够的空间存放新增的字符，
//并且知道字符串的真实长度(小于等于1000)，同时保证字符串由大小写的英文字母组成。
string replaceSpace(string iniString, int length) {
    // write code here
    string pStr=iniString;
    string str = "%20";
    int num = 0 ;
    for(int i = 0 ; i < length ; i++)
    {
        if(iniString[i]==' ')
        {
            //cout<<pStr.find(" ")<<endl;
            pStr.replace(num,1,str);
            num+=3;
        }
        else pStr[num++]=iniString[i];
        //cout<<pStr[num-1]<<endl;
    }
    //pStr[num]='\0';
    return pStr;
}

//利用字符重复出现的次数，编写一个方法，实现基本的字符串压缩功能。
//比如，字符串“aabcccccaaa”经压缩会变成“a2b1c5a3”。若压缩后的字符串没有变短，则返回原先的字符串。
string zipString(string iniString) {
    // write code here
    string pStr;
    int len = iniString.size();
    for(int i = 0 , j = 0 ; i < len ; i++)
    {
        while(i<len&&iniString[i]==iniString[j])i++;
        pStr+=iniString[j];
        stringstream s;
        s<<(i-j);
        pStr+=s.str();
        j=i;
        /*
        int aa = 30;
        stringstream ss;
        ss<<aa;
        string s1 = ss.str();
        cout<<s1<<endl; // 30
        */     //10进制int转化为string
    }
    return (len>pStr.size())?pStr:iniString;
}

//有一副由NxN矩阵表示的图像，这里每个像素用一个int表示，请编写一个算法，
//在不占用额外内存空间的情况下(即不使用缓存矩阵)，将图像顺时针旋转90度。
vector<vector<int> > transformImage(vector<vector<int> > mat, int n) {
    // write code here
    for(int i = 0 ; i < (n)/2 ; i++)
    {   //外层循环，从第(i,i)开始
        int k = n-i-1 ;
        for(int j = i ; j < k ; j++)
        {
            //每次循环一次就是外面一圈交换完毕
            int temp = mat[i][j];
            mat[i][j] = mat[k-j+i][i];
            mat[k-j+i][i] = mat[k][k-j+i];
            mat[k][k-j+i] = mat[j][k];
            mat[j][k] = temp ;
        }
    }
    return mat;
}

//请编写一个算法，若MxN矩阵中某个元素为0，则将其所在的行与列清零。
vector<vector<int> > clearZero(vector<vector<int> > mat, int n) {
    // write code here
    bool flag[305][305];
    memset(flag,false,sizeof(flag));
    for(int i = 0 ; i < n ; i++)
    {
        for(int j = 0 ; j < n ; j++)
        {
            if(mat[i][j]==0)flag[i][j]=true;
        }
    }
    for(int i = 0 ; i < n ; i++)
    {
        for(int j = 0 ; j < n ; j++)
        {
            if(flag[i][j])
            {
                for(int k = 0 ; k < n ; k++)
                {
                    mat[i][k]=0;
                    mat[k][j]=0;
                }
            }
        }
    }
    return mat;
}

//假定我们都知道非常高效的算法来检查一个单词是否为其他字符串的子串。请将这个算法编写成一个函数，
//给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成，要求只能调用一次检查子串的函数。
bool checkReverseEqual(string s1, string s2) {
    // write code here
    //判断一个字符串是否是由另一个字符串旋转得来的，那么我们可以
    //将源字符串两次拼接之后看目标字符串是否是拼接的字符串的子串
    int len1 = s1.size();
    int len2 = s2.size();
    if(len1!=len2||len1==0)return false;
    string s = s1+s1;
    if(s.find(s2)==-1)return false;
    return true;
}

struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};

//输入一个链表，输出该链表中倒数第k个结点。
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    ListNode* Node = pListHead , *Head = pListHead;
    unsigned int num = 0 ;
    while(Head!=NULL)
    {
        Head = Head->next;
        if(num>=k)Node = Node->next;
        num++;
    }
    if(num<k)return NULL;
    return Node;
}

//实现一个算法，删除单向链表中间的某个结点，假定你只能访问该结点。
//给定带删除的节点，请执行删除操作，若该节点为尾节点，返回false，否则返回true
bool removeNode(ListNode* pNode) {
    // write code here
    //只能访问该节点，所以将后继结点的数据复制到当前结点，然后删除这个后继结点。
    ListNode *Node = pNode->next;
    if(Node==NULL)
    {
        pNode = NULL ;
        return false;
    }
    pNode->val = Node->val;
    pNode->next = Node->next;
    return true;
}

//编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
//给定一个链表的头指针 ListNode* pHead，请返回重新排列后的链表的头指针。
//注意：分割以后保持原来的数据顺序不变。
ListNode* partition(ListNode* pHead, int x) {
    // write code here
    ListNode *Node = pHead , *pNode = pHead;
    while(pNode!=NULL)
    {
        if(pNode->val>=x)pNode = pNode->next;
        else
        {
            int tmp = pNode->val;
            ListNode *p = Node ;
            int current = p->val;
            int next = p->next->val;
            while(p!=pNode)
            {   //数字后移
                p->next->val = current;
                p = p->next;
                current = next;
                next = p->next->val;
            }
            Node->val = tmp ;
            Node = Node->next;
            pNode = pNode->next;
        }
    }
    return pHead;
}

//请编写一个函数，检查链表是否为回文。
//给定一个链表ListNode* pHead，请返回一个bool，代表链表是否为回文。
bool isPalindrome(ListNode* pHead) {
    // write code here
    //利用快慢指针，找到中间节点；将慢指针节点的值压入栈，到达中间节点后，
    //依次出栈与后续节点的值比较。特别注意长度奇偶数。
    if(pHead==NULL)return false;
    if(pHead->next==NULL)return true;

    ListNode *slow = pHead , *fast = pHead;
    stack<int> s;
    while(fast!=NULL&&fast->next!=NULL)
    {    //找出中间的元素
        s.push(slow->val);
        slow=slow->next;
        fast=fast->next->next;
    }
    if(fast!=NULL)
    {
        //当链表为奇数个时，中间元素忽略
        slow=slow->next;
    }
    while(slow!=NULL)
    {
        if(s.top()!=slow->val)return false;
        s.pop();
        slow=slow->next;
    }
    return true;
}

//请实现一种数据结构SetOfStacks，由多个栈组成，其中每个栈的大小为size，
//当前一个栈填满时，新建一个栈。该数据结构应支持与普通栈相同的push和pop操作。
vector<vector<int> > setOfStacks(vector<vector<int> > ope, int size) {
    // write code here
    //模拟添加删除的过程。
    /*
    添加元素时，若当前栈没满则直接添加，满了就开辟新栈
    删除元素时，若当前栈没空则直接删除，空了就看当前栈是否是第一个栈，
    是就报错，不是就删除下一个栈里面的内容
    */
    vector<vector<int> >ans;
    vector<int> tmp ;
    int len = ope.size();
    if(len==0)return ope;
    for(int i = 0 ; i < len ; ++i)
    {
        int op = ope[i][0];
        int data = ope[i][1];
        if(op==1)  //添加
        {
            if(tmp.size()==size)
            {    //满了,开辟新栈
                ans.push_back(tmp);
                tmp.clear();
                tmp.push_back(data);
            }
            else tmp.push_back(data); //没满继续放
        }
        else if(op==2)
        {
            if(!tmp.empty())
            {   //当前栈没空
                tmp.pop_back();
            }
            else if(!ans.empty())
            {  //空了
                tmp = ans.back();   //最后面的一个
                ans.pop_back();
                tmp.pop_back();
            }
            else return ans;
        }
    }
    if(!tmp.empty())ans.push_back(tmp);
    return ans;
}

//用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
class Solution
{
    /*
    入队列，直接将元素入stack1
    出队列，若stack2不为空，直接stack2出栈
    若为空，将stack1中的所有元素出栈并按序入stack2
    然后stack2在出栈
    */
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        if(stack2.empty())
        {   //stack2为空
            while(!stack1.empty())
            {
                stack2.push(stack1.top());
                stack1.pop();
            }
        }
        if(stack2.empty())return -1;
        int ans = stack2.top();
        stack2.pop();
        return ans;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

//请编写一个程序，按升序对栈进行排序（即最大元素位于栈顶），
//要求最多只能使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。

//给定一个int[] numbers(C++中为vector<int>)，其中第一个元素为栈顶，请返回排序后的栈。
vector<int> twoStacksSort(vector<int> numbers) {
    // write code here
    /*
     * 思路：
     * 只用两个栈排序，一个是有序的asc，另一个是无序的buffer就可以实现对一个栈的排序。
     * 如何有序，当原始栈只有一个时就有序了
     * numbers中第一个为栈顶
     * 主要是解决buffer栈顶元素放在asc的位置
     * 1. buffer栈顶大于等于asc栈顶或asc空直接放
     * 2. buffer栈顶小于asc栈顶
     *  buffer栈顶值出栈，临时变量存放buffer栈顶值
     *  循环从asc中拿出值放到buffer直至asc空或满足1条件
     */
    vector<int> ans;
    ans.push_back(numbers.back());   //取栈底元素
    numbers.pop_back();
    while(!numbers.empty())
    {
        int n = numbers.back();
        numbers.pop_back();
        while(!ans.empty()&&n>ans.back())
        {
            numbers.push_back(ans.back());
            ans.pop_back();
        }
        ans.push_back(n);
    }
    return ans;
}


//猫狗收容所
/*
有家动物收容所只收留猫和狗，但有特殊的收养规则，收养人有两种收养方式，
第一种为直接收养所有动物中最早进入收容所的，第二种为选择收养的动物类型（猫或狗），
并收养该种动物中最早进入收容所的。
*/
vector<int> asylum(vector<vector<int> > ope) {
    // write code here
    /*
    维护两个队列，一个队列放猫一个队列里面放狗，并且在队列里面多放一个标志位
    来标志这个猫或者狗进队列的时间，为了实现第一种收取方案
    */
    vector<int> ans;
    queue<int> cat , dog;
    int num = 0 , len = ope.size();
    for(int i = 0 ; i < len ; i++)
    {
        if(ope[i][0]==1)
        {
            if(ope[i][1]>0)
            {
                dog.push(num++);   //标志位
                dog.push(ope[i][1]);
            }
            else
            {
                cat.push(num++);    //标志位
                cat.push(ope[i][1]);
            }
        }
        else
        {
            if(ope[i][1]==1)
            {
                if(dog.empty())continue;
                dog.pop();  //先删除标志位
                ans.push_back(dog.front());
                dog.pop();
            }
            else if(ope[i][1]==-1)
            {
                if(cat.empty())continue;
                cat.pop();  //先删除标志位
                ans.push_back(cat.front());
                cat.pop();
            }
            else if(ope[i][1]==0)
            {
                if(dog.empty()&&!cat.empty())
                {
                    cat.pop();  //先删除标志位
                    ans.push_back(cat.front());
                    cat.pop();
                }
                else if(!dog.empty()&&cat.empty())
                {
                    dog.pop();  //先删除标志位
                    ans.push_back(dog.front());
                    dog.pop();
                }
                else if(!dog.empty()&&!cat.empty())
                {
                    if(dog.front()<cat.front())
                    {
                        dog.pop();  //先删除标志位
                        ans.push_back(dog.front());
                        dog.pop();
                    }
                    else
                    {
                        cat.pop();  //先删除标志位
                        ans.push_back(cat.front());
                        cat.pop();
                    }
                }
            }
        }
    }
    return ans;
}

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};

//实现一个函数，检查二叉树是否平衡
//直接遍历求子树深度的方法会有效率上的问题，因为遍历过程当中
//子节点会多次求深度，这样没有必要
//思路：后序遍历的方式，保存当前求得的深度，
//上层的节点就是当前深度加1，所以每个节点只求一次,效率上来了
//时间复杂度可以达到lonN

bool isBalance(TreeNode* root , int &depth)
{
    if(root==NULL)
    {
        depth = 0;
        return true;
    }
    int ldepth,rdepth;
    if(isBalance(root->left,ldepth)&&isBalance(root->right,rdepth))
    {
        if(abs(ldepth-rdepth)>1)return false;
        depth = max(ldepth,rdepth) + 1;
        return true;
    }
    return false;
}

bool isBalance(TreeNode* root) {
    // write code here
    int depth = 0 ;
    return isBalance(root,depth);
}

//对于一个有向图，请实现一个算法，找出两点之间是否存在一条路径。
//直接搜索找就可以了
//bool dfs(UndirectedGraphNode* x, UndirectedGraphNode* y)
//{
//    if(x==y)return true;
//    for(int i = 0 ; i < x->neighbors.size() ; i++)
//    {
//        return dfs(x->neighbors[i],y);
//    }
//    for(int i = 0 ; i < y->neighbors.size() ; i++)
//    {
//        return dfs(y->neighbors[i],x);
//    }
//    return false;
//}
//
//bool checkPath(UndirectedGraphNode* a, UndirectedGraphNode* b) {
//    // write code here
//    return dfs(a,b);
//}

////采用bfs的方法效率上可能更好一点
//bool checkPath(UndirectedGraphNode* a, UndirectedGraphNode* b) {
//    // write code here
//    return check(a,b)||check(b,a);
//}
//
//bool check(UndirectedGraphNode* a, UndirectedGraphNode* b) {
//    // write code here
//    if(a==NULL||b==NULL)
//        return false;
//    if(a==b)
//        return true;
//    map<UndirectedGraphNode*,bool> map1;
//    queue<UndirectedGraphNode*> que;
//    que.push(a);
//    while(!que.empty())
//    {
//        UndirectedGraphNode* ptr=que.front();
//        map1[ptr]=true;
//        for(int i=0;i<ptr->neighbors.size();i++)
//        {
//            if((ptr->neighbors)[i]==b)
//                return true;
//            if(ptr->neighbors[i]&&map1[ptr->neighbors[i]]!=true)
//                que.push((ptr->neighbors)[i]);
//        }
//        que.pop();
//    }
//    return false;
//}

//对于一个元素各不相同且按升序排列的有序序列，请编写一个算法，创建一棵高度最小的二叉查找树。
//就是创建一个二叉平衡树,返回创建的二叉查找树的高度。

//取数组的中间元素作为根，这样数组又分为两部分，又可以递归调用。
//临界点是当数组被分割的只有2个或者1个时，那么无论怎么构造高度都为数
//组的长度，我们再取左子树的高度和右子树的高度最大值，再加上根的高度，就
//是最低高度，其实就就是构造平衡二叉树
int depth(vector<int> vals,int low,int high)
{
    if((high-low+1)<=2)return (high-low+1);
    int mid = (low+high)/2;
    return max(depth(vals,low,mid-1),depth(vals,mid+1,high))+1;
}

int buildMinimalBST(vector<int> vals)
{
    // write code here
    return depth(vals,0,vals.size()-1);
}