Leetcode

In the town of Digitville, there was a list of numbers called nums containing integers from 0 to n - 1. Each number was supposed to appear exactly once in the list, however, two mischievous numbers sneaked in an additional time, making the list longer than usual.

As the town detective, your task is to find these two sneaky numbers. Return an array of size two containing the two numbers (in any order), so peace can return to Digitville.

Example:

Input: nums = [0,1,1,0]

Output: [0,1]

Explanation:

Solution

That is an easy problem, due to the range of the samples is too small, we can create an array to record the frequency of all numbers. Finally, we traverse the list to find the element which appear twice in the array.

Code

class Solution {
    public int[] getSneakyNumbers(int[] nums) {
        int bucket[] = new int[100];
        for(int i : nums) {
            bucket[i] += 1;
        } 
        int result[] = {0,0};
        for(int i = 0, j = 0;i < 100 ;i++){
            if(bucket[i] == 2) {
                result[j] = i;
                j++;
            }
            if(j == 2) break;
        }
        return result;
    }
    
}

---

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]

Output: 11

Explanation: The triangle looks like:

2

3 4

6 5 7

4 1 8 3

The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

Solution

You can draw an analogy to the Fibonacci sequence. However, the Fibonacci sequence compares dp[i - 1] and dp[i - 2] to determinate dp[i] .In this question,we can also use dp[] to record the minimum cost to reach each elemnent, But ,dp[i] is no longer determinated by dp[i - 1] anddp[i - 2]. In the given two-dimensional array, the first index of the element which determine dp[i][j] must be i - 1 and the second subscript is discussed in different cases:

$$\{\begin{array}{ll}& \text{ if j == 0}dp[i-1][j]\\ & \text{ if j == i}dp[i-1][j-1]\\ & \text{ else }Math.min(dp[i-1][j],dp[i-1][j-1])\end{array}$$

Code

class TriangleSolution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size() == 1) return triangle.get(0).get(0);
        int layers = triangle.size();
        int len = (layers + 1) * layers / 2;
        int dp[] = new int[len];
        dp[0] = triangle.get(0).get(0);
        dp[1] = triangle.get(1).get(0) + dp[0];
        dp[2] = triangle.get(1).get(1) + dp[0];
        for(int i = 2; i < layers; i++) {
            for(int j = 0; j <= i; j++) {
                if(j == 0) {
                    dp[(1 + i ) * i/ 2 + j] = 
                        triangle.get(i).get(j) + dp[i  *( i - 1 )/ 2 + j];
                    continue;
                }
                if(j == i) {
                    dp[(1 + i ) * i/ 2 + j] =
                        triangle.get(i).get(j) + dp[i  *( i - 1 )/ 2 + j - 1];
                    continue;
                }
                else {
                    dp[(1 + i ) * i/ 2 + j] = Math.min(
                            triangle.get(i).get(j) + dp[i  *( i - 1 )/ 2 + j],
                            triangle.get(i).get(j) + dp[i  *( i - 1 )/ 2 + j - 1]);

                }
            }

        }
        int bottomFirst = layers * (layers - 1) /2;
        int ans = dp[bottomFirst];
        for(int i = 1; i < layers; i++) {
            if(ans > dp[bottomFirst + i])
                ans = dp[bottomFirst + i];
        }
        return ans;
    }
}

---

Alice has n balloons arranged on a rope. You are given a 0-indexed string colors wherecolors[i] is the color of the ith balloon.

Alice wants the rope to be colorful. She does not want two consecutive balloons to be of the same color, so she asks Bob for help. Bob can remove some balloons from the rope to make it colorful. You are given a 0-indexed integer array neededTime where neededTime[i] is the time (in seconds) that Bob needs to remove the ith balloon from the rope.

Return the minimum time Bob needs to make the rope colorful.

Solution

We can create a variable named ans to record the minimum cost, initializing it as 0. We’ll use two pointers:fast = 1 and slow = 0. In each loop iteration, the fast pointer moves forward by one step. When the elements pointed to by the fast and slow pointers are equal, we add the minor cost to ans and move the slow pointer to the fast pointer’s position. When the elements are not equal, we simply move the slow pointer to the fast pointer’s position.

Code

class Solution {
    public int minCost(String colors, int[] neededTime) {
        int ans = 0;
        int fast = 1, slow = 0;
        for(;fast < neededTime.length; fast++){
            if(colors.charAt(fast) == colors.charAt(slow)){
                if(neededTime[slow] > neededTime[fast]){
                    ans += neededTime[fast];
                }else {
                    ans += neededTime[slow];
                    slow =  fast;
                }
            }
            else{
                slow = fast;
            }
        }
        return ans;
    }
}

---

You are given an array nums of n integers and two integers k and x.

The x-sum of an array is calculated by the following procedure:

Count the occurrences of all elements in the array. Keep only the occurrences of the top x most frequent elements. If two elements have the same number of occurrences, the element with the bigger value is considered more frequent. Calculate the sum of the resulting array. Note that if an array has less than x distinct elements, its x-sum is the sum of the array.

Return an integer array answer of length n - k + 1 where answer[i] is the x-sum of the subarray nums[i..i + k - 1].

Solution

It just need three steps to solve this problem. At First, we can use a Map to record the frequence of each element in nums. Secondly, sort all entity by frequence and value. At last, sum target elements.

Code

class Solution {
    private int singleXSum(int[] subnum,int x) {
        //使用map统计频率
        Map<Integer,Integer> freqMap = new HashMap<>();
        for(int num:subnum){
            freqMap.put(num,freqMap.getOrDefault(num,0)+1);
        }
        //创建列表存储频率并按照频率和数字降序排列
        List<Map.Entry<Integer,Integer>> entries = new ArrayList<>(freqMap.entrySet());
        Collections.sort(entries,(a,b) ->{
            if(!a.getValue().equals(b.getValue())){
                return b.getValue()-a.getValue();
            }
            return b.getKey()-a.getKey();
        });
        int result = 0;
        int count = Math.min(x,entries.size());
        for(int i=0;i<count;i++){
            Map.Entry<Integer,Integer> entry = entries.get(i);
            result += entry.getKey() * entry.getValue();
        }
        return result;

    }
    public int[] findXSum(int[] nums, int k, int x) {
        int len = nums.length;
        int[] ans = new int[len - k + 1];
        for(int i = 0; i <= len - k ; i++){
            ans[i] = singleXSum(Arrays.copyOfRange(nums,i,i + k), x );
        }
        return ans;
    }
}