Algorithms

[bigggge]

实现排序算法

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[i]) {        //相邻元素两两对比
                var temp = arr[i];        //元素交换
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

二分查找算法

function binarySearch(arr, key) {
  var low = 0, high = arr.length - 1;
  while (low <= high) {
      var mid = Math.floor((low + high) / 2);
      if (key == arr[mid]) {
          return mid;
      } else if (key < arr[mid]) {
          high = mid - 1;
      } else {
          low = mid + 1;
      }
  }
  return -1;
}

斐波那契数列

function fibonacci (n , a = 0 , b = 1) {
  if( n === 0 ) {return a};
  return fibonacci (n - 1, b, a + b);
}    

反转字符串

function r(str) {
    return str.split('').reverse().join('')
}

翻转链表

public ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode temp = head.next;
        head.next = prev;
        prev = head;
        head = temp;
    }
    return prev;
}

带环链表

public Boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }

   ListNode fast, slow;
   fast = head.next;
   slow = head;
   while (fast != slow) {
       if(fast==null || fast.next==null)
           return false;
       fast = fast.next.next;
       slow = slow.next;
   } 
   return true;
}

广度优先遍历

//非递归广度优先实现
function bfs (tree) {
  if (!tree || !tree.length) return;
  let stack = [];
  //先将第一层节点放入栈
  for (let i = 0; i < tree.length; i++) {
    stack.push(tree[i]);
  }
  let item;
  while (stack.length) {
    item = stack.shift();
    console.log(item.id);
    //如果该节点有子节点，继续添加进入栈底
    if (item.children && item.children.length) {
      stack = stack.concat(item.children);
    }
  }
}

深度优先遍历

//递归实现
function parseTreeJson (tree) {
  if (!tree || !tree.length) return;
  for (let i = 0; i < tree.length; i++) {
    let children = tree[i].children;
    console.log(tree[i].id);
    if (children && children.length > 0) {
      parseTreeJson(children);
    }
  }
}

//非递归深度优先实现
function dfs (tree) {
  if (!tree || !tree.length) return;
  let stack = [];
  //先将第一层节点放入栈
  for (let i = 0; i < tree.length; i++) {
    stack.push(tree[i]);
  }
  let item;
  while (stack.length) {
    item = stack.shift();
    console.log(item.id);
    //如果该节点有子节点，继续添加进入栈顶
    if (item.children && item.children.length) {
      stack = item.children.concat(stack);
    }
  }
}

先序遍历

function preOrder(node) {
  if (node) {
    console.log(node.value);
    preOrder(node.left);
    preOrder(node.right);
  }
}

二叉树最大深度

public int maxDepth(TreeNode root) {
     if (root == null) {
         return 0;
     }

     int left = maxDepth(root.left);
     int right = maxDepth(root.right);
     return Math.max(left, right) + 1;
}

二叉树最小深度

public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return getMin(root);
}

public int getMin(TreeNode root){
    if (root == null) {
        return Integer.MAX_VALUE;
    }

    if (root.left == null && root.right == null) {
        return 1;
    }

    return Math.min(getMin(root.left), getMin(root.right)) + 1;
}

翻转二叉树

public void invertBinaryTree(TreeNode root) {
    if (root == null) {
        return;
    }
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    
    invertBinaryTree(root.left);
    invertBinaryTree(root.right);
}