second round leetcode
57,
Insert Interval (Done)
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
List<Interval> ret = new ArrayList<Interval>();
int i = 0;
for (; i < intervals.size(); i++) {
if (intervals.get(i).end < newInterval.start) {
ret.add(intervals.get(i));
}
else {
break;
}
}
for (; i < intervals.size(); i++) {
if (intervals.get(i).start > newInterval.end) {
break;
}
else {
newInterval.start = Math.min(newInterval.start, intervals.get(i).start);
newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
}
}
ret.add(newInterval);
for (; i < intervals.size(); i++) {
ret.add(intervals.get(i));
}
return ret;
}
}
381,
Insert Delete GetRandom O(1) - Duplicates allowed (Done)
public class RandomizedCollection {
Map<Integer, Set<Integer>> map;
List<Integer> list;
Random r;
/** Initialize your data structure here. */
public RandomizedCollection() {
map = new HashMap<Integer, Set<Integer>>();
list = new ArrayList<Integer>();
r = new Random();
}
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
public boolean insert(int val) {
if (!map.containsKey(val)) {
map.put(val, new HashSet<Integer>());
map.get(val).add(list.size());
list.add(val);
return true;
}
else {
map.get(val).add(list.size());
list.add(val);
return false;
}
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
public boolean remove(int val) {
if (!map.containsKey(val)) {
return false;
}
else {
int index = map.get(val).iterator().next();
map.get(val).remove(index);
if (map.get(val).size() == 0) {
map.remove(val);
}
if (index < list.size() - 1) {
list.set(index, list.get(list.size() - 1));
map.get(list.get(list.size() - 1)).remove(list.size() - 1);
map.get(list.get(list.size() - 1)).add(index);
}
list.remove(list.size() - 1);
return true;
}
}
/** Get a random element from the collection. */
public int getRandom() {
return list.get(r.nextInt(list.size()));
}
}
/**
* Your RandomizedCollection object will be instantiated and called as such:
* RandomizedCollection obj = new RandomizedCollection();
* boolean param_1 = obj.insert(val);
* boolean param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/
4,
Median of Two Sorted Arrays (Done)
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.length;
int n = nums2.length;
int half = (m + n + 1) / 2;
int begin = 0;
int end = m;
while (begin <= end) {
int i = begin + (end - begin) / 2;
int j = half - i;
// nums1[i - 1] and nums2[j]
if (i > 0 && j < n && nums1[i - 1] > nums2[j]) {
end = i - 1;
}
// nums2[j - 1] and nums1[i]
else if (j > 0 && i < m && nums2[j - 1] > nums1[i]) {
begin = i + 1;
}
else {
int left = 0;
if (i == 0) {
left = nums2[j - 1];
}
else if (j == 0) {
left = nums1[i - 1];
}
else {
left = Math.max(nums1[i - 1], nums2[j - 1]);
}
if ((m + n) % 2 == 1) {
return left * 1.0;
}
int right = 0;
if (i == m) {
right = nums2[j];
}
else if (j == n) {
right = nums1[i];
}
else {
right = Math.min(nums1[i], nums2[j]);
}
return (left + right) / 2.0;
}
}
return -1;
}
}
死记住
45
Jump Game II (Done)
public class Solution {
public int jump(int[] nums) {
if (nums == null || nums.length <= 1) {
return 0;
}
int step = 0;
int edge = 0;
int maxReach = nums[0];
for (int i = 1; i < nums.length; i++) {
if (i > edge) {
edge = maxReach;
step++;
if (edge >= nums.length - 1) {
return step;
}
}
maxReach = Math.max(maxReach, nums[i] + i);
}
return step;
}
}
63, 在矩形四边处，处理上有点小问题 (Done)
Unique Paths II
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int[][] nums = obstacleGrid;
if (nums == null || nums.length == 0 || nums[0].length == 0) {
return 0;
}
int row = nums.length;
int col = nums[0].length;
int temp = nums[0][0];
int i = 0;
for (; i < col; i++) {
if (nums[0][i] == 0) {
nums[0][i] = 1;
}
else {
break;
}
}
for (; i < col; i++) {
nums[0][i] = 0;
}
nums[0][0] = temp;
i = 0;
for (; i < row; i++) {
if (nums[i][0] == 0) {
nums[i][0] = 1;
}
else {
break;
}
}
for (; i < row; i++) {
nums[i][0] = 0;
}
for (i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (nums[i][j] == 1) {
nums[i][j] = 0;
}
else {
nums[i][j] = nums[i - 1][j] + nums[i][j - 1];
}
}
}
return nums[row - 1][col - 1];
}
}
31,
Next Permutation (Done)
有点不顺 注意，我们需要找的一定是 > nums[i] 的最小数
** 注意：nums[] 可能会有重复。所以一开始找区域时，是 >= 时，i--
然后找最接近的最大值时，不能特殊考虑相等的情况 **
public class Solution {
public void nextPermutation(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
if (i < 0) {
reverse(nums, 0, nums.length - 1);
return;
}
int begin = i + 1;
int end = nums.length - 1;
while (begin <= end) {
int mid = begin + (end - begin) / 2;
if (nums[mid] > nums[i]) {
begin = mid + 1;
}
else {
end = mid - 1;
}
}
int temp = nums[end];
nums[end] = nums[i];
nums[i] = temp;
reverse(nums, i + 1, nums.length - 1);
}
private void reverse(int[] nums, int i, int j) {
int begin = i;
int end = j;
while (begin < end) {
int temp = nums[begin];
nums[begin] = nums[end];
nums[end] = temp;
begin++;
end--;
}
}
}
277,
Find the Celebrity (Done)
没做出来
/* The knows API is defined in the parent class Relation.
boolean knows(int a, int b); */
public class Solution extends Relation {
public int findCelebrity(int n) {
if (n <= 0) {
return -1;
}
int candidate = 0;
for (int i = 1; i < n; i++) {
if (knows(candidate, i)) {
candidate = i;
}
}
for (int i = 0; i < n; i++) {
if (i == candidate) {
continue;
}
else if (knows(i, candidate) && !knows(candidate, i)) {
continue;
}
else {
return -1;
}
}
return candidate;
}
}
280
Wiggle Sort (Done)
public class Solution {
public void wiggleSort(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
for (int i = 0; i + 1 < nums.length; i += 2) {
if (nums[i + 1] < nums[i]) {
swap(nums, i, i + 1);
}
}
for (int i = 1; i + 1 < nums.length; i += 2) {
if (nums[i] < nums[i + 1]) {
swap(nums, i, i + 1);
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
34
Search for a Range (Done)
public class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return new int[]{-1, -1};
}
int begin = 0;
int end = nums.length - 1;
int index = -1;
while (begin <= end) {
int mid = begin + (end - begin) / 2;
if (nums[mid] < target) {
begin = mid + 1;
}
else if (nums[mid] > target) {
end = mid - 1;
}
else {
index = mid;
break;
}
}
if (index == -1) {
return new int[]{-1, -1};
}
begin = 0;
end = index - 1;
while (begin <= end) {
int mid = begin + (end - begin) / 2;
if (nums[mid] == target) {
end = mid - 1;
}
else {
begin = mid + 1;
}
}
int left = end + 1;
begin = index + 1;
end = nums.length - 1;
while (begin <= end) {
int mid = begin + (end - begin) / 2;
if (nums[mid] == target) {
begin = mid + 1;
}
else {
end = mid - 1;
}
}
int right = begin - 1;
return new int[]{left, right};
}
}
163
Missing Ranges (Not Done)
** 注意可能越界，所有的 nums[i] + 1 or - 1 都得将 nums[i] 先转换成long **
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<String> findMissingRanges(int[] nums, int lower, int upper) {
List<String> ret = new ArrayList<String>();
long min = lower;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > min) {
String s = getRange(min, (long) nums[i] - 1);
ret.add(s);
}
min = (long) nums[i] + 1;
}
if (min <= upper) {
String s = getRange(min, upper);
ret.add(s);
}
return ret;
}
private String getRange(long begin, long end) {
if (begin == end) {
return "" + begin;
}
else {
return begin + "->" + end;
}
}
}
229,
Majority Element II (Done)
注意顺序，先判断i1, i2 非空时的情况，再判断空情况
public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> ret = new ArrayList<Integer>();
if (nums == null || nums.length == 0) {
return ret;
}
Integer i1 = null;
Integer i2 = null;
int c1 = 0;
int c2 = 0;
for (int i = 0; i < nums.length; i++) {
if (i1 != null && i1 == nums[i]) {
c1++;
}
else if (i2 != null && i2 == nums[i]) {
c2++;
}
else if (i1 == null) {
i1 = new Integer(nums[i]);
c1 = 1;
}
else if (i2 == null) {
i2 = new Integer(nums[i]);
c2 = 1;
}
else {
c1--;
if (c1 == 0) {
i1 = null;
}
c2--;
if (c2 == 0) {
i2 = null;
}
}
}
c1 = 0;
c2 = 0;
for (int i = 0; i < nums.length; i++) {
if (i1 != null && i1 == nums[i]) {
c1++;
}
else if (i2 != null && i2 == nums[i]) {
c2++;
}
}
if (c1 > nums.length / 3) {
ret.add(i1);
}
if (c2 > nums.length / 3) {
ret.add(i2);
}
return ret;
}
}
370,
Range Addition (Done)
没做出来
public class Solution {
public int[] getModifiedArray(int length, int[][] updates) {
int[] ret = new int[length];
for (int i = 0; i < updates.length; i++) {
int start = updates[i][0];
int end = updates[i][1];
int step = updates[i][2];
ret[start] += step;
if (end + 1 < length) {
ret[end + 1] -= step;
}
}
for (int i = 1; i < length; i++) {
ret[i] += ret[i - 1];
}
return ret;
}
}
209,
Minimum Size Subarray Sum (Done)
有点不顺畅
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int begin = 0;
int end = 0;
int minLength = Integer.MAX_VALUE;
int sum = 0;
while (end < nums.length) {
sum += nums[end];
if (sum >= s) {
minLength = Math.min(minLength, end - begin + 1);
sum -= nums[begin];
begin++;
if (begin > end) {
end = begin;
}
else {
sum -= nums[end];
}
}
else {
end++;
}
}
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}
}
396,
Rotate Function (Done)
没做出来
public class Solution {
public int maxRotateFunction(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int iteration = 0;
int base = 0;
for (int i = 0; i < A.length; i++) {
base += i * A[i];
iteration += A[i];
}
int max = base;
for (int i = 1; i < A.length; i++) {
base -= iteration;
base += A.length * A[i - 1];
max = Math.max(max, base);
}
return max;
}
}
407
Trapping Rain Water II (Done)
忘记了还需要用 priority queue
public class Solution {
private class Node {
int x;
int y;
int height;
Node (int x, int y, int height) {
this.x = x;
this.y = y;
this.height = height;
}
}
int row = 0;
int col = 0;
public int trapRainWater(int[][] heightMap) {
if (heightMap == null || heightMap.length == 0 || heightMap[0].length == 0) {
return 0;
}
this.row = heightMap.length;
this.col = heightMap[0].length;
PriorityQueue<Node> pq = new PriorityQueue<Node>(10, new Comparator<Node>() {
public int compare(Node n1, Node n2) {
return n1.height - n2.height;
}
});
boolean[][] mark = new boolean[row][col];
for (int i = 0; i < col; i++) {
pq.offer(new Node(0, i, heightMap[0][i]));
mark[0][i] = true;
if (row - 1 > 0) {
pq.offer(new Node(row - 1, i, heightMap[row - 1][i]));
mark[row - 1][i] = true;
}
}
for (int i = 0; i < row; i++) {
pq.offer(new Node(i, 0, heightMap[i][0]));
mark[i][0] = true;
if (col - 1 > 0) {
pq.offer(new Node(i, col - 1, heightMap[i][col - 1]));
mark[i][col - 1] = true;
}
}
int sum = 0;
int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!pq.isEmpty()) {
Node curr = pq.poll();
for (int i = 0; i < 4; i++) {
int next_x = curr.x + dir[i][0];
int next_y = curr.y + dir[i][1];
if (check(next_x, next_y) && !mark[next_x][next_y]) {
sum += Math.max(0, curr.height - heightMap[next_x][next_y]);
mark[next_x][next_y] = true;
pq.offer(new Node(next_x, next_y, Math.max(curr.height, heightMap[next_x][next_y])));
}
}
}
return sum;
}
private boolean check(int i, int j) {
if (i < 0 || i >= row || j < 0 || j >= col) {
return false;
}
return true;
}
}
317
Shortest Distance from All Buildings (Done)
没做出来，今天要再写一遍
public class Solution {
private class Node {
int x;
int y;
int step;
Node (int x, int y, int step) {
this.x = x;
this.y = y;
this.step = step;
}
}
int row = 0;
int col = 0;
int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
public int shortestDistance(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
row = grid.length;
col = grid[0].length;
int[][] dist = new int[row][col];
List<Node> list = new ArrayList<Node>();
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == 1) {
list.add(new Node(i, j, 0));
}
grid[i][j] = -grid[i][j];
}
}
for (int i = 0; i < list.size(); i++) {
bfs(list.get(i), grid, dist, i);
}
int max = Integer.MAX_VALUE;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == list.size()) {
max = Math.min(max, dist[i][j]);
}
}
}
return max == Integer.MAX_VALUE ? -1 : max;
}
private void bfs(Node root, int[][] grid, int[][] dist, int k) {
Queue<Node> q = new LinkedList<Node>();
q.offer(root);
while (!q.isEmpty()) {
Node curr = q.poll();
for (int i = 0; i < 4; i++) {
int nei_x = curr.x + dir[i][0];
int nei_y = curr.y + dir[i][1];
if (check(nei_x, nei_y) && grid[nei_x][nei_y] == k) {
q.offer(new Node(nei_x, nei_y, curr.step + 1));
dist[nei_x][nei_y] += curr.step + 1;
grid[nei_x][nei_y] = k + 1;
}
}
}
}
private boolean check(int i, int j) {
if (i < 0 || i >= row || j < 0 || j >= col) {
return false;
}
return true;
}
}
301
Remove Invalid Parentheses (Done)
基本写了出来，有点磨蹭
public class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> ret = new ArrayList<String>();
helper(0, 0, s, new char[]{'(', ')'}, ret);
return ret;
}
private void helper(int last_i, int last_j, String s, char[] pair, List<String> ret) {
int cnt = 0;
for (int i = last_i; i < s.length(); i++) {
char curr = s.charAt(i);
if (curr == pair[0]) {
cnt++;
}
else if (curr == pair[1]) {
cnt--;
if (cnt < 0) {
for (int j = last_j; j <= i; j++) {
if (s.charAt(j) == pair[1] && (j == last_j || s.charAt(j - 1) != pair[1])) {
helper(i, j, s.substring(0, j) + s.substring(j + 1), pair, ret);
}
}
return;
}
}
}
String r = new StringBuilder(s).reverse().toString();
if (pair[0] == '(') {
helper(0, 0, r, new char[]{')', '('}, ret);
}
else {
ret.add(r);
}
}
}
323
Number of Connected Components in an Undirected Graph (Done)
没想出来，以为还是用入度解
public class Solution {
Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
int V;
public int countComponents(int n, int[][] edges) {
this.V = n;
for (int i = 0; i < edges.length; i++) {
int u = edges[i][0];
int v = edges[i][1];
if (!map.containsKey(u)) {
map.put(u, new HashSet<Integer>());
}
if (!map.containsKey(v)) {
map.put(v, new HashSet<Integer>());
}
map.get(u).add(v);
map.get(v).add(u);
}
boolean[] mark = new boolean[n];
int cnt = 0;
for (int i = 0; i < n; i++) {
if (!mark[i]) {
cnt++;
bfs(i, mark);
}
}
return cnt;
}
private void bfs(int root, boolean[] mark) {
mark[root] = true;
Queue<Integer> q = new LinkedList<Integer>();
q.offer(root);
while (!q.isEmpty()) {
int curr = q.poll();
if (map.containsKey(curr)) {
Set<Integer> nei = map.get(curr);
for (Integer temp : nei) {
if (!mark[temp]) {
mark[temp] = true;
q.offer(temp);
}
}
}
}
}
}
279
Perfect Squares (Done)
没做出来
public class Solution {
public int numSquares(int n) {
if (n <= 0) {
return 0;
}
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; i++) {
int min = Integer.MAX_VALUE;
int j = 1;
while (j * j <= i) {
min = Math.min(min, 1 + dp[i - j * j]);
j++;
}
dp[i] = min;
}
return dp[n];
}
}
261
Graph Valid Tree
没做出来
public class Solution {
Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
public boolean validTree(int n, int[][] edges) {
for (int i = 0; i < edges.length; i++) {
int u = edges[i][0];
int v = edges[i][1];
if (!map.containsKey(u)) {
map.put(u, new HashSet<Integer>());
}
if (!map.containsKey(v)) {
map.put(v, new HashSet<Integer>());
}
map.get(u).add(v);
map.get(v).add(u);
}
int cnt = 0;
boolean[] mark = new boolean[n];
Queue<Integer> q = new LinkedList<Integer>();
q.offer(0);
mark[0] = true;
while (!q.isEmpty()) {
int curr = q.poll();
cnt++;
if (map.containsKey(curr)) {
Set<Integer> nei = map.get(curr);
for (Integer temp : nei) {
if (mark[temp]) {
return false;
}
mark[temp] = true;
map.get(temp).remove(curr);
q.offer(temp);
}
}
}
return cnt == n;
}
}
269
Alien Dictionary (Not finished)
test case 更新了，没写对
** 记住！图中，利用入度解决问题时，一定要判断，
if (!map.get(u).contains(v)) {// 再去更新入度}
删去入度时，也得先判断，当前的 u， 是否存在于 map 中 **
public class Solution {
Map<Character, Set<Character>> map = new HashMap<Character, Set<Character>>();
Map<Character, Integer> indegree = new HashMap<Character, Integer>();
public String alienOrder(String[] words) {
if (words == null || words.length == 0) {
return "";
}
for (String word : words) {
for (char c : word.toCharArray()) {
indegree.put(c, 0);
}
}
for (int i = 0; i < words.length - 1; i++) {
String s1 = words[i];
String s2 = words[i + 1];
int k = 0;
while (k < Math.min(s1.length(), s2.length())) {
if (s1.charAt(k) == s2.charAt(k)) {
k++;
}
else {
break;
}
}
if (k == Math.min(s1.length(), s2.length())) {
if (s1.length() > s2.length()) {
return "";
}
else {
continue;
}
}
else {
char c1 = s1.charAt(k);
char c2 = s2.charAt(k);
if (!map.containsKey(c1)) {
map.put(c1, new HashSet<Character>());
}
if (!map.get(c1).contains(c2)) {
map.get(c1).add(c2);
indegree.put(c2, indegree.get(c2) + 1);
}
}
}
Queue<Character> q = new LinkedList<Character>();
for (Character c : indegree.keySet()) {
if (indegree.get(c) == 0) {
q.offer(c);
}
}
String ret = "";
while (!q.isEmpty()) {
char c = q.poll();
ret += c;
if (map.containsKey(c)) {
Set<Character> nei = map.get(c);
for (Character temp : nei) {
indegree.put(temp, indegree.get(temp) - 1);
if (indegree.get(temp) == 0) {
q.offer(temp);
}
}
}
}
if (ret.length() == indegree.size()) {
return ret;
}
else {
return "";
}
}
}
332
Reconstruct Itinerary (Done)
基本写对了，还有小Bug
public class Solution {
public List<String> findItinerary(String[][] tickets) {
List<String> ret = new ArrayList<String>();
Map<String, List<String>> map = new HashMap<String, List<String>>();
for (int i = 0; i < tickets.length; i++) {
String src = tickets[i][0];
String dest = tickets[i][1];
if (!map.containsKey(src)) {
map.put(src, new ArrayList<String>());
}
insert(dest, map.get(src));
}
ret.add("JFK");
int total = tickets.length;
helper("JFK", total, map, ret);
return ret;
}
private boolean helper(String src, int total, Map<String, List<String>> map, List<String> ret) {
if (total == 0) {
return true;
}
else {
List<String> dests = map.get(src);
if (dests == null || dests.size() == 0) {
return false;
}
for (int i = 0; i < dests.size(); i++) {
String dest = dests.get(i);
ret.add(dest);
dests.remove(i);
boolean flag = helper(dest, total - 1, map, ret);
if (flag) {
return true;
}
ret.remove(ret.size() - 1);
dests.add(i, dest);
}
return false;
}
}
private void insert(String s, List<String> list) {
int i = 0;
for (; i < list.size(); i++) {
if (s.compareTo(list.get(i)) <= 0) {
break;
}
}
if (i >= list.size()) {
list.add(s);
}
else {
list.add(i, s);
}
}
}
99
Recover Binary Search Tree (Done)
没做出来
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public void recoverTree(TreeNode root) {
if (root == null) {
return;
}
TreeNode small = null;
TreeNode big = null;
Stack<TreeNode> st = new Stack<TreeNode>();
TreeNode p = root;
while (p != null) {
st.push(p);
p = p.left;
}
TreeNode pre = null;
int cnt = 0;
while (!st.isEmpty()) {
TreeNode curr = st.pop();
if (pre == null || pre.val < curr.val) {
pre = curr;
}
else {
if (cnt == 0) {
big = pre;
small = curr;
cnt++;
}
else {
small = curr;
}
}
if (curr.right != null) {
curr = curr.right;
while (curr != null) {
st.push(curr);
curr = curr.left;
}
}
}
int temp = big.val;
big.val = small.val;
small.val = temp;
}
}
394
Decode String (Not finished)
没做出来，和 basic calculator很像
public class Solution {
public String decodeString(String s) {
if (s == null || s.length() == 0) {
return s;
}
Stack<String> st = new Stack<String>();
Stack<Integer> cnt = new Stack<Integer>();
int num = 0;
String result = "";
for (int i = 0; i < s.length(); i++) {
char curr = s.charAt(i);
if (Character.isDigit(curr)) {
num = 10 * num + (curr - '0');
}
else if (curr == '[') {
st.push(result);
cnt.push(num);
result = "";
num = 0;
}
else if (curr == ']') {
int counter = cnt.pop();
StringBuilder sb = new StringBuilder();
for (int j = 0; j < counter; j++) {
sb.append(result);
}
result = st.pop() + sb.toString();
}
else {
result += curr;
}
}
return result;
}
}
227
Basic Calculator II
没做出来,因为有乘除，得有一个 char 来保存前一个运算符
224
Basic Calculator
没做出来
-
Find Leaves of Binary Tree
没能拿最优解来做 -
Nested List Weight Sum II
没做出来 -
House Robber III
没做出来 -
Interleaving String
没做出来 -
Word Break II
有点生疏，一开始忘记加cache了 -
Distinct Subsequences
没做出来
188.Best Time to Buy and Sell Stock IV
没做出来
-
Scramble String
基本思路有了，有几个东西忘了
1 . isSame, 用老判断字母组成是否一致
2 . cache, 三维dp,
dp[len][len][len + 1] -
Palindrome Partitioning II
没做出来 -
Create Maximum Number
没做出来 -
Remove K Digits
自己写了出来，但有些corner case 没考虑到
比如，最后的结果，可能有leading zero, 要去了
比如， 最后的结果，可能长度为0，这个时候不能返回空字符串，得返回 “0” -
Max Sum of Rectangle No Larger Than K
getMaxWithK()
写的有些问题
set.add(0)
还有temp, 要在判断之后再加入set中
Paint House II
没做出来,
min1, min2
lastMin1, lastMin2
- Ugly Number II
总是记不住！
int[] dp
i2, i3, i5 三个指针指向dp
-
Coin Change
写的不顺畅
而且， 内循环，循环的是 coins array -
Maximal Square
递推式写的不对。
记住，是左，上，左上，三个点 -
Counting Bits
没做出来 -
Best Time to Buy and Sell Stock with Cooldown
没做出来 -
Combination Sum IV
没做出来，和 coin change 很类似,只不过 coin change 求的是最小值，这里是累加 -
Guess Number Higher or Lower II
没做出来，和 burst baloon 很像 -
Android Unlock Patterns
没做出来。
skip[][] 是关键 -
Largest Divisible Subset
先找出最长子链的长度，以及index，然后再倒退后去复原 -
Is Subsequence
原题不难。
但是对于follow up, 需要构造map,然后用 binary search 来做 -
Bomb Enemy
没做出来
updateRow
updateCol -
Paint Fence
没做出来。
分成两种类型
diff,
same -
Longest Substring with At Most Two Distinct Characters
没做来，这么重要的题目。
不应该。
leftMost
Longest Substring Without Repeating Characters
自己写了出来，但有点磨蹭
-
Longest Substring with At Most K Distinct Characters
本可以做出来的，犯了低级错误。
map.remove 是移除 character -
Read N Characters Given Read4
忘记怎么做了 -
Read N Characters Given Read4 II - Call multiple times
知道简单版怎么做后，这个也很容易做了，加一个全局变量队列就行 -
Palindrome Pairs
自己写了出来。
但是错了挺多次。
处理好：
isPalindrome
reverse = s, “” contains in map
if word == “”, continue -
Shortest Palindrome
基本思路记得，但写的还是不顺手，没写出来 -
Valid Number
没能最后写出来。
dot, if (dot || exp)
exp, if (!num || exp)
还有 curr == ‘+’ or ‘-‘ after exp -
Substring with Concatenation of All Words
和 minimum window substring 很类似，只不过一个是 string, 一个是 character
这里要注意的是，
有两个map
外层for循环，i < len -
Mini Parser
没做出来，和 basic calculator很像。
关键一步在于，一开始判断[0] 是否为 ‘[‘
-
Encode and Decode Strings
没做出来
length of string + “/“ + string -
Group Anagrams
hashcode 没想到怎么求，
原来直接有系统函数：
Arrays.hashCode(char[] arr) -
Group Shifted Strings
基本思路是正确的。注意偏差offset -
Flip Game II
忘记怎么做了 -
Generalized Abbreviation
没做出来。其实思路和
interleave string 很像 -
Valid Word Abbreviation
没做出来，看的答案 -
Frog Jump
没做出来
DP， 看的答案 -
Sudoku Solver
基本写了出来。
记住， for 循环结束后，
board[i][j] = ‘.’;
return false; -
Meeting Rooms II
有点疙瘩 -
Min Stack
粗心错了，还得再写一遍 -
Sliding Window Maximum
Deque
peekFirst(), 左侧
peekLast(), 右侧
队列内部保持一个递减数列，
所以第一个循环，
q.peekFirst()
第二个循环，
q.peekLast() -
Maximum Size Subarray Sum Equals k
没做出来。
注意三种题：
minimum size subaray sum <= k, all members are positive
=> sliding window
maximum size subarray sum equals k
=> sums[], and using two sum
maximum size subarray sum <= k
=> need to use TreeMap
网友评论