数组
二维数组中的查找
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
该二维数组中的一个数,小于它的数一定在其左边,大于它的数一定在其下边。因此,从右上角开始查找,就可以根据 target 和当前元素的大小关系来缩小查找区间,当前元素的查找区间为左下角的所有元素。
public class Solution {
public static boolean Find(int target, int [][] array) {
for (int[] ints : array) {
for (int j = array[0].length - 1; j >= 0; j--) {
if (target == ints[j]) {
return true;
} else if (target > ints[j]) {
break;
}
}
}
return false;
}
}
第二道
......
数组笔记
1. 二维数组中,array.length指多少行,array[0].length指多少列
字符串
替换空格
请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
在字符串尾部填充任意字符,使得字符串的长度等于替换之后的长度。因为一个空格要替换成三个字符(%20),因此当遍历到一个空格时,需要在尾部填充两个任意字符。
令 P1 指向字符串原来的末尾位置,P2 指向字符串现在的末尾位置。P1 和 P2 从后向前遍历,当 P1 遍历到一个空格时,就需要令 P2 指向的位置依次填充 02%(注意是逆序的),否则就填充上 P1 指向字符的值。
从后向前遍是为了在改变 P2 所指向的内容时,不会影响到 P1 遍历原来字符串的内容。
public static String replaceSpace(StringBuffer str) {
char c = ' ';
int p1 = str.length() - 1;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == c) {
str.append("aa");
}
}
int p2 = str.length() - 1;
while (p1 >= 0) {
if (str.charAt(p1) == c) {
str.setCharAt(p2--, '0');
str.setCharAt(p2--, '2');
str.setCharAt(p2--, '%');
} else {
str.setCharAt(p2--, str.charAt(p1));
}
p1--;
}
return str.toString();
}
第二道
......
字符串笔记
1. StringBuffer会预留额外空间,因此length和capacity的值是不一样的,不要写错了
链表
从尾到头打印链表
输入一个链表,按链表从尾到头的顺序返回一个ArrayList。
递归法
要逆序打印链表 1->2->3(3,2,1),可以先逆序打印链表 2->3(3,2),最后再打印第一个节点 1。而链表 2->3 可以看成一个新的链表,要逆序打印该链表可以继续使用求解函数,也就是在求解函数中调用自己,这就是递归函数。
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> arrayList = new ArrayList<>();
if (listNode != null) {
arrayList.addAll(printListFromTailToHead(listNode.next));
arrayList.add(listNode.val);
}
return arrayList;
}
}
第二道
...
链表笔记
1. arrayList的add方法插入单个元素,addAll插入一个集合,都是从前往后顺序插入
2. 递归递归,有递也要有归,整个判断条件,告诉程序什么时候开始归
待更新...
Q.E.D.