Lintcode 「阶梯训练——美国大公司」 题解

/ 0评 / 0

String

写出一个函数 anagram(s, t) 判断两个字符串是否可以通过改变字母的顺序变成一样的字符串。 写出一个函数 anagram(s, t) 判断两个字符串是否可以通过改变字母的顺序变成一样的字符串。

比较两个字符串A和B,确定A中是否包含B中所有的字符。字符串A和B中的字符都是 大写字母

对于一个给定的 source 字符串和一个 target 字符串,你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在,则返回 -1

给出一个字符串数组S,找到其中所有的乱序字符串(Anagram)。如果一个字符串是乱序字符串,那么他存在一个字母集合相同,但顺序不同的字符串也在S中。

给出两个字符串,找到最长公共子串,并返回其长度。

给k个字符串,求出他们的最长公共前缀(LCP)

Array

给定一个数组和一个值,在原地删除与值相同的数字,返回新数组的长度。
元素的顺序可以改变,并且对新的数组不会有影响。

给定一个整数数组,找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置

给定一个排序数组,在原数组中删除重复出现的数字,使得每个元素只出现一次,并且返回新的数组的长度。不要使用额外的数组空间,必须在原地没有额外空间的条件下完成。

合并两个排序的整数数组A和B变成一个新的数组。
你可以假设A具有足够的空间(A数组的大小大于或等于m+n)去添加B中的元素。

给一个整数数组,找到两个数使得他们的和等于一个给定的数 target。 你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 0 到 n-1

给定一个整数数组A。
定义B[i] = A[0] * … * A[i-1] * A[i+1] * … * A[n-1], 计算B的时候请不要使用除法。

给出一个无序的整数数组,找出其中没有出现的最小正整数。

给一个包含 n 个整数的数组 S, 找到和与给定整数 target 最接近的三元组,返回这三个数的和。

给出一个有n个整数的数组S,在S中找到三个整数a, b, c,找到所有使得a + b + c = 0的三元组。

给出一个整数数组 nums 和一个整数 k。划分数组(即移动数组 nums 中的元素),使得:

  • 所有小于k的元素移到左边
  • 所有大于等于k的元素移到右边

返回数组划分的位置,即数组中第一个位置 i,满足 nums[i] 大于等于 k

Binary Search

实现 int sqrt(int x) 函数,计算并返回 x 的平方根。

给定一个排序数组和一个目标值,如果在数组中找到目标值则返回索引。如果没有,返回到它将会被按顺序插入的位置。

写出一个高效的算法来搜索 m × n矩阵中的值。

给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组中,返回-1

假设一个旋转排序的数组其起始位置是未知的(比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2)。
你需要找到其中最小的元素。
你可以假设数组中不存在重复的元素。

给出一个整数数组(size为n),其具有以下特点:

  • 相邻位置的数字是不同的
  • A[0] < A[1] 并且 A[n - 2] > A[n - 1]

假定P是峰值的位置则满足A[P] > A[P-1]A[P] > A[P+1],返回数组中任意一个峰值的位置。

代码库的版本号是从 1 到 n 的整数。某一天,有人提交了错误版本的代码,因此造成自身及之后版本的代码在单元测试中均出错。请找出第一个错误的版本号。

假设有一个排序的按未知的旋转轴旋转的数组(比如,0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索,如果在数组中找到目标值返回数组中的索引位置,否则返回-1。

给定一个包含 n 个整数的排序数组,找出给定目标值 target 的起始和结束位置。
如果目标值不在数组中,则返回[-1, -1]

有一些原木,现在想把这些木头切割成一些长度相同的小段木头,需要得到的小段的数目至少为 k。当然,我们希望得到的小段越长越好,你需要计算能够得到的小段木头的最大长度。

Math

Greedy

给出2*n + 1 个的数字,除其中一个数字之外其他每个数字均出现两次,找到这个数字。

给定一个整型数组,找出主元素,它在数组中的出现次数严格大于数组元素个数的二分之一。

在一条环路上有 N 个加油站,其中第 i 个加油站有汽油gas[i],并且从第i个加油站前往第i+1个加油站需要消耗汽油cost[i]
你有一辆油箱容量无限大的汽车,现在要从某一个加油站出发绕环路一周,一开始油箱为空。
求可环绕环路一周时出发的加油站的编号,若不存在环绕一周的方案,则返回-1

给出一组非负整数,重新排列他们的顺序把他们组成一个最大的整数。

给出一个字符串 A, 表示一个 n 位正整数, 删除其中 k 位数字, 使得剩余的数字仍然按照原来的顺序排列产生一个新的正整数。
找到删除 k 个数字之后的最小正整数。

给出一个非负整数数组,你最初定位在数组的第一个位置。   
数组中的每个元素代表你在那个位置可以跳跃的最大长度。    
判断你是否能到达数组的最后一个位置。

给定一个整数数组来表示排列,找出其之后的一个排列。

Linked List

给定一个链表,删除链表中倒数第n个节点,返回链表的头节点。

将两个排序链表合并为一个新的排序链表

给定一个排序链表,删除所有重复的元素每个元素只留下一个。

给定一个单链表和数值x,划分链表使得所有小于x的节点排在大于等于x的节点之前。
你应该保留两部分内链表节点原有的相对顺序。

翻转一个链表

给定一个链表,旋转链表,使得每个节点向右移动k个位置,其中k是一个非负数

给出一个所有元素以升序排序的单链表,将它转换成一棵高度平衡的二分查找树

给出一个链表,每个节点包含一个额外增加的随机指针可以指向链表中的任何节点或空的节点。
返回一个深拷贝的链表。

给定一个链表,判断它是否有环。

给定一个单链表L: L0→L1→…→Ln-1→Ln,
重新排列后为:L0→Ln→L1→Ln-1→L2→Ln-2→…
必须在不改变节点值的情况下进行原地操作。

在 O(n log n) 时间复杂度和常数级的空间复杂度下给链表排序。

Binary Tree

给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的距离。

给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是:一棵二叉树中每个节点的两个子树的深度相差不会超过1。

给定一棵二叉查找树和一个新的树节点,将节点插入到树中。
你需要保证该树仍然是一棵二叉查找树。

给出一棵二叉树,返回其节点值的层次遍历(逐层从左往右访问)

给出一棵二叉树,返回其节点值的前序遍历。

给定一个二叉树,判断它是否是合法的二叉查找树(BST)

前序遍历和中序遍历树构造二叉树

Given a binary search tree and a range [k1, k2], return all elements in the given range.

设计一个算法,并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”,读取文件后重建同样的二叉树被称为“反序列化”。

Search & Recursion

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

给出一个候选数字的set(C)和目标数字(T),找到C中所有的组合,使找出的数字和为T。C中的数字可以无限制重复被选取。

给定一个有向图,图节点的拓扑排序被定义为:

  • 对于每条有向边A--> B,则A必须排在B之前
  • 拓扑排序的第一个节点可以是任何在图中没有其他节点指向它的节点

找到给定图的任一拓扑排序

给出两个单词(start和end)和一个字典,找到从start到end的最短转换序列

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

给定一个含不同整数的集合,返回其所有的子集

给出一个具有重复数字的列表,找出列表所有不同的排列。

给定一个数字列表,返回其所有可能的排列。

Dynamic Programming

现在考虑网格中有障碍物,那样将会有多少条不同的路径?
网格中的障碍和空位置分别用 1 和 0 来表示。

假设你正在爬楼梯,需要n步你才能到达顶部。但每次你只能爬一步或者两步,你能有多少种不同的方法爬到楼顶部?

给定一个数字三角形,找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。

给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。

找出一个序列中乘积最大的连续子序列(至少包含一个数)。

给出两个单词word1和word2,计算出将word1 转换为word2的最少操作次数。
你总共三种操作方法:插入一个字符,删除一个字符,替换一个字符。

给出字符串S和字符串T,计算S的不同的子序列中T出现的个数。
子序列字符串是原始字符串通过删除一些(或零个)产生的一个新的字符串,并且对剩下的字符的相对位置没有影响。(比如,“ACE”“ABCDE”的子序列字符串,而“AEC”不是)。

给出一个字符串s和一个词典,判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。

在n个物品中挑选若干物品装入背包,最多能装多满?假设背包的大小为m,每个物品的大小为A[i]

给出三个字符串:s1、s2、s3,判断s3是否由s1和s2交叉构成。

Data Structure

发表评论

邮箱地址不会被公开。 必填项已用*标注