leetcode 957 Prison Cells After N Days & 955. Delete Columns to Make Sorted II

谁借莪１个温暖的怀抱￠ 2021-12-13 19:41 137阅读 0赞

## 957 Prison Cells After N Days ##

The first intuition is that, after first day, the first and last cell will be vacant.

So there'll be 2^6 = 64 total state for prison. And if N is big enough, there will be a loop.

The solution is find the loop count, then compute the final state.

class Solution { public int[] prisonAfterNDays(int[] cells, int N) { Map<String, Integer> m = new HashMap<String, Integer>(); for (int i = 0; i < N; ++i) { cells = compute(cells); String key = Arrays.toString(cells); if (m.get(key) != null) { int count = (N - 1) % i; for (int c = 0; c < count; ++c) { cells = compute(cells); } return cells; } else { m.put(key, i); } } return cells; } private int[] compute(int[] cells) { int[] d = new int[8]; for (int j = 1; j < 7; ++j) { d[j] = cells[j - 1] == cells[j + 1] ? 1: 0; } return d; } }

--------------------

## 955. Delete Columns to Make Sorted II ##

I used greedy to solve this problem.

It's not so hard to come up with the solution, for every letter position, iterate over A, letters are not in lexicographic order, add one to deletion counter, if in lexicographic order, record negibour relation (if the current one is lexicographic bigger or equal to the previous one).

The time complexity is O (NW) in which N is length of some A\[i\], and W is length of A.

The space complexity is O (NW) too, although some optimization can be done to the below code to make it become O(W).

class Solution { public int minDeletionSize(String[] A) { int[] dir = new int[A.length]; int N = A[0].length(); int D = 0; for (int i = 0; i < N; ++i) { int[] d = new int[A.length]; boolean valid = true; int sum = 0; for (int j = 1; j < A.length; ++j) { if (dir[j] == 0) { if (A[j].charAt(i) < A[j - 1].charAt(i)) { D += 1; valid = false; break; } else { d[j] = (A[j].charAt(i) > A[j - 1].charAt(i)) ? 1: 0; } } else { d[j] = 1; } sum += d[j]; } if (valid) { if (sum == A.length) return D; else dir = d; } } return D; } }

转载于:https://www.cnblogs.com/exhausttolive/p/10544387.html