剑指Offer在线编程题解析（167）

  • Z时代
  • 2024-01-10
  • 分类：综合

编程

0.公共数据结构代码

// 链表结构  多个问题中使用到该结构
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
// 带有随机指针的链表
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;
    RandomListNode(int label) {
        this.label = label;
    }
    @Override
    public String toString() {
        final StringBuffer sb = new StringBuffer("RandomListNode{");
        if (this!=null){
            sb.append("label=").append(label);
//            sb.append(", next=").append(next.label);
//            sb.append(", random=").append(random.label);
            sb.append("}");
        }else {
            sb.append("NULL}");
        }
        return sb.toString();
    }
}
// 带有头指针的二叉树
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;
    TreeLinkNode(int val) {
        this.val = val;
    }
}
// 多个Solutions 中使用的二叉树结构
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
    @Override
    public String toString() {
        final StringBuffer sb = new StringBuffer("TreeNode{");
        sb.append("val=").append(val);
        sb.append(", left=").append(left);
        sb.append(", right=").append(right);
        sb.append("}");
        return sb.toString();
    }
    public static void xxbl(TreeNode tn){
        System.out.print(tn.val);
        if (tn.left!=null){
            xxbl(tn.left);
        }
        if (tn.right!=null){
            xxbl(tn.right);
        }
    }
}

public class TreeNodeUtil {
    public static TreeNode add(TreeNode treeNode,int value){
        return treeNode;
    }
}

01. 二维数组中的查找

  • 题目描述

    • 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数， 判断数组中是否含有该整数。

  • https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e

/**
 * Solution01_FindIn2DArray :
 * 
 */
public class Solution01_FindIn2DArray {
    public boolean Find(int target, int [][] array) {
        boolean flag=false;
        for(int i=0;i<array.length;i++){
            for(int j=0;j<array[i].length;j++){
                if(target==array[i][j]){
                    flag=true;
                }
            }
        }
        return flag;
    }
}

02.替换空格

  • https://www.nowcoder.com/practice/4060ac7e3e404ad1a894ef3e17650423

  • 题目描述

    • 请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

  • Solution02_ReplaceBlank :

public class Solution02_ReplaceBlank {
    static StringBuffer sb = new StringBuffer("We Are Happy");
    public static  String replaceSpace(StringBuffer str) {
        if (str.length()==0){
            return str.toString();
        }else {
            StringBuffer newSb=new StringBuffer();
            for (int i = 0; i <str.length() ; i++) {
                if (str.toString().charAt(i)==" "){
                    newSb.append("%20");
                }else {
                    newSb.append(str.toString().charAt(i));
                }
            }
            return newSb.toString();
        }
    }
    public static void main(String[] args) {
        System.out.println(replaceSpace(sb));
    }
}

03.从尾到头打印链表

  • https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035

  • 题目描述

    • 输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

import java.util.ArrayList;
import java.util.Stack;
public class Solution03_PrintListFromTailToHead {
    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> sta1=new Stack<Integer>();
        ArrayList<Integer> arr=new ArrayList<Integer>();
        if(listNode==null){
            //System.out.println("输入链表为空链表");
            return arr;
        }
        while(listNode!=null){
            sta1.push(listNode.val);
            System.out.println("val="+listNode.val);
            listNode=listNode.next;
        }
        int size=sta1.size();//获取stack的size
        //注意sta1.size 是变化的
        //for(int i=0;i<=(sta1.size()+2);i++){
        for(int i=0;i<size;i++){
            System.out.println("i="+i+"  sta1.size="+sta1.size());
            arr.add(sta1.pop());
            System.out.println("i="+i+"   arr.size="+arr.size());
        }
        System.out.println(arr.size());
        return arr;
    }
    //{67,0,24,58}
    public static void main(String[] args) {
        ListNode listNode=new ListNode(67);
        listNode.next=new ListNode(0);
        listNode.next.next=new ListNode(24);
        listNode.next.next.next=new ListNode(58);
        ArrayList<Integer> a=printListFromTailToHead(listNode);
        System.out.println(a);
    }
}

以上是 剑指Offer在线编程题解析（167） 的全部内容， 来源链接： utcz.com/z/517689.html

回到顶部