编程之旅-Day2Day2-学习内容：

98 阅读 0 评论 65 点赞

我是靠谱客的博主儒雅学姐，最近开发中收集的这篇文章主要介绍编程之旅-Day2Day2-学习内容：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Day2-学习内容：

(1)剑指Offer

编程题18:删除链表中重复的节点

编程题39:数组中出现次数超过一半的数字

(2)Leetcode

例1：罗马数字换成整数

例2: 求股票买进卖出的最大利润

(3)腾讯2017年暑期实习真题

编程题1-构造回文

(4)试题广场-腾讯校招笔试真题（3道单选）

1.剑指Offer

编程题18:删除链表中重复的节点

题目描述：

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

书上解法：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if (pHead==nullptr){
            return;
        }
        ListNode *pPreNode = nullptr;
        ListNode *pNode = pHead;
        while(pNode!= nullptr){
            ListNode *pNext = pNode->next;
            bool needDelete = false;
            if(pNext!=nullptr&&pNext->val==pNode->val){
                needDelete = true;
            }
            if(!needDelete){
                pPreNode=pNode;
                pNode=pNode->next;
            }
            else{
                int val=pNode->val;
                ListNode *pToBeDel = pNode;
                while(pToBeDel!=nullptr&&pToBeDel->val==val){
                    pNext = pToBeDel->next;
                    delete pToBeDel;
                    pToBeDel = nullptr;
                    pToBeDel = pNext;
                }
                if(pPreNode==nullptr){
                    pHead=pNext;
                }
                else{
                    pPreNode->next=pNext;
                }
                pNode=pNext;
            }
            printf(pPreNode);
        }
    }
};

正确解法：（已调试通过-牛客网）

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
       if(pHead==NULL){
           return NULL;
       }
       if(pHead!=NULL && pHead->next==NULL){
           return pHead;
       }
       ListNode* current;
       if(pHead->val==pHead->next->val){
           current = pHead->next->next;
           while(current!= NULL && current->val == pHead->val)
               current=current->next;
           return deleteDuplication(current);
       }
       else{
           current = pHead->next;
           pHead->next = deleteDuplication(current);
           return pHead;
       }
    }
};

编程题39:数组中出现次数超过一半的数字

题目描述：

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

书上解法：

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(CheckInvalidArray(numbers))
            return 0;
        int result=numbers[0];
        int times=1;
        for(i=1;i<len(numbers);i++){
            if(times==0){
                result=numbers[i];
                times=1;
            }
            else if(result==number[i]){
                times +=1;
            }
            else{
                times -=1;
            }
        }
        
        if(!CheckMoreThanHalf(numbers,result))
            result=0;
        return result;
    }
    bool CheckInvalidArray(int* numbers){
        g_CheckInvalidArray = false;
        if(numbers==nullptr||len(numbers)==0)
            g_CheckInvalidArray = true
        return  g_CheckInvalidArray;
    }
    bool CheckMoreThanHalf(int* numbers,int result){
        int times=0;
        for(i=0;i<len(numbers);i++){
            if(numbers[i]==result)
                times+=1;
        }
        bool isMoreThanHalf = true;
        if (times*2<=len(numbers)){
            g_CheckInvalidArray = true;
            isMoreThanHalf = false;
        }
        return isMoreThanHalf;   
    } 
};

正确解法：（已调试通过-牛客网）

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.empty())
            return 0;
        int result=numbers[0];
        int times=1;
        for(int i=1;i<numbers.size();i++){
            if(times==0){
                result=numbers[i];
                times=1;
            }
            else if(result==numbers[i]){
                ++times;
            }
            else{
                --times;
            }
        }
        int time=0;
        for(int i=0;i<numbers.size();i++){
            if(numbers[i]==result)
                time+=1;
        }
        return (time*2<=numbers.size()) ? 0 : result;
    }
};

2.Leetcode

例1：罗马数字换成整数

正确解法： （已调试通过）

python3实现

class Solution:
    def romanToInt(self, s):
        a = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':100,'M':1000}
        ans = 0
        for i in range(len(s)):
            if i<len(s)-1 and a[s[i]]<a[s[i+1]]:
                ans-=a[s[i]]
            else:
                ans+=a[s[i]]
        return ans

例2:求股票买进卖出的最大利润

错误解法：

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int profit = 0;
        for (int i=0;i<prices.size();++i){
            for(int j=i+1;j<prices.size();++j){
                if(prices[j]>prices[i]&&(i<j)&&profit<(prices[j]-prices[i])){
                    profit=prices[j]-prices[i];
                }
            }
        }
        return profit;
    }
};

正确解法：

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        //本题由于允许多次交易（每次必须先卖出再买进），所以不好用爆搜
        //分析可知，要想利益最大化，就应该每次在波谷买进，波峰卖出，这样利益最大，操作次数最少
        //应该是使用动态规划来做可能比较简洁，个人觉得。
         
        int len = prices.size();
        vector<int> change(len,0);
        int maxPro=0;
        for(int i=1;i<len;i++){
            change[i]=prices[i]-prices[i-1];  //记录所有长和跌的情况
            if(change[i]>0)maxPro += change[i];  //累加所有长幅，即为最大收益
        }
        return maxPro;
    }
};

3.腾讯2017年暑期实习真题

编程题1-构造回文

题目描述：

给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
输出需要删除的字符个数。

程序：（已调试通过！）

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

const int MAX = 1001;
int MaxLen[MAX][MAX]; //最长公共子序列，动态规划求法

int maxLen(string s1, string s2){
    int length1 = s1.size();
    int length2 = s2.size();
    for (int i = 0; i <= length1; ++i)
        MaxLen[i][0] = 0;
    for (int i = 0; i <= length2; ++i)
        MaxLen[0][i] = 0;

    for (int i = 1; i <= length1; ++i)
    {
        for (int j = 1; j <= length2; ++j)
        {
            if (s1[i-1] == s2[j-1]){
                MaxLen[i][j] = MaxLen[i-1][j - 1] + 1;
            }
            else
            {
                MaxLen[i][j] = max(MaxLen[i - 1][j], MaxLen[i][j - 1]);
            }
        }
    }

    return MaxLen[length1][length2];
}

int main(){
    string s;
    while (cin >> s){
        int length = s.size();
        if (length == 1){
            cout << 1 << endl;
            continue;
        }
        //利用回文串的特点
        string s2 = s;
        reverse(s2.begin(),s2.end());
        int max_length = maxLen(s, s2);
        cout << length - max_length << endl;
    }
    return 0;
}

参考：https://blog.csdn.net/xubinlxb/article/details/52423974

4.试题广场-腾讯校招笔试真题（3道单选）

例1:图的广度优先搜索算法需使用的辅助数据结构为 (B)

A.三元组 B.队列 C.二叉树 D.栈

解析：深度优先搜索-栈

例2.下列数据结构不是多型数据类型的是（C）

A.堆 B.栈 C.字符串 D.有向图

例3:下列排序方法中，属于稳定排序的是（D）

A.选择排序 B.希尔排序

C.堆排序 D.归并排序

解析：选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。