NOWCODER 练习

构造回文序列

给定正整数数组, 向其中插入整数, 使其构成回文序列, 并且构成的回文序列的元素之和最小

题目和解析地址

a = [1, 2, 3, 1, 2]，插入两个1，构成 b = [1, 2, 1, 3, 1, 2, 1]，构成的和最小，为11，且是回文序列

思路：

​ 找出原始序列中元素和最大的回文子序列，这样在补全回文序列的时候只需补充剩下的就行了

​ 原始数组的和sum, sum*2 - 最大的回文子序列的和

import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        String[] strs = in.nextLine().split(" ");
        int[] a = new int[n];
        int sum = 0;  // 原始序列的和
        for (int i = 0;i < n;i ++) {
            a[i] = Integer.parseInt(strs[i]);
            sum += a[i];
        }

        long[][] dp = new long[n][n];
        for(int i = a.length-1;i >= 0;i --) {
            dp[i][i] = a[i];
//             找出a[i]..a[j] 之间有最大和的回文序列, dp[i][j] 表示回文子序列最大和
            for(int j = i + 1;j < a.length; j ++) {
                if(a[i] == a[j]) dp[i][j] = dp[i+1][j-1] + a[i] * 2;
                else dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }

        System.out.println(2 * sum - dp[0][n-1]);
    }
}

每一层的比较都是在上一层的基础之上的

Unix 风格的路径简化

符号	意义
..	上一层目录
.	本层目录
/	只有一个/表示根目录; 还可用于表示分隔符如: //a////b == /a/b == /a/b/
/a/b	根目录下的a路径下的b路径

思路:

​ 利用栈来解决这个问题, 因为出入都是从一端。

package nowCoder;

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

public class path_reduce {
    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        String origin = new String();
        origin = scan.nextLine();

        String simplePath = "";
        Stack<String> stack = new Stack<String>();

        for(int i = 0;i < origin.length(); i ++) {
            String name = "";

//            去除 //的情况
            while(i < origin.length()  && origin.charAt(i) == '/')
                i ++;
//            找到 文件夹名字 a 或者 .
            while(i < origin.length() && origin.charAt(i) != '/')
                name += origin.charAt(i++);
//            正常文件夹名入栈, 还要要剔除为空的情况
            if(!name.equals(".") && !name.equals("..") && !name.equals("")) {
                stack.push(name);
            }
//            .. 出栈
            if(!stack.isEmpty() && name.equals("..")) {
                stack.pop();
            }
        }
        if(stack.isEmpty()) {
            System.out.print("/");
        }
        while(!stack.isEmpty()) {
            simplePath = "/" + stack.pop() + simplePath;
        }
        System.out.println(simplePath);
    }
}

求和

2020.3.15

时隔两周，其中搞了一周的数学建模，还是没有拉下，这周做了四道题， 三道都特别简单，觉得这道还行，记录一下。人工智能这个课真难😭

输入两个整数 n 和 m，从数列1，2，3…….n 中随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来

输入描述:

每个测试输入包含2个整数,n和m

输出描述:

按每个组合的字典序排列输出,每行输出一种组合

输入例子1:

5 5

输出例子1:

1 42 35

思路：

​ 由于是有序的， 可以利用深度优先（DFS）搜索来找的和为m的序列

CODE:

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

public class Sum {
    private static Stack<Integer> stack = new Stack<Integer>();
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        DFS(m, n, 1);
    }
    public static void DFS(int m, int n, int beg) {
//        当m == 0 的时候表示此时栈中的和为原始的m
        if(m == 0) {
            for (int i = 0; i < stack.size(); i ++)
                System.out.print(stack.get(i)+" ");
            System.out.println();
        }

//        当 beg > m 的时候也不会执行循环
        for(int i = beg;i <= n && i <= m;i ++) {
            stack.push(i);
            DFS(m-i, n, i+1);
            stack.pop();
        }
        return;
    }
}

拓展思考：

当给我们的不是连续的整数，而是一个随机的序列，让我们找的其中的和为某一值的组合。

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

public class SumSuper {
    private static Stack<Integer> stack = new Stack<Integer>();
    static int[] origin;
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        String[] s = in.nextLine().split(" ");
        int m = in.nextInt();

        origin = new int[s.length];
        for(int i = 0; i<s.length; i++){
            origin[i] = Integer.parseInt(s[i]);
        }
        Arrays.sort(origin);

        DFS(m, origin.length-1, 0);
    }

    public static void DFS(int m, int n, int beg) {
//        当m == 0 的时候表示此时栈中的和为原始的m
        if(m == 0) {
            for (int i = 0; i < stack.size(); i ++)
                System.out.print(stack.get(i)+" ");
            System.out.println();
        }

//        当 origin[i] > m 即 从这个元素开始数组里剩下的元素都比当前的m大, 再加就超了
        for(int i = beg;i <= n && origin[i] <= m;i ++) {
            stack.push(origin[i]);
            DFS(m-origin[i], n, i+1);
            stack.pop();
        }
        return;
    }
}

链表反向转化数组

将一个链表反向转化为一个数组.

看了大神的代码, 真的是递归太厉害了

思路:

1. 创建数组全局变量 ArrayList
 2. 对链表进行递归, 每一次递归首先判断是否为空, 先递归, 再添加
 3. 最后完成的就是递归到链表的最后一个并将其先添加到数组里面

拓展: 利用链表求距离尾指针距离为K的节点, 时间复杂度为O(n)

import java.util.Scanner;

class ListNode {
    int m_nKey;
    ListNode m_pNext;
    ListNode(int m_nKey) {
        this.m_nKey = m_nKey;
    }
}

public class Main {
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int k = sc.nextInt();
        // 创建链表
        ListNode listnode1 = new ListNode(1);
        ListNode listnode = listnode1;
        for(int i = 2;i <= 7;i ++) {
            listnode1.m_pNext = new ListNode(i);
            listnode1 = listnode1.m_pNext;
        }
        // 首先确定两个指针的距离, 让后让其同时后移
        ListNode p = listnode;
        ListNode q = listnode;
        while(k-- > 0) {
            p = p.m_pNext;
        }
        while(p != null) {
            p = p.m_pNext;
            q = q.m_pNext;
        }
        System.out.println(q.m_nKey);
    }
}

重建二叉树

根据给定的前序遍历和中序遍历重建二叉树

思路:

​ 根据前序遍历确定首节点, 在中序遍历中找到首节点, 其左侧为左分支, 右侧为右分支.

​ 前序遍历除首节点外截取做分支相同的长度 则是左分支的前序遍历, 左分支则为中序遍历。

​ 右分支同理，则可以形成递归。

import java.util.Arrays;

public class 二叉树重建 {
    public static int[] pre = {1,2,4,7,3,5,6,8};
    public static int[] in = {4,7,2,1,5,3,8,6};

    public static void main(String args[]) {
        reConstructBinaryTree(pre, in);
    }
    public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length == 0) return null;
        if(pre.length == 1) return new TreeNode(pre[0]);

        TreeNode first = new TreeNode(pre[0]);
        int i = 0;
        for(; i < in.length;i ++) {
            if(in[i] == pre[0]) break;
        }
        System.out.println(i);

        first.left = reConstructBinaryTree(
                Arrays.copyOfRange(pre, 1, i+1), 
                Arrays.copyOfRange(in, 0, i));

        first.right = reConstructBinaryTree(
                Arrays.copyOfRange(pre, i+1, pre.length), 
                Arrays.copyOfRange(in, i+1, in.length));

        return first;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { 
        val = x; 
    }
}

进阶

• 根据层序遍历和中序遍历重构二叉树

/**
 * 1. 开始的层序遍历的首节点一定是根节点
 * 2. 根据根节点分为左右子树的中序遍历
 * 3. 在层序遍历中查找分别属于左右子树的元素, 
 *         元素的相对位置不变, 分别得到左右子树的层序遍历
 * 4. 形成递归
 */
import java.util.*;

public class 重建二叉树pro {
    public static void main(String args[]) {
        // 读取层序和中序
        Scanner cin = new Scanner(System.in);

        String [] mid = cin.nextLine().split(" ");
        ArrayList<Integer> level = new ArrayList(); 
        for(int i = 0;i < mid.length;i ++) {
            level.add(Integer.parseInt(mid[i]));
        }

        mid = cin.nextLine().split(" ");
        ArrayList<Integer> in = new ArrayList(); 
        for(int i = 0;i < mid.length;i ++) {
            in.add(Integer.parseInt(mid[i]));
        }
        // 执行函数
        TreeNode root = reConstructBinaryTree(level, in);
        System.out.println();

        preOrder(root);
        System.out.println();

        postOrder(root);
    }
    // 重构二叉树
    public static TreeNode reConstructBinaryTree(ArrayList<Integer> level, ArrayList<Integer> in) {
        if(level.size() == 0) return null;
        if(level.size()  == 1) {
            // 输出叶子节点
            System.out.print(level.get(0)+" ");
            return new TreeNode(level.get(0));
        }

        TreeNode first = new TreeNode(level.get(0));
        int index = in.indexOf(level.get(0));
        ArrayList<Integer> in_left = new ArrayList<Integer>(in.subList(0, index));
        ArrayList<Integer> in_right = new ArrayList<Integer>(in.subList(index+1,in.size()));

        ArrayList<Integer> level_left = new ArrayList(); 
        ArrayList<Integer> level_right = new ArrayList(); 

        // 找到左右子树的层序遍历
        for(Integer each: level) {
            if(in_left.contains(each)) level_left.add(each);
        }
        for(Integer each: level) {
            if(in_right.contains(each)) level_right.add(each);
        }

        // 形成递归
        first.left = reConstructBinaryTree(level_left, in_left);
        first.right = reConstructBinaryTree(level_right, in_right);

        return first;
    }

    public static void preOrder(TreeNode root) {
        if(root == null) return;

        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    public static void postOrder(TreeNode root) {
        if(root == null) return;

        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

将满二叉树转换为求和树 链接

​ 输入前序和中序遍历，输出求和数的中序遍历

二叉树：
10
/
-2 6
/ \ / \
8 -4 7 5

求和树：
20(4-2+12+6)
/
4(8-4) 12(7+5)
/ \ / \
0 0 0 0

public class 求和树 {
    static TreeNode root;
    public static void main(String args[]) {
        //读取遍历序列
        //。。。。。

        // 重建
        root = 二叉树重建.reConstructBinaryTree(pre, in);
        sumTree(root);
        inOrder(root);
    }

    // 每个节点的值为其左右子树的和
    public static int sumTree(TreeNode root) {
        // 叶子节点的左右节点返回0
        if(root == null) {
            return 0;
        }

        // 需要先将节点原始的值存起来, 因为返回上一级的时候, 
        // 还需要加上本节点之前的值
        int val = root.val;
        // 先对本节点进行修改
        root.val = sumTree(root.left) + sumTree(root.right); 

        // 返回本节点此时的值和之前的值的和
        return root.val + val;
    }
    public static void inOrder(TreeNode root) {
        if(root == null) return;
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
}

用两个栈实现队列

过于简单, 直接放代码

package 用两个栈实现队列;

import java.util.Stack;

/**
 * @author writing
 *    题目描述
 *    用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
 */
public class Myqueue {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

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

    public int pop() {
        while(!stack1.isEmpty()) {
            int a = stack1.pop();
            stack2.push(a);
        }
        int first = stack2.pop();
        while(!stack2.isEmpty()) {
            int a = stack2.pop();
            stack1.add(a);
        }
        return first;
    }
}

进阶

最小栈:

​ 设计一个栈，可以进行返回最小值min, push入栈，pop出栈，且算法的时间复杂度均为O(1)。

思路：

​ 难点在于最小值的时间复杂度为O(1)。利用两个栈，A用来存值，B用来存与A相对应位置之前的最小值

code:

class MyStack {
    Stack<Integer> stack = new Stack<Integer>();
    Stack<Integer> minstack = new Stack<Integer>();

    public void push(int e) {
        stack.push(e);
        if(minstack.isEmpty() || minstack.peek() > e) minstack.push(e);
        else minstack.push(minstack.peek());
    }

    public int pop() {
        minstack.pop();
        return stack.pop();
    }
    public int Min() {
        return minstack.peek();
    }
}

不幸的是这样写还是超时, 不过我看了有用c++这么写通过的，于是乎，感觉应该是语言太慢了，建议用c++尝试。