来福软谱

Posted on 2018-02-20 Edited on 2018-02-24 In Tech Disqus:

迎难而上，祝我好运。

最小横向刷墙次数

给一个数组A代表糊墙的高度，就是挨在一起的n个矩形，第i个高度为A，宽为1，然后横着刷墙，每一笔高度为1，问最少要多少笔？例如[1,2,2,3,2]->横着4笔
one-pass，两两比较，如果后面的比前面的矮，说明刷到这里就会断掉，所以要加上delta。

private static int minPaint(int[] walls) {
    int count = walls[0];
    for (int i = 1; i < walls.length; i++) {
        if (walls[i] > walls[i - 1]) {
            count += (walls[i] - walls[i - 1]);
        }
    }
    return count;
}

最少出行天数

给一个数组表示第i天可以去的地点，求去所有出现的地点所需的最短天数。
莉蔻上minmum substring简化版。首先建立一个map，频数都设为1表示我只需要去这个地方至少1天。然后双指针producer-consumer，快指针消耗location直到所有地点都去了（剩余目的地count为0），然后先根据左右慢指针更新minDays，然后开始恢复location计数到map中。

private static int minDays(int[] locations) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int location : locations) {
        map.put(location, 1);
    }
    int locationCount = map.size();
    int left = 0, right = 0, minLen = Integer.MAX_VALUE;
    while (right < locations.length) {
        map.put(locations[right], map.get(locations[right]) - 1);
        if (map.get(locations[right]) == 0) {
            locationCount--;
        }
        while (locationCount == 0) {
            int currLen = right - left + 1;
            minLen = Math.min(minLen, currLen);
            map.put(locations[left], map.get(locations[left]) + 1);
            if (map.get(locations[left]) > 0) {
                locationCount++;
            }
            left++;
        }
        right++;
    }
    return minLen;
}

分糖果

给一个数组表示糖果的id，其中可能有重复，且糖果数量一定是偶数。要求将其分成两部分，问如果想尝最多的不同的糖果，有多少种。例如[3,2,2,1,3,1]就有三种，[7,3,1,4,3,7,4,3,7]就有四种。要求时间复杂度最差O(N*lgN)，空间复杂度O(N)。
先排序，然后双指针一个从前往后，一个从后往前。left指针负责将糖果存入set，right则是调取后方的糖果往前替换，当left发现当前糖果吃过了，就从right那里swap过来继续判断，直到出现新的糖果或者穷尽。

private static int maxCandy(int[] candies) {
		if (candies == null || candies.length == 0) {
			return 0;
		}
		Arrays.sort(candies);
		Set<Integer> set = new HashSet<>();
		int half = candies.length / 2;
		int left = 0, right = candies.length - 1;
		while (left < half) {
			while (set.contains(candies[left]) && right >= half) {
				swap(candies, left, right--);
			}
			if (right < half) {
				break;
			} else {
				set.add(candies[left++]);
			}
		}
		set.add(candies[left]);
		return set.size();
	}

最小无序区间

给一个int数组，求其中最大和最小值恰好为1的非连续子序列。
给一个部分部分有序的数组，求将其中哪一部分排序之后整个数组就都有序了，求最短的区间的长度。
首先从左往右逆序对，然后从右往左找逆序对。这样就有了一个大致区间，但是还需要找区间内的min和max，分别往前和往后遍历看看是否真的完全符合，否则还需要扩展区间。例如[1,3,6,4,8,2,7,10]在前两步之后找到得失[6,4]和[8,2]实际上前面的3和后面的1都需要加入进来。

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // 找第一个逆序对
        int left = 1;
        while (left < nums.length) {
            if (nums[left - 1] > nums[left]) {
                left--;
                break;
            }
            left++;
        }
        if (left == nums.length) {  // 说明已经有序了
            return 0;
        }
        int right = nums.length - 1;
        while (right > 0) {
            if (nums[right - 1] > nums[right]) {
                break;
            }
            right--;
        }
        // 找[left, right]之间的最小、最大
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int i = left; i <= right; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        // 前面的必须小于min，后面的必须大于max，否则扩散
        while (left > 0 && nums[left - 1] > min) {
            left--;
        }
        while (right + 1 < nums.length && nums[right + 1] < max) {
            right++;
        }
        return right - left + 1;
    }
}

最长差值恰好为1的子序列

给一个int数组，求其中最大和最小值恰好为1的非连续子序列。
用Map存每个值出现的次数，然后遍历Map取key相差1都存在的进行更新。

class Solution {
    public int findLHS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int max = 0;
        for (int num : map.keySet()) {
            if (map.containsKey(num + 1)) {
                max = Math.max(max, map.get(num) + map.get(num + 1));
            }
        }
        return max;
    }
}

prefix permutation

给一个规模为N的数组，只包含数字1-N，求其中可以作为permutation的子数组的个数。例如[2,1,3,5,4]就有三个：[2,1], [2,1,3], [2,1,3,5,4]。
方法一是求和，一旦吻合permutation的sum就加一，但又overflow的风险。
方法二是利用规模为N、数字是1-N这个信息，value和index就有一一对应的关系了（虽然相差1）。只有差值为0的时候才是permutation。

private static int prefixPermutation(int[] arr) {
    int prefixCount = 0, valueIndexDelta = 0;
    for (int i = 0; i < arr.length; i++) {
        valueIndexDelta += (arr[i] - i - 1);
        if (valueIndexDelta == 0) {
            prefixCount++;
        }
    }
    return prefixCount;
}

扑克牌比大小

给两个相同长度的String表示两个人的牌，含有2-9, J, Q, K, A这些面值，判断第一个人赢的次数。
直接暴力比大小，用一个Map存牌和数字的映射关系，然后直接取就行了。

private static int getWinTimes(String a, String b) {
    if (a == null || b == null || a.length() == 0 || b.length() == 0) {
        return 0;
    }
    Map<Character, Integer> map = new HashMap<>();
    for (int i = 2; i < 10; i++) {
        map.put()
    }
}