Day28

아, 내일 방학이 끝나요. 빨리 만족스러운 직장을 찾았으면 좋겠어요. 계속 이렇게 직접적인 수입이 없어서 불안해요. 이번 해에 즐겁게 보내지 못했어요. 놀 유혹이 너무 커서 매일 뭔가를 써야 하는데 사실 답답해요. 내일 돌아갈게요. 억압감이 좀 작을 수도 있어요. 고향보다 조용하니까요.
오늘은 드디어 내가 쓴 방법보다 훨씬 번거로운 답안을 만났다. 히히:
1. 이미 하나의 수조를 알고 있다. 두 갈래 나무를 세우려면 두 갈래 나무의 뿌리 노드가 수조의 최대 수이고 왼쪽 나무는 그 수조의 모든 왼쪽 원소이며 오른쪽 나무는 그 수조의 모든 오른쪽 원소이다. 왼쪽 나무와 오른쪽 나무도 첫 번째 조건에 따른다.
사고방식: 수조 중 최대수를 경계로 좌우 두 부분으로 나누어 귀속시키는 셈이다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode ConstructMaximumBinaryTree(int[] nums) {
        if(nums == null)
        {
            return null;
        }
        int rootV = MaxNum(nums);
        List<int> leftNums = new List<int>();
        List<int> rightNums = new List<int>();
        int i = 0;
        int j = nums.Length - 1;
        while(nums[i] != rootV)
        {
            leftNums.Add(nums[i]);
            i++;
        }
        while(nums[j] != rootV)
        {
            rightNums.Add(nums[j]);
            j--;
        }
        TreeNode  t = new TreeNode(rootV);
        if(leftNums.Count != 0)
        {
            t.left = ConstructMaximumBinaryTree(leftNums.ToArray());
        }
        else
        {
            t.left = null;
        }
        if(rightNums.Count != 0)
        {
            rightNums.Reverse();
            t.right = ConstructMaximumBinaryTree(rightNums.ToArray());
        }
        else
        {
            t.right = null;
        }
        return t;
    }

    public int MaxNum(int[] nums)
    {
        int max = nums[0];
        for(int i = 1; i < nums.Length; i++)
        {
            if(nums[i] > max)
            {
                max = nums[i];
            }
        }
        return max;
    }
} 

그러니까 사람은 너무 일찍 기뻐하지 못하고 몸을 돌려 얼굴을 툭툭 때리는 경우가 많아요. 바로 쌍방이 생각하는 복잡한 문제를 눌렀어요. 그리고 문자열 문제이기도 하고(╯□□╰)...
2. 소문자로 구성된 모든 문자열을 알고 있습니다. 이 문자열을 가능한 한 많은 그룹으로 나누기 위해 각 문자는 최대 한 그룹에만 나타나고 마지막에 각 그룹의 길이를 출력해야 합니다.
사고방식: 처음에 각 문자가 나타나는 개수와 마지막에 나타나는 위치를 확정해야 한다고 생각했는데 현재로서는 방향이 대체적으로 정확하다(사실은 각 자모가 마지막에 나타나는 위치만 알면 된다). 그러나 그 후에 복잡하게 생각했다. 사실 이 단계에 이르러 이미 그룹의 모형이 있고 나머지는 그룹을 나누어 미세 조정만 하면 된다. 현재 자모를 검사한 후에 후속 자모가 그것과 같은 그룹에 속하는지 확인한다.자리 뒤에 있는 것만 찾으면 돼요.

List<int> PartitionLabels(string s)
{
    int[] last = new int[26];
    // s 
    for(int i = 0; i < s.Length; i++)
    {
        last[(int)s[i] - 98] = i;
    }

    //j ，anchor 
    int j = 0; 
    int anchor = 0;
    List<int> result = new List<int>();
    for(int i = 0; i < s.Length; i++)
    {
        j = Math.Max(j, last[(int)s[i] - 98]);
        if(j == i)
        {
            result.Add(i - anchor + 1);
            anchor = i + 1;
        }
    }
    return result;
}

3. 0에서num까지의 모든 수에서 1의 개수를 구하는 비음정수num를 알고 있습니다
정상 시간의 복잡도가 O(num*sizeof(num)인 방법은 쉽게 생각할 수 있다.

int[] CountingBits(int num)
{
    int[] result = new int[num + 1];
    for(int i = 0; i <= num; i++)
    {
        int n = i;
        int count = 0;
        while(count < n)
        {
            n &= n-1;          // 1
            count++;
        }
        result[i] = count;
    }
}

그런데 제목은 시간 복잡도가 O(n)를 초과하면 안 돼요.

int[] CountingBits(int num)
{
    int[] result = new int[num + 1];
    for(int i = 0; i <= num; i++)
    {
        result[i] = result[i>>1] + (i&1);
    }
    return result;
}

4. 길이가 n인 수조를 알고 있습니다. 수조의 모든 원소는 1부터 n까지의 정수입니다. 그 중 일부 숫자는 수조에 두 번 나타나 이 숫자를 구합니다.시간의 복잡도는 O(n)를 초과하지 않고 여분의 공간을 필요로 하지 않는다.
이 문제는 Day24가 기록한 세 번째 문제와 매우 비슷하다. 사고방식은 모두 이미 알고 있는 수조를 다시 산열하는 것이다

List<int> FindDuplicateNum(int[] nums)
{
    List<int> result = new List<int>();
    for(int i = 0; i < nums.Length; i++)
    {
        int tmp = Math.Abs(nums[i]) - 1;
        if(nums[tmp] < 0)
        {
            result.Add(tmp + 1);
        }
        nums[tmp] = -nums[tmp];
    }
    return result;
}