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

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

正文

题目1.两数相加

题目链接 题目大意: 给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。 如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例: 输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807

题目解析: 经典面试题。 用链表加法,注意进位的考虑,以及边界情况。

class Solution {
public:
   ListNode* addTwoNumbers(ListNode* node1, ListNode* node2) {
       if (!node1) {
           return node2;
       }
       if (!node2) {
           return node1;
       }
       ListNode *cur = NULL, *head = NULL;
       int addition = 0;
       while (node1 || node2) {
           int sum = addition;
           addition = 0;
           if (node1) {
               sum += node1->val;
               node1 = node1->next;
           }
           if (node2) {
               sum += node2->val;
               node2 = node2->next;
           }
           if (sum >= 10) {
               ++addition;
               sum -= 10;
           }
           if (!cur) {
               cur = new ListNode(sum);
               head = cur;
               cur->next = NULL;
           }
           else {
               cur->next = new ListNode(sum);
               cur = cur->next;
               cur->next = NULL;
           }
       }
       if (addition) {
           cur->next = new ListNode(addition);
           cur = cur->next;
           cur->next = NULL;
       }
       return head;
   }
};

题目2.无重复字符的最长子串

题目链接 题目大意: 给出一个字符串str,求出str中最长子串的长度,要求子串里没有重复的字符。

样例: Example 1: Input: "abcabcbb" Output: 3 最长子串是abc,长度是3;

Example 2: Input: "bbbbb" Output: 1 最长子串是b,长度是1;(bb的话出现重复的b)

题目解析: 如果没有重复字符的要求,那么str的最长子串就是自己; 基于此要求,我们考虑从左到右遍历字符串求subStr的时候,如果遇到某个字符subStr不存在,那么便把它加入subStr; 如果遇到某个字符是subStr已经有的,那么便把subStr已出现的字符的位置开始,左边的字符全部不要即可。 比如说对于题目的样例1,当我们枚举a/b/c的时候,都是直接加入subStr,得到abc; 当遇到第四个字符a时,把a去掉得到bc,再加入a,得到bca; 重复这个过程到字符串末尾,记录期间每个字符加入后的长度,可以得到满足要求的最长子串长度。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int vis[257] = {0};
        int maxLen = 0, cur = 0;
        for (int i = 0; i < s.length(); ++i) {
            while (vis[s[i]]) {
                vis[s[cur]] = 0;
                ++cur;
            }
            vis[s[i]] = 1;
            maxLen = max(maxLen, i - cur + 1);
        }
        return maxLen;
    }
};

题目3.Z 字形变换

题目链接 题目大意: 将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时,排列如下:

 L   C   I   R
 E T O E S I I G
 E   D   H   N

之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"LCIRETOESIIGEDHN"。

请你实现这个将字符串进行指定行数变换的函数:

string convert(string s, int numRows); 示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3 输出: "LCIRETOESIIGEDHN" 示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4 输出: "LDREOEIIECIHNTSG" 解释:

 L     D     R
 E   O E   I I
 E C   I H   N
 T     S     G

题目解析: 方法1: 找规律,模拟;

方法2: vector暂存; 去掉x坐标的影响,直接计算y的变化。 trick就是nums=1的特殊判断。

这里使用方法2,代码较为直接:

const int N = 50000;

class Solution {
public:
   string ans[N];
   string convert(string s, int numRows) {
       if (numRows <= 1) {
           return s;
       }
       string ret;
       for (int i = 0; i < numRows; ++i) {
           ans[i].clear();
       }
       int y = 0, gap = 1;
       for (int i = 0; i < s.length(); ++i) {
           ans[y].push_back(s[i]);
           y += gap;
           if (y < 0) {
               y = 1;
               gap = 1;
           }
           else if (y >= numRows) {
               y = numRows - 2;
               gap = -1;
           }
       }
       
       for (int i = 0; i < numRows; ++i) {
           ret += ans[i];
       }
       return ret;
   }
   
}leetcode;

题目4.盛最多水的容器

题目链接 题目大意: 给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 说明:你不能倾斜容器,且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

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

题目解析: 暴力,O(N^2); 递增序列优化,常数优化; 面对1,2,3,4这种bad case,还是一样;

一种O(N)的解法如下: 对于数组height[0 ~ (n-1)],假设最左边的数是x,最右边的数是y; 我们容易知道x和y组合形成的池子是width * min(x,y); 假如x<y,那么对于节点x而言,选择节点y组成形成池子已经是最优解;(因为width * height的公式中,width已经是数组最大宽度,height已经是x的最大值) 那么保存完这个计算结果,实际上x已经可以抛弃!这样便减少了(n-1)次运算! 重复以上过程,可以使得算法时间复杂度为O(N);

class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans = 0;
        int left = 0, right = height.size() - 1;
        while (left < right) {
            ans = max(ans, (right - left) * min(height[left], height[right]));
            if (height[left] < height[right]) {
                ++left;
            }
            else {
                --right;
            }
        }
        return ans;
    }
    
}leetcode;

总结

题目1 经典面试题,用来考察候选人的代码功底; 题目2 经典扫描线题目,从左到右遍历数组,记录一些状态以求最优解; 题目3 思维比较敏捷可以用找规律的方式,如果只是为了解决问题可以多用一些空间,直接去掉x坐标的影响; 题目4 也是比较常见的一类题目,暴力的做法比较简单,但是需要思考最优解。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    题目链接 题目大意: 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以...

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

    前言 最近在接触新知识,也是选择2017年的方向。 其他文集更新会放缓,没有学习就没有心得,肚中无墨就无从下笔。 但是算法练习还是挺好玩的,欢迎关注algo...

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

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

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

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

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

    前言 四道题,分别锻炼哈希、贪心、贪心+排序、二分四个能力。 第一题较为简单,后续的题目都需要一定的基础。 贪心是最基础的能力,codeforce有专门的 ...

    落影
  • 程序员进阶之算法练习(三十四)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]区间内的数字...

    落影

扫码关注云+社区

领取腾讯云代金券