算法相关问题以及对应解

LintCode上的算法相关的问题,以及相对应的解,所有答案用Java实现

斐波那契数列

查找斐波纳契数列中第 N 个数的和。
所谓的斐波纳契数列是指:

  • 前2个数是 0 和 1 。
  • 第 i 个数是第 i-1 个数和第i-2 个数的和。

斐波纳契数列的前10个数字是:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

答案解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
/**
* @param n: an integer
* @return: an ineger f(n)
*/
public int fibonacci(int n) {
// write your code here
int a = 0;
int b = 1;
for (int i=0;i<n-1;i++){
int c = a+b;
a=b;
b=c;
}
return a;
}
}

删除链表中的元素

删除链表中等于给定值val的所有节点。

样例
给出链表 1->2->3->3->4->5->3, 和 val = 3, 你需要返回删除3之后的链表:1->2->4->5

答案解析
建立一个新的节点添加到链表的起始位置,例如:new->1->2->3->3->4->5->3,然后从起始位置移动节点,当遇到要删除的节点时,将该节点删除,否则继续移动,直到遍历完所有的节点,最后返回去掉起始节点的链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
/*
* @param head: a ListNode
* @param val: An integer
* @return: a ListNode
*/
public ListNode removeElements(ListNode head, int val) {
// write your code here
ListNode node = new ListNode(0);
node.next = head;
head=node;
while (head.next != null){
if (head.next.val == val){
head.next = head.next.next;
}
else{
head = head.next;
}

}
return node.next;

}
}

整数排序

给一组整数,按照升序排序,使用选择排序,冒泡排序,插入排序或者任何 O(n2) 的排序算法。

样例
对于数组 [3, 2, 1, 4, 5], 排序后为:[1, 2, 3, 4, 5]。

  • 选择排序:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
/**
* @param A an integer array
* @return void
*/
public void sortIntegers(int[] A) {
// Write your code here
int n = A.length;
for (int i = 0; i < n; ++i)
for (int j = i+1; j < n; ++j)
if (A[j] < A[i]) {
int t = A[j];
A[j] = A[i];
A[i] = t;
}
}
}for

  • 冒泡排序规则:
    1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
    2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
    3. 针对所有的元素重复以上的步骤,除了最后一个。
    4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
/**
* @param A: an integer array
* @return: nothing
*/
public void sortIntegers(int[] A) {
// write your code here
int len = A.length;
int temp;
for (int i = 0;i<len-1;i++){
for(int j = 0;j<len-i-1;j++){
if(A[j]>A[j+1]){
temp=A[j];
A[j]=A[j+1];
A[j+1]=temp;
}
}
}
}
}
  • 插入排序:是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
/**
* @param A: an integer array
* @return: nothing
*/
public void sortIntegers(int[] A) {
// write your code here
int len = A.length;
int temp;
for (int i = 0;i<len-1;i++){
for(int j = i+1;j>0;j--){
if(A[j]>A[j-1]){
break;
}
temp = A[j];
A[j] = A[j-1];
A[j-1] = temp;
}
}
}
}

二叉树的最大节点

在二叉树中寻找值最大的节点并返回。

样例

1
2
3
4
5
     1  
/ \
-5 2
/ \ / \
0 3 -4 -5

答案解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/*
* @param root: the root of tree
* @return: the max node
*/
public TreeNode maxNode(TreeNode root) {
// write your code here
if (root == null)
return root;
TreeNode right = maxNode(root.right);
TreeNode left = maxNode(root.left);

return max(root,max(right,left));

}
private TreeNode max(TreeNode a,TreeNode b){
if (a == null)
return b;
if (b == null)
return a;
if (a.val > b.val) {
return a;
}
return b;
}

}

A + B 问题

给出两个整数a和b, 求他们的和, 但不能使用 + 等数学运算符。

答案解析

主要利用异或运算来完成,异或运算有一个别名叫做:不进位加法,那么a ^ b就是a和b相加之后,该进位的地方不进位的结果,然后下面考虑哪些地方要进位,自然是a和b里都是1的地方,a & b就是a和b里都是1的那些位置,a & b << 1 就是进位之后的结果。所以:a + b = (a ^ b) + (a & b << 1)令a’ = a ^ b, b’ = (a & b) << 1 可以知道,这个过程是在模拟加法的运算过程,进位不可能一直持续,所以b最终会变为0。因此重复做上述操作就可以求得a + b的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
/**
* @param a: An integer
* @param b: An integer
* @return: The sum of a and b
*/
public int aplusb(int a, int b) {
while(b!=0){
int _a = a^b;
int _b = (a&b)<<1;
a = _a;
b= _b;
}
return a;
}
}

尾部的零

设计一个算法,计算出n阶乘中尾部零的个数

样例
11! = 39916800,因此应该返回 2

答案解析
要求n的阶乘,就是求1到n这n个数相乘。在这1到n个数当中,只有2和5相乘的结果才会出现0,其中10的倍数也可以看做是2和5相乘的结果,所以,可以在1到n之间看看有多少个数是2的倍数以及多少个数是5的倍数就行了。容易发现2的倍数的数一定多于5的倍数的数,因此可以只看n前面有多少个5就行了,于是n/5可以得到1到n内有多少个数是5的倍数。此外,还有一些特殊情况,比如25这种,其是5和5相乘的结果,这种数和4相乘会出现2个0,同理125和8相乘会出现3个0,……,所以,还要看n/5里面有多少个5,比如n=125,125个数里有25个数是5的倍数,125里又有125/25=5个数是25的倍数。每个25的倍数又会多一个0。因此125! 的末尾0的个数就是125/5 + 125/5/5 + 125/5/5/5。其中最后一项表示125的个数,因为125和8相乘会出现3个0。如果下面还有,比如625,即需要再循环一次,就是625的个数,625乘以16会出现4个0,需要再加1,依次类推……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
/*
* @param n: An integer
* @return: An integer, denote the number of trailing zeros in n!
*/
public long trailingZeros(long n) {
// write your code here, try to do it without arithmetic operators.
long sum = 0;
while(n!=0)
{
n /= 5;
sum += n;
}
return sum;
}
}

合并排序数组

合并两个排序的整数数组A和B变成一个新的数组。

样例

给出A=[1,2,3,4],B=[2,4,5,6],返回 [1,2,2,3,4,4,5,6]

答案解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Solution {
/**
* @param A: sorted integer array A
* @param B: sorted integer array B
* @return: A new sorted integer array
*/
public int[] mergeSortedArray(int[] A, int[] B) {
int[] ans = new int[A.length + B.length];
int a = 0, b = 0, temp = 0;
while(a != A.length && b != B.length) {
if(A[a] > B[b]){
ans[temp] = B[b++];
}
else {
ans[temp] = A[a++];
}
temp ++;
}
if(a != A.length){
while(a != A.length){
ans[temp++] = A[a++];
}
}
else {
while(b != B.length){
ans[temp++] = B[b++];
}
}
return ans;
}
}

旋转字符串

给定一个字符串和一个偏移量,根据偏移量旋转字符串(从左向右旋转)
样例
对于字符串 “abcdefg”.

1
2
3
4
offset=0 => "abcdefg"
offset=1 => "gabcdef"
offset=2 => "fgabcde"
offset=3 => "efgabcd"

答案解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
/**
* @param str: an array of char
* @param offset: an integer
* @return: nothing
*/
public void rotateString(char[] str, int offset) {
// write your code here
if (str == null || str.length == 0)
return;

offset = offset % str.length;
reverse(str, 0, str.length - offset - 1);
reverse(str, str.length - offset, str.length - 1);
reverse(str, 0, str.length - 1);
}

private void reverse(char[] str, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
}
}

字符串查找

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

样例
如果 source = “source” 和 target = “target”,返回 -1。
如果 source = “abcdabcdefg” 和 target = “bcd”,返回 1。

答案解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
/**
* Returns a index to the first occurrence of target in source,
* or -1 if target is not part of source.
* @param source string to be scanned.
* @param target string containing the sequence of characters to match.
*/
public int strStr(String source, String target) {
if (source == null || target == null) {
return -1;
}

for (int i = 0; i < source.length() - target.length() + 1; i++) {
int j = 0;
for (j = 0; j < target.length(); j++) {
if (source.charAt(i + j) != target.charAt(j)) {
break;
}
}
// finished loop, target found
if (j == target.length()) {
return i;
}
}
return -1;
}
}

反转整数

样例
123 反转之后是 321。
900 反转之后是 9。
答案解析
不考虑溢出的情况下,假设一个数字为123,那么分别对这个数进行取模和整数相除运算。123%10 = 3,123/10 = 12。这样将最后一位提取出来。依次将每一位提取出来,每提取一次将提起结果乘以10然后相加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
/**
* @param number: A 3-digit number.
* @return: Reversed number.
*/
public int reverseInteger(int number) {
// write your code here
int calute = 0;

while (number>=10){
int temp = number%10;
number = number/10;
calute = (temp+calute) * 10;
}
calute = calute+number;
return calute;

}
}

二分查找

给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组中,返回-1。
样例
在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3,返回2。
答案解析
正常二分查找非重复元素的数组时,如果找到对应的结果直接返回,这次要二分到要查找的整数taraget。将这个taraget当作最大的边界继续查到只剩下两个元素为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
/**
* @param nums: The integer array.
* @param target: Target to find.
* @return: The first position of target. Position starts from 0.
*/
public static int binarySearch(int[] nums, int target) {
int start = 0;
int end = nums.length-1;
while (start+1<end){
int mid = (start+end)/2;
if (nums[mid]<target){
start=mid;
}
else {
end=mid;
}

}

if (nums[start]==target){
return start;
}
if (nums[end] == target){
return end;
}
return -1;
}
}

平面列表

给定一个列表,该列表中的每个要素要么是个列表,要么是整数。将其变成一个只包含整数的简单列表。

样例
给定 [1,2,[1,2]],返回 [1,2,1,2]。
给定 [4,[3,[2,[1]]]],返回 [4,3,2,1]。

答案解析
用递归实现,这道题很容易可以找到递归基。最里层的数组肯定全是数字。遍历数组将数字添加到新数组里。外层也是如此操作如果遇到数组则重复执行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* public interface NestedInteger {
*
* // @return true if this NestedInteger holds a single integer,
* // rather than a nested list.
* public boolean isInteger();
*
* // @return the single integer that this NestedInteger holds,
* // if it holds a single integer
* // Return null if this NestedInteger holds a nested list
* public Integer getInteger();
*
* // @return the nested list that this NestedInteger holds,
* // if it holds a nested list
* // Return null if this NestedInteger holds a single integer
* public List<NestedInteger> getList();
* }
*/
public class Solution {

// @param nestedList a list of NestedInteger
// @return a list of integer
public List<Integer> flatten(List<NestedInteger> nestedList) {

List<Integer> list = new ArrayList<Integer>();

for (NestedInteger nestedInteger : nestedList){
if (nestedInteger.isInteger()){
list.add(nestedInteger.getInteger());
}
else {
list.addAll(flatten(nestedInteger.getList()));
}
}
return list;
}
}