美文网首页
学习在白板上写程序

学习在白板上写程序

作者: Lutecium | 来源:发表于2018-03-09 19:35 被阅读0次

数学归纳法,用于证明断言对所有自然数成立

  • 证明对于N=1成立
  • 证明N>1时:如果对于N-1成立,那么对于N成立

如何证明递归函数正确执行

  • 数学归纳法中的数学、自然语言 <==> 程序语言

递归控制

  • 严格定义递归函数作用,包括参数,返回值,Side-effect
  • 先一般,后特殊
  • 每次调用必须缩小问题规模(如果不这样就成了死循环)
  • 每次问题规模缩小程度必须为1

例一:链表创建

public class Node {

    private final int value;

    private Node next;

    //构造时将next默认为空
    public Node(int value) {
        this.value = value;
        this.next = null;
    }

    public int getValue() {
        return value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    //打印链表
    public static void printLinkedList(Node head){
        while(head != null){
            System.out.print(head.getValue());
            System.out.print(" ");
            head = head.getNext();
        }
        System.out.println();
    }
}
public class LinkedListCreator {

    /**
     * Creates a linked list.递归
     * @param data the data to create the list
     * @return head of the linked list.The returned linked list
     * ends with last node with getNext() == null
     */
    public Node createLinkedList(List<Integer> data){
        if(data.isEmpty()){
            return null;
        }
        Node firstNode = new Node(data.get(0));
        firstNode.setNext(createLinkedList(data.subList(1,data.size())));
        return firstNode;
    }


    //测试创建链表
    public static void main(String[] args) {
        LinkedListCreator creator = new LinkedListCreator();
        Node.printLinkedList(creator.createLinkedList(new ArrayList<>()));
        Node.printLinkedList(creator.createLinkedList(Arrays.asList(1)));
        Node.printLinkedList(creator.createLinkedList(Arrays.asList(1,2,3,4,5)));

    }
}
  /**
     * 循环创建链表
     * @param data
     * @return
     */
    public Node createLinkedList2(List<Integer> data){
        if(data.isEmpty()){
            return null;
        }
        Node firstNode = new Node(data.get(0));
        //循环创建链表
        Node curNode = firstNode;
        for(int i=1;i<data.size();i++){
            Node nextNode = new Node(data.get(i));
            curNode.setNext(nextNode);
            curNode = nextNode;
        }
        return firstNode;
    }

例二:链表反转

public class LinkedListReverser {

    /**
     * Reaverses a linked list. 递归
     * @param head the linked list to reverse
     * @return head of the reversed linked list
     */
    Node reverseLinkedList(Node head){
        //size == 0 size == 1
        if(head == null || head.getNext() == null){
            return head;
        }

        Node newHead = reverseLinkedList(head.getNext());
        head.getNext().setNext(head);
        head.setNext(null);
        return newHead;
    }

    public static void main(String[] args) {
        LinkedListCreator creator = new LinkedListCreator();
        LinkedListReverser reverser = new LinkedListReverser();
        Node.printLinkedList(reverser.reverseLinkedList(creator.createLinkedList(new ArrayList<>())));
        Node.printLinkedList(reverser.reverseLinkedList(creator.createLinkedList(Arrays.asList(1))));
        Node.printLinkedList(reverser.reverseLinkedList(creator.createLinkedList(Arrays.asList(1,2,3,4,5))));

    }
}
    /**
     * 循环反转链表
     * @param head
     * @return
     */
    Node reverseLinkedList2(Node head){
        Node newHead = null;
        Node curHead = head;
        while(curHead != null){
          Node next = curHead.getNext();
          curHead.setNext(newHead);
          newHead = curHead;
          curHead = next;
        }
        return newHead;
    }

例三:列出所有组合

combinations([1,2,3,4],2)
要点:多个参数的初始值

public class Combinations {

    /**
     * Generates all combinations and output them,
     * selecting n elements from data.
     * @param data
     * @param n
     */
    public void combinations(List<Integer> selected,List<Integer> data, int n){
        //initial value for recursion
        //how to select elements
        //how to output

        if(n ==0 ){
            //output all selected elements
            for(Integer i: selected){
                System.out.print(i);
                System.out.print(" ");
            }
            System.out.println();
            return ;
        }
        if(data.isEmpty()){
            return ;
        }
        // select element 0
        selected.add(data.get(0));
        combinations(selected, data.subList(1,data.size()),n-1);
        // un-select element 0
        selected.remove(selected.size() - 1);
        combinations(selected, data.subList(1,data.size()),n);

    }

    public static void main(String[] args) {
        Combinations comb = new Combinations();
        comb.combinations(new ArrayList<>(),Arrays.asList(1,2,3,4),2);
        System.out.println("=========================");
        comb.combinations(new ArrayList<>(),new ArrayList<>(),0);
        System.out.println("=========================");
        comb.combinations(new ArrayList<>(),new ArrayList<>(),2);
        System.out.println("=========================");
        comb.combinations(new ArrayList<>(),Arrays.asList(1,2,3,4),1);
        System.out.println("=========================");
        comb.combinations(new ArrayList<>(),Arrays.asList(1,2,3,4),0);
        System.out.println("=========================");
    }

}

递归缺点:函数调用开销大,可能会Stack Overflow!
不要尝试递归->非递归

例四:链表删除节点

public Node deleteIfEquals(Node head,int value){
        while(head!=null && head.getValue() == value){
            head = head.getNext();
        }
        Node prev = head;
        if(head == null){
            return null;
        }
        while(prev.getNext() != null){
            if(prev.getNext().getValue() == value){
                prev.setNext(prev.getNext().getNext());
            }else{
                prev = prev.getNext();
            }
        }
        return head;
    }

例: 二分查找

  • 在有序数组中查找元素K,返回K所在下标
  • binarySearch([1,2,10,15,100],15) == 3
   /**
     * 二分查找
     * @param arr 有序
     * @param k
     * @return
     */
    public int binarySearch(int[] arr,int k){

        int a = 0;
        int b = arr.length;
        //[a,b)
        while(a < b){
            //int m = (a + b) / 2;
            int m = a + (b - a) / 2;
            if(k < arr[m]){//a...(m-1)
                b = m;
            }else if(k > arr[m]){//(m+1)...b
                a = m + 1;
            }else{
                return m;
            }
        }
        return -1;
    }

二叉树的遍历

前序遍历:ABDEGCF
中序遍历:DBGEACF
后序遍历:DGEBFCA

/**
 *  树
 * @author WangCH
 * @create 2018-03-14 20:02
 */
public class TreeNode {

    private final char value;

    private TreeNode left;

    private TreeNode right;

    public TreeNode(char value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public char getValue() {
        return value;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }
}
/**
 * 手动创建二叉数
 * @author WangCH
 * @create 2018-03-14 20:03
 */
public class TreeCreator {

    public TreeNode createSampleTree(){
        TreeNode root = new TreeNode('A');
        root.setLeft(new TreeNode('B'));
        root.getLeft().setLeft(new TreeNode('D'));
        root.getLeft().setRight(new TreeNode('E'));
        root.getLeft().getRight().setLeft(new TreeNode('G'));
        root.setRight(new TreeNode('C'));
        root.getRight().setRight(new TreeNode('F'));
        return root;
    }
}
/**
 * @author WangCH
 * @create 2018-03-21 13:46
 */
public class TreeTraversal {

    /**
     * 前序遍历二叉树
     * @param root
     */
    public void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.getValue());
        preOrder(root.getLeft());
        preOrder(root.getRight());
    }

    /**
     * 中序遍历
     * @param root
     */
    public void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.getLeft());
        System.out.print(root.getValue());
        inOrder(root.getRight());
    }

    /**
     * 后序遍历
     * @param root
     */
    public void postOrder(TreeNode root){
        if(root == null){
            return;
        }
        postOrder(root.getLeft());
        postOrder(root.getRight());
        System.out.print(root.getValue());
    }

    public static void main(String[] args) {
        TreeCreator creator = new TreeCreator();
        TreeNode sampleTree= creator.createSampleTree();

        TreeTraversal treeTraversal = new TreeTraversal();
        System.out.print("前序遍历:");
        treeTraversal.preOrder(sampleTree);
        System.out.println();
        System.out.print("中序遍历:");
        treeTraversal.inOrder(sampleTree);
        System.out.println();
        System.out.print("后序遍历:");
        treeTraversal.postOrder(sampleTree);
        System.out.println();
    }
}

相关文章

  • 学习在白板上写程序

    数学归纳法,用于证明断言对所有自然数成立 证明对于N=1成立 证明N>1时:如果对于N-1成立,那么对于N成立 如...

  • 经实验马克笔与白板笔的差别

    两种笔都可以在白板上写 但是涂擦的话白板笔要易于马克笔

  • 面试

    面试总结 领扣 冷熊简历 白板编程浅谈——Why, What, How | lucida PHP程序员进阶学习书籍...

  • 翻转二叉树(LeetCode226. 翻转二叉树)

    11月11日面试题 题目 解析 据说Homebrew的作者Max Howell在面试Google时,无法在白板上写...

  • 写汉字时的小插曲

    今天上午第二节课我们写汉字,第七课我们写木和区。 我们先在白板的田字格中写汉字,然后把田字格放大。接着通过白板上的...

  • 2017-12-26

    如果洛克的白板说成立的话,那么手拿粉笔的那个人非常重要,白板上哪些地方可以写满,哪些地方只能少写,或者哪些地方不能...

  • 去美国工作--qichao live

    一般步骤(4-6轮):1.2轮电话面试2.不错出机票飞过去面试3.白板上写程序,边说边写 面试经验:1.不在乎都解...

  • 在PC上写Swift小程序

    关键词: IBM Swift Sandbox 苹果公司在2014年的世界开发者大会(WWDC2014)上推出了一门...

  • 【脑洞】跳跳虎

    《高铁侠》动画短片制作人员,最喜欢用白板笔在白板上构思创意。这天,其中一位主创突发奇想,用白板笔在白板上画了三个圆...

  • 视觉化工作法2个优点

    由图表师在白板(纸)上用图画(文字)

网友评论

      本文标题:学习在白板上写程序

      本文链接:https://www.haomeiwen.com/subject/ddhmfftx.html