class Solution {
public int countPrimes(int n) {
int count = 0;
for (int i = 2; i < n; i++){
if (isPrime(i)) count++;
}
return count;
}
public boolean isPrime(int n){
for (int i = 2; i*i <= n; i++){
if ( n % i == 0) return false;
}
return true;
}
}
637. Average of Levels in Binary Tree
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List averageOfLevels(TreeNode root) {
List out = new ArrayList();
Queue q = new LinkedList();
q.add(root);
while(! q.isEmpty()){
int len = q.size();
Double sum = 0.0;
for (int i = 0; i < len; i++){
TreeNode c = q.remove();
if (c != null){
sum += c.val;
if(c.left !=null)q.add(c.left);
if(c.right != null)q.add(c.right);
}
}
out.add(sum/len);
}
return out;
}
}
class Solution {
public int binaryGap(int N) {
String binary = Integer.toBinaryString(N);
int first = 0;
while (first < binary.length() && binary.charAt(first) != '1'){
first ++;}
if (first == binary.length()) return 0;
int diff = Integer.MIN_VALUE;
int current = first;
for (int i = first+1; i diff){
diff = i - current;
}
current = i;
}
}
if (diff == Integer.MIN_VALUE) return 0;
return diff;
}
}
884. Uncommon Words from Two Sentences
class Solution {
public String[] uncommonFromSentences(String A, String B) {
List outputList = new ArrayList();
String[] As = A.split(" ");
String[] Bs = B.split(" ");
Map s = new HashMap();
for (int i = 0; i < As.length; i++){
if(s.get(As[i]) == null) s.put(As[i],1);
else s.put(As[i],s.get(As[i])+1);
}
for (int i = 0; i < Bs.length; i++){
if(s.get(Bs[i]) == null) s.put(Bs[i],1);
else s.put(Bs[i],s.get(Bs[i])+1);
}
for (String a: s.keySet()){
if ( s.get (a) == 1) outputList.add(a);
}
return outputList.toArray(new String[outputList.size()]);
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int rangeSumBST(TreeNode root, int L, int R) {
int out = 0;
out = rangeSumBSTHelper(root,L,R);
return out;
}
public static int rangeSumBSTHelper(TreeNode root, int L, int R){
if(root == null) return 0;
int total = 0;
if( root.val >= L && root.val <= R)
total+= root.val;
if (root.right != null)
total+= rangeSumBSTHelper(root.right,L,R);
if (root.left != null)
total+=rangeSumBSTHelper(root.left,L,R);
return total;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean leafSimilar(TreeNode root1, TreeNode root2) {
ArrayList tree1 = new ArrayList();
ArrayList tree2 = new ArrayList();
traverse(root1, tree1);
traverse(root2, tree2);
if (tree1.size() != tree2.size()) return false;
for (int i = 0; i < tree1.size(); i++){
if (tree1.get(i) != tree2.get(i)) return false;
}
return true;
}
public static void traverse (TreeNode root, ArrayList tree){
if( root.right == null && root.left == null){
tree.add(root.val);
return;
}
if (root.right != null) traverse (root.right, tree);
if (root.left != null) traverse (root.left, tree);
}
}
807. Max Increase to Keep City Skyline
class Solution {
public int maxIncreaseKeepingSkyline(int[][] grid) {
int[] rowMax = new int[grid.length];
int[] colMax = new int[grid[0].length];
for (int i = 0; i < grid.length; i++){
int max = grid[i][0];
for (int j = 1; j max ){
max = grid[i][j];
}
}
rowMax[i] = max;
}
for (int j = 0 ; j < grid[0].length; j++){
int max = grid[0][j];
for (int i = 0; i max ){
max = grid[i][j];
}
}
colMax[j] = max;
}
int ans = 0;
for (int i = 0; i < grid.length; i++){
for (int j = 0; j < grid[i].length; j++){
int min = Math.min(rowMax[i],colMax[j]);
if(grid[i][j] <span id="mce_SELREST_start" style="overflow:hidden;line-height:0;"></span>< min){
int add = min - grid[i][j];
ans+= add;
}
}
}
return ans;
}
}
Note:
Write colMax and rowMax in only one loop, instead of two loops
int[] rowMaxes = new int[N];
int[] colMaxes = new int[N];
for (int r = 0; r < N; ++r)
for (int c = 0; c < N; ++c) {
rowMaxes[r] = Math.max(rowMaxes[r], grid[r][c]);
colMaxes[c] = Math.max(colMaxes[c], grid[r][c]);
}
public int sumNumbers(String str) {
return sumNumbersHelper(str,0);
}
public int sumNumbersHelper(String str, int index){
if (index >= str.length()) return 0;
int currentInt = 0;
if(Character.isDigit(str.charAt(index))){
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(str.charAt(index));
index++;
while(index < str.length() && Character.isDigit(str.charAt(index))){
stringBuilder.append(str.charAt(index));
index++;
}
currentInt = Integer.parseInt(stringBuilder.toString());
}
return currentInt +sumNumbersHelper(str, index+1);
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return getMaximumNodeHelper(nums,0,nums.length - 1, new TreeNode(0));
}
public static TreeNode getMaximumNodeHelper(int[] nums, int start, int end, TreeNode n){
if(start == end && start end) return null;
int maxValue = Integer.MIN_VALUE;
int maxIndex = 0;
for (int i = start; i maxValue){
maxValue = nums[i];
maxIndex = i;
}
}
n.val = maxValue;
///
int maxValueRight = Integer.MIN_VALUE;
int maxIndexRight = maxIndex+1;
for (int i = maxIndex+1; i maxValueRight){
maxValueRight = nums[i];
maxIndexRight = i;
}
}
n.right = getMaximumNodeHelper(nums,maxIndex+1,end,new TreeNode(maxValueRight));
////
int maxValueLeft = Integer.MIN_VALUE;
int maxIndexLeft = maxIndex+1;
for (int i = start; i maxValueLeft){
maxValueLeft = nums[i];
maxIndexLeft = i;
}
}
n.left = getMaximumNodeHelper(nums,start,maxIndex-1,new TreeNode(maxValueLeft));
return n;
}
}
1021. Remove Outermost Parentheses
class Solution {
public static String removeOuterParentheses(String S) {
StringBuilder s = new StringBuilder();
int opened = 0;
for (char c : S.toCharArray()) {
if (c == '('&& opened > 0 ) s.append(c);
if (c == ')'&& opened > 1) s.append(c);
if (c == '(') opened++;
else opened--;
}
return s.toString();
}
}
