剑指offer1-3

1.二维数组中的查找

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

代码

public class FindElementInArray { public static boolean Find(int target, int [][] array){ int i = array.length-1; int j = 0; while(i>=0 && j<array[0].length){ if(target < array[i][j]){ i--;//比目标数大往左走 } else if(target > array[i][j]){ j++;//比目标数小往下走 } else if(target == array[i][j]){ return true; } } return false; } public static void main(String[] args) { int target = 6; int [][] array = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}}; System.out.println(Find(target, array)); } }

2.替换空格

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

代码

import java.lang.StringBuffer; public class replaceSpace { public static String Replace(String str){ if(str == null){ return null; } StringBuilder newstr = new StringBuilder(); //length是一种属性，length一般指数组的长度，length()指的是数组中某个元素的字符串长度 for(int i=0; i<str.length(); i++){ if(str.charAt(i) == ' '){ newstr.append('%'); newstr.append('2'); newstr.append('0'); } else{ newstr.append(str.charAt(i)); } } return newstr.toString(); } public static void main(String[] args) { String str = "we are happy"; System.out.println(Replace(str)); } }

3.从尾到头打印链表

题目：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

代码

import java.util.ArrayList; import java.util.Stack; // 创建链表 class ListNode{ int val; ListNode next; ListNode(int val){ this.val=val; this.next=null; } } // 利用栈先进后出工作原理 public class printListFromTailToHead { public static ArrayList<Integer> printList(ListNode listNode){ Stack<Integer> stack = new Stack<>(); while(listNode != null){ stack.push(listNode.val);//进栈 listNode = listNode.next; } ArrayList<Integer> list = new ArrayList<>(); while(!stack.isEmpty()){ list.add(stack.pop());//出栈 } return list; } //将数组转化为链表 private static ListNode buildListNode(int[] ls){ ListNode first = null, last = null, newNode; if(ls.length > 0){ for(int i=0; i<ls.length; i++){ newNode = new ListNode(ls[i]); newNode.next = null; if(first == null){ first = newNode; last = newNode; }else{ last.next = newNode; last = newNode; } } } return first; } public static void main(String[] args) { int[] ls = new int[] {1,2,4,5,3,8,9}; ListNode listNode = buildListNode(ls); System.out.println(printList(listNode)); } }