眯眯眼猫头鹰的小树杈

题目要求

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

判断S字符串中通过删减单词含有几个T字符串。例如rabbbit中含有3个rabbit字符串，通过分别删除第1，2，3个b。

题目要求

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

计算一个完全二叉树的节点个数。其中完全二叉树是指除了最后一行，其余的每一行都必须是满节点的树。

题目要求

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. 
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. 
You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000
Answer: 1

Example 2:

11000
11000
00100
00011
Answer: 3

提供一个二维数组表示一张地图，其中1代表陆地，0代表海洋。问在这张地图上一共有几个陆地.

题目要求

Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

也就是说，比较版本号。

思路一：利用java API

通过split方法将版本通过.分隔开，然后将每一段版本从string转化为int进行比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public int compareVersion(String version1, String version2) {
    String[] v1Detail = version1.split("\\.");
    String[] v2Detail = version2.split("\\.");
    int i = 0;
    while(i<v1Detail.length && i<v2Detail.length){
        int tempV1 = Integer.parseInt(v1Detail[i]);
        int tempV2 = Integer.parseInt(v2Detail[i]);
        if(tempV1<tempV2) return -1;
        if(tempV1>tempV2) return 1;
        i++;
    }
    while(i<v2Detail.length && Integer.parseInt(v2Detail[i])==0) i++;
    while(i<v1Detail.length && Integer.parseInt(v1Detail[i])==0) i++;
    if(i>=v1Detail.length && i>=v2Detail.length) return 0;
    else if(i>=v1Detail.length) return -1;
    return 1;
}

思路二：自己实现string转化为integer

自己实现将string转化为integer，可以通过循环的方式。这是一个基本的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public int compareVersion2(String version1, String version2){
    int i = 0;
    int j = 0;
    int length1 = version1.length();
    int length2 = version2.length();
    while(i<length1 || j<length2){
        int num1 = 0, num2 = 0;
        while(i<length1 && version1.charAt(i)!='.') num1 = num1*10+(version1.charAt(i++)-'0');
        while(j<length2 && version2.charAt(j)!='.') num2 = num2*10+(version2.charAt(j++)-'0');
        if(num1>num2) return 1;
        else if(num1<num2) return -1;
        i++;
        j++;
    }
    return 0;
}

题目要求

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,
X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

将所有被X环绕的O区域获取出来并转化为X

题目要求

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

假设存在这样一个链表，在链表的每一个节点中，除了记录了自身值和指向下一个节点的指针，还有一个随机指针指向链表中任意一个节点。现在要求深度复制这份链表，在不改变原链表内容的情况下，创建一组新的对象，该组对象中的值和原链表中的值相同。

217 Contains Duplicate

1

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

输入一个整数数组，查看数组中是否存在重复的值。

题目要求

1
2
3
4

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

从一个整数数组中找到一个子数组，该子数组中的所有元素的乘积最大。
比如数组[2,-3,-2,4]的最大乘积子数组为[2,3]

题目要求

1
2
3
4
5
6
7
8
9
10

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". 
When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

For example,
Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",

Return:
["AAAAACCCCC", "CCCCCAAAAA"].

所有的DNA都是有A,C,G,T这四个字母组成的，比如“ACGAATTCCG”。在研究DNA的时候，从DNA序列中找到重复出现的模式是很有用的。这个问题要求我们在一个DNA序列中找到出现超过两次的长度为10的子序列。

比如，假设DNA序列为AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT，那么找到的满足条件的子序列为**[“AAAAACCCCC”, “CCCCCAAAAA”]**

题目要求

1
2
3
4
5
6
7

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), 
return 964176192 (represented in binary as 00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?