1/27/2018 contest 69

  1. Jewels and Stones easy
  2. Global and Local Inversions medium
  3. Sliding Puzzle hard
  4. Minimize Max Distance to Gas Station hard

771. Jewels and Stones

You're given stringsJrepresenting the types of stones that are jewels, andSrepresenting the stones you have. Each character inSis a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters inJare guaranteed distinct, and all characters inJandSare letters. Letters are case sensitive, so"a"is considered a different type of stone from"A".

Example 1:

Input:
 J = "aA", S = "aAAbbbb"

Output:
 3

Example 2:

Input:
 J = "z", S = "ZZ"

Output:
 0

Note:

  • SandJwill consist of letters and have length at most 50.
  • The characters inJare distinct.

easy:

class Solution {
    public int numJewelsInStones(String J, String S) {
        if (J == null || S == null) return 0;

        Set<Character> set = new HashSet<>();
        for (char c : J.toCharArray()) {
            set.add(c);
        }
        int count = 0;
        for (char c : S.toCharArray()) {
            if (set.contains(c)) {
                count++;
            }
        }
        return count;
    }
}

775. Global and Local Inversions

We have some permutationAof[0, 1, ..., N - 1], whereNis the length ofA.

The number of (global) inversions is the number ofi < jwith0 <= i < j < NandA[i] > A[j].

The number of local inversions is the number ofiwith0 <= i < NandA[i] > A[i+1].

Returntrue if and only if the number of global inversions is equal to the number of local inversions.

Example 1:

Input:
 A = [1,0,2]

Output:
 true

Explanation:
 There is 1 global inversion, and 1 local inversion.

Example 2:

Input:
 A = [1,2,0]

Output:
 false

Explanation:
 There are 2 global inversions, and 1 local inversion.

Note:

  • Awill be a permutation of[0, 1, ..., A.length - 1]
  • Awill have length in range[1, 5000]
  • The time limit for this problem has been reduced.

两种思路，可以用BIT来做，也可以研究下问题的特征，简化计算

BIT method:

class Solution {
    public boolean isIdealPermutation(int[] a) {
        int n = a.length;
        int[] ft = new int[n+3];
        int inv = 0;
        for(int i = n-1;i >= 0;i--){
            inv += sumFenwick(ft, a[i]);
            addFenwick(ft, a[i], 1);
        }
        for(int i = 0;i < n-1;i++){
            if(a[i] > a[i+1])inv--;
        }
        return inv == 0;
    }

    public int sumFenwick(int[] ft, int i)
    {
        int sum = 0;
        for(i++;i > 0;i -= i&-i)sum += ft[i];
        return sum;
    }

    public void addFenwick(int[] ft, int i, int v)
    {
        if(v == 0 || i < 0)return;
        int n = ft.length;
        for(i++;i < n;i += i&-i)ft[i] += v;
    }
}

elegant and clever method:

Because the count of local should <= count of global, all we care is when local < global happens.The difference between local and global is global also include nonadjacent i and j, so simplify the question to for every i, find in range 0 to i-2, see if there is a element larger than A[i], if it exist, we can return false directly. and we can maintain a variable max for the linear implementation.

class Solution {
    public boolean isIdealPermutation(int[] A) {
         int max = -1;
         for(int i = 0; i < A.length-2; i++) {
             max = Math.max(max, A[i]);
             if(max > A[i+2])
                 return false;
         }
         return true;
    }
}

773. Sliding Puzzle

On a 2x3 board, there are 5 tiles represented by the integers 1 through 5, and an empty square represented by 0.

A move consists of choosing 0 and a 4-directionally adjacent number and swapping it The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]].

Given a puzzle board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.

Examples:

Input: board = [[1,2,3],[4,0,5]]

Output: 1

Explanation: Swap the 0 and the 5 in one move.

Input: board = [[1,2,3],[5,4,0]]

Output: -1

Explanation: No number of moves will make the board solved.

Input: board = [[4,1,2],[5,0,3]]

Output: 5

Explanation: 5 is the smallest number of moves that solves the board.

An example path:

After move 0: [[4,1,2],[5,0,3]]

After move 1: [[4,1,2],[0,5,3]]

After move 2: [[0,1,2],[4,5,3]]

After move 3: [[1,0,2],[4,5,3]]

After move 4: [[1,2,0],[4,5,3]]

After move 5: [[1,2,3],[4,5,0]]

Input: board = [[3,2,4],[1,5,0]]

Output: 14

Note:

board will be a 2 x 3 array as described above.

board[i][j] will be a permutation of [0, 1, 2, 3, 4, 5].

public class Solution {
    public int slidingPuzzle(int[][] board) {
        Set<String> seen = new HashSet<>(); // used to avoid duplicates
        String target = "123450";
        // convert board to string - initial state.
        String s = Arrays.deepToString(board).replaceAll("\\[|\\]|,|\\s", "");
        Queue<String> q = new LinkedList<>(Arrays.asList(s));
        seen.add(s);
        int ans = 0; // record the # of rounds of Breadth Search
        while (!q.isEmpty()) { // Not traverse all states yet?
            // loop used to control search breadth.
            for (int sz = q.size(); sz > 0; --sz) { 
                String str = q.poll();
                if (str.equals(target)) { return ans; } // found target.
                int i = str.indexOf('0'); // locate '0'
                int[] d = { 1, -1, 3, -3 }; // potential swap distances.
                for (int k = 0; k < 4; ++k) { // traverse all options.
                    int j = i + d[k]; // potential swap index.
                    // conditional used to avoid invalid swaps.
                    if (j < 0 || j > 5 || i == 2 && j == 3 || i == 3 && j == 2) { continue; } 
                    char[] ch = str.toCharArray();
                    // swap ch[i] and ch[j].
                    char tmp = ch[i];
                    ch[i] = ch[j];
                    ch[j] = tmp;
                    s = String.valueOf(ch); // a new candidate state.
                    if (seen.add(s)) { q.offer(s); } //Avoid duplicate.
                }
            }
            ++ans; // finished a round of Breadth Search, plus 1.
        }
        return -1;
    }
}

note:

  • 我们可以保存一个状态，比如说一个string，一维的比较容易转为string，Arrays.toString(), 那二维的array如何转为string呢？可以用Arrays.deepToString(board).replaceAll("\[|\]|,|\s", "")。这里有两个我们要学习的东西，一个是Arrays.deepToString().可以把二维的matrix转为一个matrix的string序列。二个是利用string的replaceAll()+正则表达式来去掉一些符号. http://www.vogella.com/tutorials/JavaRegularExpressions/article.html

  • Queue<String> q = new LinkedList<>(Arrays.asList(s)); 如何一行完成queue的初始化和加入string s。先把s转为List<String>, 然后在初始化给queue。

  • 要学会把matrix的操作转为array一维的操作，int[] d = {1, -1, 3, -3};

774. Minimize Max Distance to Gas Station

On a horizontal number line, we have gas stations at positionsstations[0], stations[1], ..., stations[N-1], whereN = stations.length.

Now, we addKmore gas stations so thatD, the maximum distance between adjacent gas stations, is minimized.

Return the smallest possible value ofD.

Example:

Input:
 stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9

Output:
 0.500000

Note:

  1. stations.lengthwill be an integer in range[10, 2000]
  2. stations[i]will be an integer in range[0, 10^8]
  3. Kwill be an integer in range[1, 10^6]
  4. Answers within10^-6of the true value will be accepted as correct.

idea:Why did I use s binary search?
In fact there are some similar problems on Leetcode so that is part of experience.
Secondly, I got a hint from "Answers within 10^-6 of the true value will be accepted as correct.". The first solution I tried was binary search.
Because binary search may not find exact value but it can approach the true answer.

Explanation of solution
Now we are using binary search to find the smallest possible value of D.
I initilzeleft = 0andright = the distance between the first and the last station
countis the number of gas station we need to make it possible.
if count > K, it meansmidis too small to realize using only K more stations.
if count <= K, it meansmidis possible and we can continue to find a bigger one.
Whenleft + 1e-6 >= right, it means the answer within 10^-6 of the true value and it will be accepted.

public double minmaxGasDist(int[] st, int K) {
        int count, N = st.length;
        double left = 0, right = st[N - 1] - st[0], mid;

        while (left +1e-6 < right) {
            mid = (left + right) / 2;
            count = 0;
            for (int i = 0; i < N - 1; ++i)
                count += Math.ceil((st[i + 1] - st[i]) / mid) - 1;
            if (count > K) left = mid;
            else right = mid;
        }
        return right;
    }

another interesting post is this: https://discuss.leetcode.com/topic/118737/approach-the-problem-using-the-trial-and-error-algorithm

It come up with a "trial and error" algorithm, which would be used if you find all other common solutions suffer severely from bad time or space performance.

results matching ""

    No results matching ""