精华内容
下载资源
问答
  • 一、概述List遍历是我们经常会使用到的一个功能,很多时候我们也会用到反向遍历,在用到反向遍历时我们常用的方法是通过for循环或者是对List反向排序来完成相应的操作,像下面代码这样:方法1:for(int i = list.size...

    一、概述

    List遍历是我们经常会使用到的一个功能,很多时候我们也会用到反向遍历,在用到反向遍历时我们常用的方法是通过for循环或者是对List反向排序来完成相应的操作,像下面代码这样:

    方法1:

    for(int i = list.size()-1; i>=0; i--) {

    System.out.println(list.get(i));

    }

    这个方法开上去就比较臃肿,写起来也相对繁琐一些。

    方法2:

    Collections.reverse(list);

    System.out.println(list);

    这种方法看似不错,但是reverse改变了原list的结构,如果我们只是要反向遍历list而不想改变list的结构的话这个方法是不适用的,除非你想在遍历完list之后再次调用reverse把list变回去,这种做法当然是不值得推荐的。

    那么有没有一种方法可以既不改变原有的List的结构,有可以很简洁的实现反向遍历呢?我个人认为,直接制作一个支持反向遍历的List就可以很好的解决这个问题。下面我们就从头开始制作支持反向遍历List。

    二、准备工作

    众所周知,所有的Collection都实现了Iterable接口,而Iterable接口中的iterator()方法就是用来实现集合类遍历的,那么我们是不是可以从这里开始入手。

    还有一点,就是为什么要基于ArrayList去做这件事而不是直接实现List接口,原因很简单,如果我要实现List接口那么我就需要实现List接口中所有的方法,而我比较懒,不想再去实现List接口中的所有方法,而且一般需要遍历处理的都是ArrayList,所有我就直接在ArrayList的基础上去做这件事,也省了不少功夫。

    三、新建List

    话不多说,开干。首先我们需要定义一个类,并且这个类要继承ArrayList:

    public class ErgodicList extends ArrayList {

    /*构造方法 start*/

    public ErgodicList() {

    super();

    }

    public ErgodicList(Collection extends T> integers) {

    super(integers);

    }

    /*构造方法 end*/

    }

    接着我们要编写能够实现反向遍历的Interator:

    /**

    * 反向遍历Iterator

    *

    * @return Iterable

    */

    public Iterable reversed() {

    return () -> new Iterator() {

    int index = ErgodicList.super.size() - 1;

    @Override

    public boolean hasNext() {

    return index > -1;

    }

    @Override

    public T next() {

    return ErgodicList.super.get(index--);

    }

    // Java8以下版本需要重写该方法

    // @Override

    // public void remove() {

    // throw new UnsupportedOperationException("remove");

    // }

    };

    }

    从代码可以看出,首先我们要取出List最末尾的Index,这一点跟for循环很像,然后就是重写Iterator接口的两个方法(java8种remove()有了默认方法,我这里也不需要它所以就没有重写),一个用来判断是否还有下一个元素,一个用来获取元素。

    到此可以支持反向遍历的List就编写好了,是不是感觉比for循环还要复杂,但是这属于一劳永逸的方法,麻烦一次以后再也不用苦逼的写for循环了。下面我们来测试一下效果如何:

    public static void main(String[] args) {

    ErgodicList integers = new ErgodicList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9));

    System.out.println("------------反向遍历结果-------------");

    integers.reversed().forEach(System.out::println);

    System.out.println("------------------------------------");

    System.out.println(integers);

    }

    241c928f296b70a49fd5f8a37f4a2e34.png

    从结果可以看出,简单的foreach代码在不改变原有List的结构的情况下(废话Interator当然不会改变List的结构)实现了List的反向遍历,并且以后再需要反向遍历的时候我们只需要new一个我们自制的List再加一个forEach就好了,用起来相当方便。

    四、衍生

    我们既然实现了反向遍历,那么可不可以实现随机遍历呢,当然没问题,举一反三是我们程序员应有的基本素养。下面来看看随机遍历的实现,还是刚才的那个List,我们再增加一个方法:

    /**

    * 随机遍历Iterator

    *

    * @return Iterable

    */

    public Iterable random() {

    return () -> {

    List randomList = new ArrayList<>(this);

    Collections.shuffle(randomList, new Random());

    return randomList.iterator();

    };

    是不是更简单,具体的说明我就不写了(我比较懒),有兴趣的朋友可以自己查一下。测试代码和反向遍历的测试也差不多,只需要:

    integers.random().forEach(System.out::println);

    使用起来体验也是很不错的,大家可以试一试。

    ------------------------------------------------------------------------------

    欢迎关注我的个人公众号,推送最新文章

    展开全文
  • 反向遍历Problem statement: 问题陈述: Write a program to print Reverse Level Order Traversal of a binary tree. 编写程序以打印二叉树的反向级别顺序遍历 。 Example: 例: Basic level order ...

    反向遍历

    Problem statement:

    问题陈述:

    Write a program to print Reverse Level Order Traversal of a binary tree.

    编写程序以打印二叉树的反向级别顺序遍历

    Example:

    例:

    Reverse Level Order Traversal
        Basic level order traversal:
        2
        7 5
        2 6 9
        5 11 4
    
        Reverse Level order traversal:
        5 11 4
        2 6 9
        7 5
        2
    
    

    Solution:

    解:

    Of course the solution is quite like the level order traversal just a little bit of modification.

    当然,该解决方案就像经过少量修改后的水平顺序遍历一样。

    Algorithm:

    算法:

    FUNCTION reverseLevelOrder (root): prints reverse Level order traversal of the tree

    FUNCTION reverseLevelOrder(root) :打印树的反向Level顺序遍历

    Prerequisite: Queue q, Stack s

    先决条件:队列q ,堆栈s

    FUNCTION reverseLevelOrder(root)// root of the tree
        1.  Declare a TreeNode type variable temp;                
        2.  Declare qto store nodes //creating a queue
        3.  Declare sfor reversal
        4.  IF (!root)   //root is null
            return;
    	
        5.  EnQueue(q,root); // EnQueue the root in the queue
    		
        6.  while(q is not empty){
                temp=DeQueue(q);  //Dequeue
                s.push(temp->data); //push temp->data to stack
                IF(temp->right)//this is different from ordinary level-order
                    EnQueue(q,temp->right); // if right child exists EnQueue
                END IF
                IF(temp->left)
                    EnQueue(q,temp->left); // if left child exists EnQueue
                END IF
            END While
        7.  While(s is not empty)
                Pop and print
            END While
        8.  DeleteQueue(q);
        9.  DeleteStack(s);
    
    
    

    Example with explanation:

    带有说明的示例:

    Reverse Level Order Traversal

    N.B: The nodes are represented by their respective values.

    注意:节点由它们各自的值表示。

    For the above example:

    对于以上示例:

    In the main we call reverseLevelOrder (2)
    ------------------------------------------------------------
    
    reverseLevelOrder (2)
    q.push(2)//EnQueue the root
    ------------------------------------------------------------
    
    1st iteration:
    q is not empty
    temp= q.front()=2
    q.pop()
    Queue status:
    Empty Queue
    s.push(temp->data) //2
    2->right not NULL
    q.push(2->right) //q.push(5)
    2->left not NULL
    q.push(2->left)//q.push(7)
    Queue status:
    5 7
    ------------------------------------------------------------
    
    2nd iteration:
    q is not empty
    temp= q.front()=5
    q.pop()
    Queue status:
    7
    s.push(temp->data) //5
    5->right not NULL
    q.push(5->right) //q.push(9)
    5->leftNULL
    Queue status:
    7 9
    ------------------------------------------------------------
    
    3rd iteration:
    q is not empty
    temp= q.front()=7
    q.pop()
    Queue status:
    9
    s.push(temp->data) //7
    7->right not NULL
    q.push(7->right) //q.push(6)
    7->left not NULL
    q.push(7->left) //q.push(2)
    Queue status:
    9 6 2
    ------------------------------------------------------------
    
    4th iteration:
    q is not empty
    temp= q.front()=9
    q.pop()
    Queue status:
    6 2
    s.push(temp->data) //9
    9->rightNULL
    9->left not NULL
    q.push(9->left) //q.push(4)
    Queue status:
    6 2 4
    ------------------------------------------------------------
    
    5th iteration:
    q is not empty
    temp= q.front()=6
    q.pop()
    Queue status:
    2 4
    s.push(temp->data) //6
    6->right not NULL
    q.push(6->right) //q.push(11)
    9->left not NULL
    q.push(6->left) //q.push(5)
    Queue status:
    2 4 11 5
    ------------------------------------------------------------
    
    6th iteration:
    q is not empty
    temp= q.front()=2
    q.pop()
    Queue status:
    4 11 5
    s.push(temp->data) //2
    2->rightNULL
    2->left  NULL
    Queue status:
    4 11 5
    ------------------------------------------------------------
    
    7th iteration:
    q is not empty
    temp= q.front()=4
    q.pop()
    Queue status:
    11 5
    s.push(temp->data) //4
    4->right NULL
    4->left   NULL
    Queue status:
    11 5
    ------------------------------------------------------------
    
    8th iteration:
    q is not empty
    temp= q.front()=11
    q.pop()
    Queue status:
    5
    s.push(temp->data) //11
    11->right NULL
    11->left   NULL
    Queue status:
    5
    ------------------------------------------------------------
    
    9th iteration:
    q is not empty
    temp= q.front()=5
    q.pop()
    Queue status:
    Empty queue
    s.push(temp->data) //5
    5->right NULL
    5->left   NULL
    Queue status:
    Empty Queue
    ------------------------------------------------------------
    
    10th iteration:
    Empty Queue
    
    Final stack status:
        5
        11
        4
        2
        6
        9
        7
        5
        2
    
    
    Pop and print:
    Output:
    5 11 4 2 6 9 7 5 2
    
    
    
    

    C++ implementation:

    C ++实现:

    #include <bits/stdc++.h>
    using namespace std;
    
    class Node{    // tree node is defined
    	public:
    	int data;
    	Node *left;
    	Node *right;
    };
    
    void reverseLevelOrder(Node *root)
    {
    	Node* temp;
    	stack<int> s;
    	queue<Node*> q;
    	q.push(root);
    	while(!q.empty()){
    		temp=q.front();
    		q.pop();
    		s.push(temp->data);
    		if(temp->right) 
    			q.push(temp->right);
    		if(temp->left)
    			q.push(temp->left);
    	}
    	while(!s.empty()){
    		cout<<s.top()<<" ";
    		s.pop();
    	}
    }
    
    Node* newnode(int data)  // creating new node
    { 
    	Node* node = (Node*)malloc(sizeof(Node)); 
    	node->data = data; 
    	node->left = NULL; 
    	node->right = NULL; 
    	return(node); 
    } 
    
    
    int main() { 
    	//**same tree is builted as shown in example**
    	Node *root=newnode(2); 
    	root->left= newnode(7); 
    	root->right= newnode(5); 
    	root->right->right=newnode(9);
    	root->right->right->left=newnode(4);
    	root->left->left=newnode(2); 
    	root->left->right=newnode(6);
    	root->left->right->left=newnode(5);
    	root->left->right->right=newnode(11);
    
    	cout<<"Reverse Level Order traversal of binary tree is :"<<endl; 
    	reverseLevelOrder(root); 
    
    	return 0; 
    }
    
    

    Output

    输出量

    Reverse Level Order traversal of binary tree is :
    5 11 4 2 6 9 7 5 2 
    
    
    

    翻译自: https://www.includehelp.com/icp/reverse-level-order-traversal.aspx

    反向遍历

    展开全文
  • map 反向遍历

    千次阅读 2018-08-31 11:39:33
    1、反向遍历:可以使用反向迭代器reverse_iterator反向遍历map映照容器中的数据,它需要rbegin()和rend()方法指出反向遍历的起始位置和终止位置。 #pragma warning(disable:4786) #include&lt;iostream&gt;...

    1、反向遍历:可以使用反向迭代器reverse_iterator反向遍历map映照容器中的数据,它需要rbegin()和rend()方法指出反向遍历的起始位置和终止位置。
    #pragma warning(disable:4786)
    #include<iostream> 
    #include<map>
    #include<string> 
    using namespace std; 
     
    int main() 

        map<int,char> m; 
        //插入元素,按照键值大小插入黑白树
        m[25]='m'; 
        m[28]='k'; 
        m[10]='x'; 
        m[30]='a'; 
        m.erase(28); 
             
        for(map<int,char>::reverse_iterator rit=m.rbegin();rit!=m.rend();rit++) 
        cout<<(*rit).first<<","<<(*rit).second<<endl;    
        return 0; 
        } 
    2、元素搜索:使用find()方法搜索某个键值,如果搜索到了,则返回该键值所在的迭代起位置否则,返回end()迭代器位置,由于map采用黑白树搜索,所以搜索速度极快。当然也可以用count()方法,但是需要如果想直接使用的话再使用键值搜索,需要两次查找,这时候就不如find功能好。

    程序代码:
    #pragma warning(disable:4786)
    #include<iostream> 
    #include<map>
    #include<string> 
    using namespace std; 
     
    int main() 

        map<int,char> m; 
        //插入元素,按照键值大小插入黑白树 
        m[25]='m'; 
        m[28]='k'; 
        m[10]='x'; 
        m[30]='a'; 

        map<int,char>::iterator it;
        it=m.find(28);
        if(it!=m.end())
              {
               cout<<(*it).first<<":"<<(*it).second<<endl;            
                }
        else cout<<"not find it"<<endl;  
        return 0; 
        }  

    展开全文
  • 反向遍历链表

    2020-02-23 11:59:18
    反向遍历链表,不改变链表结构。 利用栈的先进后出。 public static void reversePrint(HreoNode node){ if(node.next==null){ return; } //创建栈 Stack<HreoNode> stack = new Stack<HreoNode>...

    反向遍历链表,不改变链表结构。
    利用栈的先进后出。

    public static void reversePrint(HreoNode node){
        if(node.next==null){
            return; 
        }
        //创建栈
        Stack<HreoNode> stack = new Stack<HreoNode>();
        //遍历指针
        HreoNode temp = node.next;
        while(temp!=null){
            stack.push(temp);
            temp=temp.next;
        } 
        //打印栈中的数据
        while(stack.size()>0){
            System.out.println(stack.pop())
        }
    }
    
    展开全文
  • std::map 反向遍历

    2020-01-10 16:08:22
    1、反向遍历:可以使用反向迭代器reverse_iterator反向遍历map映照容器中的数据,它需要rbegin()和rend()方法指出反向遍历的起始位置和终止位置。 #pragma warning(disable:4786) #include<iostream> #include...
  • 反向遍历或者截取

    2020-06-24 17:19:25
    反向遍历元祖reversed() t=(1,'aa','哈') for i in reversed(t): print(i) 结果: 哈 aa 1 这里是引用 反向截取字符串 a='testfan' print(a[::-1]) 结果:naftset
  • map容器的反向遍历

    千次阅读 2015-11-01 23:26:25
    反向遍历:可以使用反向迭代器reverse_iterator反向遍历map容器中的数据,它需要rbegin()和rend()方法指出反向遍历的起始位置和终止位置。 #include  #include #include  using namespace std;    int ...
  • 积压订单中的订单总数》 时用到了map的反向遍历,看到问题时首先想到了优先队列,但是需要维护一个大根堆和一个小根堆,感觉操作起来比较麻烦,突发奇想使用map就能够解决。map本身就是有序的,正向遍历可以得到...
  • List遍历是我们经常会使用到的一个功能,很多时候我们也会用到反向遍历,在用到反向遍历时我们常用的方法是通过for循环或者是对List反向排序来完成相应的操作,像下面代码这样: 方法1: for(int i = list.size()-...
  • 我们通常情况下都是正向遍历一个列表,下面是一种简单的反向遍历一个列表的方式。 ## 正向遍历 >>>A = [9, 8, 7] >>>for index, a in enumerate(A): print(str(index) +' '+ str(a)) 0 9 1 8 2 ...
  • List逆向遍历、反向遍历--Iterator详解

    万次阅读 2017-12-26 20:26:58
    List逆向遍历、反向遍历–Iterator详解概述在使用java集合的时候,都需要使用Iterator。但是java集合中还有一个迭代器ListIterator,在使用List、ArrayList、LinkedList和Vector的时候可以使用。这两种迭代器有什么...
  • 反向遍历_12.3 遍历

    2021-01-12 18:05:01
    “DOM2 级遍历和范围”模块定义了两个用于辅助完成顺序遍历 DOM 结构的类型:NodeIterator 和 TreeWalker。这两个类型能够基于给定的起点对 DOM 结构执行深度优先(depth-first)的遍历操作。 在与 DOM 兼容的浏览器...
  • listIterator反向遍历学习笔记

    千次阅读 2015-05-11 23:06:41
    ListIterator接口有两个方法,可以用来反向遍历链表E previous() bollean hasPrevious()import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.ListIterator; public ...
  • TreeMap的 反向遍历

    万次阅读 2013-08-29 19:11:01
    今天写了一个程序 需要实现TreeMap的反向遍历,虽然有很多方法,但是发现treeSet有个 public Iterator descendingIterator() 返回在此 set 元素上按降序进行迭代的迭代器。 指定者: 接口 NavigableSet 中的 ...
  • QQueue的反向遍历小栗子

    千次阅读 2016-10-11 14:47:53
    可能因为某个具体的需求,需要对QQueue容器内的数据进行反向遍历,即从尾到头进行遍历。因对数据结构各种容器模板没有过多的见解,遂不献丑,相关问题不明白的自行查看相关文档或者百度。 下面是我写的一个小栗子:...
  • vector array; array.push_back( 1 ); array.push_back( 2 ); array.push_back( 3 );...for( vector::size_type i=array.size()-1;... --i ) // 反向遍历array数组 { cout << array[i] << endl...
  • } //遍历双向链表(反序) void ReTravelDLinkList(DLinkNode L) { printf("rn****************反向遍历******************************rn"); DLinkNode p=L; int length = DLinkListLength(L); for (int i = 0; ...
  • 反向遍历数组

    2019-07-25 15:26:18
    /*Recerse a number */ #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #define N 10 int main() { int a[N], i; printf("Enter %d number: ", N); for (i = 0;... scanf("%d", ...
  • 从尾到头打印单链表(反向遍历)思路代码实现(代码中的reversePrint方法) 思路 代码实现(代码中的reversePrint方法) import java.util.Scanner; import java.util.Stack; public class SingleLinkedListDemo...
  • 反向遍历删除(多线程) public static void main(String[] args) { ArrayList list = new ArrayList(); list.add("111"); list.add("222"); list.add("222"); list.add("333"); list.add("444"); list.add("333"); ...
  • “如何高效等反向遍历单链表” 一般情况下会想到一个很笨的方法:计算个数,然后再根据个数每一次将遍历的索引减一。 第二种方式就是将原链表反过来,再遍历。如果要求不改变原有结构,可以使用新建一个反向的链表...
  • 二叉树反向遍历

    千次阅读 2017-10-15 22:48:56
    //编写一道自下而上,从右至左的二叉树层次遍历 #include typedef struct BiTree() { int data; struct BiTree *lchild,*rchild; }BiTNode,*BiTree; void RelevelOrder(BiTree T) { InitStack(S); InitQueue...
  • 洛谷 P3916 图的遍历 菜鸟生成记(4) 只从被邻接矩阵的"爆栈"坑了一次后;我再也不用邻接矩阵了,只要与图有关,直接邻接表走起;这次的数据结构搭配还可以,但是算法又掉链子了;暴力超时T_T;(这时想起数据结构老师说的一...
  • LinkedHashMap 反向遍历

    千次阅读 2018-06-19 09:33:50
    import java.util.*; public class Test { public static void main(String[] args) { // Map&lt;String,Object&gt; hashMap = new HashMap&lt;&gt;(16); // for(int i=0;...// ...
  • 题目描述 给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。例如:给定二叉树[3,9,20,null,null,15,7],3/\920/\157返回锯齿形层序遍历如下...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,879
精华内容 751
关键字:

反向遍历