目录
一 跳台阶
1.1 题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
1.2 题目分析
- 第1阶有只能1级，一种跳法；
- 第2阶可以两次1级、一次2级两种跳法；
- 若楼梯阶级 k = 3
- 跳 2 步到 3：剩下的是第1步没跳，起始跳到第1步只有一种；
- 跳 1 步到 3：剩下的是第2步没跳，起始跳到第2步有两种。
通过分类讨论，问题规模就减少了:
- 若楼梯阶级 k = n
- 跳 2 步到 n：剩下的是第 n – 2 步没跳，起始跳到第 n – 2 步跳法；
- 跳 1 步到 n：剩下的是第 n – 1 步没跳，起始跳到第 n – 1 步跳法。
总结来说：n 级台阶跳法就相当于 n-1 级再跳一次1阶的跳法和 n-2 级再跳一次2阶的总和。
1.3 题目求解
public class Solution {
public int JumpFloor(int target) {
if(target == 1 || target == 2) {
return target;
}
return JumpFloor(target - 1) + JumpFloor(target - 2);
}
}二 斐波那契数列
2.1 题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39
2.2 题目分析
| 0项 | 1项 | 2项 | …… | n项 |
| 0 | 1 | 1 | …… | （n-1）项+（n-2）项 |
2.3 题目求解
public class Solution {
public int Fibonacci(int n) {
if(n<=1) {
return n;
}
return Fibonacci(n-1) + Fibonacci(n-2);
}
}三 用两个栈实现队列
3.1 题目描述
用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。 队列中的元素为 int 类型。
3.2 题目分析
队列的特性是：先入先出。
栈的特性是：先入后出。
3.3 题目求解
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.size()==0) {
while(stack1.size()!=0) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}四 变态跳台阶
4.1 题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
4.2 题目分析
(1) – (2) 得到：
4.3 题目求解
public class Solution {
public int JumpFloorII(int target) {
if(target<=1) {
return target;
}
return 2*JumpFloorII(target-1);
}
}五 从尾到头打印链表
5.1 题目描述
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
5.2 题目分析
- listNode 是链表，只能从头遍历到尾，但是输出却要求从尾到头，这是典型的“先进后出”，我们可以想到栈！
- ArrayList 中有个方法是 add(index,value)，可以指定 index 位置插入 value 值，index + 1之后的元素都往后移动一位。
5.3 题目求解
栈实现
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList list = new ArrayList();
Stack stack = new Stack();
while (listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
while (!stack.empty()) {
list.add(stack.pop());
}
return list;
}
}add(index,value) 实现
/**
* 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 list = new ArrayList();
while (listNode != null) {
list.add(0,listNode.val);
listNode = listNode.next;
}
return list;
}
}六 反转链表
6.1 题目描述
输入一个链表，反转链表后，输出新链表的表头。
6.2 题目分析
1 这块牵涉到三个链表节点，前一个节点 preNode，当前节点 head 和 后一个节点 nextNode。
2 要想实现链表反转，这块需要操作四步：
- 第一步 nextNode 存储 head 指向的下一个节点；
- 第二步 head 指向 preNode；
- 第三步 preNode 往前移动；
- 第四步 head 往前移动；
6.3 题目求解
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode preNode = null;
ListNode nextNode = null;
while(head != null) {
nextNode = head.next;
head.next = preNode;
preNode = head;
head = nextNode;
}
return preNode;
}
}七 链表中倒数第 K 个节点
7.1 题目描述
输入一个链表，输出该链表中倒数第k个结点。
7.2 题目分析
为了实现只遍历链表一次就能找到倒数第 k 个结点，我们可以定义快慢指针，通过两个步骤实现：
第一个步骤：快指针从链表的头指针开始遍历向前走 k-1步，慢指针保持不动；
第二个步骤：从第 k 步开始，快指针往前走，慢指针也开始从链表的头指针开始遍历。由于快慢指针的距离保持在 k-1 ， 当快指针到达链表的尾结点时，慢指针正好是倒数第 k 个结点。
7.3 题目求解
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null || k < 1) {
return null;
}
ListNode fast = head;
ListNode slow = head;
for(int i=0;i<k;i++) {
if(fast == null) {
return null;
}
fast = fast.next;
}
while(fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}八 合并两个排序的链表
8.1 题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
8.2 题目分析
- 遍历解法
同时不断遍历两个链表，取出小的追加到新的头节点后，直至两者其中一个为空，再将另一者追加的新链表最后。
- 递归解法
递归的核心方法是将问题规模不断缩小化，合并两个长度为 n 和 m 的链表，在 value(n) < value(m) 可以将规模缩减为合并长度为 (n-1) 和 m 的链表。
8.3 题目求解
遍历解法
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode head = new ListNode(-1);
ListNode current = head;
while(list1 != null && list2 != null) {
if(list1.val < list2.val) {
current.next = list1;
list1 = list1.next;
} else {
current.next = list2;
list2 = list2.next;
}
current = current.next;
}
if(list1 != null) {
current.next = list1;
}
if(list2 != null) {
current.next = list2;
}
return head.next;
}
}递归解法
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
if (list1.val < list2.val) {
list1.next = Merge(list1.next, list2);
return list1;
} else {
list2.next = Merge(list1, list2.next);
return list2;
}
}
}九 对称二叉树
9.1 题目描述
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
9.2 题目求解
- 递归
1.只要 pRoot.left 和 pRoot.right 是否对称即可。
2.左右节点的值相等且对称子树 left.left， right.right ; left.rigth, right.left 也对称。
public boolean isSymmetrical(TreeNode pRoot) {
if(pRoot == null) {
return true;
}
isSymmetrical(pRoot.left, pRoot.right);
}
public boolean isSymmetrical(TreeNode left, TreeNode right) {
if(left == null && right == null) {
return true;
}
if(left == null || right == null) {
return false;
}
return left.val == right.val && isSymmetrical(left.left, right.right) && isSymmetrical(left.right, right.left);
}-
非递归
/===================非递归算法，利用DFS和BFS=============================//
/*
* DFS使用stack来保存成对的节点
* 1.出栈的时候也是成对成对的 ，
1.若都为空，继续；
2.一个为空，返回false;
3.不为空，比较当前值，值不等，返回false；
* 2.确定入栈顺序，每次入栈都是成对成对的，如left.left， right.right ;left.rigth,right.left
*/
boolean isSymmetrical(TreeNode pRoot) {
if(pRoot == null) {
return true;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(pRoot.left);
stack.push(pRoot.right);
while(!stack.empty()) {
TreeNode right = stack.pop();
TreeNode left = stack.pop();
if(right == null && left == null) {
continue;
}
if(right == null || left == null) {
return false;
}
if(right.val != left.val) {
return false;
}
stack.push(left.left);
stack.push(right.right);
stack.push(left.right);
stack.push(right.left);
}
return true;
}*
* BFS使用Queue来保存成对的节点，代码和上面极其相似
* 1.出队的时候也是成对成对的
1.若都为空，继续；
2.一个为空，返回false;
3.不为空，比较当前值，值不等，返回false；
* 2.确定入队顺序，每次入队都是成对成对的，如left.left， right.right ;left.rigth,right.left
*/
boolean isSymmetricalBFS(TreeNode pRoot) {
if(pRoot == null) {
return true;
}
Queue<TreeNode> s = new LinkedList<>();
s.offer(pRoot.left);
s.offer(pRoot.right);
while(!s.isEmpty()) {
TreeNode left= s.poll();//成对取出
TreeNode right= s.poll();
if(left == null && right == null) {
continue;
}
if(left == null || right == null) {
return false;
}
if(left.val != right.val) {
return false;
}
//成对插入
s.offer(left.left);
s.offer(right.right);
s.offer(left.right);
s.offer(right.left);
}
return true;
}十 统计一个数字在排序数组中出现的次数
统计一个数字在排序数组中出现的次数。
10.1 直接比较统计，O(N)的时间复杂度。
public class Solution {
public int GetNumberOfK(int[] a, int key) {
int count = 0;
for(int i:a) {
if(i == key) {
count++;
}
}
return count;
}
}10.2 利用二分查找，分别找出最先出现和最后出现的位置，再统计出现的次数即可，时间复杂度为O(logN)。
public class Solution {
public int GetNumberOfK(int [] array , int k) {
int length = array.length;
if(length == 0){
return 0;
}
int firstK = getFirstK(array, k, 0, length-1);
int lastK = getLastK(array, k, 0, length-1);
if(firstK != -1 && lastK != -1){
return lastK - firstK + 1;
}
return 0;
}
//递归写法
private int getFirstK(int [] array , int k, int start, int end){
if(start > end){
return -1;
}
int mid = (start + end) >> 1;
if(array[mid] > k){
return getFirstK(array, k, start, mid-1);
}else if (array[mid] < k){
return getFirstK(array, k, mid+1, end);
}else if(mid-1 >=0 && array[mid-1] == k){
return getFirstK(array, k, start, mid-1);
}else{
return mid;
}
}
//循环写法
private int getLastK(int [] array , int k, int start, int end){
int length = array.length;
int mid = (start + end) >> 1;
while(start <= end){
if(array[mid] > k){
end = mid-1;
}else if(array[mid] < k){
start = mid+1;
}else if(mid+1 < length && array[mid+1] == k){
start = mid+1;
}else{
return mid;
}
mid = (start + end) >> 1;
}
return -1;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之家整理，本文链接：https://www.bmabk.com/index.php/post/9583.html
