标签归档:LeetCode

LeetCode-118-119-121-141-155

 

118 Pascal’s Triangle119 Pascal’s Triangle II121 Best Time to Buy and Sell Stock141 Linked List Cycle155 Min Stack 均较为简单,合并完成解题报告。

118 Pascal’s Triangle

概述

帕斯卡三角绘制。

分析

所谓帕斯卡三角,也叫做杨辉三角(也是贾宪三角……),解释可以在维基百科上得知。

那么只需按照定义,逐层生成即可。

解法

119 Pascal’s Triangle II

概述

只绘制杨辉三角的某行。

分析

属于118 Pascal’s Triangle的扩展题目,可以考虑直接复用118的代码,生成后返回。

问题在于时间复杂度过高。后续可以优化。

解法

121 Best Time to Buy and Sell Stock

概述

给出股价列表,找出最大的获利。

分析

可以想到,获利最大,即买入价最低,卖出价最高。

每个时间段都会有最高的卖出价,在数组中,一个区间的最大值是一定的。从后向前遍历,如果当前值不大于当前位置之后的最大值,那么当前值开始的最大值,仍然是当前值之后的最大值。反之则是当前值。

只需要针对价格,再次遍历数组,获得每个位置的数字的差值,即可知道在哪一位置时获利最大,即差值最大。

解法

141 Linked List Cycle

概述

判断单向链表中是否存在环。

分析

简单的做法,用hash存储当前的节点指针值,如果再次遇到这一指针,说明有环。

但是目前还没有做出不需要额外空间的做法。

解法

155 Min Stack

概述

用单向链表实现一个可以直接获得最小值的栈。

分析

栈的特点是先进后出。

push 操作,可以看做是更换首节点的操作。同时,由于要直接获得最小值,可以入栈时判断是否比当前的最小值更小,由此可以完成更新操作。

pop 操作,可以看做是删除首节点的操作。同样的,如果pop的数值比小于等于最小值,需要遍历链表找到最小值。

如是,随时获得栈最小值的时间复杂度是O(1)

解法

LeetCode-66-67-83-217

 

标题中提到的4道题目都较为简单,合并到一起写解题记录。

66 Plus One

概述

Plus One 即给定以数组形式表示各位的数字,将这一数字加1的结果输出为数组即可。

分析

这一题主要处理的是常规的运算的进位问题,同时,由于数组并没有确定数字为int,那么位数不定,需要按照正常的竖式运算的步骤进行。

当计算发现最高位需要进位时,申请更大的空间,返回结果。

解法

67 Add Binary

概述

Add Binary66 Plus One 很相似,只不过由十进制数变为了二进制数的加法。

输入是字符串,输出也是字符串。

分析

二进制加法,仍然按照竖式计算的方式进行即可。无需多说。

解法

83 Remove Duplicates from Sorted List

概述

Remove Duplicates from Sorted List 即在已排序的单向链表中完成去重。

分析

链表已排序,去重工作变得相当容易,只需要判断当前节点的值是否等于上一节点的值,如果等于则将链表当前的下一指针指向下下一个节点,周而复始。

解法

217 Contains Duplicate

概述

Contains Duplicate 判断数组中是否有重复的值。

分析

使用Hash完成这一判断最为容易,判断一个值是否在 HashMap 中存在即可。

解法

LeetCode-24-26-27

 

Swap Nodes in PairsRemove Duplicates from Sorted ArrayRemove Element 均为简单题,合并到一起写解题思路。

24 Swap Nodes in Pairs

概述

Swap Nodes in Pairs 即是将相邻的两个节点交换形成新的链表,要求在于不能修改值,只能做链表节点操作。

对于空间复杂度上也要要求,只能在 O(1) 这个复杂度上完成。

分析

对于链表操作,无需多说,这里需要注意的地方在于:

  • 第一组元素(前2个)的第二个节点需要变成新链表的首节点
  • 在循环中,前一组的第一个节点要连接的是下一组的第二个节点

明确上述两个关键步骤之后,需要做的就是申请变量暂存目前处理节点的位置以及记录上一组节点的第一个节点。

解法

26 Remove Duplicates from Sorted Array

概述

Remove Duplicates from Sorted Array 即通过数组元素移动操作,去除数组中重复的数字,并且返回不重复数字的个数。

分析

本题的需要注意,单纯返回非重复数字的长度是不够的,由于空间复杂度也有要求,需要在原数组中通过移位等操作将重复元素删除。

在是已经排序了的数组的情况下,相同数字必然是连续的,只需要遍历一遍数字,遇到相同的数字,将下一数字之后的数组元素前移即可。

下一次循环开始的

解法

27 Remove Element

概述

Remove Element 同样是remove,和26的区别是给定的数字进行去除。

分析

Remove Duplicates from Sorted Array 的解法类似,不同的是考虑终止条件的时候需要注意删除了元素之后相当于产生了一个数组,长度是发生了变化,循环时需要考虑这一因素。

解法

其他

26 与 27 逐个搬迁并不是最佳解法,还有优化的空间。

LeetCode-9

title: LeetCode-9

date: 2016-04-20 23:13:59

categories: Try

tags: LeetCode

概述

Palindrome Number 判断文字是否是回文,输出布尔值。

分析

作为一道 Easy 的题目,看起来并不是特别麻烦,不过这题要求无需增加附加的空间复杂度。

题目要求判断是否为回文数,那么负数肯定不是回文数,因为负数带有符号位。

从字符串的角度来看,回文只需判断反转之后是否相同即可,那么针对数字亦可以使用这一方法。

考虑到数字反转之后会出现溢出的情况,而正数溢出之后在 Java 中的处理方式则是变为一个负数(参见 SO 上的问题 How does Java handle integer underflows and overflows and how would you check for it?),那么反转后变为负数的数字自然不是一个回文数了,因为反转之后在非负整数的范围内显然这个数字不存在。

不新增变量的情况下,只能通过递归来解决问题了。

解法

public class Solution {
    public static int len(int v) {
        return (v == 0 ? 0 : 1 + len(v / 10));
    }

    public static int reverse(int x) {
        if (x < 10) {
            return x;
        }

        return reverse(x / 10) + (x % 10) * (int)Math.pow(10, len(x) - 1);
    }

    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }

        if (x == 0) {
            return true;
        }

        return x == reverse(x);
    }
}

LeetCode-3

 

概述

今天份的LeetCode题目 Longest Substring Without Repeating Characters 也是一道 Medium 的题目。

大意即找出给定字符串中的连续最长非重复子序列的长度。

分析

首先,字符串连续的前提之下,若在位置 nm (m>n)出现了重复的字符,n位置以及之前的字符是不能再继续算入连续的非重复字符串的,所以,这时候统计的字符串的起始位置要变为 n + 1 位置下的字符。

在出现重复时,判断当前已经连续的非重复字符的个数是否已经大于已记录的最长字符串的长度,如大于则替换之。

最后返回计算出的结果即可。

这一方法只需一次遍历字符串即可得知最大的长度,由于使用了HashMap存储最长子串中的字符与下标的对应关系,时间复杂度为O(n)

解法