1295. Find Numbers with Even Number of Digits
class Solution {
public int countDigits(int num){
int count = 1;
while(num /10 !=0){
num = num /10;
count++;
}
return count;
}
public int findNumbers(int[] nums) {
int count = 0;
for (int i = 0; i < nums.length; i++){
if(countDigits(nums[i]) % 2 == 0) count++;
}
return count;
}
}
1200. Minimum Absolute Difference
Brute Force: Time Limit Exceed
class Solution {
public List<List> minimumAbsDifference(int[] arr) {
List<List> out = new ArrayList();
int minAbs = Integer.MAX_VALUE;
Arrays.sort(arr);
for (int i = 0; i < arr.length; i++){
for (int j= i+1; j < arr.length; j++){
minAbs = Math.min(minAbs, Math.abs(arr[i] - arr[j]));
}
}
for (int i = 0; i < arr.length; i++){
for (int j= i+1; j < arr.length; j++){
if(Math.abs(arr[i] - arr[j]) == minAbs) {
ArrayList pair = new ArrayList();
pair.add(arr[i]);
pair.add(arr[j]);
out.add(pair);
}
}
}
return out;
}
}
Easy Optimization:
class Solution {
public List<List> minimumAbsDifference(int[] arr) {
List<List> out = new ArrayList();
int minAbs = Integer.MAX_VALUE;
Arrays.sort(arr);
//LinkedHashMap to preserve the insertion order
LinkedHashMap index = new LinkedHashMap();
for (int i = 0; i Math.abs(arr[i+1] - arr[i])){
minAbs = Math.abs(arr[i+1] - arr[i]);
index = new LinkedHashMap();
index.put(i,i+1);
}
}
for (Integer a : index.keySet()){
ArrayList in = new ArrayList();
in.add(arr[a]);
in.add(arr[index.get(a)]);
out.add(in);
}
return out;
}
}
1337. The K Weakest Rows in a Matrix
class Solution {
private class Row{
int rowNum;
int soliders;
public Row(int rowNum, int soliders) {
this.rowNum = rowNum;
this.soliders = soliders;
}
public int getRowNum() {
return rowNum;
}
public void setRowNum(int rowNum) {
this.rowNum = rowNum;
}
public int getSoliders() {
return soliders;
}
public void setSoliders(int soliders) {
this.soliders = soliders;
}
}
public int[] kWeakestRows(int[][] mat, int k) {
int rowCount =0;
ArrayList rows = new ArrayList();
int i = 0;
for(i =0; i < mat.length; i++) {
rowCount =0;
for (int j = 0; j < mat[i].length; j++) {
if(mat[i][j] == 1) rowCount++;
}
rows.add(new Row(i,rowCount));
}
Collections.sort(rows, new Comparator(){
@Override
public int compare(Row o1, Row o2) {
if (o1.getSoliders() == o2.getSoliders())
{
return ((Integer)o1.getRowNum()).compareTo((Integer)o2.getRowNum());
}
return ((Integer)o1.getSoliders()).compareTo((Integer)o2.getSoliders());
}});
int[] out = new int[k];
for (int j = 0; j < out.length; j++) {
out[j] = rows.get(j).getRowNum();
}
return out;
}
}
1356. Sort Integers by The Number of 1 Bits
class Solution {
public int[] sortByBits(int[] arr) {
Integer[] arrObject = new Integer[arr.length];
for (int i = 0; i < arr.length; i++) {
arrObject[i] = arr[i];
}
Arrays.sort(arrObject, new Comparator() {
@Override
public int compare(Integer o1, Integer o2) {
if (countOnes(o1) == countOnes(o2))
return o1.compareTo(o2);
else if (countOnes(o1) > countOnes(o2))
return 1;
else
return -1;
}
});
for (int i = 0; i < arr.length; i++) {
arr[i] = arrObject[i];
}
return arr;
}
public static int countOnes(int n) {
int count = 0;
while (n != 0) {
n = n & (n - 1);
count++;
}
return count;
}
}
1207. Unique Number of Occurrences
class Solution {
public boolean uniqueOccurrences(int[] arr) {
HashMap h = new HashMap();
for(int i = 0; i < arr.length; i++) {
h.put(arr[i], h.getOrDefault(arr[i],0)+1);
}
if(h.size() == 0) return true;
HashSet repeats = new HashSet();
for (Integer a: h.keySet()) {
if(repeats.contains(h.get(a))) return false;
else repeats.add(h.get(a));
}
return true;
}
}
1022. Sum of Root To Leaf Binary Numbers
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int sum = 0;
public void construct(TreeNode root,String prev){
if (root == null) return;
if( root.left == null && root.right == null){
sum+=Integer.parseInt(prev+root.val,2);
return;
}
construct(root.left,prev+""+root.val);
construct(root.right,prev+""+root.val);
}
public int sumRootToLeaf(TreeNode root) {
if (root == null) return 0;
if(root.left == null && root.right == null) return root.val;
construct(root.left,root.val+"");
construct(root.right,root.val+"");
return sum;
}
}
1047. Remove All Adjacent Duplicates In String
class Solution {
public String removeDuplicates(String S) {
if(S == null || S.isEmpty()) return "";
if(S.length() ==1) return S;
for (int i = 0; i < S.length() - 1; i++){
if(S.charAt(i) == S.charAt(i+1))
return removeDuplicates(S.substring(0,i)+S.substring(i+2));
}
return S;
}
}
107. Binary Tree Level Order Traversal II
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List> levelOrderBottom(TreeNode root) {
if (root == null) return new LinkedList();
List<List> out = new ArrayList();
Queue q = new LinkedList();
q.offer(root);
while(!q.isEmpty()){
ArrayList current = new ArrayList();
int size = q.size();//we must put it in variable is the size changes each loop
for(int i =0; i < size; i++){
TreeNode c = q.poll();
if(c != null){
current.add(c.val);
if(c.left != null)
q.offer(c.left);
if(c.right != null)
q.offer(c.right);
}
}
out.add(current);
}
Collections.reverse(out);
return out;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public static boolean isMirror(TreeNode r, TreeNode l){
if( r == null && l == null) return true;
if( r == null && l != null) return false;
if( r != null && l == null) return false;
if (r.val != l.val) return false;
if (r.val == l.val)
return isMirror(l.right,r.left) && isMirror(l.left, r.right);
else return false;
}
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isMirror(root.right,root.left);
}
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null && l2 == null) return null;
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode out = null;
ListNode current = null;
if(l1.val == l2.val) {
out =new ListNode(l1.val);
l1 = l1.next;
out.next = new ListNode(l2.val);
l2 = l2.next;
current = out.next;
}else
if(l1.val < l2.val) {
out =new ListNode(l1.val);
l1 = l1.next;
current = out;
}
else {
out =new ListNode(l2.val);
l2 = l2.next;
current = out;
}
while(l1 != null || l2 != null) {
if(l1 == null && l2 == null)
return out;
else if (l1 == null && l2 != null) {
current.next = l2;
return out;
}
else if ( l1 != null && l2 == null) {
current.next = l1;
return out;
}
else if (l1.val l2.val) {
ListNode newListNode = new ListNode(l2.val);
current.next = newListNode;
current = current.next;
l2 = l2.next;
}
}
return out;
}
}
