2020-4-1

1111.有效括号的嵌套深度

✒解题思路：

1. 一道看不懂的题…

public class Solution {
    public int[] maxDepthAfterSplit(String seq) {
        int[] ans = new int [seq.length()];
        int idx = 0;
        for(char c: seq.toCharArray()) {
            ans[idx++] = c == '(' ? idx & 1 : ((idx + 1) & 1);
        }
        return ans;
    }
}

1046.最后一块石头的重量

✒解题思路：

1. 使用堆，优先队列

class Solution {
	public int lastStoneWeight(int[] stones) {
		Queue<Integer> pq = new PriorityQueue<>((v1,v2) -> v2 - v1);
		for (int num : stones) {
			pq.offer(num);
		}
		while (pq.size() > 1) {
			int x = pq.poll();
			int y = pq.poll();
			if (x > y) {
				pq.offer(x - y);
			}
		}
		return pq.size() == 0 ? 0 : pq.peek();
	}
}

面试题40.最小的k个数

✒解题思路：

1. 堆

class Solution {
	public int[] getLeastNumbers(int[] arr, int k) {
		int len = arr.length;
		if (len == 0 || k == 0) {
			return new int[0];
		}
		PriorityQueue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
		for (int i : arr) {
			if (pq.size() < k) {
				pq.offer(i);
			} else if (i < pq.peek()) {
				pq.poll();
				pq.offer(i);
			}
		}
		int[] result = new int[pq.size()];
		int index = 0;
		for (int num : pq) {
			result[index++] = num;
		}
		return result;
	}
}

451.根据字符出现频率排序

✒解题思路：

1. 堆

class Solution {
	public String frequencySort(String s) {
		StringBuilder result = new StringBuilder();
		if (s == null) {
			return result.toString();
		}
		Map<Character, Integer> map = new HashMap<>();
		for (char c : s.toCharArray()) {
			if (map.containsKey(c)) {
				map.put(c, map.get(c) + 1);
			} else {
				map.put(c, 1);
			}
		}
		Queue<Character> pq = new PriorityQueue<>((m1, m2) -> map.get(m2) - map.get(m1));
		for (char c : map.keySet()) {
			pq.offer(c);
		}
		while (!pq.isEmpty()) {
			char c = pq.poll();
			int size = map.get(c);
			for (int i = 0; i < size; i++) {
				result.append(c);
			}
		}
		return result.toString();
	}
}

703.数据流中的第K大元素

✒解题思路：

1. 堆

class KthLargest {
	Queue<Integer> pq;
	int k;

	public KthLargest(int k, int[] nums) {
		pq = new PriorityQueue<>();
		this.k = k;
		for (int num : nums) {
			if(pq.size()<k){
				pq.offer(num);
			}else if(num>pq.peek()){
				pq.poll();
				pq.offer(num);
			}
		}
	}

	public int add(int val) {
		if (pq.size() < k) {
			pq.offer(val);
		} else if (val > pq.peek()) {
			pq.poll();
			pq.offer(val);
		}
		return pq.peek();
	}
}
/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

263.丑数

✒解题思路：

1. 当该数存在2,3,5之外的因子时就不为丑数

class Solution {
	public boolean isUgly(int num) {
		if (num == 0) {
			return false;
		}
		while (num != 1) {
			if (num % 2 == 0) {
				num /= 2;
				continue;
			}
			if (num % 3 == 0) {
				num /= 3;
				continue;
			}
			if (num % 5 == 0) {
				num /= 5;
				continue;
			}
			return false;
		}
		return true;
	}
}