专栏首页落影的专栏程序员进阶之算法练习(四十九)LeetCode

程序员进阶之算法练习(四十九)LeetCode

正文

题目1.两数之和

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

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

题目解析: 先不考虑复杂度,直接两个for循环,对于每个数字nums[i],寻找target-nums[i]是否也在数组; 这样的时间复杂度为O(N^2),可以牺牲一些空间来换取更快的速度:比如说把已经出现过的数字用hash表直接存下来,这样下次用hash表直接循环该数字是否存在。 题目的要求还要输出数组下标,那么可以用hash表的值来存数组下标。

class Solution {
    unordered_map<int, int> mp;
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        mp.clear();
        vector<int> ans;
        
        for (int i = 0; i < nums.size(); ++i) {
            if (mp[target - nums[i]]) {
                ans.push_back(i);
                ans.push_back(mp[target - nums[i]] - 1);
                break;
            }
            mp[nums[i]] = i + 1;
        }
        return  ans;
    }
}leetcode;

2.整数反转

题目链接 题目大意: 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。

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

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

示例 3: 输入: 120 输出: 21

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

题目解析: 将负号单独拿出来考虑,只考虑整数的翻转。

因为最终结果可能超过int范围,那么可以用long long来处理。

class Solution {
public:
   int reverse(int x) {
       lld ret = 0, flag = x < 0 ? -1 : 1;
       lld tmp = abs(x), sz = 1;
       while (tmp) {
           ret = tmp % 10 + ret * 10;
           tmp /= 10;
       }
       lld intLeft = -(1LL << 31), intRight = (1LL << 31) - 1;
       if (ret < intLeft || ret > intRight) {
           ret = 0;
       }
       return (int)ret * flag;
   }
}leetcode;

注意: 1在位移的时候,是按int来处理的,需要改成1LL;

3.字符串转换整数 (atoi)

题目链接 题目大意: 请你来实现一个 atoi 函数,使其能将字符串转换成整数。 首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。接下来的转化规则如下: 如果第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字字符组合起来,形成一个有符号整数。 假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成一个整数。 该字符串在有效的整数部分之后也可能会存在多余的字符,那么这些字符可以被忽略,它们对函数不应该造成影响。 注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换,即无法进行有效转换。 在任何情况下,若函数不能进行有效的转换时,请返回 0 。

提示: 本题中的空白字符只包括空格字符 ' ' 。 假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围,请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1: 输入: "42" 输出: 42

示例 2: 输入: " -42" 输出: -42 解释: 第一个非空白字符为 '-', 它是一个负号。 我们尽可能将负号与后面所有连续出现的数字组合起来,最后得到 -42 。

示例 3: 输入: "4193 with words" 输出: 4193 解释: 转换截止于数字 '3' ,因为它的下一个字符不为数字。

示例 4: 输入: "words and 987" 输出: 0 解释: 第一个非空字符是 'w', 但它不是数字或正、负号。 因此无法执行有效的转换。

示例 5: 输入: "-91283472332" 输出: -2147483648 解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 因此返回 INT_MIN (−231) 。

题目解析: 按照题目的要求实现,拆分出来具体的过程。 1、还未进行数字转换的状态,hasConvert=false,此时可以允许空格跳过; 2、遇到+、-、数字之后,hasConvert=true,不允许空格跳过,遇到非数字符号结束转化; 3、符号和数字分开处理,超过int大小分别出来,可以用long long来暂存;

整体代码不复杂。

class Solution {
public:
   int myAtoi(string str) {
       long long ret = 0;
       int flag = 0; // 前置符号, 0表示还没放过, 1 是正数,-1是负数
       bool hasConvert = false;
       for (int i = 0; i < str.length(); ++i) {
           if (str[i] == '-' || str[i] == '+') {
               if (flag) {
                   return flag * ret;
               }
               flag = str[i] == '-' ? -1 : 1;
               hasConvert = true;
           }
           else if (str[i] >= '0' && str[i] <= '9') {
               if (!flag) flag = 1;
               hasConvert = true;
               ret = ret * 10 + str[i] - '0';
               if (flag * ret < -(1LL << 31)) {
                   return -(1LL << 31);
               }
               if (flag * ret > (1LL << 31) - 1) {
                   return (1LL << 31) - 1;
               }
           }
           else if (!hasConvert && str[i] == ' ') {
               continue;
           }
           else {
               return flag * ret;
           }
       }
       return flag * ret;
   }
}lc;

注意: 题目很坑,+1 这种数据也没有说明; +03这种,会认为是数字3,题目的严谨程度较差;

4.回文数

题目链接 题目大意: 判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

示例 1: 输入: 121 输出: true

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

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

题目解析: 将数字转成字符串,然后开始从左右两边开始遍历,如果遇到不一样的字符串则输出false; 如果没有发现不一样的字符,则左右边界递进,则最后输出true;

class Solution {
public:
    bool isPalindrome(int x) {
        char s[20];
        sprintf(s, "%d", x);
        int end = strlen(s) - 1, st = 0;
        while (st < end) {
            if (s[st] != s[end]) {
                return false;;
            }
            ++st;
            --end;
        }
        return true;
    }
}leetcode;

思考: 如果是要在字符串中找出最长的回文串呢?

5.最长公共前缀

题目链接 题目大意: 编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""。

示例 1: 输入: ["flower","flow","flight"] 输出: "fl"

示例 2: 输入: ["dog","racecar","car"] 输出: ""

解释: 输入不存在公共前缀。 说明: 所有输入只包含小写字母 a-z 。

题目解析: 前缀和,直接for循环遍历。

class Solution {
public:
   string longestCommonPrefix(vector<string>& strs) {
       string ret;
       while (true && strs.size()) {
           for (int i = 0; i < strs.size(); ++i) {
               if (strs[i].size() < ret.length() + 1) {
                   return ret;
               }
               if (i > 0 && strs[i][ret.length()] != strs[0][ret.length()]) {
                   return ret;
               }
           }
           ret.push_back(strs[0][ret.length()]);
       }
       return ret;
   }
}leetcode;

注意: vector为空的情况。

总结

题目1,需要用hash来降低复杂度,unordered_map是很不错的hash选项; 题目2,反过来计算整数即可,边界问题是int范围,改一改就是很不错的题目; 题目3,这是一道题意比较复杂的模拟题,但是拆分出几点规则之后,代码还是比较清爽; 题目4,直接转成字符串,走字符串匹配;(思考题 O(N)回文串算法-Manacher) 题目5,直接遍历计算,算法的复杂度也没有太多优化空间;

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 程序员进阶之算法练习(四十八)LeetCode

    题目链接 题目大意: 给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。 ...

    落影
  • 程序员进阶之算法练习(十九)

    前言 这周很忙,但是越忙的时候反而越喜欢抽空做算法题。 欢迎关注algorithm文集。 这次A、B、C都是很合适的面试题。 正文 A. Memory ...

    落影
  • 程序员进阶之算法练习(四十四)

    题目链接 题目大意: 给出整数x,求两个整数a和b,满足: ???(?,?)+???(?,?)=? . GCD是最大公约数; LCM是最小公约数;

    落影
  • 程序员进阶之算法练习(十四)

    前言 坚持做算法练习对开发的好处是抽象能力变强,拿到一个需求能很快对其进行抽象,然后再用学过的设计模式相关知识进行整理,最后用代码实现。 最大的好处在于:对...

    落影
  • 程序员进阶之算法练习(二十九)

    落影
  • 程序员进阶之算法练习(三十四)LeetCode专场

    LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 1、2、3题都是Medium的难度,大概是头条的面试题水准; 4、5题是Hard...

    落影
  • 程序员进阶之算法练习(二十四)

    前言 已经有三个月未更新算法文章,大厂工作环境是步步紧逼的,使得所有的人越来越忙碌。余下的学习时间,要用于技术预研、知识面开阔、底层原理理解等等,慢慢算法只能占...

    落影
  • 程序员进阶之算法练习(四十二)

    题目链接 题目大意: n个学生参加测试,一共有m道题,每道题的答案可能是(A, B, C, D , E)中的一个; m道题分别有?1,?2,…,??,共m...

    落影
  • 程序员进阶之算法练习(四十七)

    题目链接 题目大意: 给出一个整数1~n的排列。 接下来有m个询问,每个询问包括 l, r, x。 (l <= x <= r) [l, r]区间内的数字...

    落影

扫码关注云+社区

领取腾讯云代金券