第6章 线性数据结构

1、报数

算法分析

模拟
将链表看出循环数组，若该点叫到m则移出

时间复杂度

Java 代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main{
    static List<Integer> list = new ArrayList<Integer>();
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        for(int i = 0;i <= n - 1;i ++) list.add(i);
        int start = 0;
        while(list.size() != 1)
        {
            start = (start + m - 1) % list.size();
            list.remove(start);
        }
        System.out.println(list.get(0) + 1);
    }
}

2、敲7

算法分析

用队列模拟比链表模拟更加方便，直接，先将前m - 1个元素按顺序放到队尾，开始模拟，判断队头，若队头满足7的要求则扔掉，否则放进队尾

时间复杂度

Java 代码

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main{
    static Queue<String> q = new LinkedList<String>();
    static boolean check(int x)
    {
        if(x % 7 == 0) return true;
        while(x > 0)
        {
            if(x % 10 == 7) return true;
            x /= 10;
        }
        return false;
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int num = scan.nextInt();
        for(int i = 0;i <= n - 1;i ++)
        {
            q.add(scan.next());
        }
        for(int i = 0;i < m - 1;i ++) 
        {
            q.add(q.poll());
        }
        while(q.size() != 1)
        {
            if(check(num)) 
            {
                q.poll();
            }
            else q.add(q.poll());
            num ++;
        }
        System.out.println(q.poll());
    }
}

3、括号匹配

算法分析

使用了栈的数据结构，需要用Pair结构体来记录某个字符对应的位置编号id，枚举每个字符

• 1、若栈为空，或者和栈顶元素不匹配，则把该字符添加到栈中
• 2、若匹配，则将栈顶元素pop出，且记录两个匹配字符的编号

时间复杂度

Java 代码

import java.util.Scanner;
import java.util.Stack;

public class Main{
    static int N = 50010;
    static Stack<Pair> stack = new Stack<Pair>();
    static char[] temp = new char[N];
    static String[] ans = new String[N];
    static int k = 0;
    static int len = 0;
    //判断是否匹配
    static boolean look(char a,char b)
    {
        if(a == '(' && b == ')') return true;
        return false;
    }
    static boolean check()
    {
        for(int i = 1;i <= len;i ++)
        {
            if(stack.isEmpty() || !look(stack.peek().c,temp[i]))
            {
                stack.add(new Pair(i,temp[i]));
            }
            else
            {
                ans[k ++] = stack.peek().id + " " + i;
                stack.pop();
            }
        }
        if(stack.isEmpty()) return true;
        return false;
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        char[] charArray = scan.next().toCharArray();
        len = charArray.length;
        for(int i = 1;i <= len;i ++) temp[i] = charArray[i - 1];
        if(!check()) System.out.println("No");
        else 
        {
            System.out.println("Yes");
            for(int i = 0;i < k;i ++) System.out.println(ans[i]);
        }
    }
}
class Pair
{
    int id;
    char c;
    Pair(int id,char c)
    {
        this.id = id;
        this.c = c;
    }
}

import java.util.Scanner;
import java.util.Stack;

public class Main {
    static int N = 50000;
    static Stack<Integer> s2 = new Stack<Integer>();
    static Stack<Character> s1 = new Stack<Character>();
    static int[] ans1 = new int[N];
    static int[] ans2 = new int[N];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String s = scan.next().trim();
        int n = s.length();
        s = " " + s;
        int cnt = 0;
        for(int i = 1;i <= n;i ++)
        {
            if(s1.isEmpty() || s.charAt(i) == '(')
            {
                s1.add(s.charAt(i));
                s2.add(i);
            }
            
            else
            {
                if(s1.peek() == '(')
                {
                    ans1[cnt] = s2.peek();
                    ans2[cnt] = i;
                    cnt ++;
                    
                    s1.pop();
                    s2.pop();
                }
                else 
                {
                    s1.add(s.charAt(i));
                    s2.add(i);
                }
            }
        }
        
        if(!s1.isEmpty()) System.out.println("No");
        else 
        {
            System.out.println("Yes");
            for(int i = 0;i < cnt;i ++)
            {
                System.out.println(ans1[i] + " " + ans2[i]);
            }
        }
    }
}

4、网页跳转

算法分析

类似编辑器的题目，开2个栈，假设左边是s1栈，右边是s2栈

• 1、visit操作：将visit的页面放进s1栈，并输出s1栈顶，清空s2栈
• 2、back操作：将s1栈的元素放在s2栈中，输出s1栈顶
• 3、foword操作：将s2栈的元素放在s1栈中，输出s1栈顶

时间复杂度

Java 代码

编辑器

import java.util.Scanner;
import java.util.Stack;

public class Main{
    static Stack<String> s1 = new Stack<String>();
    static Stack<String> s2 = new Stack<String>();
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        while(n -- > 0)
        {
            String s = scan.next();
            if(s.equals("VISIT"))
            {
                String address = scan.next();
                s1.add(address);
                System.out.println(s1.peek());
                s2.clear();//清空s2栈
            }
            else if(s.equals("FORWARD"))
            {
                if(s2.isEmpty()) System.out.println("Ignore");
                else 
                {
                    s1.add(s2.pop());
                    System.out.println(s1.peek());
                }
            }
            else
            {
                if(s1.size() <= 1) System.out.println("Ignore");
                else 
                {
                    s2.add(s1.pop());
                    System.out.println(s1.peek());
                }
            }
        }
    }
}