欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法分析与设计第一周

程序员文章站 2022-07-14 17:49:24
...

第一周

第一周讲了分治,但是找不到分治的题目,所以随便找了两道题做了一下。

第一题:

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

分析:此题与算法没什么关系,主要看逻辑的严密性。有两个注意点:符号、溢出。其中溢出比较隐蔽,我用的是long来存数,并判断是否int溢出,然后转化为int输出。

代码:

class Solution {
public:
    int myAtoi(string str) {

        int i = 0;
        int sign = 1;
        long tempResult = 0;
        int result;

        while (str[i] == ' ')
            ++i;

        if ( str[i] == '-' || str[i] == '+')
        {
            if (str[i] == '-')
            sign = -1;
            ++i;
        }


        while ('0' <= str[i] && str[i] <= '9' && i < str.length())
        {
            tempResult = tempResult * 10 + (str[i] - '0');

            if (tempResult * sign > INT_MAX)
            return INT_MAX;
            else if (tempResult * sign < INT_MIN)
            return INT_MIN;

            ++i;
        }

            result = tempResult * sign;
            return result;
    }
};

第二题:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice

分析:方法一:暴力法,最简单的思路,即嵌套遍历数组,直到找到答案,这个算法复杂度为O(n^2),效率较差。

代码:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        vector<int> result;
        int first;
        int second;

        for (first = 0; first < nums.size(); ++first)
        {
            for (second = first + 1; second != nums.size(); second++)
            {
                if (nums[first] + nums[second] == target)
                {
                    result.push_back(first);
                    result.push_back(second);
                    return result;
                }
            }
        }
    }
};

方法二:只要选择了第一个元素,第二个元素是不需要顺序遍历找的,所以可以利用哈希表,因为哈希表查询平均时间是O(1),然后遍历查找第一个元素即可,将复杂的降为O(n)。

代码:

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target)
{
    unordered_map<int, int> hash;
    vector<int> result;

        for (int i = 0; i < numbers.size(); i++)
        {
            hash[numbers[i]] = i;
        }

    for (int i = 0; i < numbers.size(); i++) {

        int numberToFind = target - numbers[i];


        if (hash.find(numberToFind) != hash.end() && hash[numberToFind] != i) {

            result.push_back(hash[numberToFind]);
            result.push_back(i);            
            return result;
        }

    }

    return result;
}

};
相关标签: 算法