lintcode专题
LintCode 恢复IP地址
给一个由数字组成的字符串。求出其可能恢复为的所有IP地址。 样例 给出字符串 “25525511135”，所有可能的IP地址为： [ “255.255.11.135”, “255.255.111.35” ] 和LintCode 电话号码的字母组合类似。 首先找到合适的位数组合。一共4位，每一位的长度要大于等于1，小于等于3，且4位和为字符串长度. 另外要判断每1 位的数字组合，是
LintCode 最长无重复字符的子串
给定一个字符串，请找出其中无重复字符的最长子字符串。 例如，在”abcabcbb”中，其无重复字符的最长子字符串是”abc”，其长度为 3。 对于，”bbbbb”，其无重复字符的最长子字符串为”b”，长度为1。 从左向右扫描，遇到重复的字符时，从前面出现该字符的位置的下一个字符开始，重新扫描，直到扫描到最后。例如： abcbdefgdk 字符abcbdefgdk下标0123456789
LintCode 最长回文子串
给出一个字符串（假设长度最长为1000），求出它的最长回文子串，你可以假定只有一个满足条件的最长回文串。 样例 给出字符串 “abcdzdcab”，它的最长回文子串为 “cdzdc”。 挑战 O(n2) 时间复杂度的算法是可以接受的，如果你能用 O(n) 的算法那自然更好。 第一次AC的连O（n2）都不是的，是O（n3），遍历所有子串。代码如下： class Solution:"""@
LintCode 电话号码的字母组合
Given a digit string excluded 01, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. 样例 给定 “
LintCode 通配符匹配
参考资料 判断两个可能包含通配符“？”和“*”的字符串是否匹配。匹配规则如下： ‘?’ 可以匹配任何单个字符。 ‘*’ 可以匹配任意字符串（包括空字符串）。 两个串完全匹配才算匹配成功。 函数接口如下: bool isMatch(const char *s, const char *p) 一些例子： isMatch(“aa”,”a”) → false isMatch(“aa”,”
LintCode 落单的数 ⅡⅢ
参考资料 落单的数Ⅱ 给出3*n + 1 个的数字，除其中一个数字之外其他每个数字均出现三次，找到这个数字。 样例 给出 [1,1,2,3,3,3,2,2,4,1] ，返回 4 落单的数Ⅲ 给出2*n + 2个的数字，除其中两个数字之外其他每个数字均出现两次，找到这两个数字。 样例 给出 [1,2,2,3,4,4,5,3]，返回 1和5 利用位运算操作。 Ⅱ ： int类型有
LintCode 寻找缺失的数
给出一个包含 0 .. N 中 N 个数的序列，找出0 .. N 中没有出现在序列中的那个数。 样例 N = 4 且序列为 [0, 1, 3] 时，缺失的数为2。 题目说的不是很清楚，意思就是如下： 给定给一个序列，有N个数，对于{0,1,2，……N}这个N+1个数的序列中，少了哪一个数？ 这道题和LintCode上另一道题类似——《落单的数》 给出2*n + 1 个的数字，除其中一
LintCode 吹气球
有n个气球，编号为0到n-1，每个气球都有一个分数，存在nums数组中。每次吹气球i可以得到的分数为 nums[left] * nums[i] * nums[right]，left和right分别表示i气球相邻的两个气球。当i气球被吹爆后，其左右两气球即为相邻。要求吹爆所有气球，得到最多的分数。 样例 给出 [4, 1, 5, 10] 返回 270 nums = [4, 1, 5, 10]
跟LintCode的算法题杠上了（1334旋转数组）
题目 给定一个数组，将数组向右移动k步，其中k为非负数。 输入: [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转1步: [7,1,2,3,4,5,6] 向右旋转2步: [6,7,1,2,3,4,5] 向右旋转3步: [5,6,7,1,2,3,4] 输入: [-1,-100,3,99], k = 2 输出: [3,99,-1,-100]
跟LintCode的算法题杠上了（1451到最近的人的最大距离）
题目 在一排座位（ seats）中，1 代表有人坐在座位上，0 代表座位上是空的。 至少有一个空座位，且至少有一人坐在座位上。 亚历克斯希望坐在一个能够使他与离他最近的人之间的距离达到最大化的座位上。 返回他到离他最近的人的最大距离。 1 <= seats.length <= 20000 seats 中只含有 0 和 1，至少有一个 0，且至少有一个 1。 样例 1: 输入：[1,0
跟LintCode的算法题杠上了（1728卡牌分组）
题目 给定一副牌，每张牌上都写着一个整数。 此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组： 每组都有 X 张牌。 组内所有的牌上都写着相同的整数。 仅当你可选的 X >= 2 时返回 true。 1 <= deck.length <= 10000 0 <= deck[i] < 10000 示例1 输入: [1,2,3,4,4,3,2,1] 输出: tr
跟LintCode的算法题杠上了（2424输出杨辉三角）
题目 你的代码需要从标准输入流（控制台）中读入一个正整数 n，然后计算出前 n 行的杨辉三角并将结果打印到标准输出流（控制台）中。 样例 评测机会将整个项目的代码编译为一个可执行的 Main 程序，并按照这样的方式执行你的代码 Main。你的代码需要从标准输入流（控制台）中读入数据 n，并将前 n 行的杨辉三角打印到标准输出流（控制台）中。输出格式见样例。 样例一 * 你的代码需要从标准
几个字符串相关的题目，来自LeetCode和LintCode
这个是Leetcode上关于字符串的题目，要求实现一个 strstr 函数，搜寻子串在源字符串中的位置，如果没有在源字符串中则返回 -1. 链接如下： https://leetcode.com/problems/implement-strstr/ C++实现如下： class Solution {public:int strStr(string haystack, string need
LintCode 1210 给定一个整数数组，找到所有不同的可能的升序子序列，一个升序子序列的长度至少应为2。
因为数据有重复所以回溯法会给出重复的结果，需要set去重复。 class Solution {public:/*** @param nums: an integer array* @return: all the different possible increasing subsequences of the given array*/set<vector<int>> judge;vecto
LintCode 375 深度复制一个二叉树。 给定一个二叉树，返回一个他的 克隆品 。
解一、返回值在return /*** Definition of TreeNode:* class TreeNode {* public:* int val;* TreeNode *left, *right;* TreeNode(int val) {* this->val = val;* this->left = this->right =
LintCode 570 给一个由 1 - n 的整数随机组成的一个字符串序列，其中丢失了一个整数，请找到它。
情况特殊，考虑逻辑即可 class Solution {public:/*** @param n: An integer* @param str: a string with number from 1-n in random order and miss one number* @return: An integer*/int findMissing2(int n, string &str)
LintCode 778 给定一个m×n的非负矩阵代表一个大洲，矩阵的每个单元格的值代表此处的地形高度，矩阵的左边缘和上边缘是“太平洋”，下边缘和右边缘是“大西洋”。
一、遍历每个点，每个点来一次dfs，结果超时 class Solution {public:/*** @param matrix: the given matrix* @return: The list of grid coordinates*/vector<vector<int>> globalans;vector<vector<int>> pacificAtlantic(vector<ve
LintCode 107 给定字符串 s 和单词字典 dict，确定 s 是否可以分成一个或多个以空格分隔的子串，并且这些子串都在字典中存在。
代码一、使用递归算法，超时 class Solution {public:/** @param s: A string* @param dict: A dictionary of words dict* @return: A boolean*/bool wordBreak(string &s, unordered_set<string> &dict) {// write your code h
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结尾的