lintcode专题

lintcode Ugly Number II python

Description Ugly number is a number that only have factors 2, 3 and 5. Design an algorithm to find the nth ugly number. The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12... 利用动态规划的思想 de

lintcode 判断一个单链表是否有环及环的链接点

今天又一次做了这个参见的题目，不过是在不想写东西了，随手转载一篇给定一个单链表，只给出头指针h： 1、如何判断是否存在环？ 2、如何知道环的长度？ 3、如何找出环的连接点在哪里？ 4、带环链表的长度是多少？解法： 1、对于问题1，使用追赶的方法，设定两个指针slow、fast，从头指针开始，每次分别前进1步、2步。如存在环，则两者相遇；如不

牛客NC324 下一个更大的数(三)【中等双指针 Java/Go/PHP/C++】参考lintcode 52 · 下一个排列

题目题目链接： https://www.nowcoder.com/practice/475da0d4e37a481bacf9a09b5a059199 思路第一步：获取数字上每一个数，组成数组arr第二步：利用“下一个排列” 问题解题方法来继续作答，步骤：利用lintcode 52 下一个排列的解放方法从后往前找，找到第一对(i,j),i<j，使得 nums[i] < num[j] ,

Lintcode 用递归打印从1到N位的最大整数

题目要求用递归打印从1到N位的最大整数（十进制），如n=2 返回[1,2,…99]. 实际上这道题是想让我们用全排列的思想分别按位进行递归，每位有0-9这十种可能。然而当用python写的时候不好用string类型存储数字，因为字符串不可改变。而用list存储数字的时候是酱紫的[1,9],对应数字19.然后还要对这个再进行处理。所以干脆用最简单的数字，递增递归。（这样栈会爆，因为这是一个大数

Lintcode 合并两个排序的链表

将两个排序链表合并为一个新的排序链表样例给出 1->3->8->11->15->null，2->null，返回 1->2->3->8->11->15->null。递归实现： """Definition of ListNodeclass ListNode(object):def __init__(self, val, next=None):self.val = valself.n

lintcode 前序序列和中序序列构建二叉树

根据前序遍历和中序遍历树构造二叉树. 给出中序遍历：[1,2,3]和前序遍历：[2,1,3]. 返回如下的树: 2 / \ 1 3 """Definition of TreeNode:class TreeNode:def __init__(self, val):self.val = valself.left, self.right = None, None"""class Solu

lintcode 求最长公共子串

给出两个字符串，找到最长公共子串，并返回其长度。这个其实比较简单，因为只要返回最长公共子串的长度就可以了，不用找出他们。PS：如果要是要求返回最长公共子串呢？动态规划，最优子结构if s[i] == t[j], L[i,j] = L[i-1,j-1]+1 if s[i]!=t[j] L[i,j] = 0, 这里是区别于最长公共子序列的，因为L[i,j] 代表以i结尾的s[i]和以j结尾的

lintcode 旋转数组的最小数字

假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。你需要找到其中最小的元素。数组中可能存在重复的元素。想法：二分查找变形，最小数字一定是最大值后面的那个。当[11101],[1,0,1,1,1]时没办法判断，顺序查找。 class Solution { public: /** * @param num: the r

lintcode 空格替换

设计一种方法，将一个字符串中的所有空格替换成 %20 。你可以假设该字符串有足够的空间来加入新的字符，且你得到的是“真实的”字符长度。你的程序还需要返回被替换后的字符串的长度。对于字符串”Mr John Smith”, 长度为 13 替换空格之后的结果为”Mr%20John%20Smith” class Solution {public:/*** @param string: An

lintcode第一题：A + B 问题说起python的数字类型

问题描述给出两个整数 aa 和 bb , 求他们的和。挑战显然你可以直接 return a + b，但是你是否可以挑战一下不这样做？（不使用++等算数运算符）正确答案 __AUTHOR = "tyltr"__DATE = "18-2-28 下午9:27 """"001.给出两个整数a和b, 求他们的和, 但不能使用 + 等数学运算符"""class Solution

lintcode 1650 Legal Article 编程练习（python）

题目描述：给定一篇由大写字母、小写字母、逗号、句号组成的文章，求使文章不合法的字母数。文章不合法有2种情况： 1.句子的第一个字母用了小写。 2.不是单词的首字母用了大写。代码及注解如下： # coding=utf-8class Solution:"""@param s: the article@return: the number of letters that are ill

LintCode_两个整数相除

问题描述：将两个整数相除，要求不使用乘法、除法和 mod 运算符。如果溢出，返回 2147483647 。样例：给定被除数 = 100 ，除数 = 9，返回 11。算法思想：方法一：（这是开始自己想出来的，算法思想简单，缺点是，循环次数多，运行速度慢）如果不能采用乘除运算方法，那么可以采用加减方式，当然还要（1）、注意分类：正正，正负，负正，负负；（2）、溢出问题；

LintCode_字符串查找

问题描述：对于一个给定的 source 字符串和一个 target 字符串，你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在，则返回 -1。样例：如果 source = "source" 和 target = "target"，返回 -1。如果 source = "abcdabcdefg" 和 target = "bcd"，返回 1。算

LintCode_最后一个单词的长度

问题描述：给定一个字符串，包含大小写字母、空格' '，请返回其最后一个单词的长度。如果不存在最后一个单词，请返回 0 。样例：给定 s = "Hello World"，返回 5。注意：一个单词的界定是，由字母组成，但不包含任何的空格。算法思想：因为要检测最后一个单词，因此，要从字符串的最后往前检索。刚开始的没有考虑到该字符串的最后几个字符可能是空格的情况。如果是检

LintCode_尾部的零

问题描述：设计一个算法，计算出n阶乘中尾部零的个数样例：11! = 39916800，因此应该返回 2 算法实现：方法一：这是个数学题，最开始就想到应该检测n阶乘中有多少个5的因子，因此采用一个for循环，遍历2~n的每个数，判断能否被5整除，并且能拆分成多少个5的因子，这种方法非常耗时； public static long trailingZeros(long n

LintCode_合并区间

问题描述：给出若干闭合区间，合并所有重叠的部分。样例：给出的区间列表 => 合并后的区间列表： [ [[1, 3], [1, 6],[2, 6], => [8, 10],[8, 10], [15, 18][15, 18] ]]

LintCode_中位数

问题描述：给定一个未排序的整数数组，找到其中位数。中位数是排序后数组的中间值，如果数组的个数是偶数个，则返回排序后数组的第N/2个数。样例：给出数组[4, 5, 1, 2, 3]，返回 3；给出数组[7, 9, 4, 5]，返回 5 算法：插入排序算法排序； public static int median(int[] nums){if(nums==

lintCode_两个字符串是变位词

问题描述：写出一个函数 anagram(s, t) 去判断两个字符串是否是颠倒字母顺序构成的样例：给出 s= "abcd"，t= "dcab"，返回 true 算法思想： public static boolean anagram(String s,String t){boolean flag=true;//如果s或t为空，或s/t长度为0，或者s与t的

LintCode 2. 尾部的零

这道题，分析如下，1到n的阶乘末尾的0数有多少个,只需要统计出n分别除以5,25,125...等5的整数次幂即可，然后相加就可得到n末尾包含的0的个数。每次5出现首先2,4都比5小，所以对于新出现的5的整数次幂的倍数时，前面肯定已经存在了足够的2使得2*5=10，从而在末尾产生新的0。我的实现过程如下： class Solution {public:/** @para

LintCode- 翻转字符串

翻转字符串给定一个字符串，逐个翻转字符串中的每个单词。样例给出s = “the sky is blue”，返回”blue is sky the” 说明单词的构成：无空格字母构成一个单词输入字符串是否包括前导或者尾随空格？可以包括，但是反转后的字符不能包括如何处理两个单词间的多个空格？在反转字符串中间空格减少到只含一个 //方法一public class Solut

LintCode-翻转链表

翻转链表翻转一个链表样例给出一个链表1->2->3->null，这个翻转后的链表为3->2->1->null 挑战在原地一次翻转完成通过三个链表指向，依次轮转。完成原地一次翻转。 /*** Definition for ListNode.* public class ListNode {*

LintCode- 链表倒数第n个节点

链表倒数第n个节点找到单链表倒数第n个节点，保证链表中节点的最少数量为n。样例给出链表 3->2->1->5->null和n = 2，返回倒数第二个节点的值1. /*** Definition for ListNode.* public class ListNode {* int val;* ListNode next;* ListNode(int val)

LintCode- 最长上升连续子序列

最长上升连续子序列给定一个整数数组（下标从 0 到 n-1， n 表示整个数组的规模），请找出该数组中的最长上升连续子序列。（最长上升连续子序列可以定义为从右到左或从左到右的序列。）样例给定 [5, 4, 2, 1, 3], 其最长上升连续子序列（LICS）为 [5, 4, 2, 1], 返回 4. 给定 [5, 1, 2, 3, 4], 其最长上升连续子序列（LICS）为 [1,

LintCode-有效回文串

有效回文串给定一个字符串，判断其是否为一个回文串。只包含字母和数字，忽略大小写。样例 “A man, a plan, a canal: Panama” 是一个回文。 “race a car” 不是一个回文。注意你是否考虑过，字符串有可能是空字符串？这是面试过程中，面试官常常会问的问题。在这个题目中，我们将空字符串判定为有效回文。挑战 O(n) 时间复杂度，且不占用额

LintCode-比较字符串

比较字符串比较两个字符串A和B，确定A中是否包含B中所有的字符。字符串A和B中的字符都是大写字母样例给出 A = “ABCD” B = “ACD”，返回 true 给出 A = “ABCD” B = “AABC”，返回 false 注意在 A 中出现的 B 字符串里的字符不需要连续或者有序。 public class Solution {/*** @param A :

LintCode-爬楼梯

爬楼梯假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？样例比如n=3，1+1+1=1+2=2+1=3，共有3中不同的方法返回 3 登上第1级：1种登上第2级：2种登上第3级：1+2=3种（前一步要么从第1级迈上来,要么从第2级迈上来）登上第4级：2+3=5种（前一步要么从第2级迈上来,要么从第3级迈上来）登