1 public class Test1120 {
 2 
 3     public static void main(String[] args) {
 4 
 5         int array[] = new int[]{3, 2, 1, 8, 9, 6, 7};
 6 
 7         selectSort(array);
 8         for (int element : array) {
 9             System.out.print(element + " ");
10         }
11     }
12 
13     private static void swap(int array[], int left, int right) {
14         int tmp = array[left];
15         array[left] = array[right];
16         array[right] = tmp;
17     }
18 
19     /**
20      * 逆序的冒泡
21      *
22      * @param array 数组
23      */
24     private static void bubbleSort(int array[]) {
25         for (int i = 0; i < array.length; i++) {
26             for (int j = array.length - 1; j > i; j--) {
27                 if (array[j] < array[j - 1]) {
28                     swap(array, j, j - 1);
29                 }
30             }
31         }
32     }
33 
34     /**
35      * 优化版的冒泡 如果某次遍历没有一个元素进行了交换，那么认为之后的均有序，提前剪枝
36      *
37      * @param array 数组
38      */
39     private static void bubbleSortV2(int array[]) {
40         boolean flag = true;
41         for (int i = 0; i < array.length && flag; i++) {
42             flag = false;
43             for (int j = array.length - 1; j > i; j--) {
44                 if (array[j] < array[j - 1]) {
45                     swap(array, j, j - 1);
46                     flag = true;
47                 }
48             }
49         }
50     }
51 
52     /**
53      * 选择排序
54      *
55      * @param array 数组
56      */
57     private static void selectSort(int array[]) {
58         //选择排序
59         int min;
60         for (int i = 0; i < array.length - 1; i++) {
61             min = i;
62             for (int j = i + 1; j < array.length; j++) {
63                 if (array[j] < array[min]) {
64                     min = j;
65                 }
66             }
67             if (min != i) {
68                 swap(array, min, i);
69             }
70         }
71     }
72 }

public class ZzTest {
    
    public static void main(String[] args) {
        int[] list = {34, 3, 53, 2, 23, 7, 14, 10, 10, 10};

        quickSort(list, 0, list.length - 1);

        for (int element : list) {
            System.out.print(element + " ");
        }
        System.out.println();
    }

    private static int getMiddle(int[] list, int low, int high) {
        int tmp = list[low];    //数组的第一个作为中轴
        while (low < high) {
            while (low < high && list[high] >= tmp) {
                high--;
            }
            list[low] = list[high];   //比中轴小的记录移到低端
            while (low < high && list[low] <= tmp) {
                low++;
            }
            list[high] = list[low];   //比中轴大的记录移到高端
        }
        list[low] = tmp;              //中轴记录到尾
        return low;                   //返回中轴的位置
    }

    private static void quickSort(int[] list, int low, int high) {
        if (low < high) {
            int middle = getMiddle(list, low, high);  //将list数组进行一分为二
            quickSort(list, low, middle - 1);        //对低字表进行递归排序
            quickSort(list, middle + 1, high);       //对高字表进行递归排序
        }
    }
}

/**
 * 堆排序演示
 *
 * @author Lvan
 */
public class HeapSort {
    public static void main(String[] args) {
//        int[] arr = {5, 1, 7, 3, 1, 6, 9, 4};
        int[] arr = {16, 7, 3, 20, 17, 8};

        heapSort(arr);

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }


    /**
     * 创建堆，
     * @param arr 待排序列
     */
    private static void heapSort(int[] arr) {
        //创建堆
        for (int i = (arr.length - 1) / 2; i >= 0; i--) {
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr, i, arr.length);
        }

        //调整堆结构+交换堆顶元素与末尾元素
        for (int i = arr.length - 1; i > 0; i--) {
            //将堆顶元素与末尾元素进行交换
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;

            //重新对堆进行调整
            adjustHeap(arr, 0, i);
        }
    }

    /**
     * 调整堆
     * @param arr 待排序列
     * @param parent 父节点
     * @param length 待排序列尾元素索引
     */
    private static void adjustHeap(int[] arr, int parent, int length) {
        //将temp作为父节点
        int temp = arr[parent];
        //左孩子
        int lChild = 2 * parent + 1;

        while (lChild < length) {
            //右孩子
            int rChild = lChild + 1;
            // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
            if (rChild < length && arr[lChild] < arr[rChild]) {
                lChild++;
            }

            // 如果父结点的值已经大于孩子结点的值，则直接结束
            if (temp >= arr[lChild]) {
                break;
            }

            // 把孩子结点的值赋给父结点
            arr[parent] = arr[lChild];

            //选取孩子结点的左孩子结点,继续向下筛选
            parent = lChild;
            lChild = 2 * lChild + 1;
        }
        arr[parent] = temp;
    }
}

 1 public class Test1120 {
 2 
 3     public static void main(String[] args) {
 4         int array[] = new int[]{1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
 5         int number1 = 11;
 6         int number2 = 14;
 7         int result1 = binarySearch(array, number1);
 8         int result2 = binarySearch(array, number2);
 9         System.out.println(result1);
10         System.out.println(result2);
11     }
12 
13     private static int binarySearch(int array[], int num) {
14         int l, r, mid;
15         l = 0;
16         r = array.length - 1;
17         int res = -1;
18 
19         while (l <= r) {
20 
21             mid = (l + r) / 2;
22             if (array[mid] > num) r = mid - 1;
23             else if (array[mid] < num) l = mid + 1;
24             else return mid + 1;
25         }
26         return res;
27     }
28 }

 1 public class Test1 {
 2     public static void main(String[] args) {
 3         Node head = new Node(0);
 4         Node node1 = new Node(1);
 5         Node node2 = new Node(2);
 6         Node node3 = new Node(3);
 7         head.setNext(node1);
 8         node1.setNext(node2);
 9         node2.setNext(node3);
10 
11         // 打印反转前的链表
12         Node h = head;
13         while (null != h) {
14             System.out.print(h.getData() + " ");
15             h = h.getNext();
16         }
17         // 调用反转方法
18 //        head = reverse1(head);
19         head = reverse2(head);
20 
21         System.out.println("\n**************************");
22         // 打印反转后的结果
23         while (null != head) {
24             System.out.print(head.getData() + " ");
25             head = head.getNext();
26         }
27     }
28 
29     /**
30      * 递归，在反转当前节点之前先反转后续节点
31      */
32     private static Node reverse1(Node head) {
33         // head看作是前一结点，head.getNext()是当前结点，reHead是反转后新链表的头结点
34         if (head == null || head.getNext() == null) {
35             return head;// 若为空链或者当前结点在尾结点，则直接还回
36         }
37         Node reHead = reverse1(head.getNext());// 先反转后续节点head.getNext()
38         head.getNext().setNext(head);// 将当前结点的指针域指向前一结点
39         head.setNext(null);// 前一结点的指针域令为null;
40         return reHead;// 反转后新链表的头结点
41     }
42 
43 
44     /**
45      * 遍历，将当前节点的下一个节点缓存后更改当前节点指针
46      */
47     private static Node reverse2(Node head) {
48         if (head == null) {
49             return null;
50         }
51         Node pre = head;// 上一结点
52         Node cur = head.getNext();// 当前结点
53         Node tmp;// 临时结点，用于保存当前结点的指针域（即下一结点）
54         while (cur != null) {// 当前结点为null，说明位于尾结点
55             tmp = cur.getNext();
56             cur.setNext(pre);// 反转指针域的指向
57 
58             // 指针往下移动
59             pre = cur;
60             cur = tmp;
61         }
62         // 最后将原链表的头节点的指针域置为null，还回新链表的头结点，即原链表的尾结点
63         head.setNext(null);
64 
65         return pre;
66     }
67 }
68 
69 class Node {
70     private int data;
71     private Node next;
72 
73     public Node(int Data) {
74         this.data = Data;
75     }
76 
77     public int getData() {
78         return data;
79     }
80 
81     public void setData(int Data) {
82         this.data = Data;
83     }
84 
85     public Node getNext() {
86         return next;
87     }
88 
89     public void setNext(Node Next) {
90         this.next = Next;
91     }
92 }

 1 class Node {
 2     Node next;
 3     int val;
 4 
 5     Node(int val) {
 6         this.val = val;
 7     }
 8 }
 9 
10 
11 public class Solution {
12     public static void main(String[] args) {
13         Node n1 = new Node(1);
14         Node n2 = new Node(2);
15         Node n3 = new Node(3);
16         Node n4 = new Node(4);
17         Node n5 = new Node(5);
18 
19         n1.next = n2;
20         n2.next = n3;
21         n3.next = n4;
22         n4.next = n5;
23         n5.next = n3;
24 
25         System.out.println(isCircle(n1));
26         System.out.println(isCircle2(n1));
27     }
28 
29     private static boolean isCircle(Node n) {
30         Node slow = n;
31         Node fast = n.next;
32 
33         while (fast != null) {
34             if (slow == fast) {
35                 return true;
36             }
37             slow = slow.next;
38             fast = fast.next.next;
39             if (fast == null) {
40                 return false;
41             }
42         }
43         return true;//元素只有一个，我们认为也算成环
44     }
45 
46     private static boolean isCircle2(Node n) {
47         HashSet<Node> hashSet = Sets.newHashSet();
48         while (n != null) {
49             if (hashSet.contains(n)) {
50                 return true;
51             } else {
52                 hashSet.add(n);
53             }
54             n = n.next;
55             if (n == null) {
56                 return false;
57             }
58         }
59         return true;
60     }
61 }

public static Node getEnterNode(Node head) {
        Node slow = head.getNextNode();
        Node fast = head.getNextNode().getNextNode();
        //找到交点
        while (slow != null && fast != null) {
            if (slow == fast) {
                break;
            }
            slow = slow.getNextNode();
            fast = fast.getNextNode().getNextNode();
        }
        //分别从头结点和交点出发,第一次相遇 则为环入口点
        Node no = head.getNextNode();
        slow = slow.getNextNode();
        while (slow != no) {
            no = no.getNextNode();
            slow = slow.getNextNode();
        }
        return no;
    }

  1 package com.balfish.hotel.zzAlgorithm;
  2 
  3 import com.google.common.collect.ImmutableMap;
  4 
  5 import java.util.Stack;
  6 import java.util.regex.Pattern;
  7 
  8 /**
  9  * 中缀表达式 -> 逆波兰表达式(后缀表达式) -> 计算结果
 10  * <p>
 11  * 仅为了说明算法的实现，我们假设操作数均为0-9，符号只有加减乘除和括号
 12  * <p>
 13  * Created by yhm on 2017/11/21 AM11:26.
 14  */
 15 public class Test1121 {
 16 
 17     /**
 18      * guava jar
 19      * 获得符号对应的优先级，我们假设只有'#', '+', '-', '*', '/', '(', ')'
 20      */
 21     private static final ImmutableMap<Character, Integer> map = ImmutableMap
 22             .<Character, Integer>builder()
 23             .put('#', 0) //初始栈
 24             .put('(', 1)
 25             .put('+', 2)
 26             .put('-', 2)
 27             .put('*', 3)
 28             .put('/', 3)
 29             .put(')', 4)
 30             .build();
 31 
 32     public static void main(String[] args) {
 33         System.out.println(middleToSuffixExpression("a + b * c + (d * e + f)*g"));
 34         System.out.println(middleToSuffixExpression("5 * (3 + 4) - 6 + 8/2"));
 35         System.out.println(calSuffixExpression(middleToSuffixExpression("5 * (3 + 4) - 6 + 8/2")));
 36     }
 37 
 38     /**
 39      * 中缀表达式转成后缀表达式
 40      * a + b*c + (d * e + f) * g -> abc*+de*f+g*+
 41      *
 42      * @param middle 中缀表达式
 43      * @return 后缀表达式
 44      */
 45     private static String middleToSuffixExpression(String middle) {
 46         MyStack<Character> charStack = new MyStack<>();
 47         StringBuilder stringBuilder = new StringBuilder();
 48         charStack.push('#');
 49 
 50         for (char c : middle.toCharArray()) {
 51             if (c == ' ') {
 52                 continue;
 53             }
 54 
 55             if (map.get(c) == null) { //不是操作符
 56                 stringBuilder.append(c);
 57                 continue;
 58             }
 59 
 60             if (c == '(') {
 61                 charStack.push(c);
 62             } else if (c == ')') {
 63                 while (true) {
 64                     Character peek = charStack.peek();
 65                     charStack.pop();
 66                     if (peek == '(') {
 67                         break;
 68                     }
 69                     stringBuilder.append(peek);
 70                 }
 71             } else {
 72                 while (true) {
 73                     Character peek = charStack.peek();
 74                     if (map.get(c) > map.get(peek)) {
 75                         charStack.push(c);
 76                         break;
 77                     }
 78                     // 栈顶优先级高,需要弹出
 79                     charStack.pop();
 80                     stringBuilder.append(peek);
 81                 }
 82             }
 83         }
 84 
 85         // 剩余的符号全部弹出
 86         while (true) {
 87             Character peek = charStack.peek();
 88             if (peek == '#') {
 89                 break;
 90             }
 91             charStack.pop();
 92             stringBuilder.append(peek);
 93         }
 94         return stringBuilder.toString();
 95     }
 96 
 97     /**
 98      * 计算后缀表达式
 99      *
100      * @param suffix 后缀表达式
101      * @return 结果，方便起见，我们假设结果为int不暴栈
102      */
103     private static Integer calSuffixExpression(String suffix) {
104         Stack<Integer> stack = new Stack<>();
105         for (char c : suffix.toCharArray()) {
106             if (Pattern.compile("[0-9]").matcher(String.valueOf(c)).matches()) {
107                 stack.push(c - '0');
108             } else {
109                 int second = stack.peek();
110                 stack.pop();
111                 int first = stack.peek();
112                 stack.pop();
113                 Integer tmp = cal(first, second, c);
114                 stack.push(tmp);
115             }
116         }
117         return stack.peek();
118     }
119 
120     private static Integer cal(int first, int second, char c) {
121         Integer ret = null;
122         switch (c) {
123             case '+':
124                 ret = first + second;
125                 break;
126             case '-':
127                 ret = first - second;
128                 break;
129             case '*':
130                 ret = first * second;
131                 break;
132             case '/':
133                 ret = first / second;
134                 break;
135         }
136         return ret;
137     }
138 }

#include <iostream>
#include <cstring>
#include <cstdio>
#include <stack>
using namespace std;
int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    while(cin >> n)
    {
        int flag=0;
        if (n==0)break;
        int temp=n;
        for(int i=0;i<temp-1;i++)
        {
            if(n%9==0)
            {
                flag=1;
                break;
            }
            n%=9;
            n=n*temp;
        }
        if(flag==1)cout << 9 << endl;
        else
        {
            if(n>9)n%=9;
            cout << n << endl;
        }
    }
    return 0;
}