Binary Tree Çap Hesabı

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/529/week-2/3293/

>> Solution 1 - Use DFS with Recursion

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	import java.util.*;
	class BinaryTreeDiameterCalculatorWithRecursion {
	public int diameterOfBinaryTree(TreeNode root) {
	SolutionFinder finder = new SolutionFinder();
	findDepth(root, finder);
	return finder.value;
	}
	/**
	*
	*/
	private int findDepth(TreeNode currentRoot, SolutionFinder finder){
	if(currentRoot==null) {
	return 0;
	}
	// Calculate the depth of a node in the usual way
	// max(depth of node.left, depth of node.right) + 1
	int leftDepth = findDepth(currentRoot.left, finder);
	int rightDepth = findDepth(currentRoot.right, finder);
	int currentDepth = 1 + Math.max(leftDepth,rightDepth);
	// Check if current diameter is the maximum and save it
	int currentDiameter = leftDepth + rightDepth;
	finder.suggestDiameter(currentDiameter);
	return currentDepth;
	}
	private class SolutionFinder {
	private int value = 0;
	private void suggestDiameter(int currentDiameter){
	if(this.value < currentDiameter) {
	this.value = currentDiameter;
	}
	}
	}
	}

view raw BinaryTreeDiameterCalculatorWithRecursion.java hosted with ❤ by GitHub

>> Solution 2 - Use Post Order DFS with Two Stacks

See

• https://www.geeksforgeeks.org/dfs-traversal-of-a-tree-using-recursion/
• https://www.geeksforgeeks.org/iterative-postorder-traversal/ 

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	import java.util.*;
	class BinaryTreeDiameterCalculatorWithStack {
	public int diameterOfBinaryTree(TreeNode root) {
	if(root == null) {
	return 0;
	}
	int diameter = -1;
	Map<TreeNode,TreeNodeInfo> nodeInfoMap = new HashMap<>();
	Stack<TreeNodeInfo> s1 = new Stack<>();
	Stack<TreeNodeInfo> s2 = new Stack<>();
	// Postorder DFS Traversal (Left, Right, Root)
	s1.push(new TreeNodeInfo(root));
	while(!s1.isEmpty()) {
	TreeNodeInfo current = s1.pop();
	s2.push(current);
	if(current.left != null) {
	s1.push(current.left);
	}
	if(current.right != null) {
	s1.push(current.right);
	}
	}
	while(!s2.isEmpty()) {
	TreeNodeInfo current = s2.pop();
	// Traversal Action
	current.setDiameter(current.getLeftNodeDepth() + 1, current.getRightNodeDepth() + 1);
	if(diameter < current.diameter){
	diameter = current.diameter;
	}
	}
	return diameter;
	}
	private class TreeNodeInfo {
	// TreeNode node;
	TreeNodeInfo left;
	TreeNodeInfo right;
	int depth;
	int diameter;
	TreeNodeInfo(TreeNode node){
	// this.node = node;
	this.left = node.left == null ? null : new TreeNodeInfo(node.left);
	this.right = node.right == null ? null : new TreeNodeInfo(node.right);
	}
	int getLeftNodeDepth(){
	return left == null ? -1 : left.depth;
	}
	int getRightNodeDepth(){
	return right == null ? -1 : right.depth;
	}
	void setDiameter(int leftDepth, int rightDepth){
	this.depth = Math.max( leftDepth, rightDepth);
	diameter = leftDepth + rightDepth;
	}
	}
	}

view raw BinaryTreeDiameterCalculatorWithStack.java hosted with ❤ by GitHub

Basit Stack Veri Yapısı

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

https://leetcode.com/explore/featured/card/30-day-leetcoding-challenge/529/week-2/3292/
 

>> Solution 1 :Basit linked list, her node'da minimumu tut

	/**
	* Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
	* Your MinStack object will be instantiated and called as such:
	*
	* > MinStack obj = new MinStack();
	* > obj.push(x);
	* > obj.pop();
	* > int param_3 = obj.top();
	* > int param_4 = obj.getMin();
	*
	*/
	class MinStack {
	private Node top;
	public MinStack() {
	top = null;
	}
	public void push(int element) {
	top = new Node (element, top);
	}
	public void pop() {
	Node popped = top;
	top = top.next;
	}
	public int top() {
	return top.value;
	}
	public int getMin() {
	return top.minValue;
	}
	private class Node {
	int value;
	int minValue;
	Node next;
	Node(int value,Node next){
	this.value = value;
	this.next = next;
	if(next == null || value < next.minValue){
	minValue = value;
	} else {
	minValue = next.minValue;
	}
	}
	}
	}

view raw MinStack.java hosted with ❤ by GitHub

O(1) time complexity, O(n) space complexity

Backspace Iceren String Karsilastirma

https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/529/week-2/3291/



Solution 1: Interpreter pattern

	class BackspaceStringCompareInterpreter {
	/**
	* Given two strings S and T, return if they are equal when both are typed into empty text editors.
	*
	* Performance: O(n) time, O(n) space
	*
	* @param S lower case letters with backspace # E.g. ab##
	* @param T lower case chars with backspace # E.g. #a#c
	*
	* @return S contentEquals T
	*/
	public boolean backspaceCompare(String S, String T) {
	Expression expS = constructExpression(S);
	String resultS = expS.interpret();
	Expression expT = constructExpression(T);
	String resultT = expT.interpret();
	return resultS.equals(resultT);
	}
	private Expression constructExpression(String context) {
	Expression exp = null;
	for(char c : context.toCharArray()) {
	if(isLetter(c)) {
	if(exp == null) {
	exp = new CharExpression(c);
	} else {
	exp = new ConcatExpression(exp, new CharExpression(c));
	}
	} else {
	exp = new BackspaceExpression(exp);
	}
	}
	return exp;
	}
	private boolean isLetter(char c) {
	return !isBackspace(c);
	}
	private boolean isBackspace(char c) {
	return c == '#';
	}
	private interface Expression {
	String interpret();
	}
	private class BackspaceExpression implements Expression {
	private Expression before;
	BackspaceExpression(Expression before) {
	this.before = before;
	}
	public String interpret() {
	if(before == null) {
	return "";
	}
	String beforeStr = before.interpret();
	if(beforeStr.length() <= 1) {
	return "";
	}
	return beforeStr.substring(0, beforeStr.length()-1);
	}
	}
	private class ConcatExpression implements Expression {
	private Expression exp1;
	private Expression exp2;
	ConcatExpression(Expression exp1,Expression exp2) {
	this.exp1 = exp1;
	this.exp2 = exp2;
	}
	public String interpret() {
	return new StringBuilder()
	.append(exp1.interpret())
	.append(exp2.interpret())
	.toString();
	}
	}
	private class CharExpression implements Expression {
	private char letter;
	CharExpression(char letter) {
	this.letter = letter;
	}
	public String interpret() {
	return String.valueOf(letter);
	}
	}
	}

view raw BackspaceStringCompareInterpreter.java hosted with ❤ by GitHub

Solution 2: Using Stack

	import java.util.*;
	class BackspaceStringCompareWithStack {
	/**
	* @param S lower case letters with backspace # E.g. ab##
	* @param T lower case chars with backspace # E.g. #a#c
	*
	* @return S contentEquals T
	*/
	public boolean backspaceCompare(String S, String T) {
	String resultS = constructString(S);
	String resultT = constructString(T);
	return resultS.equals(resultT);
	}
	private String constructString(String context) {
	Stack<Character> stack = new Stack<>();
	for(char c : context.toCharArray()) {
	if(isLetter(c)) {
	stack.push(c);
	} else if(!stack.isEmpty()){
	stack.pop();
	}
	}
	return stack.toString();
	}
	private boolean isLetter(char c) {
	return !isBackspace(c);
	}
	private boolean isBackspace(char c) {
	return c == '#';
	}
	}

view raw BackspaceStringCompareWithStack.java hosted with ❤ by GitHub

Biri Hariç Tüm Sayıların İkişer Adet Bulunduğu Dizideki Yanlız Sayıyı Bulma

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

>> Solution 1: Using list - O(n^2) time, O(n) space

    /**
     * Given a non-empty array of integers, every element appears twice except for one. Find that single one.
     *
     * Performance: O(n^2) time, O(n) space
     *
     */
    public int singleNumber(int[] nums) {
       
        // O(n) space
        List<Integer> allElements = new ArrayList<>();
       
        // O(n^2) time
        for(int n : nums){
           
            Integer nWrapped = Integer.valueOf(n);
            if(allElements.contains(nWrapped)){
                allElements.remove(nWrapped);
            } else {
                allElements.add(nWrapped);
            }
           
        }
       
        return allElements.get(0);
    }

 Solution 2: Using hash map, O(n) time, O(n) space

    /**
     * Given a non-empty array of integers, every element appears twice except for one. Find that single one.
     *
     * Performance: O(n) time, O(n) space
     *
     */
    public int singleNumber(int[] nums) {
       
        Map<Integer, Integer> elementCounts = new HashMap<>();
       
        // O(n) time, O(n) space
        for(int n : nums){
            Integer wrappedVal = Integer.valueOf(n);
            int currentCount = elementCounts.getOrDefault(wrappedVal,0)+1;
            elementCounts.put( wrappedVal , currentCount );
        }
       
        // O(n) time, O(1) space
        for(int n : nums) {
            Integer wrappedVal = Integer.valueOf(n);
            if(elementCounts.get(wrappedVal) == 1) {
                return n;
            }
        }
       
        throw new UnsupportedOperationException("Not a correct input set");
    }

 Solution 3a: Using math, O(n) time, O(n) space

    /**
     * Given a non-empty array of integers, every element appears twice except for one. Find that single one.
     *
     * Performance: O(n) time, O(n) space
     *
     *  sumOfSet = a+b+c
     *  sumOfNums = c + 2*(a+b+c)
     *  sumOfNums = c + 2*sumOfSet - c
     *  c = 2*sumOfSet - c
    */
    public int singleNumber(int[] nums) {

        // O(n) time, O(1) space
        int sumOfNums = IntStream
            .of(nums)
            .sum();
       
        // O(n) time, O(n) space
        int sumOfSet = IntStream.of(nums)
            .boxed()
            .collect(Collectors.toSet())
            .stream()
            .mapToInt(Integer::intValue)
            .sum();
       
        return 2*sumOfSet - sumOfNums;
    }

  Solution 3b: Using math, O(n) time, O(n) space - but better runtime

    /**
     * Given a non-empty array of integers, every element appears twice except for one. Find that single one.
     *
     * Performance: O(n) time, O(n) space
     *
     *  sumOfSet = a+b+c
     *  sumOfNums = c + 2*(a+b+c)
     *  sumOfNums = c + 2*sumOfSet - c
     *  c = 2*sumOfSet - c
    */
    public int singleNumber(int[] nums) {

        int sumOfNums = 0;
        int sumOfSet = 0;
        Set<Integer> elements = new HashSet<>(); // O(1) space
      
        // O(n) time
        for(int n : nums) {
            Integer intWrapped = Integer.valueOf(n);
            if(!elements.contains(intWrapped)) {
                elements.add(intWrapped);
                sumOfSet += n;
            }
            sumOfNums += n;
        }
      
        return 2*sumOfSet - sumOfNums;
    }

 

 Solution 4 : Bit operations, O(n) time, O(1) space

   /**
    * Given a non-empty array of integers, every element appears twice except for one. Find that single one.
    *
    * Performance: O(n) time, O(1) space
    *
    *  a XOR 0 = n
    *  a XOR a = 0
    *  a XOR b XOR a = a
    */
    public int singleNumber(int[] nums) {

        // O(1) space
        int result = 0;
      
        // O(n) time
        for(int n : nums) {
            result = result ^ n;
        }
      
        return result;
    }