数值的整数次方
题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
解法：递归or迭代
public class Solution {
public double Power(double base,int e1) {
int e = Math.abs(e1);
if(e==0)
return 1;
if(e==1)
return base;
double result = Power(base, e>>1);
result *= result;
if(e%2==1)
result *= base;
if(e1<0)
return 1.0/result;
return result;
}
}
调整数组顺序使得奇数位于偶数的前面
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
解法一：使用两个指针，分别从数组两边开始行走，判断并交换
解法二：创建一个新的数组，遍历原数组，时间复杂度为O(n*2)
public class Solution {
public void reOrderArray(int [] array) {
int[] arr = new int[array.length];
int k = 0;
for(int i = 0 ; i<array.length;i++){
if(array[i]%2==1)
arr[k++] = array[i];
}
for(int i = 0 ; i<array.length;i++){
if(array[i]%2==0)
arr[k++] = array[i];
}
for(int j = 0 ; j<array.length;j++){
array[j] = arr[j];
}
}
}
链表中倒数第K个节点
题目描述
输入一个链表，输出该链表中倒数第k个结点。
解法：类似于快慢指针的思想，假设链表长度为n,倒数第K个节点就是整数第n-k个节点，快指针走到第k个的时候，慢指针开始和快指针一起走，当快指针走到最后一个的时候，慢指针走到n-k的位置及倒数第k个节点，在此之前要判断链表的长度是否大于等于k;
/*
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 == 0){
return null;
}
ListNode node = head;
for(int i = 0 ; i< k ; i++){
if(node!=null){
node = node.next;
}else{
return null;
}
}
while(node!=null){
node = node.next;
head = head.next;
}
return head;
}
}
反转链表
题目描述
输入一个链表，反转链表后，输出新链表的表头。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode pNode = head;
ListNode preNode = null;
ListNode newNode = null;
while(pNode!=null){
ListNode pnext = pNode.next;
if(pNode.next==null)
newNode = pNode;
pNode.next = preNode;
preNode = pNode;
pNode = pnext;
}
return newNode;
}
}
合并两个排序的链表
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
解法：使用递归的思想
/*
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 && list2 == null){
return null;
}
if(list1 == null)
return list2;
if(list2 == null)
return list1;
ListNode list3 = null;
if(list1.val<list2.val){
list3 = list1;
list3.next = Merge(list1.next,list2);
}else{
list3 = list2;
list3.next = Merge(list1,list2.next);
}
return list3;
}
}
树的子结构
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
解法：看到树的操作就往递归的思想靠拢
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public boolean DoesTree(TreeNode r1,TreeNode r2){
if(r2 == null){
return true;
}
if(r1 == null){
return false;
}
if(r1.val != r2.val){
return false;
}
return DoesTree(r1.left,r2.left)&&DoesTree(r1.right,r2.right);
}
public boolean HasSubtree(TreeNode r1,TreeNode r2) {
boolean flag = false;
if(r1 != null && r2 != null){
if(r1.val == r2.val){
flag = DoesTree(r1,r2);
}
if(flag == false){
flag = HasSubtree(r1.left,r2);
}
if(flag == false){
flag = HasSubtree(r1.right,r2);
}
}
return flag;
}
}
二叉树的镜像
题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义：源二叉树
8
/
6 10
/ \ /
5 7 9 11
镜像二叉树
8
/
10 6
/ \ /
11 9 7 5
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public void Mirror(TreeNode root) {
if(root == null){
return;
}
if(root.left == null && root.right == null)
return;
TreeNode node = root.left;
root.left = root.right;
root.right = node;
if(root.left!=null){
Mirror(root.left);
}
if(root.right!=null){
Mirror(root.right);
}
}
}
顺时针打印矩阵
题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
则依次打印出数字
1, 2, 3, 4,
8, 12,16,15,
14,13,9, 5,
6, 7, 11,10.
解法：考察细节
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> list = new ArrayList<>();
public void Print(int[][] matrix,int columns,int rows,int start){
int endX = columns - 1 -start;
int endY = rows -1 -start;
//从左到右打印一行
for (int i = start ; i<= endX;i++ ){
int num = matrix[start][i];
list.add(num);
}
//从上到下打印一列
if(start < endY){
for (int j = start+1;j<=endY;j++){
int num = matrix[j][endX];
list.add(num);
}
}
//从右到左打印一行
if( start < endX && start < endY){
for (int i = endX-1;i>=start;i--){
int num = matrix[endY][i];
list.add(num);
}
}
//从下向上打印一行
if(start<endX && start<endY-1){
for (int j = endY-1;j>=start+1;j--){
int num = matrix[j][start];
list.add(num);
}
}
}
public ArrayList<Integer> printMatrix(int [][] matrix) {
int columns = matrix[0].length;//矩阵列数
int rows = matrix.length;//矩行数
if (matrix == null || columns <= 0 || rows <= 0)
return null;
int start = 0;
while (start*2<columns && start*2<rows){
Print(matrix,columns,rows,start);
++start;
}
return list;
}
}
包含min函数的栈
题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
import java.util.Stack;
public class Solution {
public static Stack<Integer> stack1 = new Stack<>();
public static Stack<Integer> stack2 = new Stack<>();
public void push(int node) {
if(stack2.isEmpty()){
stack2.push(node);
}
if(node <= stack2.peek()){
stack2.push(node);
}else{
stack2.push(stack2.peek());
}
stack1.push(node);
}
public void pop() {
if(stack2.isEmpty()){
throw new RuntimeException();
}
stack1.pop();
stack2.pop();
}
public int top() {
if(stack1.isEmpty()){
throw new RuntimeException();
}
return stack1.peek();
}
public int min() {
if(stack2.isEmpty()){
throw new RuntimeException();
}
return stack2.peek();
}
}
栈的压入，弹出序列
题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
解法：直接创建一个辅助栈，模拟一遍压入弹出的过程，看最后栈是否为空，若是空，则匹配成功
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length==0||popA.length==0){
return false;
}
Stack<Integer> stack = new Stack<>();
int j = 0 ;
for (int i = 0 ; i < pushA.length ; i++){
stack.push(pushA[i]);
while (!stack.empty()&&stack.peek() == popA[j]){
stack.pop();
j++;
}
}
return stack.empty();
}
}
公众号写的比较全，更多请关注公众号：
qrcode_for_gh_bca5e6591047_258 (1).jpg
网友评论