刷题

链表

JZ6 从尾到头打印链表

 public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> array=new ArrayList<Integer>();
        while(listNode!=null){
            array.add(0,listNode.val);
            listNode=listNode.next;
        }
        return array;
    }

思路：定义一个array数组，将指针的值挨个加入数组中，然后返回

知识点：

定义arraylist数组格式 ArrayList array=new ArrayList();
arraylist数组加入元素，如果需要逆序则每次中0位置添加元素 array.add(0,listNode.val);

JZ24 反转链表

使用指针反转链表

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

思路：在同一个链表上进行翻转，首先定义一个空节点phead，phead作为新链表的头节点。依次沿着原来head路线将节点挨个插入新节点的头位置，并始终用phead记录头节点的位置，直到原节点为空。

使用栈反转链表

public ListNode ReverseList(ListNode head){
        Stack<ListNode>stack=new Stack<ListNode>();
        while(head!=null){
            stack.add(head);
            head=head.next;
        }
        ListNode node=new ListNode(-1);
        ListNode temp=node;
        while(!stack.isEmpty()){
            temp.next=stack.pop();
            temp=temp.next;
        }
        temp.next=null;
        return node.next;
}

思路：首先将链表中的元素都加入栈中，然后定义链表，将栈中元素挨个插入链表中

知识点：

定义栈 Stackstack=new Stack();
栈的相关函数
1. stack.add();
2. stack.isEmpty()
3. stack.pop()

定义新链表首先定义一个头节点head，再用一个node记录头节点位置进行操作，最后记得将链表封住

    ListNode head=new ListNode(-1);
    ListNode node=head;

然后用node进行接下来的操作

JZ25 合并两个排序的链表

非递归

public ListNode Merge(ListNode list1,ListNode list2) {
    ListNode head=new ListNode(-1);
        ListNode node=head;
        while(list1!=null&&list2!=null){
            if(list1.val>list2.val){
                node.next=list2;
                node=node.next;
                list2=list2.next;
            }
            else{
                node.next=list1;
                node=node.next;
                list1=list1.next;
            }
        }
        if(list1!=null){
            node.next=list1;
        }
        if(list2!=null){
            node.next=list2;
        }
        return head.next;
}

思路：首先定义一个链表，在while循环中，将两个链表挨个进行比较将较小的节点加入新链表中，直到其中一个链表遍历完，再将还未遍历的链表加入新节点；

递归

public ListNode Merge(ListNode list1,ListNode list2){
        if(list1==null)
            return list2;
        if(list2==null)
            return list1;
        if(list1.val<list2.val){
            list1.next=Merge(list1.next,list2);
            return list1;
        }
        else{
            list2.next=Merge(list1,list2.next);
            return list2;
        }
}

思路：使用递归合并，首先是结束递归的条件，当其中一个链表遍历完毕后，返回另一个链表的剩下的节点。接下来就是产生递归，将较小节点的下一个节点和另一个链表节点进入递归，然后返回该头节点。

JZ52 两个链表的第一个公共结点

使用set集合

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2){
        HashSet<ListNode> set=new HashSet<ListNode>();
        while(pHead1!=null){
            set.add(pHead1);
            pHead1=pHead1.next;
        }
        while(pHead2!=null){
            if(set.contains(pHead2))
                return pHead2;
            pHead2=pHead2.next;
        }
        return null;
}

思路：将一个链表元素加入set数组中，然后用另一个链表进行判断

知识点：

定义set数组： HashSet set=new HashSet();
set数组不会存在相同的节点
set.contains(pHead2)：用于判断是否含有

双链表法

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2){
        ListNode a=pHead1;
        ListNode b=pHead2;
        while(a!=b){
            a=(a!=null)?a.next:pHead2;
            b=(b!=null)?b.next:pHead1;
        }
        return a;
}

思路：相当于将pHead1链表变为了pHead1+pHead2，pHead2链表变为了pHead2+pHead1，两链表长度相同，同时进行遍历，如果有相同值就会退出循环，当两新链表遍历完都位null，也退出循环返回null

JZ23 链表中环的入口结点

使用set数组

public ListNode EntryNodeOfLoop(ListNode pHead){
    	HashSet<ListNode> set=new HashSet<ListNode>();
        while(pHead!=null){
            if(set.contains(pHead))
                return pHead;
            set.add(pHead);
            pHead=pHead.next;
        }
        return null;
}

思路：挨个将节点加入set数组中，如果遇到相同的节点就是环头

双指针

public ListNode EntryNodeOfLoop(ListNode pHead){
        ListNode fast=pHead;
        ListNode slow=pHead;
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)
                break;
        }
        if(fast==null||fast.next==null)
            return null;
        fast=pHead;//接下来说明已经有环了
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast;
}

思路：快指针每次前进2，慢指针前进1，在不为空的情况下说明有环，在第一次相遇后，快指针路程为满指针的两倍，让快指针从头开始，以相同的速度前进，第二次相遇的位置就是入口。

原因：如果两指针能相遇，快指针的节点数为慢指针的节点数的两倍，从环头节点到相遇点的距离可以抵消，然后就是从头节点到环头和相遇点到环头的距离相等。或者设slow距离为n，fast为2n，设环头到相遇点的距离为x，则由slow可知头节点到环头的距离为n-x，由fast可知，在去除一个完整的到相遇点的n后，剩下一个n减去环头到相遇点的x也是n-x，所以可证明相遇点为环头。

JZ22 链表中倒数最后k个结点

使用数组

public ListNode FindKthToTail (ListNode pHead, int k){
        ArrayList<ListNode>array=new ArrayList<ListNode>();
        ListNode node=pHead;
        while(node!=null){
            array.add(node);
            node=node.next;
        }
        if(array.size()<k)
            return node;
        for(int i=0;i<array.size()-k;i++){
            pHead=pHead.next;
        }
        return pHead;
}

思路：将节点加入ArrayList数组中，利用该数组的size函数来进行遍历，时间复杂度太高。

双指针

public ListNode FindKthToTail (ListNode pHead, int k){
        ListNode fast=pHead;
        ListNode slow=pHead;
        for(int i=0;i<k;i++){
            if(fast==null)
                return null;
            fast=fast.next;
        }
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
}

思路：利用双指针，让fast指针先走k步，两指针再以同样的速度前行，当fast遍历完后，slow就是倒数个，注意链表长度和k之间的关系

JZ35 复杂链表的复制

双链表法

public RandomListNode Clone(RandomListNode pHead){
    if(pHead==null)
        return null;
    RandomListNode node=pHead;
    while(node!=null){  //首先克隆一个链表
        RandomListNode temp=new RandomListNode(node.label);
        temp.next=node.next;
        node.next=temp;
        node=temp.next;
    }
    RandomListNode fast=pHead;
    while(fast!=null){  //将随机指针加上
        if(fast.random!=null)
            fast.next.random=fast.random.next;
        fast=fast.next.next;
    }
    RandomListNode slow=pHead.next;
    RandomListNode res=slow;
    fast=pHead;
    while(fast!=null){  //将两链表分开
        if(fast.next!=null)
            fast.next=fast.next.next;
        if(slow.next!=null)
            slow.next=slow.next.next;
        fast=fast.next;
        slow=slow.next;
    }
    return res;
}

思路：分成三步，第一步将原链表的结点对应的拷贝节点连在其后，最后链表变成原1 -> 拷1 -> 原2 -> 拷2 -> … -> null 的形式。第二步将一个指针指向原链表的节点，一个指向拷贝链表的节点，那么就有拷->random = 原->random->next (random不为空)。第三步用双指针将两条链表拆分。

使用map数组

JZ18 删除链表的节点

public ListNode deleteNode (ListNode head, int val) {
    // write code here
    if(head.val==val)
        return head.next;
    ListNode node=head.next;
    ListNode pre=head;
    while(node!=null){
        if(node.val==val){
            pre.next=node.next;
            break;
        }
        node=node.next;
        pre=pre.next;
    }
    return head;
}

思路：设置两个指针，node先遍历一个节点，pre代表node的前一个节点，如果node是目标节点，则直接将node进行替换。

JZ76 删除链表中重复的结点

public ListNode deleteDuplication(ListNode pHead){
        ListNode node=new ListNode(-1);
        node.next=pHead;
        ListNode pre=node;
        ListNode temp=pHead;
        while(temp!=null){
            if(temp.next!=null&&temp.val==temp.next.val){
                temp=temp.next;
                while(temp.next!=null&&temp.val==temp.next.val){
                    temp=temp.next;
                }
                temp=temp.next;
                pre.next=temp;
            }
            else{
                temp=temp.next;
                pre=pre.next;
            }
        }
        return node.next;
}

思路：使用双指针法，pre的下一个指向temp，temp用于进行判断重复节点，当遇到重复节点时，temp一直向后遍历直到完全越过这个节点，在将pre指过去。

树

JZ55 二叉树的深度

public int TreeDepth(TreeNode root) {
        if(root==null)
            return 0;
        int a=TreeDepth(root.left);
        int b=TreeDepth(root.right);
        return a>b?a+1:b+1;
}

思路：使用递归来求得层数

public int TreeDepth(TreeNode root){
        if(root==null)
            return 0;
        Queue<TreeNode>queue=new LinkedList<TreeNode>();
        queue.add(root);
        int level=0;
        while(!queue.isEmpty()){
            int size=queue.size();
            while(size>0){
                size--;
                TreeNode temp=queue.peek();queue.remove();
                if(temp.left!=null)queue.add(temp.left);
                if(temp.right!=null)queue.add(temp.right);
            }
            level++;
        }
        return level;
}

思路：使用队列的思路，首先创建一个队列，然后将头节点加入队列，进入循环，定义一个size为队列的一层的数量，在内循环中挨个将队列一层中的节点数量取出来，加入其子节点，一直到遍历完整个树。

知识点：

定义队列 Queuequeue=new LinkedList();
取出队列的头节点 queue.peek()
移除队列的头节点 queue.remove()

JZ77 按之字形顺序打印二叉树

 public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList res=new ArrayList();
        if(pRoot==null)
            return res;
        Queue<TreeNode> q=new LinkedList<TreeNode>();
        Boolean flag=true;
        q.add(pRoot);
        while(!q.isEmpty()){
            int size=q.size();
            ArrayList a=new ArrayList();
            while(size>0){
                size--;
                TreeNode temp=q.peek();q.remove();
                if(flag==true)//用于翻转
                    a.add(temp.val);
                else
                    a.add(0,temp.val);
                if(temp.left!=null)q.add(temp.left);
                if(temp.right!=null)q.add(temp.right);
            }
            res.add(a);
            flag=!flag;
        }
        return res;
    }
 

思路：利用层次遍历打印二叉树，利用一个flag来完成之行

知识点：

对于ArrayList的二维数组，可以首先定义一个没有类型的ArrayList数组，然后定义其他的ArrayList数组，再用直接add
对于队列queue q.poll( )==q.peek()+q.remove();

JZ54 二叉搜索树的第k个节点

    public int KthNode (TreeNode proot, int k) {
        // write code here
        if(proot==null||k==0)
            return -1;
        Queue<TreeNode>queue=new LinkedList<TreeNode>();
        HashSet<Integer>set=new HashSet<Integer>();
        queue.add(proot);
        while(!queue.isEmpty()){
            int size=queue.size();
            while(size>0){
                size--;
                TreeNode node=queue.poll();
                set.add(node.val);
                if(node.left!=null)queue.add(node.left);
                if(node.right!=null)queue.add(node.right);
            }
        }
        if(set.size()<k)
            return -1;
        int num=0;
        for(Integer i:set){
            if(num==k-1){
                num=i;
                break;
            }
            num++;
        }
        return num;
    }

思路：使用set数组的自动排序（由小到大）的属性进行求解，利用层次遍历将所有节点加入set数组中，再遍历set数组找到第k个节点

知识点：

对于set这种数组循环遍历 for(Integer i:set)

JZ7 重建二叉树

    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        if(pre.length==0)
            return null;
        TreeNode root=new TreeNode(pre[0]);
        for(int i=0;i<vin.length;i++){
            if(vin[i]==pre[0]){
                root.left=reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(vin,0,i));									root.right=reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(vin,i+1,vin.length));
                break;
            }
        }
        return root;
    }

思路：使用递归的思路，利用先序遍历第一个数组的第一个元素是头节点的特性，来找到中序遍历对应的节点，来进行分割。

知识点：

提取数组的一部分 Arrays.copyOfRange(pre,1,i+1) 左闭右开
提取数组进行递归时，看提取哪一部分就算提取节点的数量

JZ26 树的子结构

public boolean HasSubtree(TreeNode root1,TreeNode root2) {
    if(root1==null||root2==null)
        return false;
    return judge(root1,root2)||HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
}
public boolean judge(TreeNode root1,TreeNode root2){
    if(root2==null)
        return true;
    if(root1==null )
        return false;
    if(root1.val==root2.val)
        return judge(root1.left,root2.left)&&judge(root1.right,root2.right);
    else
        return false;
}

思路：还是采用递归的方式判断是否时子结构

JZ27 二叉树的镜像

public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot==null)
            return pRoot;
        TreeNode left=pRoot.left;
        TreeNode right=pRoot.right;
        pRoot.left=right;
        pRoot.right=left;
        Mirror(pRoot.left);
        Mirror(pRoot.right);
        return pRoot;
}

思路：采用递归的方式交换左右子树

public TreeNode Mirror (TreeNode pRoot) {
    	if(pRoot==null)
            return null;
        Queue<TreeNode> q=new LinkedList<TreeNode>();
        q.add(pRoot);
        while(!q.isEmpty()){
            int size=q.size();
            while(size>0){
                size--;
                TreeNode node=q.peek();q.remove();
                TreeNode temp=node.left;
                node.left=node.right;
                node.right=temp;
                if(node.left!=null)q.add(node.left);
                if(node.right!=null)q.add(node.right);
            }
        }
        return pRoot;
}

思路：采用bfs的思路进行交换

JZ32 从上往下打印二叉树

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    ArrayList<Integer>array=new ArrayList<Integer>();
    if(root==null)
        return array;
    Queue<TreeNode>queue=new LinkedList<TreeNode>();
    queue.add(root);
    while(!queue.isEmpty()){
        int size=queue.size();
        while(size>0){
            size--;
            TreeNode temp=queue.poll();
            array.add(temp.val);
            if(temp.left!=null)queue.add(temp.left);
            if(temp.right!=null)queue.add(temp.right);
        }
    }
    return array;
}

思路：使用bfs的方式遍历整个树

JZ33 二叉搜索树的后序遍历序列

public boolean VerifySquenceOfBST(int [] sequence) {
    if(sequence==null||sequence.length==0)
        return false;
    return Verify(sequence,0,sequence.length-1);
}
public boolean Verify(int []sequence,int first,int last){
    if(last<=first)
        return true;
    int root =sequence[last];
    int cutpoint=first;
    while(cutpoint<last&&sequence[cutpoint]<=root)
        cutpoint++;            //分成两段，前一段都小于等于根节点，后一段应该都大于根节点
    for(int i=cutpoint;i<last;i++)
        if(sequence[i]<root)
            return false;
    return Verify(sequence,first,cutpoint-1)&&Verify(sequence,cutpoint,last-1);
}

思路：利用后续遍历的特点，最后一个值是头节点，找到头节点后，根据二叉搜索树的特点将前面数组分成两份，然后判断是否完全符合二叉搜索树特点。

JZ82 二叉树中和为某一值的路径(一)

public boolean hasPathSum (TreeNode root, int sum) {
    // write code here
    if(root==null||sum==0)
        return false;
    int count=0;
    return judge(root,count,sum);
    
}
public boolean judge(TreeNode root,int count,int sum){
    count+=root.val;
    if(root.left==null&&root.right==null)
        if(count==sum)
            return true;
        else
            return false;
    boolean left=false,right=false;
    if(root.left!=null)
       left=judge(root.left,count,sum);
    if(root.right!=null)
       right=judge(root.right,count,sum);
    return left||right;
    
}

思路：利用dfs的思路，找到叶子节点然后进行判断

JZ34 二叉树中和为某一值的路径(二)

public void dfs(int expectNumber, TreeNode root, ArrayList<ArrayList<Integer>> ans, int count, ArrayList<Integer> ans_){
    count += root.val;
    ans_.add(root.val);
    if(root.left == null && root.right == null) {
        if(count == expectNumber) {   //知识点4
            ArrayList<Integer> ans_temp = new ArrayList<>();
            ans_temp.addAll(ans_);
            ans.add(ans_temp);
        }
    }
    if(root.left != null)
        dfs(expectNumber, root.left, ans, count, ans_);
    if(root.right != null)
        dfs(expectNumber, root.right, ans, count, ans_);
    ans_.remove(ans_.size() - 1);   //回溯
}
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    if(root != null)
        dfs(expectNumber, root, ans, 0, new ArrayList<>());
    return ans;
}

思路：和上道题一样的思路，从根节点到叶子节点求和然后判断是否和预计值相等。不同的是这道题需要求路径，所以要定义两个数组，一个二维数组用于最后的结果，一维数组代表指针的路径，当判断是要的路径后，便将一维数组的值加入二维数组中。

知识点：

关于java参数传递，java的数据类型分为基本数据类型和引用类型，对于基本数据类型都是值传递，对于引用类型例如数组类型，传递的是地址，所以在另一个函数改变后，无需返回也能改变。
但对于string类型，string是一个类，参数传递的时候应该是引用传递，实际上是参数传递，是因为String的值在创建后是不能更改的，任何的修改相当于重新创建一个对象。
对于这种需要记录路径的问题，需要对数组进行回溯，因为每次刚进这个函数时，path数组都添加了这个节点，当遍历完这个路径后，要遍历其他路径时，path里面还有当前路径的值，所以当函数结束时，需要去掉当前值进行回溯。
对于需要新创建一个数组，将path里的值加入，再用二维数组添加新数组这个做法，原因是二维数组添加的是path数组的引用，所以如果二维数组添加path，当每次path数组进行回溯时，当前path数组的值会发生变化，会导致二维数组的值也跟着变化。

JZ84 二叉树中和为某一值的路径(三)

int res=0;
public void dfs(TreeNode root,int sum,int count){
    count+=root.val;
    if(count==sum)
        res++;
    if(root.left!=null)dfs(root.left,sum,count);
    if(root.right!=null)dfs(root.right,sum,count);
    return;
}
public int FindPath (TreeNode root, int sum) {
    // write code here
    if(root==null)
        return 0;
    Queue<TreeNode>q=new LinkedList<TreeNode>();
    q.add(root);
    while(!q.isEmpty()){
        int size=q.size();
        while(size>0){
            size--;
            TreeNode node=q.peek();q.remove();
            dfs(node,sum,0);
            if(node.left!=null)q.add(node.left);
            if(node.right!=null)q.add(node.right);
        }
    }
    return res;
}

思路：层次遍历来确定每次的根节点，然后再dfs求和，由于节点值不一定为正数，所以同一个根节点可能有多个路径

JZ36 二叉搜索树与双向链表

public void inorder(TreeNode root,ArrayList<TreeNode> array){
    if(root==null)
        return;
    inorder(root.left,array);
    array.add(root);
    inorder(root.right,array);
}
public TreeNode Convert(TreeNode pRootOfTree) {
    ArrayList<TreeNode> array=new ArrayList<TreeNode>();
    if(pRootOfTree==null)
        return null;
    inorder(pRootOfTree,array);
    for(int i=0;i<array.size()-1;i++){
        array.get(i).right=array.get(i+1);
        array.get(i+1).left=array.get(i);
    }
    return array.get(0);
}

思路：利用中序遍历将节点加入数组中，然后再在数组中对各个节点添加左右关系

知识点：

调用ArrayList数组中一个值 array.get(i)

JZ79 判断是不是平衡二叉树

public boolean IsBalanced_Solution(TreeNode root) {
   if(root==null)return true;
   return Math.abs(deep(root.left)-deep(root.right))<2&&IsBalanced_Solution(root.left)&&IsBalanced_Solution(root.right);
}
public int deep(TreeNode root){
    if(root==null)return 0;
    return Math.max(deep(root.left),deep(root.right))+1;
}

思路：利用递归的方法，判断根节点的左子树和右子树，左子树，右子树深度之差小于2

知识点：

求一个树的深度

public int deep(TreeNode root){
    if(root==null)return 0;
    return Math.max(deep(root.left),deep(root.right))+1;
}

JZ8 二叉树的下一个结点

ArrayList<TreeLinkNode>array=new ArrayList<TreeLinkNode>();
public TreeLinkNode GetNext(TreeLinkNode pNode) {
    TreeLinkNode node=pNode;
    while(pNode.next!=null)
        pNode=pNode.next;
    inorder(pNode);
    for(int i=0;i<array.size();i++)
        if(node==array.get(i))
            return i==array.size()-1?null:array.get(i+1);
    return null;
}
public void inorder(TreeLinkNode root){
    if(root!=null){
        inorder(root.left);
        array.add(root);
        inorder(root.right);
    }
}

思路：利用next指向父节点来找到根节点，然后按照中序遍历将节点加入数组中，然后再在数组中找到该节点的下一个节点

JZ28 对称的二叉树

boolean isSymmetrical(TreeNode pRoot) {
    if(pRoot==null)
        return true;
    return judge(pRoot.left,pRoot.right);
}
boolean judge(TreeNode root1,TreeNode root2){
    if(root1==null&&root2==null)
        return true;
    if(root1==null||root2==null)
        return false;
    if(root1.val==root2.val)
        return judge(root1.left,root2.right)&&judge(root1.right,root2.left);
    return false;
}

思路：judge的第二个if不能缺少，不然可能会出现越界的问题

JZ78 把二叉树打印成多行

ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    ArrayList<ArrayList<Integer>>array=new ArrayList<ArrayList<Integer>>();
    Queue<TreeNode>q=new LinkedList<TreeNode>();
    if(pRoot==null)
        return array;
    q.add(pRoot);
    while(!q.isEmpty()){
        int size=q.size();
        ArrayList<Integer>a=new ArrayList<Integer>();
        while(size>0){
            size--;
            TreeNode temp=q.peek();q.remove();
            a.add(temp.val);
            if(temp.left!=null)q.add(temp.left);
            if(temp.right!=null)q.add(temp.right);
        }
        array.add(a);
    }
    return array;
}

思路：使用bfs遍历一遍，每一层为一个一维数组加入二维数组中

知识点：

一维数组每次都是新创建的，不用担心一维数组变化而导致二维数组变化得问题

JZ86 在二叉树中找到两个节点的最近公共祖先

public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
    // write code here
    //首先使用bfs，将父子关系加进map中，然后o1的所有父节点加入set数组中，在从下到上判断o2的父节点是否存在于set数组
    Queue<TreeNode>q=new LinkedList<TreeNode>();
    HashMap<Integer,Integer>map=new HashMap<Integer,Integer>();
    map.put(root.val,Integer.MAX_VALUE);
    q.add(root);
    while(!map.containsKey(o1)||!map.containsKey(o2)){
        TreeNode node=q.poll();
        
        if(node.left!=null){
            map.put(node.left.val,node.val);
            q.add(node.left);
        }
        if(node.right!=null){
            map.put(node.right.val,node.val);
            q.add(node.right);
        }
    }
    HashSet<Integer>set=new HashSet<Integer>();
    while(map.containsKey(o1)){
        set.add(o1);//需要将根节点和其父节点添加进map，否则set里不会存在根节点
        o1=map.get(o1);
    }
    while(!set.contains(o2)){
        o2=map.get(o2);
    }
    return o2;
}

思路：首先使用bfs将各个节点及其父节点加入map中，然后将o1及其所有父节点都加入set中，然后挨个判断o2及其父节点是否在set中存在

知识点：

树中有关节点及其父节点之间关系时，考虑map
map定义 HashMap<Integer,Integer>map=new HashMap<Integer,Integer>();
map的相关方法
1. 加入 map.put(a,b);
2. 判断map中是否含有某值 map.containsKey(o1)
3. 得到map中一个键对 o1=map.get(o1)

JZ68 二叉搜索树的最近公共祖先

public int lowestCommonAncestor (TreeNode root, int p, int q) {
    // write code here
    //使用上一题的方法
    
    Queue<TreeNode>queue=new LinkedList<TreeNode>();
    HashMap<Integer,Integer>map=new HashMap<Integer,Integer>();
    map.put(root.val,Integer.MAX_VALUE);
    queue.add(root);
    while(!map.containsKey(p)||!map.containsKey(q)){
        TreeNode node=queue.poll();
        if(node.left!=null){
            map.put(node.left.val,node.val);
            queue.add(node.left);
        }
        if(node.right!=null){
            map.put(node.right.val,node.val);
            queue.add(node.right);
        }
    }
    HashSet<Integer>set=new HashSet<Integer>();
    while(map.containsKey(p)){
        set.add(p);//需要将根节点和其父节点添加进map，否则set里不会存在根节点
        p=map.get(p);
    }
    while(!set.contains(q)){
        q=map.get(q);
    }
    return q;
}

思路：和上题一样的思路，没有利用二叉搜索树的特点

队列 & 栈

JZ9 用两个栈实现队列

Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node) {
    stack1.add(node);
}

public int pop() {
    if(stack2.isEmpty()){
        while(!stack1.isEmpty()){
            stack2.add(stack1.peek());
            stack1.pop();
        }
    }
    int res=stack2.peek();
    stack2.pop();
    return res;
}

思路：进队列操作直接进栈，出队列的话每次等stack2空了之后，再将stack1加入stack2

知识点：

定义栈 Stack stack1 = new Stack();
栈的相关方法：
1. 进栈 stack.add(node）
2. 判断栈是否为空 stack.isEmpty()
3. 出栈 stack1.pop()
4. 栈顶元素 stack2.peek()

JZ30 包含min函数的栈

	Stack<Integer>stack1=new Stack<Integer>();
    Stack<Integer>stack2=new Stack<Integer>();
    public void push(int node) {
        stack1.add(node);
        if(stack2.isEmpty())
            stack2.add(node);
        else{
            if(node<stack2.peek())
                stack2.add(node);
            else
                stack2.add(stack2.peek());
        }
    }
    
    public void pop() {
        stack1.pop();
        stack2.pop();
    }
    
    public int top() {
        return stack1.peek();
    }
    
    public int min() {
        return stack2.peek();
    }

思路：对于push pop top，stack都自带函数，但min需要一个辅助栈，每次保证栈顶都是最小值

JZ31 栈的压入、弹出序列

public boolean IsPopOrder(int [] pushA,int [] popA) {
  //利用一个辅助栈存之前的元素
    Stack<Integer>stack=new Stack<Integer>();
    int index=0;
    for(int i=0;i<pushA.length;i++){
        if(pushA[i]!=popA[index])
            stack.add(pushA[i]);
        else{
            index++;
            while(!stack.isEmpty()&&stack.peek()==popA[index]){
                stack.pop();
                index++;
            }
        }
    }
    return stack.isEmpty();
}

思路：利用一个栈来模拟这个过程，挨个判断push每个值，如果push和pop的值不相等，说明这个元素还没有出栈，所以将该元素加入栈中，如果push和pop的值相等，就当这个值出栈了，及index++，然后再判断pop中接下来的值是否和栈中元素对应相等，如果相等则index++，出栈，最后再判断栈是否为空。

JZ73 翻转单词序列

public String ReverseSentence(String str) {
    String []s=str.split(" ");
    String res="";
    for(int i=s.length-1;i>=0;i--)
        res+=" "+s[i];
    return res.substring(1);
}

思路：利用string的split函数将str区分开来，然后再反向用res添加

知识点：

String []s=str.split(“ “); 将str用空格区分开来，再装入数组中
res.substring(begin，end); 提取字符串中的一部分

JZ59 滑动窗口的最大值

public ArrayList<Integer> maxInWindows(int [] num, int size) {
    ArrayList<Integer>array=new ArrayList<Integer>();
    if(size==0)
        return array;
    for(int i=0;i<num.length+1-size;i++){
        array.add(max(Arrays.copyOfRange(num,i,i+size)));
    }
    return array;
}
public int max(int []a){
    int max=Integer.MIN_VALUE;
    for(int i=0;i<a.length;i++)
        if(max<a[i])
            max=a[i];
    return max;
}

思路：挨个取出一段求出最大值加入

知识点：

提取出数组的一段 Arrays.copyOfRange(num,i,i+size) 返回类型和数组类型一样
str.substring(begin，end); 提取字符串中的一部分

搜索算法

JZ53 数字在升序数组中出现的次数

public int GetNumberOfK(int [] array , int k) {
   return bis(array,k,0,array.length-1);
}
public int bis(int []array,int k,int first,int last){
    if(last<first)
        return 0;
    if(last==first)
        if(array[first]==k)
            return 1;
        else
            return 0;
    int mid=first+(last-first)/2;
    if(array[mid]==k)
        return bis(array,k,first,mid-1)+bis(array,k,mid+1,last)+1;
    else if(array[mid]<k)
        return bis(array,k,mid+1,last);
    else
        return bis(array,k,first,mid-1);
}

思路：使用二分法进行求解，模板背住

JZ4 二维数组中的查找

public boolean Find(int target, int [][] array) {
    if(array.length==0||array[0].length==0)
        return false;
    int r=0,c=array[0].length-1;
    while(r<array.length&&c>=0){
        if(array[r][c]==target)
            return true;
        else if(array[r][c]>target){
            c--;
        }
        else if(array[r][c]<target){
            r++;
        }
    }
    return false;
}

思路：类似与二分法的思想，右上角大小处于中间，如果小于target，则往下移动，如果大于target，则往左移动

JZ11 旋转数组的最小数字

int min=Integer.MAX_VALUE;
public int minNumberInRotateArray(int [] array) {
    bis(array,0,array.length-1);
    return min;
}
public void bis(int [] array,int first,int last){
    if(first==last){
        min=array[first];
        return;
    }
    int mid=first+(last-first)/2;
    if(array[mid]>array[last])
        bis(array,mid+1,last);
    else if(array[mid]<array[last]){
        bis(array,first,mid);
    }
    else{
        bis(array,first,--last);
    }
}

思路：使用二分法，每次和最后一个节点比较

JZ44 数字序列中某一位的数字

public int findNthDigit (int n) {
    // write code here
    if(n<10)
        return n;
    n-=10;
    int digital=2;
    long low=10,sum=90;//sum表示这个范围内有多少个数
    while(n>=sum*digital){
        n-=sum*digital;//sum*digital表示这个范围内的数
        sum*=10;
        low*=10;
        digital++;
    }
    return (String.valueOf(low+n/digital)).charAt(n%digital)-'0';
}

思路：根据数字的位数将n分为多个区分范围，0-9，10-99，100-999等，然后再判断n是在哪个范围由此找到n是哪个数字。

知识点：

将数字转化为字符串 String.valueOf(number)
取字符串中某个字符 str.charAt(n)
提取字符串中的一部分 str.substring(begin，end);

回溯

JZ12 矩阵中的路径

public boolean hasPath (char[][] matrix, String word) {
    // write code here
    for(int i=0;i<matrix.length;i++)
        for(int j=0;j<matrix[0].length;j++){
            if(matrix[i][j]==word.charAt(0)){
                if(dfs(matrix,word,i,j,0)==true)
                    return true;
            }
        }
    return false;
}
public boolean dfs(char[][] matrix,String word,int x,int y,int count){
    if(x<0||x>=matrix.length||y<0||y>=matrix[0].length||matrix[x][y]!=word.charAt(count))
        return false;
    if(count==word.length()-1)
        return true;
    char temp=matrix[x][y];
    matrix[x][y]='.';
    count++;
    boolean flag=dfs(matrix,word,x+1,y,count)||dfs(matrix,word,x-1,y,count)||dfs(matrix,word,x,y+1,count)||dfs(matrix,word,x,y-1,count);
    matrix[x][y]=temp;
    return flag;
}

思路：循环遍历查找数组中节点和word头字符相同的进入dfs遍历，没有用visit数组，而是直接将matrix变化来实现相同的效果，最后记得要改回来，不然回溯其他路径时该点还是不可走。

JZ13 机器人的运动范围

private static int num=0;
private static int [][]visit=new int[101][101];
public int movingCount(int threshold, int rows, int cols) {
    dfs(threshold,rows,cols,0,0);
    return num;
}
public void dfs(int threshold,int rows,int cols,int x,int y){
    if(x<0||x>=rows||y<0||y>=cols||visit[x][y]==1)
        return;
    visit[x][y]=1;
    int xx=x<100?x/10+(x-((int)(x/10)*10)):1;
    int yy=y<100?y/10+(y-((int)(y/10)*10)):1;
    if(xx+yy>threshold){
        return;
    }
    num++;
    dfs(threshold,rows,cols,x+1,y);dfs(threshold,rows,cols,x-1,y);dfs(threshold,rows,cols,x,y+1);dfs(threshold,rows,cols,x,y-1);
    return;
}

思路：使用dfs，走每个点判断是否符合要求，这道题不用在函数最后把visit改回来，因为不需要求路径啥的

排序

JZ3 数组中重复的数字

public int duplicate (int[] numbers) {
    // write code here
    HashSet<Integer>set=new HashSet<Integer>();
    for(int i=0;i<numbers.length;i++){
        if(set.contains(numbers[i]))
            return numbers[i];
        set.add(numbers[i]);
    }
    return -1;
}

JZ51 数组中的逆序对

public int InversePairs(int [] array) {
    long count=0;
    for(int i=array.length-1;i>0;i--)
        for(int j=i-1;j>=0;j--){
            if(array[j]>array[i])
                count++;
        }
    int res=(int)Math.floorMod(count,1000000007);
    return res;
}

JZ40 最小的K个数

使用Array类自带的方法

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
    ArrayList<Integer>array=new ArrayList<Integer>();
    if(k==0)
        return array;
    Arrays.sort(input);
    for(int i=0;i<k;i++)
        array.add(input[i]);
    return array;
}

堆排序

    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer>array=new ArrayList<Integer>();
        if(k==0 || k>input.length)
            return array;
        PriorityQueue<Integer>queue=new PriorityQueue<>((num1,num2)->num2-num1);
        for(int i=0;i<k;i++){
            queue.add(input[i]);
        }
        for(int i=k;i<input.length;i++){
            if(queue.peek()>input[i]){
                queue.poll();
                queue.add(input[i]);
            }
        }
        for(int i=0;i<k;i++){
            array.add(queue.poll());
        }
        return array;
    }

思路：利用PriorityQueue来建堆，然后来依次添加剩下的元素，得到最后的结果

快速排序

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
    ArrayList<Integer>array=new ArrayList<Integer>();
    if(k==0 || k>input.length)
        return array;
    quickSort(input,0,input.length-1);
    for(int i=0;i<k;i++)
        array.add(input[i]);
    return array;
}
public void quickSort(int []input,int left,int right){
    if(left>right)
        return;
    int start=left;int end=right;
    int par=input[start];
    int temp;
    while(start<end){
        while(start<end&&input[end]>=par)
            end--;
        while(start<end&&input[start]<=par)
            start++;
        if(start<end){
            temp=input[start];
            input[start]=input[end];
            input[end]=temp;
        }
    }
    input[left]=input[start];//将初始位置和par进行交换
    input[start]=par;
    quickSort(input,left,end-1);
    quickSort(input,end+1,right);
}

思路：使用快排排序，再提取前k个。

冒泡法

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
    int N=input.length;
    ArrayList<Integer> list=new ArrayList<>();
    if(k>N || N==0 ) return list;
    for(int i=0;i<N;i++){
        for(int j=0;j<N-1;j++){
            if(input[j]>input[j+1]){
                int temp=input[j];
                input[j]=input[j+1];
                input[j+1]=temp;
            }
        }
    }
    for(int i=0;i<k;i++)
        list.add(input[i]);
    return list;
}

模拟

JZ29 顺时针打印矩阵

public ArrayList<Integer> printMatrix(int [][] matrix) {
       ArrayList<Integer>arr=new ArrayList<Integer>();
       if(matrix.length==0||matrix[0].length==0)
           return arr;
        int lx=0,rx=matrix[0].length-1;
        int ty=0,dy=matrix.length-1;
        while(lx<=rx&&ty<=dy){
            for(int i=lx;i<=rx;i++)
                arr.add(matrix[ty][i]);
            for(int i=ty+1;i<=dy;i++)
                arr.add(matrix[i][rx]);
            if(ty<dy){
                for(int i=rx-1;i>=lx;i--)
                    arr.add(matrix[dy][i]);
            }
            if(lx<rx){
                for(int i=dy-1;i>ty;i--)
                    arr.add(matrix[i][lx]);
            }
            lx++;rx--;ty++;dy--;
        }
        return arr;
    }

思路：按照题目中要求的顺序打印代码

JZ61 扑克牌顺子

public boolean IsContinuous(int [] numbers) {
    Arrays.sort(numbers);
    int count=0;
    int i=0;
    while(numbers[i]==0){
        count++;
        i++;
    }
    for(i=count;i<numbers.length-1;i++){
        if(numbers[i]==numbers[i+1])
            return false;
        count-=(numbers[i+1]-numbers[i]-1);
        if(count<0)
            return false;
    }
    if(count>=0)
        return true;
    return false;
}

思路：首先对数组排序，然后求得0的数量，然后再判断其他数之间的差距够不够用0来弥补

JZ67 把字符串转换成整数(atoi)

public int StrToInt (String s) {
    // write code here
    int res=0,val=Integer.MAX_VALUE/10;
    int i=0,sign=1,len=s.length();
    if(len==0)
        return 0;
    while(s.charAt(i)==' '){
        i++;
        if(i==len)
            return 0;
    }
    if(s.charAt(i)=='-'){
        sign=-1;
        i++;
    }
    else if(s.charAt(i)=='+')
        i++;
    for(int j=i;j<len;j++){
        if(s.charAt(j)<'0'||s.charAt(j)>'9')
            break;
        if(res>val||res==val&&s.charAt(j)>Integer.MAX_VALUE%10+'0')//判断是否越界，来确定符号
            return sign==1?Integer.MAX_VALUE:Integer.MIN_VALUE;
        res=res*10+(s.charAt(j)-'0');
    }
    return sign*res;
}

思路：首先去掉空格，然后判断数值的正负，接着循环取数，考虑越界的情况来确定数字的正负

JZ20 表示数值的字符串

public boolean isNumeric (String str) {
    // write code here
    boolean isnum=false,isdot=false,ise=false;
    char[] s=str.trim().toCharArray();
    for(int i=0;i<s.length;i++){
        if(s[i]>='0'&&s[i]<='9')
            isnum=true;
        else if(s[i]=='.'){
            if(isdot||ise)
                return false;
            isdot=true;
        }
        else if(s[i]=='e'||s[i]=='E'){
            if(ise||!isnum)
                return false;
            ise=true;
            isnum=false;
        }
        else if(s[i]=='+'||s[i]=='-'){
            if(i!=0&&s[i-1]!='e'&&s[i-1]!='E')
                return false;
        }
        else
            return false;
    }
    return isnum;
}

思路：利用三个isnum，isdot，ise来进行判断

知识点：

char[] s=str.trim().toCharArray(); trim方法删除字符串头尾空白符，toCharArray将字符串转化为字符数组

动态规划

JZ42 连续子数组的最大和

public int FindGreatestSumOfSubArray(int[] array) {
    int pre=array[0];
    int maxx=array[0];
    for(int i=1;i<array.length;i++){
        pre=Math.max(pre+array[i],array[i]);
        maxx=Math.max(pre,maxx);
    }
    return maxx;
}

思路：每次判断pre+array[i],array[i]的大小，相当于求一个局部最优，然后将每次的局部最优求出一个全局最优

JZ85 连续子数组的最大和(二)

    public int[] FindGreatestSumOfSubArray (int[] array) {
        // write code here
        int pre=array[0];
        int max=array[0];
        int left=0,right=0,begin=0,end=0,length=1;
        for(int i=1;i<array.length;i++){
            right++;
            if(array[i]>pre+array[i])
                left=i;
            pre=Math.max(array[i],array[i]+pre);
            if(pre>max||pre==max&&(right-left+1)>length){
                begin=left;
                end=right;
                max=pre;
                length=right-left+1;
            }
        }
        return Arrays.copyOfRange(array,begin,end+1);
    }

思路：和上道题一样的求最大值的思路，在上道题的基础上加了几个定位，left，right用于记录当前最大值的位置，然后再和max进行判断

JZ69 跳台阶

递归

public int jumpFloor(int target) {
    if(target<0)
        return 0;
    if(target==0)
        return 1;
    return jumpFloor(target-2)+jumpFloor(target-1);
}

思路：这个和求深度不一样

动态规划

public int jumpFloor(int target) {
    int []res=new int[100];
    res[1]=1;res[2]=2;
    for(int i=3;i<=target;i++){
        res[i]=res[i-2]+res[i-1];
    }
    return res[target];
}

JZ71 跳台阶扩展问题

动态规划

public int jumpFloorII(int target) {
    int []res=new int[21];
    for(int i=1;i<=target;i++){
        for(int j=1;j<i;j++){
            res[i]+=res[j];
        }
        res[i]+=1;
    }
    return res[target];
}

思路：进行累加

递归

public class Solution {
    public int jumpFloorII(int target) {
        if(target<0)
            return 0;
        if(target==0)
            return 1;
        int res=0;
        for(int i=1;i<=target;i++)
            res+=jumpFloorII(target-i);
        return res;
    }
}

JZ10 斐波那契数列

    public int Fibonacci(int n) {
        int []res=new int[41];
        res[1]=1;res[2]=1;
        for(int i=3;i<=n;i++){
            res[i]=res[i-1]+res[i-2];
        }
        return res[n];
    }

JZ70 矩形覆盖

public int rectCover(int target) {
    int []res=new int[39];
    res[1]=1;res[2]=2;
    for(int i=3;i<=target;i++)
        res[i]=res[i-2]+res[i-1];
    return res[target];
}

JZ63 买卖股票的最好时机(一)

public int maxProfit (int[] prices) {
    // write code here
    int max=0,min=prices[0];
    for(int i=1;i<prices.length;i++){
        if(min>prices[i])min=prices[i];
        else
            max=Math.max(max,prices[i]-min);
    }
    return max;
}

JZ47 礼物的最大价值

    public int maxValue (int[][] grid) {
        // write code here
        int [][]res=new int[202][202];
        for(int i=1;i<grid.length+1;i++)
            for(int j=1;j<grid[0].length+1;j++){
                res[i][j]=Math.max(res[i-1][j],res[i][j-1])+grid[i-1][j-1];
            }
        return res[grid.length][grid[0].length];
    }

思路：状态方程Math.max(res[i-1][j],res[i][j-1])+grid[i-1][j-1] 通过这个状态方程求得最后结果很像0-1背包

JZ48 最长不含重复字符的子字符串

    public int lengthOfLongestSubstring (String s) {
        // write code here
        int []position=new int[128];
        int begin=0,result=0;
        for(int i=0;i<s.length();i++){
            begin=Math.max(begin,position[s.charAt(i)]);//1
            result=Math.max(result,i-begin+1);//2
            position[s.charAt(i)]=i+1;//3
        }
        return result;
    }

思路：本题的思路还是挨个求得当前字符串长度，然后从中找出最长的。难点在于遇到相同的字符时，怎么找到上一个相同字符的位置，本题使用一个数组来记录每个字符的最近位置。代码1，是找出字符串起点位置，看是当前的起点还是相同字符串位置的起点。代码2就是求最大值。代码3是遍历过这个字符，来记录其最新位置，i+1是因为下次遇到相同字符串，是抛掉这个字符来求的长度。

JZ46 把数字翻译成字符串

    public int solve (String nums) {
        // write code here
        int []res=new int[91];
        if(nums.length()==0||nums.charAt(0)=='0')
            return 0;
        res[0]=1;
        for(int i=1;i<nums.length();i++){
            if(nums.charAt(i)!='0')
                res[i]=res[i-1];
            if(nums.charAt(i-1)=='1'||(nums.charAt(i-1)=='2'&&nums.charAt(i)<='6')){
                if(i==1)
                    res[i]+=1;
                else
                    res[i]+=res[i-2];
            }
        }
        return res[nums.length()-1];
    }

思路：这道题的难点是考虑如何处理‘0’，如果当前字符是0的话，那只能看前面是否是1或者2，如果是的话那情况就和i-2时相同，如果不是那就是0。

位运算

JZ65 不用加减乘除做加法

    public int Add(int num1,int num2) {
        while(num2!=0){
            int sum=num1^num2;
            int temp=(num1&num2)<<1;
            num1=sum;
            num2=temp;
        }
        return num1;
    }

思路：num1代表非进位，num2代表进位

JZ15 二进制中1的个数

public int NumberOf1(int n) {
    int ans=0;
    int flag=1;
    while(flag!=0){
        if((n&flag)!=0)ans++;
        flag<<=1;
    }
    return ans;
}

思路：用flag从左往右判断1的个数

JZ16 数值的整数次方

    public double Power(double base, int exponent) {
        if(exponent==0)
            return (double)1;
        if(exponent<0){
            base=1/base;
            exponent=-exponent;
        }
        double res=1;
        for(int i=exponent;i>0;i--){
            res*=base;
        }
        return res;
  }

思路：难点在于exponent可以为负数，为负数时，将base变为1/base，然后exponent变为其相反数

JZ56 数组中只出现一次的两个数字

public int[] FindNumsAppearOnce (int[] array) {
    // write code here
    boolean []flag=new boolean[1000001];
    HashSet<Integer> set=new HashSet<Integer>();
    for(int i=0;i<array.length;i++){
        if(set.contains(array[i])){
            flag[array[i]]=true;
            set.remove(array[i]);
        }
        else if(flag[array[i]]==false)
            set.add(array[i]);
    }
    int []res=new int[2];
    int j=0;
    for(Integer i:set){
        res[j]=i;
        j++;
    }
    return res;
}

思路：这个用于一个数字可以存在多次

JZ64 求1+2+3+…+n

    public int Sum_Solution(int n) {
        int sum=(int)(Math.pow(n,2)+n)>>1;
        return sum;
    }

刷题

链表

JZ6 从尾到头打印链表

JZ24 反转链表

JZ25 合并两个排序的链表

JZ52 两个链表的第一个公共结点

JZ23 链表中环的入口结点

JZ22 链表中倒数最后k个结点

JZ35 复杂链表的复制

JZ18 删除链表的节点

JZ76 删除链表中重复的结点

树

JZ55 二叉树的深度

JZ77 按之字形顺序打印二叉树

JZ54 二叉搜索树的第k个节点

JZ7 重建二叉树

JZ26 树的子结构

JZ27 二叉树的镜像

JZ32 从上往下打印二叉树

JZ33 二叉搜索树的后序遍历序列

JZ82 二叉树中和为某一值的路径(一)

JZ34 二叉树中和为某一值的路径(二)

JZ84 二叉树中和为某一值的路径(三)

JZ36 二叉搜索树与双向链表

JZ79 判断是不是平衡二叉树

JZ8 二叉树的下一个结点

JZ28 对称的二叉树

JZ78 把二叉树打印成多行

JZ86 在二叉树中找到两个节点的最近公共祖先

JZ68 二叉搜索树的最近公共祖先

队列 & 栈

JZ9 用两个栈实现队列

JZ30 包含min函数的栈

JZ31 栈的压入、弹出序列

JZ73 翻转单词序列

JZ59 滑动窗口的最大值

搜索算法

JZ53 数字在升序数组中出现的次数

JZ4 二维数组中的查找

JZ11 旋转数组的最小数字

JZ44 数字序列中某一位的数字

回溯

JZ12 矩阵中的路径

JZ13 机器人的运动范围

排序

JZ3 数组中重复的数字

JZ51 数组中的逆序对

JZ40 最小的K个数

模拟

JZ29 顺时针打印矩阵

JZ61 扑克牌顺子

JZ67 把字符串转换成整数(atoi)

JZ20 表示数值的字符串

动态规划

JZ42 连续子数组的最大和

JZ85 连续子数组的最大和(二)

JZ69 跳台阶

JZ71 跳台阶扩展问题

JZ10 斐波那契数列

JZ70 矩形覆盖

JZ63 买卖股票的最好时机(一)

JZ47 礼物的最大价值

JZ48 最长不含重复字符的子字符串

JZ46 把数字翻译成字符串

位运算

JZ65 不用加减乘除做加法

JZ15 二进制中1的个数

JZ16 数值的整数次方

JZ56 数组中只出现一次的两个数字

JZ64 求1+2+3+…+n

CATALOG

FEATURED TAGS