This is very easy question basically you count how many negative number.
class Solution {
public int arraySign(int[] nums) {
int count = 0;
for(int i = 0; i < nums.length; i ++){
if(nums[i] == 0) return 0;
if(nums[i] < 0){
count ++;
}
}
return count % 2 == 0 ? 1 : -1;
}
}
Since today's questions are too easy, we just put down the res for both weekly challange and daily challange.
class Solution {
public double average(int[] salary) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int total = 0;
for(int n : salary){
min = Math.min(min,n);
max = Math.max(max,n);
total += n;
}
return (total - min - max) / (double)(salary.length - 2);
}
}
// the native apporach
class Solution {
public int[][] indexPairs(String text, String[] words) {
ArrayList<int[]> res = new ArrayList<>();
Arrays.sort(words,(a,b) ->{return a.length() - b.length();}); // insure the order.
for(int i = 0; i < text.length(); i ++){
for(String word : words){
if(text.substring(i).startsWith(word)){
res.add(new int[]{i,i + word.length() - 1});
}
}
}
int[][] ans = new int[res.size()][2];
for(int i = 0; i < res.size(); i ++){
ans[i] = res.get(i);
}
return ans;
}
}
Because trie can detect a shorter word along the way, this avoid the sorting which can take extra time. this is a better solution.
class Solution {
public class TrieNode{
boolean word;
TrieNode[] children;
public TrieNode(){
word = false;
children = new TrieNode[26]; //26 character
}
}
public class MyTrie{
TrieNode root;
public MyTrie(){
root = new TrieNode();
}
public void add(String word){
TrieNode curr = root;
for(char c : word.toCharArray()){
if(curr.children[c - 'a'] == null){
curr.children[c - 'a'] = new TrieNode();
}
curr = curr.children[c - 'a'];
}
curr.word = true;
}
public boolean serach(String word){
TrieNode curr = root;
for(char c : word.toCharArray()){
if(curr.children[c - 'a'] == null) return false;
curr = curr.children[c - 'a'];
}
return curr.word;
}
}
public int[][] indexPairs(String text, String[] words) {
MyTrie trie = new MyTrie();
for(String word : words){
trie.add(word);
}
List<int[]> res = new ArrayList<>();
for(int i = 0; i < text.length(); i ++){
TrieNode p = trie.root;
for (int j = i; j < text.length(); j++) {
if (p.children[text.charAt(j) - 'a'] == null) {
break;
}
p = p.children[text.charAt(j) - 'a'];
if (p.word) {
res.add(new int[] { i, j });
}
}
}
int[][] ans = new int[res.size()][];
ans = res.toArray(ans);
return ans;
}
}
Still union find, it is easy to identify, but there is little twist, initially I thought of sorting the edges, so we can union type 3 first, but this takes n log n time because sorting is bound by that, if we traversal twice the edges, still we only take just n time, so it would actually beat the way I implemented at begining. other than this, this question uses two union find data structure but everthing should be just the same.
class Solution {
public int maxNumEdgesToRemove(int n, int[][] edges) {
// still union find
// we can remove edge if when we trying to connect the nodes are already connected
UnionFind alice = new UnionFind(n);
UnionFind bob = new UnionFind(n);
int res = 0;
// do union for type 3 first
for(int[] edge : edges){
if(edge[0] == 3){
int a = edge[1];
int b = edge[2];
res += (alice.union(a,b) | bob.union(a,b));
}
}
for(int[] edge : edges){
int type = edge[0];
int a = edge[1];
int b = edge[2];
if(type == 1){
res += alice.union(a,b);
}else if(type == 2){
res += bob.union(a,b);
}
}
if(alice.isValid() && bob.isValid()){
return edges.length - res;
}else{
return -1;
}
}
public class UnionFind {
int[] parent;
int[] size;
int n;
public UnionFind(int n){
parent = new int[n + 1];
size = new int[n + 1];
for(int i = 0; i <= n; i ++){
parent[i] = i;
size[i] = 1;
}
this.n = n;
}
public int find(int a){
if(parent[a] == a) return a;
return parent[a] = find(parent[a]);
}
public int union(int a, int b){
int pa = find(a);
int pb = find(b);
if(pa == pb) return 0;
if(size[pa] > size[pb]){
// join b into a
parent[pb] = a;
size[pa] += size[pb];
}else{
parent[pa] = b;
size[pb] += size[pa];
}
n --;
return 1;
}
public boolean isValid(){
return n == 1;
}
}
}
Another same union find question , you can figure out it is a union find problem by the hint that determine a and b connected and a minimal spanning tree kind of a deal.
class Solution {
int[] parent;
int[] size;
public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
int queriesCount = queries.length;
boolean[] res = new boolean[queriesCount];
// init
parent = new int[n];
size = new int[n];
for(int i = 0; i < n; i ++){
parent[i] = i;
size[i] = 1;
}
// Store original indices with all queries.
int[][] queriesWithIndex = new int[queriesCount][4];
for (int i = 0; i < queriesCount; ++i) {
queriesWithIndex[i][0] = queries[i][0];
queriesWithIndex[i][1] = queries[i][1];
queriesWithIndex[i][2] = queries[i][2];
queriesWithIndex[i][3] = i;
}
Arrays.sort(edgeList,(a,b) ->{return a[2] - b[2];});
Arrays.sort(queriesWithIndex,(a,b) ->{return a[2] - b[2];});
int edgesIndex = 0;
for(int i = 0; i < queriesCount; i ++){
int p = queriesWithIndex[i][0];
int q = queriesWithIndex[i][1];
int limit = queriesWithIndex[i][2];
int originalIndex = queriesWithIndex[i][3];
// because we have the edges sorted
// while our paths are smaller than limit, we want to attache all the edges thta is less than limit
// if this made p q in a same union aka connected, we return true
while(edgesIndex < edgeList.length && edgeList[edgesIndex][2] < limit){
int node1 = edgeList[edgesIndex][0];
int node2 = edgeList[edgesIndex][1];
union(node1,node2);
edgesIndex += 1;
}
res[originalIndex] = find(p) == find(q);
}
return res;
}
private int find(int a){
if(parent[a] == a) return a;
return parent[a] = find(parent[a]);
}
private int union(int a, int b){
int pa = find(a);
int pb = find(b);
if(pa == pb) return 0;
if(size[pa] > pb){
parent[pb] = a;
size[pa] += size[pb];
}else{
parent[pa] = b;
size[pb] += size[pa];
}
return 1;
}
}
This question is marked hard, but in realality this is not a difficult question. Simple union find problem, you find all the samilar strs and union them , starts with n groups after union all possible strs, what you have left is group standing.
class Solution {
// union find
int[] parent;
int[] size;
public int numSimilarGroups(String[] strs) {
int n = strs.length;
parent = new int[n];
size = new int[n];
for(int i = 0; i < n; i ++){
parent[i] = i;
size[i] = 1;
}
int count = n;
for(int i = 0; i < n; i ++){
for(int j = i + 1; j < n; j ++){
String a = strs[i];
String b = strs[j];
if(similar(a,b)){
count -= union(i,j);
}
}
}
return count;
}
private int find(int a){
if(parent[a] == a) return a;
return parent[a] = find(parent[a]);
}
private int union(int a, int b){
int pa = find(a);
int pb = find(b);
if(pa == pb) return 0;
if(size[pa] > size[pb]){
// join b to a
parent[pb] = a;
size[pa] += size[pb];
}else{
parent[pa] = b;
size[pb] += size[pa];
}
return 1;
}
private boolean similar(String a, String b){
int diff = 0;
for(int i = 0; i < a.length(); i ++){
if(a.charAt(i) != b.charAt(i)){
diff ++;
}
}
return diff == 2 || diff == 0;
}
}
This is a harder question for me, write on paper and find the parttern.
class Solution {
public int bulbSwitch(int n) {
// n == 0 all bulbs are off
// n == 1 all bulbs with factor of 1
// n == 2 all bulbs with factor 2 (2,4,6,8,10)...
// n == 3 all bulbs with factor 3 (3,6,9).....
// ......
// so we are finding number from 1 to n are perfect square
// essencially we are trying to find the sqrt of the n
return (int) Math.sqrt(n);
}
}
Simple reccurssion, you have a base case where you have just 1 digit, simply return it, you have recussive case, you add all the digit and return addDigits adds all these digit recurssively
class Solution {
public int addDigits(int num) {
// base case
if(num < 10) return num;
int res = 0;
while(num != 0){
res += num % 10;
num /= 10;
}
return addDigits(res);
}
}
Consider we have a full infinite set at first Use a running curr to keep track of smallest number and priority queue to keep track if we have scarlet numbers before running smallest
class SmallestInfiniteSet {
PriorityQueue<Integer> pq = new PriorityQueue<>();
int curr;
public SmallestInfiniteSet() {
// set curr smallest to 1
curr = 1;
}
public int popSmallest() {
if(!pq.isEmpty())return pq.poll();
// if we have nothing in pq, curr smallest is what we poll out, and sus next number would be curr + 1
curr ++;
return curr - 1;
}
public void addBack(int num) {
if(num < curr & !pq.contains(num)){
// number is small and we dont have it in our pq
// add back
pq.add(num);
}
}
}
/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* SmallestInfiniteSet obj = new SmallestInfiniteSet();
* int param_1 = obj.popSmallest();
* obj.addBack(num);
*/
Very straightforward question, just mimc the instruction using priority queue.
class Solution {
public int lastStoneWeight(int[] stones) {
// very straight forward, we use priority queue to ensure we polling the largest 2 stones
PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->{return b - a;});
for(int stone : stones){
pq.add(stone);
}
// while we have 2 or more stones
while(pq.size() > 1){
int a = pq.poll();
int b = pq.poll();
if(a != b){
int remain = Math.abs(a - b);
pq.add(remain);
}
}
// return nothing if we got no stone or last stone standing.
return pq.isEmpty() ? 0 : pq.poll();
}
}
All the dp problem is kinda similar, this is marked at hard, but in reality it is backtrack question possible sub array partition with little modification.
class Solution {
int[] memo;
int MOD = 1000000007;
public int numberOfArrays(String s, int k) {
memo = new int[s.length() + 1];
Arrays.fill(memo,-1);
return dp(s,k,0);
}
private int dp(String s, int k, int curr){
// base case
if(curr == s.length()) return 1; // we have no more possible number to play with
if(s.charAt(curr) == '0') return 0; // leading zero
// solved case
if(memo[curr] != -1) return memo[curr];
// start res with 0
int res = 0;
for(int i = curr; i < s.length(); i ++){
// try pairtition at every possible point
String num = s.substring(curr,i + 1);
// if num > k then we know we cant have this number
if (Long.parseLong(num) > k)
break;
// add to res if we made to the end (+ 1) res
res = (res + dp(s,k,i + 1)) % MOD;
}
return memo[curr] = res;
}
}