1 二维数组中的查找
public class Solution {
public boolean Find(int target, int [][] array) {
if (array.length == 0) {
return false;
}
int len1 = array.length;//求行
int len2 = array[0].length;//求列
for (int j = len2 - 1; j >= 0; j--) {
for (int i = 0; i <= len1 - 1; i++) {
if (target < array[i][j]) {
break;
}else if (target > array[i][j]) {
continue;
}else {
return true;
}
}
}
return false;
}
}
2 替换字符串
public class Solution {
public String replaceSpace(StringBuffer str) {
if (str == null) {
return null;
}
/*
if (str.length() == 0) {//出错
return null;
}
*/
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c == ' ') {
str.replace(i,i+1,"%20");
}
}
return str.toString();
}
}
3 从尾到头打印链表
import java.util.Stack;//注意添加包
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if (listNode == null) {
ArrayList<Integer> list = new ArrayList<>();
return list;
}
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;
}
}
4 重建二叉树
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.util.*;
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre.length == 0||in.length == 0){
return null;
}
TreeNode node = new TreeNode(pre[0]);
for(int i = 0; i < in.length; i++){
if(pre[0] == in[i]){
node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));
node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1,in.length));
}
}
return node;
}
}
5 两个栈实现队列
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if (stack2.isEmpty()) {//只有当stack2为空时才一次性将stack1中的数据全部压入
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
6 旋转数组的最小数字
//二分查找
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if (array.length == 0) {
return 0;
}
int low = 0;
int high = array.length - 1;
while (low < high) {
int mid = (low + high) / 2;
if (array[mid] > array[high]) {//注意是拿mid和high比
low = mid + 1;
}else if (array[mid] < array[high]) {
high = mid;
}else {
high -= 1;
}
}
return array[low];
}
}
7 斐波那契数列
//1,1,2,3,5,8,13,21
public class Solution {
public int Fibonacci(int n) {
if (n == 0) {
return 0;
}
int a = 1, b = 1, c = 0;
if (n == 1 || n == 2) {
return 1;
}else {
for (int i = 3; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
}
return c;
}
}
8 跳台阶
//变版斐波那契数列:1,2,3,5,8,13,21
//当前台阶的跳法总数=当前台阶后退一阶的台阶的跳法总数+当前台阶后退二阶的台阶的跳法总数
//n级=n-1级的每个方法后面添上1，n-2级的每个方法后面填上2
public class Solution {
public int JumpFloor(int target) {
if (target <= 0) {
return 0;
}
if (target == 1) {
return 1;
}
if (target == 2) {
return 2;
}
int a = 1;
int b = 2;
int c = 0;
for (int i = 3; i <= target; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
}
9 变态跳台阶
//n = 之前所以方法的和再加1,
//1,2,4,8,16,32
public class Solution {
public int JumpFloorII(int target) {
if (target <= 0) {
return 0;
}
if (target == 1) {
return 1;
}
if (target == 2) {
return 2;
}
int sum = 3;
int c = 0;
for (int i = 3; i <= target; i++) {
sum = sum + c;
c = sum + 1;
}
return c;
}
}
10 矩形覆盖
//变斐波那契:1,2,3,5,8,13,21；同跳台阶
public class Solution {
public int RectCover(int target) {
if (target <= 0) {
return 0;
}
if (target == 1) {
return 1;
}
if (target == 2) {
return 2;
}
int a = 1;
int b = 2;
int c = 0;
for (int i = 3; i <= target; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
}
