LintCode/LeetCode 트레이닝 문제 & 정답 상세 - 기초편

1. 두 갈래 나무에서 값이 가장 큰 노드를 찾아 되돌아간다. 다음 두 갈래 나무를 제시한다.

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

값이 3인 노드를 되돌려줍니다.

public class Solution {
    /**
 * @param root the root of binary tree
 * @return the max node
 */
public TreeNode maxNode(TreeNode root) {
    if (root == null) {
        return null;
    }
    return getMaxTreeNode(root);
}

private TreeNode getMaxTreeNode(TreeNode root) {
    if (root == null) {
        return new TreeNode(Integer.MIN_VALUE);
    }
    TreeNode left = getMaxTreeNode(root.left);
    TreeNode right = getMaxTreeNode(root.right);
    if (root.val > left.val && root.val > right.val) {
        return root;
    } else if (right.val > left.val && right.val > root.val) {
        return right;
    }
    return left;
}
 }

요약: 귀속적인 사상을 사용했다.빈 판단으로 주의하기;
2. 단례
단례는 가장 흔히 볼 수 있는 디자인 모델 중의 하나다.언제든지 어떤 종류가 존재하고 가장 많은 구체적인 실례가 존재한다면 우리는 이런 디자인 모델을 단례라고 부른다.예를 들어class Mouse(동물이 아닌mouse오)에 대해singleton 모델로 설계해야 한다.
당신의 임무는 get Instance 방법을 설계하는 것입니다. 주어진 클래스에 대해 get Instance를 호출할 때마다 같은 실례를 얻을 수 있습니다.
예: Java에서:
A a = A.getInstance(); A b = A.getInstance(); a는 b와 같아야 한다.
도전: get Instance를 병렬로 호출하면 프로그램도 정확하게 실행할 수 있습니까?

class Solution {
private volatile static  Solution mInstance = null;
/**
* @return: The same instance of this class every time
*/
public static Solution getInstance() {
    if (mInstance == null) {
        synchronized(Solution.class) {
            if (mInstance == null) {
                mInstance = new Solution();    
            }
        }
    }
    return mInstance;
}

private Solution() {}

}
주의: 하나의 예를 실현하려면 두 가지 주의사항이 있다. ① 구조기를 사유화하고 외부에서 구조기를 통해 대상을 만드는 것을 허락하지 않는다.② 공개된 정적 방법으로 외부로 돌아가는 유일한 실례
참고: 단례 모드의 몇 가지 문법 비교:http://wuchong.me/blog/2014/08/28/how-to-correctly-write-singleton-pattern/
3. 정수 정렬
한 조의 정수를 주고 오름차순으로 정렬하며 선택 정렬, 거품 정렬, 정렬 또는 O(n2)의 정렬 알고리즘을 삽입합니다.
예: 수조[3, 2, 1, 4, 5]의 경우 정렬 후: [1, 2, 3, 4, 5].
답안(java 버전):
정렬 선택:

public void sortIntegers(int[] A) {
    int i, j, min, temp, len = A.length;
    for (i = 0; i < len -1; i++) {
        min = i; // 
        for (j = i + 1; j < len; j++) { // ， 
            if (A[min] > A[j]) {
                min = j;
            }
        }
        if (i != min) { // 
            temp = A[min];
            A[min] = A[i];
            A[i] = temp;
        }
    }    
}

거품 정렬:

public void sortIntegers(int[] A) {
    int i, j, temp, len = A.length;
    for (i = 0; i < len - 1; i++) {
        for (j = 0; j < len - i - 1; j ++)
        if (A[j] > A[j+1]) {
            temp = A[j+1];
            A[j+1] = A[j];
            A[j] = temp;
        }
    }
    
}

답안 해석: 각 언어의 실현은 위키백과를 참고하십시오.https://zh.wikipedia.org/wiki/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F
** 4, 피보나치 수열 **
피보나치 수열의 N번째 수를 찾아라.이른바 피보나치 수열은 앞의 두 수가 0과 1이라는 것을 가리킨다.i번째 수는 i-1번째 수와 i-2번째 수의 합이다.피보나치 수열의 상위 10개 숫자는 0, 1, 2, 3, 5, 8, 13, 21, 34...
답:

public int fibonacci(int n) {
    // write your code here
    int a1 = 0;
    int a2 = 1;
    int result = 0;
    if (n == 1) {
        return a1;
    }
    if (n == 2) {
        return a2;
    }
    for (int i = 3; i <= n; i++) {
        result = a1 + a2;
        a1 = a2; 
        a2 = result;
    }
    return result;
}

주의사항: 1, n은 1부터 시작하는 것이지 0이 아니다. 일반적으로 우리는 귀속적인 방식으로 실현할 생각을 하지만 이 시간은 비용이 매우 크다.

int fibonacci(int n) { 
  if (n == 1)
      return 0;
  else if (n == 2)
      return 1;
  return fib(n-1) + fib(n-2);
}

3. 제목 설명: 개구리가 계단을 뛰어오르고 네모난 벽돌을 깔면 참고:http://www.bubuko.com/infodetail-1099705.html