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;
}
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;
}
}
11 二进制中1的个数
//一个数减去1再和这个数做位与运算，结果是将这个数 最 右边的那位1置0.一直操作直到这个数为0，这样有几个1就操作几次
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while (n != 0) {//java中必须为boolean表达式
count++;
n = (n - 1) & n;
}
return count;
}
}
12 数值的整数次方
import java.util.*;
public class Solution {
public double Power(double base, int exponent) {
if (base ==0.0 & exponent < 0) {//如果底数为0，且指数为负数，需要取倒数，但0不能做分母。
return 0.0;
}
int abs = Math.abs(exponent);//取绝对值
double result = pow(base, abs);//求指数为绝对值时的结果
if (exponent < 0) {
return 1 / result;
}
return result;
}
public double pow(double base, int abs) {
if (abs == 0) {//绝对值为0，返回1.0
return 1.0;
}
if (abs == 1) {//绝对值为1，返回底数
return base;
}
double re = pow(base,abs >> 1);
re *= re;
if ((abs & 1) == 1) {//奇数要多乘个base,
return re *= base;
}
return re;
}
}
13 奇数位于偶数前
//快排，不能保证相对位置不变。
//low奇数，low向后走直到遇到偶数。
//high是偶数，high向前走直到遇到奇数。
//如果low在high前，交换。
public class Solution {
public void reOrderArray(int [] array) {
if (array.length == 0) {
return;
}
int low = 0;
int high = array.length - 1;
while (low < high) {
while ((array[low] & 1) == 1) {//位与比求余效率高
low += 1;
}
while ((array[high] & 1) == 0) {
high -= 1;
}
if (low < high) {
int temp = array[low];
array[low] = array[high];
array[high] = temp;
}
}
}
}
//插入排序，保证相对位置不变
//第1个数先不管，i从第2个数开始向后走，先找到第1个奇数
//j=i，找到j前一个偶数，j向前走，一次换
//2，4，6，5，7：i先走到5，j也定位到5，5和6，4，2依次换
public class Solution {
public void reOrderArray(int [] array) {
if (array.length == 0) {
return;
}
for (int i = 1; i < array.length; i++) {
int target = array[i];
if ((array[i] & 1) == 1) {//如果为奇数
int j = i;
while (j >= 1 && (array[j - 1] & 1) == 0 ) {
array[j] = array[j - 1];
j--;
}
array[j] = target;
}
}
}
}
14 输入一个链表，输出该链表中倒数第k个结点。
/*
1.定义两个游标p1，p2，其中p2先走k步，然后p1和p2一起走，当p2走到空时，p1为倒数第k个结点
2.需要验证head为空，k<1，k大于链表长度三种情况
*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if (head == null || k < 1)
return null;
ListNode p1 = head;
ListNode p2 = head;
for (int i = 0; i < k; i++) {
if (p2 == null)//当k大于链表长度时会发生
return null;
p2 = p2.next;
}
while (p2 != null) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
}
15 反转链表
public class Solution {
public ListNode ReverseList(ListNode head) {
if (head == null) {
return null;
}
ListNode newHead = null;
ListNode pNode = head;
ListNode pPre = null;
while (pNode != null) {
ListNode pNext = pNode.next;//若pNode一开始为空，这句话写到外面就是错的
if (pNext == null) {
newHead = pNode;
}
pNode.next = pPre;
pPre = pNode;
pNode = pNext;
}
return newHead;
}
}
16 合并两个排序链表
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
ListNode node = null;
if (list1.val <= list2.val) {
node = list1;
node.next = Merge(list1.next, list2);
}else {
node = list2;
node.next = Merge(list1, list2.next);
}
return node;
}
}
17 树的子结构
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if (root1 == null || root2 == null) {
return false;
}
boolean flag = false;
if (root1.val == root2.val) {//如果根值相同才去判断是否为子结构，以这个根点开始
flag = IsSubtree(root1, root2);//判断是否为子结构的方法
}
if (!flag) {//以这个点开始的，不是子结构
flag = HasSubtree(root1.left, root2);//左子树结点和root2比
if (!flag) {
flag = HasSubtree(root1.right, root2);//如果左子树不是，比较右子树
}
}
return flag;
}
public boolean IsSubtree(TreeNode root1, TreeNode root2) {
if (root2 == null) {//右树已比完，左树还有，情况正确
return true;
}
if (root1 == null && root2 != null) {//左树已完，右树还有，错误
return false;
}
if (root1.val == root2.val) {
return IsSubtree(root1.left, root2.left) && IsSubtree(root1.right, root2.right);
}else {
return false;
}
}
}
18 树的镜像
public class Solution {
public void Mirror(TreeNode root) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {//叶结点
return;
}
TreeNode pTemp = root.left;//交换root的左右子树
root.left = root.right;
root.right = pTemp;
if (root.left != null) {//还有子结点
Mirror(root.left);
}
if (root.right != null) {
Mirror(root.right);
}
}
}
19 顺时针打印矩阵
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> list = new ArrayList<>();
if (matrix.length == 0) return list;
int len1 = matrix.length;
int len2 = matrix[0].length;
int layers = (Math.min(len1, len2) + 1) / 2;
for (int i = 0; i < layers; i++) {
for (int m = i; m < len2 - i; m++) {//注意考虑一列
list.add(matrix[i][m]);
}
for (int n = i + 1; n < len1 - i; n++) {//注意考虑一行
list.add(matrix[n][len2 - 1 - i]);
}
for (int p = len2 - 2 - i; (p >= i) && (len1 - 1 - i != i);p--) {//防止只有一行
list.add(matrix[len1 - 1 - i][p]);
}
for (int k = len1 - 2 - i; (k > i) && (len2 - 1 - i != i);k--) {//防止只有一列
list.add(matrix[k][i]);
}
}
return list;
}
}
