注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
一共三道题,第一道题是改错,大家share下思路~ 1. You are given an implementation of a function: class Solution { public int solution(int[] A, int X); } This function, when given a zero-indexed array A of N integers, sorted in non-decreasing order, and some integer X, looks for X in A. If X is present in A, then the function returns position of (some) occurrence of X in A. Otherwise, the function returns −1. For example, given the following array: A[0] = 1 A[1] = 2 A[2] = 5 A[3] = 9 A[4] = 9 and X = 5, the function should return 2, as A[2] = 5. Unfortunately, there is a bug in the implementation. Find it and correct it. You should modify at most twolines of code. Assume that: · N is an integer within the range [0..100,000]; · each element of array A is an integer within the range [−2,000,000,000..2,000,000,000]; · array A is sorted in non-decreasing order; · X is an integer within the range [−2,000,000,000..2,000,000,000]. Complexity: · expected worst-case time complexity is O(log(N)); · expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments). class Solution { int solution(int[] A, int X) { int N = A.length; if (N == 0) { return -1; } int l = 0; int r = N - 1; while (l < r) { int m = (l + r) / 2; if (A[m] > X) { r = m - 1; } else { l = m; } } if (A[l] == X) { return l; } return -1; } } 2. A binary tree is either an empty tree (represented by an empty pointer) or a node consisting of a single integer value and two binary trees called the left subtree and right subtree. A binary tree T is given. A path in tree T is a non-empty sequence of nodes of tree T such that each consecutive node in the sequence is a subtree of its preceding node. A path P in tree T is given. The amplitude of path P is the maximum difference between values of nodes on path P. The amplitude of tree T is the maximum amplitude of paths in T. If tree T is empty, then it does not have any paths and its amplitude is assumed to be 0. For example, consider the following tree T consisting of nine nodes: Sequence [9, 8, 2] is a path in this tree. Sequence [12, 8, 2] is not a path in this tree. Path [5, 8, 2] has amplitude 6. Paths [9, 8, 2] and [5, 8, 12] have amplitude 7. The amplitude of the tree is 7, as no path in it has amplitude greater than [9, 8, 2] or [5, 8, 12]. Assume that the following declarations are given: class Tree {
public int x;
public Tree l;
public Tree r;
} Write a function: class Solution { public int solution(Tree T); } that, given a tree T consisting of N nodes, returns the amplitude of T. For example, given tree T shown in the example above, the function should return 7. Assume that: · N is an integer within the range [0..1,000,000]; · each element of tree T is an integer within the range [−1,000,000,000..1,000,000,000]. Complexity: · expected worst-case time complexity is O(N); · expected worst-case space complexity is O(N). // you can also use imports, for example: // import java.math.*; class Solution { public int solution(Tree T) { // write your code in Java SE 6 } } 3. A non-empty string S = S[0]S[1]...S[N-1] consisting of N characters is given. The K-th cyclic shift of this string, where 0 ≤ K < N, is a string T defined as follows: T = S[K]S[K+1]...S[N−1]S[0]S[1]...S[K−1] | | | | | |
For example, these are all cyclic shifts of the string S = "codility": "codility" is 0th cyclic shift of "codility" "odilityc" is 1st cyclic shift of "codility" "dilityco" is 2nd cyclic shift of "codility" "ilitycod" is 3rd cyclic shift of "codility" "litycodi" is 4th cyclic shift of "codility" "itycodil" is 5th cyclic shift of "codility" "tycodili" is 6th cyclic shift of "codility" "ycodilit" is 7th cyclic shift of "codility" If a cyclic shift of a given string S is equal to S, then it is called a cyclic automorphism of S. Each string has at least one cyclic automorphism, namely the 0th cyclic shift. For example, the 0th and 3rd cyclic shifts of the string "byebye" constitute all of its cyclic automorphisms. Write a function: class Solution { public int solution(String S); } that, given a string S of length N, returns the number of cyclic automorphisms of S. For example, given S = "byebye", the function should return 2, as explained in the example above. Assume that: · N is an integer within the range [1..1,000,000]; · string S consists only of lower-case letters (a−z). Complexity: · expected worst-case time complexity is O(N); · expected worst-case space complexity is O(N) (not counting the storage required for input arguments). // you can also use imports, for example: // import java.math.*; class Solution { public int solution(String S) { // write your code in Java SE 6 } } |