Skip to content

Home

Jump to bottom
CoderDream edited this page May 11, 2022 · 2 revisions

Welcome to the lagou-edu-101-datastructure wiki!

package com.example.demo.lagou;

/**
 * 功能描述
 *
 * @since 2022-05-09
 */
public class Test2 {
     static int a = 0 ;
     static {
         a = 1;
         b = 1;
     }
     static int b = 0;
 
     public static void main(String[] args) {
         System.out.println(a);
         System.out.println(b);
     }
}
// 输出
// 1
// 0
package com.example.demo.lagou;

import java.util.Stack;

/**
 * 功能描述 例 1，给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须与
 * 相同类型的右括号匹配，左括号必须以正确的顺序匹配。例如，{ [ ( ) ( ) ] } 是合法的，而 { ( [ ) ] } 是非法的。
 * 这个问题很显然是栈发挥价值的地方。原因是，在匹配括号是否合法时，左括号是从左到右依次出现，而右括号则
 * 需要按照“后进先出”的顺序依次与左括号匹配。因此，实现方案就是通过栈的进出来完成。
 * 具体为，从左到右顺序遍历字符串。当出现左括号时，压栈。当出现右括号时，出栈。并且判断当前右括号，和被
 * 出栈的左括号是否是互相匹配的一对。如果不是，则字符串非法。当遍历完成之后，如果栈为空。则合法。
 *
 * @since 2022-05-10
 */
public class StackDemo {
    public static void main(String[] args) {
        String a = "{[()()]}";
        String b= "{[)]}";
        System.out.println(isLegal(a));
        System.out.println(isLegal(b));
    }

    /**
     * 是否为左边的字符串
     * @param c 字符串
     * @return 判断结果
     */
    private static int isLeft(char c) {
        if(c == '{' || c == '(' || c == '[') {
            return 1;
        } else {
            return 2;
        }
    }

    /**
     * 是否配对
     * @param p 左边字符串
     * @param curr 当前字符串
     * @return 匹配结果
     */
    private static int isPair(char p, char curr) {
        if((p == '{' && curr == '}' ) || (p == '(' && curr == ')' ) || (p == '[' && curr == ']' )) {
            return 1;
        } else {
            return 0;
        }
    }

    /**
     * 是否合法
     * @param s 字符串
     * @return 是否合法
     */
    private static String isLegal(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char curr = s.charAt(i);
            if(isLeft(curr) == 1) {
                stack.push(curr);
            } else {
                if(stack.empty()) {
                    return "非法";
                }
                char p = stack.pop();
                if(isPair(p, curr) == 0) {
                    return "非法";
                }
            }
        }
        if(stack.empty()) {
            return "合法";
        } else {
            return "非法";
        }
    }
}
package com.example.demo.lagou;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 功能描述 给定一个包含 n 个元素的链表，现在要求每 k 个节点一组进行翻转，打印翻转后的链表结果。其中，k 是一个正整数，且 n 可被 k 整除。
 * 例如，链表为 1 -> 2 -> 3 -> 4 -> 5 -> 6，k = 3，则打印 321654。仍然是这道题，我们试试用栈来解决它吧。
 *
 * @since 2022-05-10
 */
public class StackDemo2 {
    public static void main(String[] args) {
        String source = "12345678";
        Integer k = 4;
        System.out.println(reverseGroup(source, k));
        String source2 = "123456";
        Integer k2 = 3;
        System.out.println(reverseGroup(source2, k2));
    }

    private static String reverseGroup(String source, Integer k) {
        //String source = "12345678";
        Integer n = source.length();
        //Integer k = 4;
        List<Stack<Character>> list = new ArrayList<>();
        int stackCount = 1;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            if (i >= k * (stackCount - 1) && i <= k * stackCount) {
                stack.push(source.charAt(i));
                if (i == (stackCount * k - 1)) {
                    Stack<Character> tempStack = new Stack<>();
                    tempStack.addAll(stack);
                    list.add(tempStack);
                    stackCount++;
                    stack.clear();
                }
            }
        }

        StringBuilder stringBuilder = new StringBuilder();

        for (Stack<Character> stack2 : list) {
            while (!stack2.isEmpty()) {
                // System.out.println();
                stringBuilder.append(stack2.pop());
            }
        }

        return stringBuilder.toString();
    }

}
package com.example.demo.lagou;

import java.util.LinkedList;

/**
 * 功能描述 我们来看一个关于用队列解决约瑟夫环问题。约瑟夫环是一个数学的应用问题，具体为，已知 n 个人（以编号 1，
 * 2，3...n 分别表示）围坐在一张圆桌周围。从编号为 k 的人开始报数，数到 m 的那个人出列；他的下一个人又从 1
 * 开始报数，数到 m 的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。这个问题的输入变量就是
 * n 和 m，即 n 个人和数到 m 的出列的人。输出的结果，就是 n 个人出列的顺序。
 * 这个问题，用队列的方法实现是个不错的选择。它的结果就是出列的顺序，恰好满足队列对处理顺序敏感的前提。
 * 因此，求解方式也是基于队列的先进先出原则。解法如下：
 * 1. 先把所有人都放入循环队列中。注意这个循环队列的长度要大于或者等于 n。
 * 2. 从第一个人开始依次出队列，出队列一次则计数变量 i 自增。如果 i 比 m 小，则还需要再入队列。
 * 3. 直到i等于 m 的人出队列时，就不用再让这个人进队列了。而是放入一个用来记录出队列顺序的数组中。
 * 4. 直到数完 n 个人为止。当队列为空时，则表示队列中的 n 个人都出队列了，这时结束队列循环，输出数组内
 * 记录的元素。
 *
 * @since 2022-05-10
 */
public class QueueDemo {
    public static void main(String[] args) {
        int k = 2;
        ring(10, 5, k);
    }

    /**
     *
     * @param n 人数
     * @param m 出列人的报数值
     */
    private static void ring(int n, int m, int k) {
        // 1. 先把所有人都放入循环队列中
        LinkedList<Integer> q = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            q.add(i);
        }

        // 2. 重新排序队列，循环遍历队列，把k前面的人放到队尾
        int element = 0;
        int i = 1;
        // 位置是否小于k
        for (; i < k; i++) {
            // 取出元素
            element = q.poll();
            // 放入队尾
            q.add(element);
        }
        // 报数器的初始值
        i = 1;
        // 如果队列不为空，继续循环遍历队列
        while (q.size() > 0) {
            // 取出队列第一个元素
            element = q.poll();
            // 报数值是否等于m
            if(i < m) {
                // 不等于则放入队尾
                q.add(element);
                i++;
            } else {
                // 等于则报数重置为1
                i = 1;
                // 打印出列的元素
                System.out.println(element);
            }
        }
    }
}
package com.example.demo.lagou;

import java.util.LinkedList;

/**
 * 功能描述 我们来看一个关于用队列解决约瑟夫环问题。约瑟夫环是一个数学的应用问题，具体为，已知 n 个人（以编号 1，
 * 2，3...n 分别表示）围坐在一张圆桌周围。从编号为 k 的人开始报数，数到 m 的那个人出列；他的下一个人又从 1
 * 开始报数，数到 m 的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。这个问题的输入变量就是
 * n 和 m，即 n 个人和数到 m 的出列的人。输出的结果，就是 n 个人出列的顺序。
 * 这个问题，用队列的方法实现是个不错的选择。它的结果就是出列的顺序，恰好满足队列对处理顺序敏感的前提。
 * 因此，求解方式也是基于队列的先进先出原则。解法如下：
 * 1. 先把所有人都放入循环队列中。注意这个循环队列的长度要大于或者等于 n。
 * 2. 从第一个人开始依次出队列，出队列一次则计数变量 i 自增。如果 i 比 m 小，则还需要再入队列。
 * 3. 直到i等于 m 的人出队列时，就不用再让这个人进队列了。而是放入一个用来记录出队列顺序的数组中。
 * 4. 直到数完 n 个人为止。当队列为空时，则表示队列中的 n 个人都出队列了，这时结束队列循环，输出数组内
 * 记录的元素。
 *
 * @since 2022-05-10
 */
public class HanioDemo {
    public static void main(String[] args) {
        String x = "x";
        String y = "y";
        String z = "z";
        haonio(3, x, y, z);
        //   ring(10, 5, k);
    }

    /**
     * 把 n 个盘子从 x 移动到 z
     *
     * 1. 把从小到大的 n-1 个盘子，从 x 移动到 y；
     * 2. 接着把最大的一个盘子，从 x 移动到 z；
     * 3. 再把从小到大的 n-1 个盘子，从 y 移动到 z。
     *
     * @param n 盘子树
     * @param x 柱子x
     * @param y 柱子y
     * @param z 柱子z
     */
    private static void haonio(int n, String x, String y, String z) {
        if (n < 1) {
            System.out.println("汉诺塔的层数不能小于1");
        } else if (n == 1) {
            System.out.println("移动：" + x + "->" + z);
        } else {
            // 1、移动x到y
            haonio(n - 1, x, z, y);
            // 2、x移动到z，自己打印，不用递归
            System.out.println("移动：" + x + "->" + z);
            // 3、移动y到z
            haonio(n - 1, y, x, z);
        }
    }
}








              


          



  
          

            


            
Clone this wiki locally