剑指Offer 刷题代码：
- 二维数组中的查找
题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：从右上角开始查找，作比较 是返回 ，小了row++ ，大了 col–
Java:
public boolean Find(int target, int [][] array) {
int row = 0;
int col = array[0].length -1;
while(row<array.length && col>= 0) {
if (array[row][col]==target) {
return true;
}
else if (array[row][col]<target) {
row++;
}
else {
col--;
}
}
return false;
}
2.替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路： 新建一个newstr 判断当前 str 中位置是不是空格 不是append 进 newstr,是 append %20
public class Solution {
public String replaceSpace(StringBuffer str) {
StringBuffer newstr = new StringBuffer();
for(int i=0; i<str.length(); i++){
if(str.charAt(i)!=' ')
newstr.append(str.charAt(i));
else
newstr.append("%20");
}
return newstr.toString();
}
}
3.数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方
public class Solution {
public double Power(double base, int exponent) {
//本题注意的是exponent小于0 或者 等于 0 的情况 还有base为0的情况
double result = 1;
if(exponent < 0){
base = 1/base;
exponent = (-1) * exponent;
for (int i = 1; i <= exponent; i++) {
result = result *base;
}
}
else{
for (int i = 1; i <= exponent; i++) {
result = result *base;
}
}
return result;
}
}
public class Solution {
//时间复杂度O(n)
public double Power(double base, int exponent) {
int n = Math.abs(exponent);
if (n == 0)
return 1;
if (n == 1)
return base;
//以上两个if判断可省。for循环中判断
double result = 1.0;
for (int i = 0; i < n; i++) {
result *= base;
}
if (exponent < 0) {
result = 1 / result;
}
return result;
}
}
4.二进制中1的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示.
思路：最简单的思路，整数n每次进行无符号右移一位，同1做&运算，可以判断最后以为是否为1。n&(n-1) 操作相当于把二进制表示中最右边的1变成0。所以只需要看看进行了多少次这样的操作即可。看看什么时候n为0.
0110&0101 -> count=1,n=0100 & 0011 -> n=0000 count=2
public class Solution {
public int NumberOf1(int n) {
int count =0;
while(n!=0){
n=n&(n-1);
count++;
}
return count;
}
}
5.从头到尾打印链表
题目描述：
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
代码：
//新建一个 ArrayList 对象 判断节点是不是空，然后添加节点。反转
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> addressArrayList =new ArrayList<Integer>();
if(listNode == null){
ArrayList first =new ArrayList();
return first;
}
while(listNode != null){
addressArrayList.add(listNode.val);
listNode =listNode.next;
}
Collections.reverse(addressArrayList);
return addressArrayList;
}
}
//利用堆栈实现
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode == null){
ArrayList firstlist =new ArrayList();
return firstlist;
}
Stack<Integer> stk = new Stack<Integer>();
while(listNode != null){
stk.push(listNode.val);
listNode = listNode.next;
}
ArrayList<Integer> arr =new ArrayList<Integer>();
while(!stk.empty()){
arr.add(stk.pop());
}
return arr;
}
}
//大佬写的递归实现 1 2 3 4 5 实现 5 4 3 2 然后add 1
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
private ArrayList<Integer> re = new ArrayList<Integer>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode==null)
return re;
printListFromTailToHead(listNode.next);
re.add(listNode.val);
return re;
}
}
6.斐波那契额数列
现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39
//递归 占用内存打大
public class Solution {
public int Fibonacci(int n) {
if(n==0){
return 0;
}else if(n==1){
return 1;
}else{
return Fibonacci(n-1)+Fibonacci(n-2);
}
}
}
//非递归
public class Solution {
public int Fibonacci(int n) {
int a=1,b=1,c=0;
if(n==0) return 0;
else if(n==1||n==2) return 1;
else {
for(int i=2;i<n;i++){
c=a+b;
b=a;
a=c;
}
return c;
}
}
}
7.旋转数组的最小数字【这个题暂时没看懂】
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
//这样直接求最小写能通过，但不是题目本意
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
int min=array[0];
for(int i=0;i<array.length-1;i++){
if (min>array[i]){
min=array[i];
}
}
return min;
}
}
//用到二分，找到中间的数，然后和最左边的值进行比较，若大于最左边的数，则最左边从mid开始，若小于最右边值，则最右边从mid开始。若左中右三值相等，则取mid前后值中较小的数。
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
int front=0;
int rear =array.length-1;
int middle =(front+rear)/2;
while(front<rear){
if(rear-front == 1)
break;
middle =(rear+front)/2;
if(array[middle] >= array[front]){
front = middle;
}else{
rear = middle;
}
}
return array[rear];
}
}
8.用两个栈实现一个队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
// push 第一个栈 ，然后 查看第二个栈如果第二个不空直接pop 如果为空 第一个先push 第二个再pop
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()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
9.重建二叉树：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
//利用 前序和中序生成树
import java.util.Arrays;
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if (pre == null || in == null) {
return null;
}
if (pre.length == 0 || in.length == 0) {
return null;
}
if (pre.length != in.length) {
return null;
}
TreeNode root = new TreeNode(pre[0]);//第一个
for (int i = 0; i < in.length; i++) {
if (pre[0] == in[i]) {
//pre的0往后数i个是左子树的，copyofrange包含前面的下标，不包含后面的下标
//in的i往前数i个是左子树的。
root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i)); // 分别除去根节点
//注意in是从i+1开始，因为i是现在的根，i+1开始才是右子树
root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length),
Arrays.copyOfRange(in, i + 1, in.length));
}
}
return root;
}
}
10.跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
// 递归 ：斐波拉契数序列，初始条件n=1:只能一种方法，n=2:两种 ,对于第n个台阶来说，只能从n-1或者n-2的台阶跳上来，所以 F(n) = F(n-1) + F(n-2)
public class Solution{
public int JumpFloor(int n){
if(n==0) return 0;
else if(n==1)return 1;
else if(n==2)return 2;
else return JumpFloor(n-1)+JumpFloor(n-2);
}
}
11.变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
//参考思路：
//竟然是个等比数列
public class Solution {
public int JumpFloorII(int target) {
int res=1;
for(int i=1;i<=target-1;i++){
res=res*2;
}
return res;
}
}
12.矩阵覆盖
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
//依然是斐波那契数列 可以试着 归纳做
public class Solution {
public int RectCover(int n) {
if(n==0) return 0;
else if(n==1) return 1;
else if(n==2) return 2;
else{
int result;
result=RectCover(n-1)+RectCover(n-2);
return result;
}
}
}
13.调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
//通过 Arraylist 变长数组解决
import java.util.ArrayList;
public class Solution {
public void reOrderArray(int [] array) {
ArrayList<Integer> jlist = new ArrayList<Integer>();
ArrayList<Integer> olist = new ArrayList<Integer>();
for(int i=0; i<array.length;i++){
if(array[i]%2==0)
olist.add(Integer.valueOf(array[i]));
else
jlist.add(Integer.valueOf(array[i]));//valueOf 是将int转换为Integer
}
jlist.addAll(olist); //先把所有偶数加上
int temp=0;
for(int i=0;i< jlist.size();i++){
array[temp]=jlist.get(i).intValue();//intValue是反过来
temp++;
}
}
}
//另一种方法 前偶后奇交换
import java.util.ArrayList;
public class Solution {
public void reOrderArray(int [] array) {
int temp = 0;
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - 1 - i; j++) {
// 前偶后奇数就交换
if ((array[j] & 1) == 0 && (array[j + 1] & 1) == 1) { //与1位与得1就是奇数，1只有最后一位是1
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
}
14.链表中倒数第k个结点
输入一个链表，输出该链表中倒数第k个结点。
//一种思路 先遍历求长度 ，然后输入倒数第K个 【不行】
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head ==null) return head;
ListNode node =head;
int count =0;
while(node != null){
count++;
node =node.next;
}
if(count < k) return null;
ListNode p= head;
for(int i=0;i<count -k;i++){
p=p.next;
}
return p;
}
}
//正常思路：设置两个游标，让快的领先K个,然后一块走，fast==null slow指向的那个就是
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode slow = head;
ListNode fast = head;
if(head ==null || k<=0){
return null;
}
for(int i=1;i<k;i++){快的先走k-1步，倒数第三个，其实应该快的指到第三个，只需要走两步即可。
if(fast.next == null)
return null;
else
fast=fast.next;
}
while(fast.next != null){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
15.反转链表
题目描述
输入一个链表，反转链表后，输出新链表的表头。
// 设置 三个指针 pre head next next =head.next head-next=pre pre=head head=next
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head==null)
return null;
//head为当前节点，如果当前节点为空的话，那就什么也不做，直接返回null；
ListNode pre = null;
ListNode next = null;
//当前节点是head，pre为当前节点的前一节点，next为当前节点的下一节点
//需要pre和next的目的是让当前节点从pre->head->next1->next2变成pre<-head next1->next2
//即pre让节点可以反转所指方向，但反转之后如果不用next节点保存next1节点的话，此单链表就此断开了
//所以需要用到pre和next两个节点
//1->2->3->4->5
//1<-2<-3 4->5
while(head!=null){
//做循环，如果当前节点不为空的话，始终执行此循环，此循环的目的就是让当前节点从指向next到指向pre
//如此就可以做到反转链表的效果
//先用next保存head的下一个节点的信息，保证单链表不会因为失去head节点的原next节点而就此断裂
next = head.next;
//保存完next，就可以让head从指向next变成指向pre了，代码如下
head.next = pre;
//head指向pre后，就继续依次反转下一个节点
//让pre，head，next依次向后移动一个节点，继续下一次的指针反转
pre = head;
head = next;
}
//如果head为null的时候，pre就为最后一个节点了，但是链表已经反转完毕，pre就是反转后链表的第一个节点
//直接输出pre就是我们想要得到的反转后的链表
return pre;
}
}
16 .合并两个排序的链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
//新建一个链表 比较两个链表看小的加入新链表 然后 长的链表在比较完毕后直接添加到尾部
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null) return list2;
if(list2 == null) return list1;
//新建一个用于存放融合之后的链表
ListNode res = new ListNode(0);
ListNode merlistNode =res;
while(list1 !=null && list2 != null){
if(list1.val <list2.val){
merlistNode.next=list1; //链上小的list1
list1=list1.next;
merlistNode=merlistNode.next;
}
else{
merlistNode.next=list2;
list2=list2.next;
merlistNode=merlistNode.next;
}
}
if(list1!=null)
merlistNode.next=list1;
if(list2!= null)
merlistNode.next=list2;
return res.next;
}
}
//递归
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
ListNode newHead = null;
if (list1.val <= list2.val) {
newHead = list1;
newHead.next = Merge(list1.next,list2);
}else {
newHead = list2;
newHead.next = Merge(list1,list2.next);
}
return newHead;
}
}
17最大子序列和
给定一个序列，求最大的子序列和
//穷举 n3
public static int maxSub_1(int [] sequence){
int max=0;
int n =sequence.length;
int sum=0;
// i 设置窗口
for(int i=1;i<=n;i++) //第一重循环执行一次计算出长度为 i 的所有子序列的和的最大值
for(int j=0;j<n;j++){
sum=0;
for(int k=j;k<j+i && k<n;k++) j-j+i 为当前子序列
sum+=sequence[k];
if(sum>max) max=sum;
}
return max;
}
//改进 n2
public static int maxSub_2(int [] sequence){
int max=0;
int n =sequence.length;
int sum=0;
for(int i=0;i<=n;i++) { //第一重循环执行一次计算出长度为 i 的所有子序列的和的最大值
sum = 0;
for (int j = i; j < n; j++) {
sum += sequence[j];
if (sum > max) max = sum;
}
}
return max;
}
//递归 nlogn 分 左 右 中间
public static int maxSum(int[] sequence,int left,int right){
if(left == right) //只有一个数据
if(sequence[left]>0)
return sequence[left];
else
return 0;
int mid =(left+right)/2;
int maxLeftSum= maxSum(sequence,left,mid);
int maxRightSum= maxSum(sequence,mid+1,right);
int maxLeftBorderSum=0,leftBorderSum=0;
for(int i = mid;i>=left;i--){
leftBorderSum+=sequence[i];
if(leftBorderSum> maxLeftBorderSum)
maxLeftBorderSum=leftBorderSum;
}
int maxRightBorderSum=0,rightBorderSum=0;
for(int i=mid+1;i<=right;i++){
rightBorderSum+=sequence[i];
if(leftBorderSum> maxRightBorderSum)
maxRightBorderSum=rightBorderSum;
}
return max3(maxLeftSum,maxRightSum,maxRightBorderSum+maxRightBorderSum);
}
public static int max3(int a,int b,int c){
int max=a>b? a:b;
max=max>c? max:c;
return max;
}
//DP n 动态规划
public static int maxSub_4(int [] sequence){
int max=0;
int n= sequence.length;
int sum=0;
for(int i=0;i<n;i++){
sum+=sequence[i];
if(sum>max) max=sum;
else if(sum<0) sum=0;
}
return max;
}
18.树的子结构判断
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路：
//先从根开始再把左作为根，再把右作为根由本函数决定。把一个为根的时候的具体比对过程是第二个函数决定。
//从根可以认为是一颗树，从左子树开始又可以认为是另外一颗树，从右子树开始又是另外一棵树。
//本函数就是判断这一整颗树包不包含树2，如果从根开始的不包含，就从左子树作为根节点开始判断，
//再不包含从右子树作为根节点开始判断。
//是整体算法递归流程控制。
/**
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) {
boolean res = false;
if (root1 != null && root2 != null) {
if(root1.val == root2.val){
res = doesTree1haveTree2(root1,root2);
}
if(!res)
{
res = HasSubtree(root1.left, root2);
}
if(!res)
{
res = HasSubtree(root1.right, root2);
}
}
return res;
}
//本函数，判断从当前的节点 ，开始两个树能不能对应上，是具体的比对过程
public boolean doesTree1haveTree2(TreeNode root1,TreeNode root2) {
if(root2 == null)
return true;
if(root1 == null)
return false;
if(root1.val != root2.val){
return false;
}
//如果根节点可以对应上，那么就去分别比对左子树和右子树是否对应上
return doesTree1haveTree2(root1.left, root2.left) && doesTree1haveTree2(root1.right, root2.right);
}
}
19.二叉树的镜像
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义：源二叉树
/**
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){
TreeNode temp = root.left;
root.left=root.right;
root.right = temp;
Mirror(root.left);
Mirror(root.right);
}
}
}
//栈解决
/*public void Mirror(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node.left != null || node.right != null) {
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
}
if(node.left != null)
stack.push(node.left);
if(node.right != null)
stack.push(node.right);
}
}*/
20.顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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 {
/**
* 基本思路：
* 1.左上角的坐标和右下角的坐标固定了一圈矩阵，先打印这一圈矩阵。其中，对矩阵只有一行或者一列分别打印。
* 2.打印完了这一圈，左上角坐标都+1 ，右下角的都减一，到更内一圈。
*比如：4*4的矩阵，(0,0)--(3,3)然后，(1,1)--(2,2)
* 3.当左上角跑到右下角下面就结束了。
* —---------|
| |
| |
|----------
* @param matrix
* @return
*/
public ArrayList<Integer> printMatrix(int [][] matrix){
ArrayList<Integer> list = new ArrayList<Integer>(); //新建 list数组
int topRow = 0;
int topCol = 0;
int downRow = matrix.length - 1;
int downCol = matrix[0].length - 1;
while (topRow <= downRow && topCol <= downCol) { //当满足左上角的小于等于右下角就可以循环
printCircle(list, matrix, topRow++, topCol++, downRow--, downCol--);
}
return list;
}
public void printCircle(ArrayList<Integer> list, int [][] matrix, int topRow, int topCol, int downRow, int downCol) {
if (topRow == downRow) { //子矩阵只有一行的时候
for (int i = topCol; i <= downCol; i++) {//注意循环开始的条件，是从这一列开始，不是从零
list.add(matrix[topRow][i]);
}
}
else if (topCol == downCol) {//子矩阵只有一列的时候
for (int i = topRow; i <= downRow; i++) {//
list.add(matrix[i][topCol]);
}
}
else { //其他的情况下
int currentRow = topRow;
int currentCol = topCol;
while (currentCol != downCol) {//左到右 本行最后一个不访问，在下个循环里面。如
list.add(matrix[topRow][currentCol]);
currentCol++;
}
while (currentRow != downRow) {//上到下0
list.add(matrix[currentRow][downCol]);
currentRow++;
}
while (currentCol != topCol) {//右到左
list.add(matrix[downRow][currentCol]);
currentCol--;
}
while (currentRow != topRow) {//下到上
list.add(matrix[currentRow][topCol]);
currentRow--;
}
}
}
}
21.两个链表的第一个公共结点
输入两个链表，找出它们的第一个公共结点
//相交节点的判断 公共部分是相交部分
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
// 首先，如果相交，那么尾节点一定是一样的。
// 接下来，谁长谁就先走一定的步数，然后一起走，肯定是同时到达相交的点。
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1 == null || pHead2 ==null) return null;
ListNode cur1 = pHead1;
ListNode cur2 = pHead2;
int n =0;
while(cur1.next != null){
n++; // 记录长度
cur1=cur1.next;
}
while(cur2.next != null){
n--;
cur2=cur2.next;
}
if(cur1 != cur2) return null; //判断尾节点是否相同
cur1 = n>0? pHead1:pHead2; //cur1 是 长 的 链表
cur2 = cur1 == pHead1? pHead2:pHead1;
n=Math.abs(n);
while(n !=0){
n--;
cur1 =cur1.next;
}
while(cur1 !=cur2){
cur1 =cur1.next;
cur2 = cur2.next;
}
return cur1;
}
}
22 链表中环的入口节点
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null
//判断有环的思路
思路：
第一步，找环中相汇点。分别用p1，p2指向链表头部，
- p1每次走一步，p2每次走二步，直到p1==p2找到在环中的相汇点。
通过快慢指针来判断是否有环，现在我们假设两个指针相遇在z点，如图
fast指针走过a+b+c+b
slow指针走过a+b
那么2*(a+b) = a+b+c+b
所以a = c
此时让slow回到起点，fast依然停在z，两个同时开始走，一次走一步
那么它们最终会相遇在y点，正是环的起始点【有点难理解】
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead)
{
if (pHead == null || pHead.next == null) {
return null;
}
ListNode fast = pHead;
ListNode slow = pHead;
while(fast != null && fast.next!=null){
slow = slow.next;
fast = fast.next.next;//一个走一步 一个走两步
if(slow == fast){ //直到相遇
fast = pHead; // 之后让fast 从头开始走 fast slow 都从头开始走
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
23.数组中只出现一次的数字
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
//思路 利用异或 数组异或 相同的数为0 和顺序无关
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int e0=0,e0ne=0;
for(int num:array)
e0 ^= num; // e0的结果为 a^b a b 为那两个数
int firstOne =e0 &(~e0+1);//求得二进制中第一位1，比如101和011得到001
for(int cur:array)
if((cur & firstOne) !=0){ //把第k位是1的找出来进行异或
e0ne ^=cur; //最后的到一个 a
}
num1[0]=e0ne;
num2[0] = e0ne^e0; // eone 为 a 则 eone^e0 为b
}
}
24.丑数
把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
public class Solution {
/**
* 剑指offer的思路：
* 取一个数组来放丑数，下一个丑数必定是这个数组里面的数乘以2或者3
* 或者5，这三种中最小的那一个。依次，判断下去
* @param index
* @return
*/
public int GetUglyNumber_Solution(int index) {
if(index <= 0)
return 0;
int [] res = new int[index];
res[0] = 1;//先把1放入
int m2 = 0;//控制乘以2的位置，假设得到一个丑数是乘以2得到的，
//那么下一次就是数组中的下一个丑数可能达到。
int m3 = 0;
int m5 = 0;
for (int i = 1; i < index; i++) {
int min = Math.min(res[m2]*2, Math.min(res[m3]*3, res[m5]*5));
res[i] = min;//最小的那个作为当前的丑数
//判断是由谁乘以得到的
if(res[m2] *2 == min)//假设res[1]是乘以2得到的丑数，那么下一次就要判断
//是否是res[2]乘以2可能得到丑数，所以就要++
m2++;
if(res[m3]*3 == min)
m3++;
if(res[m5]*5 == min)
m5++;
}
return res[index - 1];
}
}
25.数组中出现超过数组长度的一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
public class Solution {
//我的想法：排序取出中间数
//哈希表记录
public int MoreThanHalfNum_Solution(int [] array) {
int cand=0;
int times =0;
for(int i =0;i< array.length;i++){
if(times ==0){
cand = array[i];
times = 1;
}else if(array[i] == cand){
times++;
}else{
times--;
}
}
times =0;
//做判断 cand 到底是不是 那个数
for(int i=0; i<array.length;i++){
if(array[i] ==cand)
times++;
}
if(times*2 >array.length) return cand;
else return 0;
}
}
26.最小的K个数
输入N个数，找出其中最小的K个数。例如，输入1，2，3，4，5，6，7，8,求最小的4个数，既输出1,2,3,4。
//还有其他方法建立一个堆
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Arrays;
public class Solution {
//笨方法 排序 然后选择前K个
//一种解法
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
List<Integer> list =new ArrayList<Integer>();
if(k> input.length || k==0) return (ArrayList)list;
for( int i =0;i<k;i++){
list.add(input[i]); //先放k个数
}
for( int i=k; i< input.length;i++){
Collections.sort(list); //每次都排序
if(input[i]<list.get(k-1)){ //从k后面一个开始遍历，如果比list里面最大的值小，就替换掉。重新排序一次。循环执行
list.set(k-1,input[i]);
}
}
return (ArrayList)list;
}
}
27 .把数组排成最小的数
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
思路一的复杂度为O(n!),那么我们能不能不进行全排列就能找到那个特定的排列呢？很容易想到就是排序，如果能想到一个很好的排序策略，即可优雅得到最后的结果。
对于给定的2个数，a和b。如何确定两者之间的排序策略呢？我们可以发现这两者的排列为：ab,ba。我们最终目的是找到字典序最小的那个排列，所以我们肯定应该保持这种关系，从而决定是否交换顺序：
1. 当ab < ba, a排在b的左边
2. 当ab > ba, b排在a的左边
3. 当ab = ba, 位置关系随意
不理解的话，可以结合选择排序算法来理解，我们在n个元素选择出最小的作为左边的值，显然它应该位于所有n-1个元素的左边，也就是第一个位置上。接着在n-1个元素找到次最小，反复如此，直到没有剩余元素。
如果你理解了选择排序的做法，又因为一般的排序算法的结果都是一样，所以我们可以采用更快的排序算法来解答此题，为了方便，直接了使用了库函数，当然你可以自行实现快速排序或归并排序，这些都未尝不可。
public static String PrintMinNumber2(int [] numbers) {
if(numbers == null || numbers.length == 0) {
return "";
}
String[] strNumbers = new String[numbers.length];
for(int i = 0; i < numbers.length; i++) {
strNumbers[i] = String.valueOf(numbers[i]);
}
Arrays.sort(strNumbers, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return (o1 + o2).compareTo(o2 + o1);
}
});
StringBuilder sb = new StringBuilder();
for(int i = 0; i < strNumbers.length; i++) {
sb.append(strNumbers[i]);
}
return sb.toString();
}
28.包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））
import java.util.Stack;
/*
* 思路：用一个栈stack保存数据，用另外一个栈min保存依次入栈最小的数
* 比如，stack中依次入栈，5, 4, 3, 8, 10,11,12,1
* 则min依次入栈，5, 4, 3, 3, 3, 3, 3, 1
* 每次入栈的时候，如果入栈的元素比min中的栈顶元素小或等于则入栈，否则入stack的栈顶元素。
* 保持stack中和min中保持相同个数的元素 ，同时保持min的栈顶是此时原栈的最小值。
*/
public class Solution {
Stack<Integer> stackData =new Stack();
Stack<Integer> stackMin =new Stack<Integer>();
public void push(int node) {
stackData.push(node);
if(stackMin.size()==0|| stackMin.peek()> node)
stackMin.push(node);
else
stackMin.push(stackMin.peek());
}
public void pop() {
if(! stackData.isEmpty()){
stackData.pop();
stackMin.pop();
}
}
public int top() {
return stackData.peek();
}
public int min() {
return stackMin.peek();
}
}
29.栈的压入弹出
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
import java.util.ArrayList;
import java.util.Stack;
/**借用一个辅助的栈，遍历压栈顺序，先讲第一个放入栈中，这里是1，
然后判断栈顶元素是不是出栈顺序的第一个元素，这里是4，很显然1≠4，所以我们继续压栈，
直到相等以后开始出栈，出栈一个元素，则将出栈顺序向后移动一位，直到不相等，
这样循环等压栈顺序遍历完成，如果辅助栈还不为空，说明弹出序列不是该栈的弹出顺序。
举例：
入栈1,2,3,4,5
出栈4,5,3,2,1
首先1入辅助栈，此时栈顶1≠4，继续入栈2
此时栈顶2≠4，继续入栈3
此时栈顶3≠4，继续入栈4
此时栈顶4＝4，出栈4，弹出序列向后一位，此时为5，,辅助栈里面是1,2,3
此时栈顶3≠5，继续入栈5
此时栈顶5=5，出栈5,弹出序列向后一位，此时为3，,辅助栈里面是1,2,3
….
依次执行，最后辅助栈为空。如果不为空说明弹出序列不是该栈的弹出顺序。**/
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA ==null ||popA == null || pushA.length ==0 ||popA.length ==0)
return false;
int index =0; //弹出序列的索引
Stack <Integer> stack =new Stack<Integer>();
for(int i =0;i<pushA.length;i++){
stack.push(pushA[i]);
while(! stack.isEmpty() && stack.peek() == popA[index]){
stack.pop();
index++;
} //当栈不为空 且 栈顶元素等于弹出序列元素时候，弹出一个
}
return stack.isEmpty(); //如果辅助栈不为空
}
}
30.和为 S 的两个数
题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
输出描述:
对应每个测试案例，输出两个数，小的先输出
定义两个指针 一个指前 一个指后 指针游走
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> list = new ArrayList<>();
if(array == null || array.length <2)
return list;
int low = 0;
int high = array.length-1;
while(low<high){
int small = array[low];
int big = array[high];
if (small+big == sum){
list.add(small);
list.add(big);
break;
}else if (small+big <sum){
low++;
}else{
high--;
}
}
return list;
}
}
31.左旋转字符串
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
先旋转 前 n 个 和后 n 个 最后整个旋转
public class Solution {
public String LeftRotateString(String str,int n) {
if(str == null || str.trim().length() ==0){
return str;
}
int len =str.length();
n = n % len;
char[] charstr = str.toCharArray();
reverse(charstr,0,n-1);
reverse(charstr,n,len-1);
reverse(charstr,0,len-1);
return String.valueOf(charstr);
}
private void reverse(char[] charstr, int i ,int j){
while(i<j){
char temp = charstr[i];
charstr[i] = charstr[j];
charstr[j] = temp;
i++;
j--;
}
}
}
- 翻转字符串
例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
／／普通方法 将空格把字符串切分然后 倒着写入 StringBuffer 中
public class Solution {
public String ReverseSentence(String str){
if(str == null || str.trim().length() == 0){
return str;
}
String[] strs = str.split(" ");
StringBuffer sb = new StringBuffer();
for(int i = strs.length-1; i>=0; i--){
sb.append(strs[i]);
if(i>0){
sb.append(" ");
}
}
return sb.toString();
}
}
//先将要整个字符串发转 再逐个单词反转
public class Solution {
public String ReverseSentence(String str){
if(str == null || str.length() ==0 || str.trim().length() ==0)
return str;
StringBuffer sb = new StringBuffer();
String re = reverse(str);
String[] s = re.split(" ");
for(int i =0 ; i< s.length -1 ;i++){
sb.append(reverse(s[i])+" ");
}
sb.append(reverse(s[s.length-1]));
return String.valueOf(sb);
}
public String reverse(String str){
StringBuffer sb =new StringBuffer();
for(int i = str.length()-1;i>=0;i--){
sb.append(str.charAt(i));
}
return String.valueOf(sb);
}
}
今天的文章Bulldozer_code分享到此就结束了，感谢您的阅读。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/66068.html
