LeetCode做题

快要找工作了,一般的面试都会考这种算法题,可是自己不会,只能最近开始每天多做做题(这叫刻意练习),训练自己。慢慢总结。我是用C++实现的。
对于每个问题的答案,我在网上找到了这个帖子,这个老哥真是厉害,基本上每个题都给出了答案,而且附有简短的讲解链接在这里https://www.cnblogs.com/grandyang/p/4606334.html

对于这些算法题,不但要有基本的思路,还要考虑到边界条件,比如正数负数零都要考虑到,字符空串和nullptr指针等。还要考虑到功能测试比如数字非常大超过int,超过long等问题。还要考虑到错误输入,负面测试用例,我们怎么处理

1、基本数据结构,算法,技巧,时间复杂度

1、技巧

在数组和字符串中经常使用的一种方法就是双指针,使用双指针技巧的典型场景之一是你想要从两端向中间迭代数组。这时你可以使用双指针技巧:一个指针从始端开始,而另一个指针从末端开始。值得注意的是,这种技巧经常在排序数组中使用。其实我认为,要想使用也可以用sort函数先排好序,不就可以用了吗。
第二种场景:同时有一个慢指针和一个快指针。解决这类问题的关键是确定两个指针的移动策略。与前一个场景类似,你有时可能需要在使用双指针技巧之前对数组进行排序,也可能需要运用贪心想法来决定你的运动策略。

2、常用算法的时间复杂度

哈希表的时间复杂度 O(n)
二分查找时间复杂度O(log2n)
....

2、数组篇

Leetcode第一题:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]


这道题是第一道题,我最开始是用的暴力解法,时间复杂度是O(n^2),但是提交之后就是所有的测试用例通过,但是显示timeout,所以只好另辟蹊径。使用一个 HashMap,来建立数字和其坐标位置之间的映射,由于 HashMap 是常数级的查找效率,这样在遍历数组的时候,用 target 减去遍历到的数字,就是另一个需要的数字了,直接在 HashMap 中查找其是否存在即可,注意要判断查找到的数字不是第一个数字,比如 target 是4,遍历到了一个2,那么另外一个2不能是之前那个2,整个实现步骤为:先遍历一遍数组,建立 HashMap 映射,然后再遍历一遍,开始查找,找到则记录 index。
参考代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        vector<int> res;
        for (int i = 0; i < nums.size(); ++i) {
            m[nums[i]] = i;
        }
        for (int i = 0; i < nums.size(); ++i) {
            int t = target - nums[i];
            if (m.count(t) && m[t] != i) {
                res.push_back(i);
                res.push_back(m[t]);
                break;
            }
        }
        return res;
    }
};

LeetCode第167题:给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。
说明:
返回的下标值(index1 和 index2)不是从零开始的。
可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

这道题我上来又是直接暴力解法,所以又是测试用例全部通过,但是timeout,所以另辟蹊径,这里使用双指针法,从两头分别向中间移动,当两个指针位置相加为target的时候,直接返回就行了,如果相加之后的和大于target,需要右指针左移,左指针不动,反之如果相加之后的和小于target,需要左指针右移,右指针不动。直到找到和为target
参考代码

timeout的代码

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int index1 = 0,index2 = 0;
        vector<int> vi = {index1+1,index2+1};
        for(index1 = 0;index1<numbers.size();++index1)
        {
            for(index2 = index1+1;index2<numbers.size();++index2)
            {
                if(numbers[index1] + numbers[index2] == target)
                {
                    vi[0] = index1+1;
                    vi[1] = index2+1;
                    return vi;
                }
            }
        }
        return vi;
    }
};

正常通过的代码

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int l = 0, r = numbers.size() - 1;
        while (l < r) {
            int sum = numbers[l] + numbers[r];
            if (sum == target) return {l + 1, r + 1};
            else if (sum < target) ++l;
            else --r;
        }
        return {};
    }
};

leetcode第15题:给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]

双指针解法,首先对数组中的元素进行排序,由小到大。然后定义三个指针使用三个指针(k<i<j)。固定最小的k在左边i=k+1,j=nums.size()-1。 移动两个指针包夹求解。保存使得nums[i]+nums[j]+nums[k]=0的解。偏大时j左移,偏小时i右移。i和j相遇时,表示以当前k为最小值的解已经全部求得。k++ 进入下一次循环。解决重复解:上面的思路中可能存在重复解,原因是在i,j,k指针在移动时可能会出现重复数字的情况,比如:nums[i]==nums[i+1],这样的移动不考虑进去的话就会产生重复解。

参考代码

class Solution {
public:
    vector<vector<int> > threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int> >res;   
        int _size=nums.size();    
        if(_size<3||nums.front()>0||nums.back()<0)
        return res;
        int i,j,k;
        for(k=0;k<=_size-3;k++){
            if(nums[k]>0)
                break;                        //如果第一个元素都大于0,肯定越加越大,不可能为0了
            if(k>0&&nums[k]==nums[k-1])
                continue;                               //跳过无意义移动
            i=k+1;j=_size-1;
            while(i<j){
                if(nums[i]+nums[j]+nums[k]>0)
                    j--;
                else if(nums[i]+nums[j]+nums[k]<0)
                    i++;
                else{
                    res.push_back({nums[i],nums[j],nums[k]});
                    while(i<j&&nums[i]==nums[i+1])      //跳过无意义移动
                        i++;
                    while(i<j&&nums[j]==nums[j-1])      //同上
                        j--;
                    i++;
                    j--;           
                }
            }
        }
        return res;
    }
};

LeetCode第18题:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。
注意:
答案中不可以包含重复的四元组。

示例:
给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。
满足要求的四元组集合为:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]


和上边的差不多,因为要使用双指针的方法,排序是必须要做。使用四个指针(a<b<c<d)。固定最小的a和b在左边,c=b+1,d=_size-1 移动两个指针包夹求解。保存使得nums[a]+nums[b]+nums[c]+nums[d]==target的解。偏大时d左移,偏小时c右移。c和d相遇时,表示以当前的a和b为最小值的解已经全部求得。b++,进入下一轮循环b循环,当b循环结束后。a++,进入下一轮a循环。 即(a在最外层循环,里面嵌套b循环,再嵌套双指针c,d包夹求解)。解决重复解:上面的解法存在重复解的原因是因为移动指针时可能出现重复数字的情况。所以我们要确保移动指针后,对应的数字要发生改变才行哦。
参考代码

class Solution{
    public: 
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        vector<vector<int> > res;
        if(nums.size()<4)
        return res;
        int a,b,c,d,_size=nums.size();
        for(a=0;a<=_size-4;a++){
            if(a>0&&nums[a]==nums[a-1]) continue;      //确保nums[a] 改变了
            for(b=a+1;b<=_size-3;b++){
                if(b>a+1&&nums[b]==nums[b-1])continue;   //确保nums[b] 改变了
                c=b+1,d=_size-1;
                while(c<d){
                    if(nums[a]+nums[b]+nums[c]+nums[d]<target)
                        c++;
                    else if(nums[a]+nums[b]+nums[c]+nums[d]>target)
                        d--;
                    else{
                        res.push_back({nums[a],nums[b],nums[c],nums[d]});
                        while(c<d&&nums[c+1]==nums[c])      //确保nums[c] 改变了
                            c++;
                        while(c<d&&nums[d-1]==nums[d])      //确保nums[d] 改变了
                            d--;
                        c++;
                        d--;
                    }
                }
            }
        }
        return res;
    }
};

LeetCode第26题:给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。

使用双指针,一个快指针在前,一个慢指针在后,如果两个指针指向的数一样,则快指针加1,如果两个指针指向的数不一样,则快指针和慢指针都加1,加1之后同时让慢指针的那个位置的数字改为快指针指向的那个数字。 返回的长度就是慢指针指向的位置加1.

参考代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) 
    {
        int pre = 0, cur = 0, n = nums.size();  //pre是慢指针,cur是快指针
        while(cur < n)
        {
            if(nums[pre] == nums[cur])
            {
                cur++;
            }
            else 
            {
                nums[++pre] = nums[cur++];
            }
        }
        return nums.empty()? 0:pre+1;
    }
};

LeetCode第27题:给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。

这道题和上面的那道题差不多,还是原地修改,我们就用这个数组,从头开始循环判断当前值是否是val,不是的话就放下来,是的话就继续往后循环。并不用双指针来解决了。

参考代码

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i = 0 , j =0;
        for (i = 0;i<nums.size();++i) {
            if(nums[i] != val){
                nums[j++] = nums[i];
            }
        }
        return nums.empty()?0:j;
    }
};

Leetcode53题:给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

这道题我的想法就是暴力解法,设置一个变量max,用来记录连续子数组的最大和,从数组第一个元素开始,往后加,如果比当前的max大,就更新max,否则就继续往后加。然后第二遍从数组的第二个元素开始再往后加,以此类推,最后得到的max就是最大和。
参考代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max = INT_MIN;//必须要先把max设置为编译器中定义的最小值
        int sum = 0; //用来记录和,然后和max进行比较用的
        int i = 0,j = 0;
        for (i = 0;i<nums.size();++i) {
            sum = 0;//这里再进入这层循环的时候要先把sum置为0
            for (j = i;j<nums.size();++j) {
                sum = sum + nums[j];
                if(sum > max){
                    max = sum;
                }
            }
        }
        return nums.empty()?0:max;
    }
};

Leetcode第35题:给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:

输入: [1,3,5,6], 2
输出: 1
示例 3:

输入: [1,3,5,6], 7
输出: 4
示例 4:

输入: [1,3,5,6], 0
输出: 0

这道题很简单了,分两个阶段进行。先判断数组中有没有这个元素,有的话,返回索引值,没有的话,进行第二个阶段,将他插到数组里边去。只需要从头开始循环判断这个值是否比当前的值小,小的话说明就插在这个位置了,如果一直到最后都没有比他大的,说明就插在最后一个地方,返回这个值就可以了。

参考代码

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int i;
        for(i = 0;i<nums.size();++i)
        {
            if(nums[i] == target)
            {
                return i;
            }
        }
        for(i = 0;i<nums.size();++i)
        {
            if(target < nums[i])
            {
                return i;
            }
            if(i == nums.size()-1)
            {
                return i+1;
            }
        }
        return 0;
    }
};

Leetcode第66题:给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外,这个整数不会以零开头

示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

示例 2:
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

这个题解法就是一层循环遍历数组,在数组的最后的那个数字加1,如果这个数字不是9,就把他加1 返回数组,如果是9,就把他置0,进行第二层循环,判断倒数第二个数是不是9,以此类推。最后如果遍历完成数组的第一个数是0,这时候就应该在数组的最前面插入一个1。

参考代码

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        for(int i = digits.size() - 1; i>=0;--i)
        {
            if(digits[i] < 9)
            {
                digits[i] += 1;
                return digits;
            }      
            else 
            {
                digits[i] = 0;
            }
        }
        if (digits.front() == 0) 
            digits.insert(digits.begin(), 1);
        return digits;
    }
};

LeetCode第88题:给定两个有序整数数组 nums1 和 nums2,将nums2合并到nums1中,使得num1成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]

因为nums1有足够的空间,且num1的大小为m,所以我先把num2的元素拷贝到num1元素的末尾,然后在将num1进行sort排序

参考代码

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = 0;
        for(i = 0;i<n;++i)
        {
            nums1[i+m] = nums2[i];
        }
        sort(nums1.begin(),nums1.end());
    }
};

Leetcode第121题:给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。

示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。


这就是在算数组后面的元素减去前面的元素,什么时候他的差是最大的。我用暴力解法,定义一个变量max,表示最大利润,定义一个sub变量,表示差值,然后双层for循环,第一层固定为某个元素,第二层就用这个元素后面的减去这个元素得到sub,如果sub大于max,则更新max。最后返回max。注意考虑数组为空的情况
参考代码

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

LeetCode第122题:给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润=5-1=4后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。


这个问题就是如果后一天的价钱比前一天的高(这两天是紧挨着的),就出售,以此类推即可
参考代码

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


未完,待续……

3、字符串

Leetcode第3题:给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。


使用滑动窗口法,使用双指针,一个快指针,一个慢指针,再维护一个变量,用来返回他的最长的长度。再定义一个容量256的数组,下标对应的的就是ASCII码。初始让快指针指向-1,慢指针指向0,向前滑动,具体还是看源代码比较清楚。
参考代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int freq[256] = {0};//记录字符串中这个元素出现的个数
        int l = 0, r = -1; //滑动窗口为s[l...r]
        int res = 0;

        //l为左指针,r为右指针

        // 整个循环从 l == 0; r == -1 这个空窗口开始
        // 到l == s.size(); r == s.size()-1 这个空窗口截止
        // 在每次循环里逐渐改变窗口, 维护freq, 并记录当前窗口中是否找到了一个新的最优值

        //数组下标从0开始,所以假设字符串s长度5的话,s[4]就已经是最后一个字母了
        while(l < s.size()){
            if(r + 1 < s.size() && freq[s[r+1]] == 0){//二者同时成立才执行if中的语句
                r++;
                freq[s[r]]++;
            }else {   //r已经到头 || freq[s[r+1]] == 1
                freq[s[l]]--;
                l++;
            }
            res = max(res, r-l+1);
        }
        return res;
    }
};

leetcode第7题:给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。

示例 1:
输入: 123
输出: 321

示例 2:
输入: -123
输出: -321

示例 3:
输入: 120
输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231,  231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。


参考代码

class Solution {
public:
    int reverse(int x) {
        int res = 0;
        while (x != 0) {
            if (abs(res) > INT_MAX / 10) return 0;
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
};

leetcode第9题:判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
示例 1:
输入: 121
输出: true

示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶:你能不将整数转为字符串来解决这个问题吗?

方法就是将数字转成字符串,利用tostring函数,定义两个字符串变量,一个是s,就是整数的正序,再定义一个s2,一开始也是整数的正序,然后我们对它进行逆转,然后判断s2和s的各个位是否相等

参考代码

class Solution {
public:
    bool isPalindrome(int x) {
        string s = to_string(x);
        cout << s << endl;
        string s2 = to_string(x);
        char tmp;
        int l = 0,r = s.size()-1;
        for(l=0;l<s.size();l++)
        {
            if(l<r)
            {
                tmp= s[l];
                s[l] = s[r];
                s[r] = tmp;
            }
            r--;
        }
        cout << s << endl;
        for(int i = 0;i<s.size();++i)
        {
            if(s[i] != s2[i])
            {
                return false;
            }
        }
        return true;
    }
};

leetcode第28题:实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回  -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:
当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。
对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

这道题让我们在一个字符串中找另一个字符串第一次出现的位置,那首先要做一些判断,如果子字符串为空,则返回0,如果子字符串长度大于母字符串长度,则返回 -1。然后开始遍历母字符串,这里并不需要遍历整个母字符串,而是遍历到剩下的长度和子字符串相等的位置即可,这样可以提高运算效率。从母字符串的第一个位置开始,往后判断是否后面的字母和子字符串相等,相等则继续,反之则break。进行第二次循环,母字符串的第二个字母,往后判断,以此类推
参考代码

class Solution {
public:
    int strStr(string haystack, string needle)
    {
        int i,j;
        if(haystack.size()<needle.size())
        {
            return -1;
        }
        if(needle == "")
        {
            return 0;
        }
        for(i=0;i<=haystack.size()-needle.size();++i)
        {
            for(j = 0;j<needle.size();++j)
            {
                if(haystack[i+j]!=needle[j])
                {
                    break;
                }
            }
            if(j==needle.size())
            {
                return i;
            }
        }
        return  -1;
    }
};

leetcode第43题:给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
说明:

num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头,除非是数字 0 本身。
不能使用任何标准库的大数类型(比如 BigInteger)或直接将输入转换为整数来处理。


这道题让我们求两个字符串数字的相乘,输入的两个数和返回的数都是以字符串格式储存的,这样做的原因可能是这样可以计算超大数相乘,可以不受 int 或 long 的数值范围的约束,那么该如何来计算乘法呢,小时候都学过多位数的乘法过程,都是每位相乘然后错位相加,那么这里就是用到这种方法,举个例子,比如 89 x 76,那么根据小学的算术知识,不难写出计算过程如下:

    8 9  <- num2
    7 6  <- num1
-------
    5 4
  4 8
  6 3
5 6
-------
6 7 6 4

参考代码

class Solution {
public:
    string multiply(string num1, string num2) {
        string res = "";
        int m = num1.size(), n = num2.size();
        vector<int> vals(m + n);
        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                int mul = (num1[i] - '0') * (num2[j] - '0');
                int p1 = i + j, p2 = i + j + 1, sum = mul + vals[p2];
                vals[p1] += sum / 10;
                vals[p2] = sum % 10;
            }
        }
        for(int val = 0;val<vals.size();++val)//for循环把vals中的内容放到res中
        {
            if (!res.empty() || vals[val] != 0)//这里这句话的意思就是前面的数是0的话,就不要放到res中了
            {
                res.push_back(vals[val] + '0');
            }
        }
        
        return res.empty() ? "0" : res;
    }
};

4、链表

5、树

6、栈和队列

7、查找和排序

8、贪心算法

9、回溯算法

10、动态规划

11、循环和递归

Last modification:February 7th, 2020 at 09:22 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment

2 comments

  1. gwefd Google Chrome 78.0.3904.108 Windows 7 中国 广西 桂林

    不降权单号网 不降权空包 快递代发www.uudanhaowang.com

  2. yhm Google Chrome 78.0.3904.108 Windows 7 中国 广西 桂林

    空包代发、一件代发快递就发www.danhw.com