微软暑期2022实习笔试题

• 第一题：数组内移动最小次数

• 题目

  Given a sorted array like [1,2,4,4,4]. Each element in the array should occur exactly same number of times as element. 
  For Example 1 should occur 1 time, 2 should occur 2 times, n should occur n times, 
  After minimum number of moves, the array will be rendered as [1,4,4,4,4]

public int minMoves(int[] data) {
    int minOperations = 0;
    for(int i = 0, j = 0; i < data.length; i = j) {
        while (j < data.length && data[i] == data[j]) j++;
        int frequency = j - i;
        minOperations += Math.min(Math.abs(data[i] - frequency), frequency);
    }
    return minOperations;
}

• 第二题：求公司项目最大项目价值
• 题目：

import (
    "math"
)

func Solution(V []int, A []int, B []int) int {
    // write your code in Go 1.4
    maxValueWithDependency := 0
    requirementMap := make(map[int]int, len(B))
    for i := 0; i < len(B); i++ {
        // if requirements num > 1, skip the project
        if _, ok := requirementMap[B[i]]; ok {
            requirementMap[B[i]] = -1
            continue
        }
        requirementMap[B[i]] = A[i]
    }
    for i := range B {
        // requirement project > 1
        if requirementMap[B[i]] == -1 {
            continue
        }
        // requirement project is requiring another project
        if _, ok := requirementMap[A[i]]; ok {
            continue
        }
        value := V[B[i]] + V[A[i]]
        if value > maxValueWithDependency {
            maxValueWithDependency = value
        }
    }
    maxValue, secondMaxValue := math.MinInt32, math.MinInt32
    for i := range V {
        if _, ok := requirementMap[i]; ok {
            continue
        }
        if V[i] > maxValue {
            secondMaxValue = maxValue
            maxValue = V[i]
        } else if V[i] > secondMaxValue {
            secondMaxValue = V[i]
        }
    }
    if secondMaxValue > 0 {
        maxValue = maxValue + secondMaxValue
    }
    if maxValue > maxValueWithDependency {
        return maxValue
    } else {
        return maxValueWithDependency
    }
}

• 第三题：求旅游完所有景点需要的最少天数
• 题目，我从csdn上找了一个类似的，题解也几乎模仿他来的，不过最后一步左移，出现了差一问题，所以我只好在结果那里进行手动步增

    public int solution(int[] A) {
        // write your code in Java SE 8
                int tripLen = A.length;
        if (tripLen == 0) return 0;
        if (tripLen == 1) return A[0];

        HashSet<Integer> locations = new HashSet<>();
        HashMap<Integer, Integer> countMap = new HashMap<>();
        int begin = 0;
        int end = 0;
        int min_vac = Integer.MAX_VALUE;
        for (int location : A) locations.add(location);
        for (int location : A) countMap.put(location, 0);

        while (end < tripLen) {
            int loc = A[end];
            if (countMap.containsKey(loc)) countMap.put(loc, countMap.get(loc) + 1);

            boolean isTravelDone = true;
            for (Integer location : locations) {
                if (countMap.get(location) <= 0) isTravelDone = false;
            }

            while (isTravelDone) {
                min_vac = Math.min(min_vac, end - begin);
                int loc_s = A[begin];
                begin++;
                countMap.put(loc_s, countMap.get(loc_s) - 1);
                if (countMap.get(loc_s) <= 0) isTravelDone = false;
            }
            end++;
        }
        return min_vac + 1;
    }