眯眯眼猫头鹰的小树杈

Owned By Deer&Owl

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. 
Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

For example:
"112358" is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Given a string containing only digits '0'-'9', write a function to determine if it's an additive number.
阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

和前面几题相比，这题还增加了一个限制条件，也就是说我们在抛出股票之后，还需要冷却一天才可以买入下一只股票。那么我们进行什么样的操作才能使收益最大呢？

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:
     3
    / \
   2   3
    \   \ 
     3   1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
     3
    / \
   4   5
  / \   \ 
 1   3   1
Maximum amount of money the thief can rob = 4 + 5 = 9.

即如何从树中选择几个节点，在确保这几个节点不直接相连的情况下使其值的和最大。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
10
11
12
Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:
Given the list [1,[4,[6]]],
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

假设有一个嵌套形式的数组，要求按照顺序遍历数组中的元素。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note: 
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

假设有一个非空的整数数组，从中获得前k个出现频率最多的数字。

阅读全文 »

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:
Each element in the result must be unique.
The result can be in any order.

找出两个无序数组中重合的值。

阅读全文 »

发表于 更新于 分类于 ，

题目

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
For an undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1 :

Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3 

Output: [1]
Example 2 :

Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5 

Output: [3, 4]
Note:

According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

在无向图的生成树中，我们可以指定任何一个节点为这棵树的根节点。现在要求在这样一棵生成树中，找到生成树的高度最低的所有根节点。

其实，决定一棵树的高度往往是树中的最长路径，只有我们选择最长路径的中间点才能够尽可能减少树的高度。那么我们如何找到所有的中间节点呢？

当出发点只有两个时，我们知道中间节点就是从出发点同时出发，当二者相遇或者二者只间隔一个位置是所在的点就是两个出发点的重点。那么多个出发点也是同样的道理，每个人从各个出发点出发，最终相遇的点就是我们所要找的中间点。

这题的思路有些类似于拓扑排序，每次我们都会去除所有入度为0的点，因为这些点肯定是叶节点。然后不停的往中间走，直到剩下最后一个叶节点或是最后两个叶节点。

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

这个图中删除所有入度为0的点就只剩下1，因此我们知道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
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    if(n==1) return Collections.singletonList(0);
    //初始化邻接表
    List<Set<Integer>> adj = new ArrayList<Set<Integer>>();
    for(int i = 0 ; i<n ; i++) {
        adj.add(new HashSet<Integer>());
    }
    for(int[] edge : edges) {
        adj.get(edge[0]).add(edge[1]);
        adj.get(edge[1]).add(edge[0]);
    }
    
    List<Integer> leaves = new ArrayList<Integer>();
    for(int i = 0 ; i<adj.size() ; i++) {
        if(adj.get(i).size() == 1) {
            leaves.add(i);
        }
    }
    
    while(n > 2) {
        n -= leaves.size();
        List<Integer> newLeaves = new ArrayList<>();
        for (int i : leaves) {
            int j = adj.get(i).iterator().next();
            adj.get(j).remove(i);
            if (adj.get(j).size() == 1) newLeaves.add(j);
        }
        leaves = newLeaves;
    }
    return leaves;
}

思路二：简化数据结构

这里使用degree数组存储每个顶点的度数，即连接的变数。度数为一的顶点就是叶节点。再用connected存储每个顶点所连接的所有边的异或值。
这里使用异或的原因是对同一个值进行两次异或即可以回到最初值。

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
40
public List<Integer> findMinHeightTrees2(int n, int[][] edges) {
    if(n==1) return Collections.singletonList(0);
    int[] connected = new int[n];
    int[] degree = new int[n];
    
    for(int[] edge : edges) {
        int v1 = edge[0];
        int v2 = edge[1];
        connected[v1] ^= v2;
        connected[v2] ^= v1;
        
        degree[v1]++;
        degree[v2]++;
    }
    
    LinkedList<Integer> queue = new LinkedList<Integer>();
    for(int i = 0 ; i<degree.length ; i++) {
        if(degree[i] == 1) {
            queue.offer(i);
        }
    }
    
    while(n > 2 && !queue.isEmpty()) {
        int size = queue.size();
        for(int i = 0 ; i<size ; i++) {
            int v = queue.poll();
            n--;
            int v1 = connected[v];
            connected[v1] ^= v;
            degree[v1]--;
            if(degree[v1] == 1) {
                queue.add(v1);
            }
        }    
    }
    
    List<Integer> result = new ArrayList<Integer>();
    result.addAll(queue);
    return result;
}

发表于 更新于 分类于 ，

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

Operations allowed:

Fill any of the jugs completely with water.
Empty any of the jugs.
Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.
Example 1: (From the famous "Die Hard" example)

Input: x = 3, y = 5, z = 4
Output: True
Example 2:

Input: x = 2, y = 6, z = 5
Output: False

假设现在有两个杯子，每个杯子分别最多可以装x和y升水，假设现在水的供应量是无限的，问是否有可能用这两个杯子共同承装z升水，可以用两个杯子执行的操作如下：

  1. 将任何一个杯子装满水
  2. 倒掉任何一个杯子中的所有水
  3. 将一个杯子中的水倒进另一个杯子，直到另一个杯子满了或者是当前的杯子已经空了

比如，如果现在两个杯子A和B分别能装3升水和5升水，需要在两个杯子中共装4升水。我们可以找到这样一个序列满足题目要求：

  1. 将B杯倒满水并导入A中，此时A:3 B:2
  2. 将A杯倒空，并将B中的水倒入A中，此时A:2 B:0
  3. 将B杯装满并倒A中，此时A:3 B:4
  4. 将A杯倒掉，此时A:0 B:4
阅读全文 »

发表于 更新于 分类于 ，

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k 
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

Input: [1,2,3,4,5]
Output: true
Example 2:

Input: [5,4,3,2,1]
Output: false

假设有一个无序的数组，如果数组中从左到右存在三个由小到大的数字，则返回true。否则返回false。

题目的额外要求是：O(n)的时间复杂度和O(1)的空间复杂度

阅读全文 »

发表于 更新于 分类于 ，

题目

1
2
3
4
5
6
7
8
9
10
Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:
You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

假设有一组字母和一组从杂志中获取的字母，问是否能够用从杂志中获取的字母构成想要的那组字母，要求每个单词只能使用一次。

阅读全文 »
0%