记一些常见的手撕算法

怕什么真理无穷，进一寸有进一寸的欢喜

1.二分查找

    public int binarySearch(int[] arr,int key){int low = 0;int high = arr.length - 1;int mid = 0;if(key>arr[high]||keyhigh){return -1;}while(low<=high){mid = (low + high)/2;if(arr[mid] > key){high = mid - 1;}else if(arr[mid] < key){low = mid +1;}else {return mid;}}return -1;}

2.快速排序

    public void quickSort(int[] arr,int low,int high){int start = low;int end = high;int key = arr[low];while(start < end){//从后向前找while(start < end && arr[end] >= key){end--;}//交换arr－end和arr－startif(arr[end] >= key){int temp = arr[end];arr[end] = arr[start];arr[start] = temp;}//从前向后找while(start < end && arr[start] <= key){start++;}//交换if(arr[start] >= key){int temp = arr[start];arr[start] = arr[end];arr[end] = temp;}}//递归if(start > low){quickSort(arr,low,start-1);}if(end < high){quickSort(arr,end+1,high);}}

3.二叉树的层次遍历

    public void LaywerTraversal(TreeNode root){if(root==null){return;}LinkedList list = new LinkedList();list.add(root);TreeNode temp;while (!list.isEmpty()){temp = list.poll();System.out.println(temp.val);if(temp.left != null){list.add(temp.left);}if(temp.right!=null){list.add(temp.right);}}}

4.蛇形打印二叉树

    public void snakePrint(TreeNode root){if(root == null){return;}//用2个栈解决LinkedList list1 = new LinkedList();LinkedList list2 = new LinkedList();TreeNode curNode;int flag =0;list1.add(root);while(!list1.isEmpty()){curNode = list1.remove(list1.size() - 1);System.out.println(curNode.val);if(flag ==0){if(curNode.left != null){list2.add(curNode.left);}if(curNode.right != null){list2.add(curNode.right);}}else {if(curNode.right != null){list2.add(curNode.right);}if(curNode.left != null){list2.add(curNode.left);}}//打印下一层if(list1.isEmpty()){flag = 1 - flag;ListNode temp;temp = list1;list1 = list2;list2 = temp;}}}

5.链表实现加法(逆序链表)

    public linkNode linkedAdd(linkNode link1, linkNode link2){if(link1 == null || link2 == null){return (link1 ==null)?link2:link1;}//所返回的头节点linkNode res;linkNode Ptail = res;linkNode p1 = link1,p2 = link2;//进位符int carry = 0;int temp;//处理长度相同的部分while(p1!=null &&p2!=null){temp = p1.val + p2.val +carry;carry = temp/10;temp = temp%10;LinkNode cur = new LinkNode(temp);Ptail.next = cur;Ptail = cur;p1 = p1.next;p2 = p2.next;}//处理2个链表中较长的部分linkNode p = (p1!=null)?p1:p2;while(p!=null){temp = p.val + carry;carry = temp/10;temp = temp%10;LinkNode cur = new LinkNode(temp);Ptail.next = cur;Ptail = cur;p = p.next;}//处理可能存在的进位if(carry!=0){LinkNode cur = new LinkNode(carry);Ptail.next = cur;}return sum;}

6.反转链表

    public listNode reverse(listNode head){if(head ==null){return null;}if(head.next ==null){return head;}//res为返回链表的头指针//p为当前指针 pre为前指针listNode res = null;listNode p = head;listNode pre = null;while(p!=null){listNode temp = p.next;if(temp == null){res = p;}p.next = pre;pre = p;p = temp;}return res;}

7.查找数组中第k大的数

    public int find(int[] arr,int k,int low,int high){//处理特殊情况int len = arr.length;if(k>len){return -1;}//降序排列，快排后数组被切分为两个int index =0;int cutPoint = partition(arr,low,high);if(cutPoint == k - 1){index = cutPoint;return arr[index];}else if(cutPoint >= k - 1){return arr[topK(arr,low,cutPoint - 1)];}else {return arr[topK(arr,cutPoint + 1,high)];}}public int partition(int[] arr.int low,int high){int key = arr[low];while(low=key&&low

    public double sqrt(double target,double prescise){double start = 0;double end = target;double middle,square;if(target < 0){return -1.0;}if(target >=1.0){while(start - end > prescise){middle = (start + end)/2;square = middle*middle;if(square > target){end = middle;}else{start = middle;}}return (start + end)/2;}else {start = target;end = 1;while(end - start > prescise){middle = (start + end)/2;square = middle*middle;if(square > target){end = middle;}else {start = middle;}}return (start + end)/2;}}

    public int getSubString(int[] arr){if(arr.length == 0){return -1;}int max = arr[0];int cur = arr[0];for(int i =1;i 0?cur + arr[i]:arr[i];if(cur > max){max = cur;}}return max;}

    public int maxProfit(int[] arr){if(arr.length==0||arr==null){return -1;}int buy = arr[0];int max = 0;for(int i =0;i

    public int depthOfTree(TreeNode root){//认为空树的深度为0if(root==null){return 0;}int leftDepth = depthOfTree(root.left);int rightDepth = depthOfTree(root.right);return math.max(leftDepth,rightDepth) + 1;}

    public int minDepthOfTree(TreeNode root){if(root==null){return 0;}int minLeft = minDepthOfTree(root.left);int minRight = minDepthOfTree(root.right);if(minLeft==0||minRight==0){return minLeft+minRight+1;}else{return math.min(minLeft,minRight) +1;}}

    public void preOrder(TreeNode root){//先序遍历需要用一个栈Stack sk = new Stack();while(root!=null || !sk.isEmpty()){while(root!=null){System.out.print(root.value);sk.push(root);root = root.left;}if(!sk.isEmpty()){root = sk.pop().right;}}}

    public void midOrder(TreeNode root){Stack sk = new Stack();while(root!=null || !sk.isEmpty()){while(root!=null){sk.push(root);root = root.left;}if(!sk.isEmpty()){root = sk.pop();System.out.print(root.value);root = root.right;}}}

    public void postOrder(TreeNode root){Stack sk1 = new Stack();Stack sk2 = new Stack<>();while(root!=null || !sk1.isEmpty()){while(root!=null){sk1.push(root);sk2.push(0);root = root.left;}while(!sk1.isEmpty() &&sk2.peek() == 1){sk2.pop();System.out.println(sk1.pop().value);}if(!sk1.isEmpty()){sk2.pop();sk2.push(1);root = sk1.peek();root = root.right;}}}

    public static int[] sort(int[] a,int low,int high){if(high == low) return a;int mid = (low+high)/2;//划分if(low

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！