眯眯眼猫头鹰的小树杈

Owned By Deer&Owl

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

现在有一个非空字符串s和一个非空的字典wordDict。现在向s中添加空格从而构成一个句子，其中这个句子的所有单词都存在与wordDic中。字典中不包含重复的单词。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

Any live cell with fewer than two live neighbors dies, as if caused by under-population.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by over-population..
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
Write a function to compute the next state (after one update) of the board given its current state.

Follow up: 
Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

这个内容在维基百科上讲述的非常详细，有图文示例。
这个游戏玩家在游戏开始后是不能操作的，完全是由最初的状态来决定最终的结果。板上的每个小格子有两种状态，live或dead。
而根据游戏规则，每一次这个板上的内容将会随着前一次板上的内容发生变化。变化的规则如下：

  • 如果当前格子为live，那么只要它周围live邻居的数量大于3个或是小于2个，该格子就会变成dead状态。
  • 如果当前个字为dead，那么只要它周围live的邻居数量正好为3个，该格子就会变成live状态。否则还是dead状态。

现在输入一个状态，让我们更新出板子的下一个状态。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5
as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

设计一个方法将一个二叉树序列化并反序列化。序列化是指将对象转化成一个字符串，该字符串可以在网络上传输，并且到达目的地后可以通过反序列化恢复成原来的对象。

在Leetcode中，树的序列化是通过广度优先遍历实现的，就如题目中所介绍的那样。

这里我们使用中序遍历来解决这个问题。

##思路和代码##
中序遍历是指递归的先遍历当前节点，然后按同样的方式递归的遍历左子树，再递归的遍历右子树。因此题目中的例子的中序遍历结果为[1,2,3,4,5]。但是，标准的中序遍历并不能使我们将该结果反构造成一棵树，我们丢失了父节点和子节点之间的关系。因此我们需要适当的插入空值来保存父节点和子节点的关系。

因此，我们将访问到空值也记录下来，结果如下[1,2, , ,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
private static final String NULL = "N";
private static final String SPLITOR = ",";

 // Encodes a tree to a single string.
public String serialize(TreeNode root) {
    StringBuilder result = new StringBuilder();
    inOrder(root, result);
    return result.toString();
}

private void inOrder(TreeNode root, StringBuilder result){
    if(root==null){
        result.append(NULL).append(SPLITOR);
    }else{
        result.append(root.val).append(SPLITOR);
        inOrder(root.left, result);
        inOrder(root.right, result);
    }
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    Deque<String> nodes = new LinkedList<String>(Arrays.asList(data.split(SPLITOR)));
    return buildTree(nodes);
}

private TreeNode buildTree(Deque<String> nodes) {
    String val = nodes.remove();
    if (val.equals(NULL)) return null;
    else {
        TreeNode node = new TreeNode(Integer.valueOf(val));
        node.left = buildTree(nodes);
        node.right = buildTree(nodes);
        return node;
    }
}

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
You are playing the following Bulls and Cows game with your friend:
You write down a number and ask your friend to guess what the number is. 
Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called "bulls") and how many digits match the secret number but locate in the wrong position (called "cows"). 
Your friend will use successive guesses and hints to eventually derive the secret number.

For example:

Secret number:  "1807"
Friend's guess: "7810"
Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)
Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows. In the above example, your function should return "1A3B".

Please note that both secret number and friend's guess may contain duplicate digits, for example:

Secret number:  "1123"
Friend's guess: "0111"
In this case, the 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return "1A1B".
You may assume that the secret number and your friend's guess only contain digits, and their lengths are always equal.

Bulls and Cows游戏简单来说就是你随手写下一个n位数，并让你同学猜这个数字是什么。假设你的朋友也会猜测一个n位数，他每猜一个数字，你就需要告诉他，猜测的数字中位置正确且值正确的数字(bulls)有几个，位置不正确但是值不正确的数字(cows)有几个。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. 
Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.
Note:
The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.

现在有一个整数数组，你需要为每一个数组赋予正号或是负号，使其的和为目标值。

阅读全文 »

发表于 更新于 分类于 ，

Range Sum Query Immutable 题目要求

1
2
3
4
5
6
7
8
9
10
11
12
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:
Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:
You may assume that the array does not change.
There are many calls to sumRange function.

假设有一个整数数组，计算下标从i到j（包含i和j）的数字的和。求和的请求将会在同一个整数数组上多次请求。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.
Example:
Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
Note:
The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.

可以先参考数组不发生变动时的题目。

这里的难度在于数组可以在中间出现变动，那么面对大容量数组的时候如何选择一个合适的数据结构及很重要。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

这里模拟实现了一个换钱算法。传入的参数为手上有的纸币的面额以及希望兑换的面额。这里假设纸币的数量是无穷的。

这题本质上考察的是动态规划思想。这里有两种动态规划的方法，分别从递归和非递归的角度解决这个问题。具体的情况还是要看数据的分布情况来确定选择哪种方法。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:
"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

现在有一个字符串包含一些左右括号以及字母。一个合法的字符串是指左括号和右括号必定成对出现。要求得出用最少次数的删除可以得到的所有的合法字符串。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

Given n = 3. 

At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off]. 

So you should return 1, because there is only one bulb is on.

一共有n个初始状态为关闭的灯泡。第一次打开所有灯泡，第二次每隔一个灯泡关闭一个灯泡，第三次每隔两个灯泡按一下开关。依次类推，问第n次之后开着的灯泡的数量有几个？

阅读全文 »
0%