S1
package SwordToOffer;
/**
* 题目描述
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
* @author panfei
*
*/
public class S1 {
public static void main(String[] args) {
int[][] arr = {{1,2,3},{4,5,6}};
System.out.println(Find(3,arr));
}
public static boolean Find(int target, int [][] array) {
if(array == null || array.length <= 0)
return false;
for(int i =0;i<array.length;i++){
for(int j=0;j<array[i].length;j++){
if(target == array[i][j])
return true;
}
}
return false;
}
}
S2
package SwordToOffer;
/**
* 请实现一个函数，将一个字符串中的空格替换成“%20”。
* 例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
* @author panfei
*
*/
public class S2 {
public static void main(String[] args) {
StringBuffer str = new StringBuffer("We are happy");
System.out.println(replaceSpace(str));
}
public static String replaceSpace(StringBuffer str) {
String s = str.toString();
s = s.replace(" ", "%20");
return s;
}
}
s3
package SwordToOffer;
import java.util.ArrayList;
/**
* 输入一个链表，从尾到头打印链表每个节点的值
*
* @author panfei
*
*/
public class S3 {
ArrayList<Integer> list = new ArrayList<Integer>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if (listNode != null) {
printListFromTailToHead(listNode.next);
list.add(listNode.val);
}
return list;
}
}
s4
package SwordToOffer;
/**
* 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
* 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
*
* @author panfei
*
*/
public class S4 {
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
TreeNode root = reConstructBinaryTree(pre, 0, pre.length - 1, in, 0,
in.length - 1);
return root;
}
private TreeNode reConstructBinaryTree(int[] pre, int startPre, int endPre,
int[] in, int startIn, int endIn) {
if (startPre > endPre || startIn > endIn) {
return null;
}
TreeNode root = new TreeNode(pre[startPre]);
for (int i = startIn; i <= endIn; i++) {
if (in[i] == pre[startPre]) {
root.left = reConstructBinaryTree(pre, startPre + 1, startPre
+ i - startIn, in, startIn, i - 1);
root.right = reConstructBinaryTree(pre, i - startIn + startPre
+ 1, endPre, in, i + 1, endIn);
}
}
return root;
}
}
s5
package SwordToOffer;
import java.util.Stack;
/**
* 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
*
* @author panfei
*
*/
public class S5 {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if (stack1.isEmpty() && stack2.isEmpty()) {
throw new RuntimeException("Queue is Empty");
}
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
s6
package SwordToOffer;
/**
* 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
* 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
*
* @author panfei
*
*/
public class S6 {
public static void main(String[] args) {
int[] arr = { 3, 4, 5, 1, 2 };
System.out.println(minNumberInRotateArray(arr));
}
public static int minNumberInRotateArray(int[] array) {
if (array == null || array.length <= 0)
return 0;
for (int i = 0; i < array.length; i++) {
if (array[i] > array[i + 1]) {
return array[i + 1];
}
}
return 0;
}
}
s7
package SwordToOffer;
import java.util.Scanner;
/**
* 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39
*
* @author panfei
*
*/
public class S7 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// System.out.println(Fibonacci(n));
System.out.println(F2(n));
sc.close();
}
public static int Fibonacci(int n) {
if (n == 1 || n == 2)
return 1;
if (n > 2) {
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
return 0;
}
public static int F2(int n) {
int res = 0;
int a = 1;
int b = 1;
while (n - 2 > 0) {
a = a + b;
b = a - b;
res = a;
n--;
}
return res;
}
}
s8
package SwordToOffer;
/**
* 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
*
* @author panfei
*
*/
public class S8 {
public int JumpFloor(int target) {
if (target == 1 || target == 2) {
return target;
}
return JumpFloor(target - 1) + JumpFloor(target - 2);
}
}
s9
package SwordToOffer;
/**
* 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。 求该青蛙跳上一个n级的台阶总共有多少种跳法。
*
* @author panfei
*
*/
public class S9 {
public int JumpFloorII(int target) {
if (target == 1 || target == 2)
return target;
return 2 * JumpFloorII(target - 1);
}
}
s10
package SwordToOffer;
/**
* 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。 请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
*
* @author panfei
*
*/
public class S10 {
public int RectCover(int target) {
if (target <= 0)
return 0;
if (target == 1 || target == 2)
return target;
return RectCover(target - 1) + RectCover(target - 2);
}
}
s11
package SwordToOffer;
import java.util.Scanner;
/**
* 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
*
* @author panfei
*
*/
public class S11 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(NumberOf1(n));
}
public static int NumberOf1(int n) {
int count = 0;
while (n != 0) {
count++;
n = n & (n - 1);
}
return count;
}
}
s12
package SwordToOffer;
/**
* 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
*
* @author panfei
*
*/
public class S12 {
public static void main(String[] args) {
double base = 2.0d;
int e = -4;
System.out.println(Power(base,e));
}
public static double Power(double base, int exponent) {
double res = 1.0d;
for(int i=0;i<Math.abs(exponent);i++){
res *= base;
}
if(exponent>=0){
return res;
}else{
return 1/res;
}
//更简单的
// return Math.pow(base, exponent);
}
}
s13
package SwordToOffer;
/**
* 输入一个整数数组，实现一个函数来调整该数组中数字的顺序， 使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，
* 并保证奇数和奇数，偶数和偶数之间的相对位置不变。
*
* @author panfei
*
*/
public class S13 {
public static void main(String[] args) {
int[] arr = { 7, 2, 3, 1, 4 };
// 7,2||3,1,4
reOrderArray(arr);
}
public static void reOrderArray(int[] array) {
int mid = array.length / 2;
for (int i = 0; i < mid; i++) {
for (int j = mid; j < array.length; j++) {
if (array[i] % 2 == 0 && array[j] % 2 == 1) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
}
s14
package SwordToOffer;
/**
* 输入一个链表，输出该链表中倒数第k个结点。
*
* @author panfei
*
*/
public class S14 {
public ListNode FindKthToTail(ListNode head, int k) {
ListNode p, q;
p = q = head;
int i = 0;
for (; p != null; i++) {
if (i >= k)
q = q.next;
p = p.next;
}
return i < k ? null : q;
}
}
s15
package SwordToOffer;
/**
* 输入一个链表，反转链表后，输出链表的所有元素。
*
* @author panfei
*
*/
public class S15 {
public ListNode ReverseList(ListNode head) {
if(head == null)
return null;
ListNode pre = null;
ListNode next = null;
while(head!=null){
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}
s16
package SwordToOffer;
/**
* 输入两个单调递增的链表，输出两个链表合成后的链表， 当然我们需要合成后的链表满足单调不减规则。
*
* @author panfei
*
*/
public class S16 {
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;
}
}
}
s17
package SwordToOffer;
/**
* 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
*
* @author panfei
*
*/
public class S17 {
public boolean HasSubtree(TreeNode root1, TreeNode root2) {
if (root1 == null || root2 == null) {
return false;
}
return isSubTree(root1, root2) || isSubTree(root1.left, root2)
|| isSubTree(root1.right, root2);
}
public boolean isSubTree(TreeNode root1, TreeNode root2) {
if (root2 == null)
return true;
if (root1 == null)
return false;
if (root1.val == root2.val) {
return isSubTree(root1.left, root2.left)
&& isSubTree(root1.right, root2.right);
} else {
return false;
}
}
}
s18
package SwordToOffer;
import java.util.Stack;
/**
* 操作给定的二叉树，将其变换为源二叉树的镜像。
*
* @author panfei
*
*/
public class S18 {
public void Mirror(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
if (root == null)
return;
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);
}
}
}
s19
package SwordToOffer;
import java.util.ArrayList;
/**
* 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字， 例如，如果输入如下矩阵： 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.
*
* @author panfei
*
*/
public class S19 {
public static void main(String[] args) {
int[][] arr = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
ArrayList list = printMatrix(arr);
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
}
public static ArrayList<Integer> printMatrix(int[][] matrix) {
ArrayList<Integer> list = new ArrayList<Integer>();
int row = matrix.length;
int col = matrix[0].length;
if (row == 0 || col == 0)
return null;
int top = 0, left = 0, bottom = row - 1, right = col - 1;
while (top <= bottom && left <= right) {
// left-->right
for (int i = left; i <= right; i++) {
list.add(matrix[top][i]);
}
// top-->bottom
for (int i = top + 1; i <= bottom; i++) {
list.add(matrix[i][right]);
}
// right-->left
if (top != bottom) {
for (int i = right - 1; i >= left; i--) {
list.add(matrix[bottom][i]);
}
}
// bottom-->top
if (left != right) {
for (int i = bottom - 1; i > top; i--) {
list.add(matrix[i][left]);
}
}
left++;
top++;
right--;
bottom--;
}
return list;
}
}
s20
package SwordToOffer;
/**
* 定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
*
* @author panfei
*
*/
import java.util.Stack;
public class S20 {
public void push(int node) {
}
public void pop() {
}
public int top() {
return 0;
}
public int min() {
return 0;
}
}
s21
package SwordToOffer;
import java.util.Stack;
/**
* 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
* 假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序， 序列4，5,3,2,1是该压栈序列对应的一个弹出序列，
* 但4,3,5,1,2就不可能是该压栈序列的弹出序列。 （注意：这两个序列的长度是相等的）
*
* @author panfei
*
*/
public class S21 {
public boolean IsPopOrder(int[] pushA, int[] popA) {
if (pushA == null || popA == null)
return false;
Stack<Integer> stack = new Stack<Integer>();
int popIndex = 0;
for (int i = 0; i < pushA.length; i++) {
stack.push(pushA[i]);
// 若栈不为空,且栈顶元素等于弹出序列
while (!stack.isEmpty() && stack.peek() == popA[popIndex]) {
stack.pop();
popIndex++;
}
}
return stack.isEmpty();
}
}
s22
package SwordToOffer;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
/**
* 从上往下打印出二叉树的每个节点，同层节点从左至右打印。(二叉树的层次遍历)
*
* @author panfei
*
*/
public class S22 {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
if (root == null)
return list;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode treeNode = queue.poll();
if (treeNode.left != null) {
queue.offer(treeNode.left);
}
if (treeNode.right != null) {
queue.offer(treeNode.right);
}
list.add(treeNode.val);
}
return list;
}
}
s23
package SwordToOffer;
/**
* 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。 假设输入的数组的任意两个数字都互不相同。
*
* @author panfei
*
*/
public class S23 {
public boolean VerifySquenceOfBST(int[] sequence) {
if (sequence.length == 0)
return false;
if (sequence.length == 1)
return true;
return judge(sequence, 0, sequence.length - 1);
}
public boolean judge(int[] arr, int start, int end) {
if (start >= end)
return true;
int i = end;
// 从后向前找
while (i > start && arr[i - 1] > arr[end])
i--;// 找到比根节点小的点
for (int j = start; j < i - 1; j++) {
if (arr[j] > arr[end]) {
return false;
}
}
return judge(arr, start, i - 1) && judge(arr, i, end - 1);
}
}
s24
package SwordToOffer;
import java.util.ArrayList;
/**
* 输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径. 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
*
* @author panfei
*
*/
public class S24 {
public ArrayList<Integer> list = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> allList = new ArrayList<ArrayList<Integer>>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
if (root == null)
return allList;
list.add(root.val);
target -= root.val;
if (target == 0 && root.left == null && root.right == null) {
allList.add(new ArrayList<Integer>(list));
}
FindPath(root.left, target);
FindPath(root.right, target);
list.remove(list.size() - 1);
return allList;
}
}
s25
package SwordToOffer;
/**
* 输入一个复杂链表（每个节点中有节点值，以及两个指针， 一个指向下一个节点，另一个特殊指针指向任意一个节点）， 返回结果为复制后复杂链表的head。
* （注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
*
* @author panfei
*
*/
public class S25 {
public RandomListNode Clone(RandomListNode pHead) {
if (pHead == null)
return null;
// 开辟一个新节点
RandomListNode pCloneHead = new RandomListNode(pHead.label);
pCloneHead.next = pHead.next;
pCloneHead.random = pHead.random;
// 递归其他节点
pCloneHead.next = Clone(pHead.next);
return pCloneHead;
}
class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
public RandomListNode(int label) {
this.label = label;
}
}
}
s26
package SwordToOffer;
/**
* 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。 要求不能创建任何新的结点，只能调整树中结点指针的指向。
*
* @author panfei
*
*/
public class S26 {
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree == null)
return null;
if (pRootOfTree.left == null && pRootOfTree.right == null) {
return pRootOfTree;
}
// 将左子树构造成双链表,并返回链表头节点
TreeNode left = Convert(pRootOfTree.left);
TreeNode p = left;
// 定位至左子树双联表最后一个节点
while (p != null && p.right != null) {
p = p.right;
}
// 如果左子树链表不为空的话,将当前root追加到左子树链表
if (left != null) {
p.right = pRootOfTree;
pRootOfTree.left = p;
}
// 将右子树构造成双联表,并返回链表头节点
TreeNode right = Convert(pRootOfTree.right);
// 如果右子树链表不为空的话，将该链表追加到root节点之后
if (right != null) {
right.left = pRootOfTree;
pRootOfTree.right = right;
}
return left != null ? left : pRootOfTree;
}
}
s27
package SwordToOffer;
import java.util.ArrayList;
import java.util.Collections;
/**
* 输入一个字符串(长度不超过9(可能有字符重复),字符只包括大小写字母),按字典序打印出该字符串中字符的所有排列。
* 例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
*
* @author panfei
*
*/
public class S27 {
public ArrayList<String> Permutation(String str) {
ArrayList<String> res = new ArrayList<String>();
if (str != null && str.length() > 0) {
PermutationHelper(str.toCharArray(), 0, res);
Collections.sort(res);
}
return res;
}
public static void PermutationHelper(char[] c, int i, ArrayList<String> list) {
if (i == c.length - 1) {// 解空间的一个叶节点
list.add(String.valueOf(c));// 找到一个解
} else {
for (int j = i; j < c.length; j++) {
if (j == i || c[j] != c[i]) {
swap(c, i, j);
PermutationHelper(c, i + 1, list);
swap(c, i, j);// 复位
}
}
}
}
public static void swap(char[] c, int i, int j) {
char temp = c[i];
c[i] = c[j];
c[j] = temp;
}
}
s28
package SwordToOffer;
/*
* 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
* 例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
* 由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
*
* --------其他思路:先排序,若存在符合条件的数,则一定是数组中间的那个数
*/
public class S28 {
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 2, 2, 2, 2, 5, 4, 2 };
System.out.println(MoreThanHalfNum_Solution(arr));
}
// O(n)解法
public static int MoreThanHalfNum_Solution(int[] array) {
if (array.length == 0)
return 0;
int len = array.length;
int num = array[0];
int count = 1;
for (int i = 1; i < len; i++) {
if (num == array[i]) {
count++;
} else {
count--;
}
if (count == 0) {
num = array[i];
count = 1;
}
}
count = 0;
for (int i = 0; i < len; i++) {
if (num == array[i])
count++;
}
if (2 * count > len)
return num;
return 0;
}
}
s29
package SwordToOffer;
import java.util.ArrayList;
import java.util.Arrays;
/**
* 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
*
* @author panfei
*
*/
public class S29 {
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> list = new ArrayList<Integer>();
if (input.length < k)
return list;
Arrays.sort(input);
for (int i = 0; i < k; i++) {
list.add(input[i]);
}
return list;
}
}
s30
package SwordToOffer;
/**
* HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。 今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,
* 当向量全为正数的时候 ,问题很好解决。但是, 如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？
* 例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。 你会不会被他忽悠住？(子向量的长度至少是1)
*
* @author panfei
*
*/
public class S30 {
public static void main(String[] args) {
int[] arr = { 6, -3, -2, 7, -15, 1, 2, 2 };
System.out.println(FindGreatestSumOfSubArray(arr));
}
//一维dp
public static int FindGreatestSumOfSubArray(int[] array) {
if (array == null || array.length <= 0) {
return 0;
}
int sum = array[0];
int temp = array[0];
for (int i = 1; i < array.length; i++) {
temp = temp < 0 ? array[i] : temp + array[i];
sum = temp > sum ? temp : sum;
}
return sum;
}
}
s31
package SwordToOffer;
/**
* 求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？
* 为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次, 但是对于后面问题他就没辙了。
* ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。
*
* @author panfei
*
*备注：给一个最简单的代码，具体解释可以去leetcode上面去看。
*https://leetcode.com/discuss/44281/4-lines-o-log-n-c-java-python
*/
public class S31 {
public int NumberOf1Between1AndN_Solution(int n) {
int ones = 0;
for (long m = 1; m <= n; m *= 10) {
ones += (n / m + 8) / 10 * m + (n / m % 10 == 1 ? n % m + 1 : 0);
}
return ones;
}
}
s32
package SwordToOffer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
/**
* 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
* 例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
*
* @author panfei
*
*/
public class S32 {
public static void main(String[] args) {
int[] arr = { 3, 32, 321 };
System.err.println(PrintMinNumber(arr));
}
public static String PrintMinNumber(int[] numbers) {
String res = "";
ArrayList<Integer> list = new ArrayList<Integer>();
int len = numbers.length;
for (int i = 0; i < len; i++) {
list.add(numbers[i]);
}
Collections.sort(list, new Comparator<Integer>() {
public int compare(Integer str1, Integer str2) {
String s1 = str1 + "" + str2;
String s2 = str2 + "" + str1;
return s1.compareTo(s2);
}
});
for (int i : list) {
res += i;
}
return res;
}
}
s33
package SwordToOffer;
import java.util.ArrayList;
/**
* 把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数， 但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。
* 求按从小到大的顺序的第N个丑数
*
* @author panfei
*
*/
public class S33 {
public int GetUglyNumber_Solution(int index) {
if (index <= 0)
return 0;
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(1);
int q2 = 0, q3 = 0, q5 = 0;
while (list.size() < index) {
int m2 = list.get(q2) * 2;
int m3 = list.get(q3) * 3;
int m5 = list.get(q5) * 5;
int min = Math.min(m2, Math.min(m3, m5));
list.add(min);
if (min == m2)
q2++;
if (min == m3)
q3++;
if (min == m5)
q5++;
}
return list.get(list.size() - 1);
}
}
s34
package SwordToOffer;
/**
* 在一个字符串(1<=字符串长度<=10000，全部由字母组成)中 找到第一个只出现一次的字符,并返回它的位置
*
* @author panfei
*
*/
public class S34 {
public int FirstNotRepeatingChar(String str) {
char[] c = str.toCharArray();
int[] a = new int['z' + 1];
for (char ch : c) {
a[(int) ch]++;
}
for (int i = 0; i < c.length; i++) {
if (a[(int) c[i]] == 1) {
return i;
}
}
return -1;
}
}
s35
package SwordToOffer;
/**
* 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
* 输入一个数组,求出这个数组中的逆序对的总数P。
* 并将P对1000000007取模的结果输出。 即输出P%1000000007
* @author panfei
*
*/
public class S35 {
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6,7,0};
System.out.println(InversePairs(arr));
}
public static int InversePairs(int [] array) {
return 0;
}
}
s36
package SwordToOffer;
/**
* 输入两个链表，找出它们的第一个公共结点。
*
* @author panfei
*
*/
public class S36 {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
int len1 = getLength(pHead1);
int len2 = getLength(pHead2);
if (len1 > len2) {
pHead1 = clearGap(pHead1, len1 - len2);
} else {
pHead2 = clearGap(pHead2, len2 - len1);
}
while (pHead1 != null) {
if (pHead1 == pHead2)
return pHead1;
pHead1 = pHead1.next;
pHead2 = pHead2.next;
}
return null;
}
public ListNode clearGap(ListNode node, int gap) {
while (gap-- != 0) {
node = node.next;
}
return node;
}
public int getLength(ListNode pHead) {
if (pHead == null)
return 0;
int sum = 1;
while (pHead.next != null)
sum++;
return sum;
}
}
s37
package SwordToOffer;
/**
* 统计一个数字在排序数组中出现的次数。
*
* @author panfei
*
*/
public class S37 {
public int GetNumberOfK(int[] array, int k) {
int count = 0;
if (array == null || array.length <= 0)
return 0;
for (int i = 0; i < array.length; i++) {
if (k == array[i])
count++;
}
return count;
}
}
s38
package SwordToOffer;
/**
* 输入一棵二叉树，求该树的深度。 从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径， 最长路径的长度为树的深度。
*
* @author panfei
*
*/
public class S38 {
public int TreeDepth(TreeNode root) {
if (root == null)
return 0;
return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1;
}
}
s39
package SwordToOffer;
/**
* 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
*
* @author panfei
*
*/
public class S39 {
public boolean isBalanced = true;
public boolean IsBalanced_Solution(TreeNode root) {
getDepth(root);
return isBalanced;
}
public int getDepth(TreeNode root) {
if (root == null)
return 0;
int left = getDepth(root.left);
int right = getDepth(root.right);
if (Math.abs(left - right) > 1) {
isBalanced = false;
}
return right > left ? right + 1 : left + 1;
}
}
s40
package SwordToOffer;
/**
* 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
*
* @author panfei
*
*/
public class S40 {
// num1,num2分别为长度为1的数组。传出参数
// 将num1[0],num2[0]设置为返回结果
public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
if (array == null || array.length <= 1) {
num1[0] = num1[0] = 0;
return;
}
int len = array.length, index = 0, sum = 0;
for (int i = 0; i < len; i++) {
sum ^= array[i];
}
for (index = 0; index < 32; index++) {
if ((sum & (1 << index)) != 0)
break;
}
for (int i = 0; i < len; i++) {
if ((array[i] & (1 << index)) != 0) {
num2[0] ^= array[i];
} else {
num1[0] ^= array[i];
}
}
}
/**
* 数组a中只有一个数出现一次，其他数都出现了2次，找出这个数字
*/
public static int findForm(int[] a) {
int len = a.length, res = 0;
for (int i = 0; i < a.length; i++) {
res = res ^ a[i];
}
return res;
}
/**
* 数组a中只有一个数出现一次，其他数字都出现了3次，找出这个数字
*/
public static int getNum(int[] arr) {
int[] bits = new int[32];
int len = arr.length;
for (int i = 0; i < len; i++) {
for (int j = 0; j < 32; j++) {
bits[j] = bits[j] + ((arr[i] >>> j) & 1);
}
}
int res = 0;
for (int i = 0; i < 32; i++) {
if (bits[i] % 3 != 0) {
res = res | (1 << i);
}
}
return res;
}
}
s41
package SwordToOffer;
import java.util.ArrayList;
/**
* 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。
* 但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。
* 没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good
* Luck!
*
* @author panfei
*
*/
public class S41 {
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> allList = new ArrayList<ArrayList<Integer>>();
if (sum <= 1)
return allList;
int start = 1, end = 2;
while (start != (sum + 1) / 2) {
int cur = getSum(start, end);
if (cur == sum) {
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = start; i <= end; i++) {
list.add(i);
}
allList.add(list);
start++;
end++;
} else if (cur < sum) {
end++;
} else {
start++;
}
}
return allList;
}
public int getSum(int start, int end) {
int sum = 0;
for (int i = start; i <= end; i++) {
sum += i;
}
return sum;
}
}
s42
package SwordToOffer;
import java.util.ArrayList;
/**
* 输入一个递增排序的数组和一个数字S，在数组中查找两个数， 是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
*
* @author panfei
*
*/
public class S42 {
public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
ArrayList<Integer> list = new ArrayList<Integer>();
if (array == null || array.length <= 0) {
return list;
}
int start = 0, end = array.length - 1;
while (start < end) {
if (array[start] + array[end] == sum) {
list.add(array[start]);
list.add(array[end]);
return list;
} else if (array[start] + array[end] > sum) {
end--;
} else {
start++;
}
}
return list;
}
}
s43
package SwordToOffer;
/**
* 汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。
* 对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。
* 例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
*
* @author panfei
*
*/
public class S43 {
public static void main(String[] args) {
String str = "abcXYZdef";
System.out.println(LeftRotateString(str, 3));
}
public static String LeftRotateString(String str, int n) {
String res = "";
if (str == null || str.length() <= 0)
return res;
String s1 = str.substring(0, n);
String s2 = str.substring(n, str.length());
res = s2 + s1;
return res;
}
}
s44
package SwordToOffer;
/**
* 牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。
* 同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。 例如，“student. a am
* I”。后来才意识到，这家伙原来把句子单词的顺序翻转了， 正确的句子应该是“I am a student.”。
* Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
*
* @author panfei
*
*/
public class S44 {
public static void main(String[] args) {
String str = "I am a student.";
String s1 = "";
System.out.println(ReverseSentence(s1));
}
public static String ReverseSentence(String str) {
if (str == null || str.length() <= 0)
return str;
String[] s = str.split(" ");
StringBuffer sb = new StringBuffer();
for (int i = s.length - 1; i > 0; i--) {
sb.append(s[i]).append(" ");
}
sb.append(s[0]);
return sb.toString();
}
}
s45
package SwordToOffer;
/**
* LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...
* 他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh
* My God!”不是顺子.....LL不高兴了,他想了想,决定大\小
* 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So
* Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何。为了方便起见,你可以认为大小王是0。
*
* @author panfei
*
*/
public class S45 {
/**
* 需要满足:1.除0外没有重复的数 2.max - min < 5
*
* @param numbers
* @return
*/
public boolean isContinuous(int[] numbers) {
if (numbers == null || numbers.length <= 0)
return false;
int min = 14;
int max = -1;
int[] d = new int[14];
d[0] = -5;
int len = numbers.length;
for (int i = 0; i < len; i++) {
d[numbers[i]]++;
if (numbers[i] == 0) {
continue;
}
if (d[numbers[i]] > 1) {
return false;
}
if (numbers[i] > max) {
max = numbers[i];
}
if (numbers[i] < min) {
min = numbers[i];
}
}
if (max - min < 5)
return true;
return false;
}
}
s46
package SwordToOffer;
/**
* 每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。 HF作为牛客的资深元老,自然也准备了一些小游戏。
* 其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。 然后,他随机指定一个数m,让编号为0的小朋友开始报数。
* 每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,
* 从他的下一个小朋友开始,继续0...m-1报数....这样下去....
* 直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。
* 请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
*
* @author panfei
*
*/
public class S46 {
public int LastRemaining_Solution(int n, int m) {
if (n == 0)
return -1;
if (n == 1)
return 0;
else {
return (LastRemaining_Solution(n - 1, m) + m) % n;
}
}
}
s47
package SwordToOffer;
/**
* 求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
*
* @author panfei
*
*/
public class S47 {
/**
*
解题思路：
* 1.需利用逻辑与的短路特性实现递归终止。
* 2.当n==0时，(n>0)&&((sum+=Sum_Solution(n-1))>0)只执行前面的判断，为false，然后直接返回0；
* 3.当n>0时，执行sum+=Sum_Solution(n-1)，实现递归计算Sum_Solution(n)。
*
* @param n
* @return
*/
public int Sum_Solution(int n) {
int res = n;
boolean ans = (n > 0) && ((res += Sum_Solution(n - 1)) > 0);
return res;
}
}
s48
package SwordToOffer;
/**
* 写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号
*
* @author panfei
*
*/
public class S48 {
public int Add(int num1, int num2) {
while (num2 != 0) {
int temp = num1 ^ num2;
num2 = (num1 & num2) << 1;
num1 = temp;
}
return num1;
}
/**
* 首先看十进制是如何做的： 5+7=12，三步走 第一步：相加各位的值，不算进位，得到2。 第二步：计算进位值，得到10.
* 如果这一步的进位值为0，那么第一步得到的值就是最终结果。
*
* 第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。
*
* 同样我们可以用三步走的方式计算二进制值相加： 5-101，7-111
* 第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。
*
* 第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，(101&111)<<1。
*
* 第三步重复上述两步， 各位相加 010^1010=1000，进位值为100=(010&1010)<<1。 继续重复上述两步：1000^100 =
* 1100，进位值为0，跳出循环，1100为最终结果。
*/
}
s49
/**
* 将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
*
* @author panfei
*
*/
public class S49 {
public int StrToInt(String str) {
char[] c = str.toCharArray();
return 0;
}
}
s50
package SwordToOffer;
/**
* 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。
* 也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
* 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
*/
public class S50 {
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
// 这里要特别注意~返回任意重复的一个，赋值duplication[0]
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
public boolean duplicate(int numbers[], int length, int[] duplication) {
boolean[] k = new boolean[length];
for (int i = 0; i < k.length; i++) {
if (k[numbers[i]] == true) {
duplication[0] = numbers[i];
return true;
}
k[numbers[i]] = true;
}
return false;
}
}
s51
package SwordToOffer;
/**
* 给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。
* <p>
* 思路
* B[i]的值可以看作下图的矩阵中每行的乘积。
* 下三角用连乘可以很容求得，上三角，从下向上也是连乘。
* 因此我们的思路就很清晰了，先算下三角中的连乘，即我们先算出B[i]中的一部分，然后倒过来按上三角中的分布规律，把另一部分也乘进去。
*/
public class S51 {
public int[] multiply(int[] A) {
int[] B = new int[A.length];
if (A.length != 0) {
B[0] = 1;
//计算下三角连乘
for (int i = 1; i < A.length; i++) {
B[i] = B[i - 1] * A[i - 1];
}
int temp = 1;
//计算上三角
for (int j = A.length - 2; j >= 0; j--) {
temp *= A[j + 1];
B[j] *= temp;
}
}
return B;
}
}
s52
package SwordToOffer;
/**
* 请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。
* 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
* <p>
* 思路:
* <p>
* 当模式中的第二个字符不是“*”时：
* 1、如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。
* 2、如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。
* <p>
* 而当模式中的第二个字符是“*”时：
* 如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方式：
* 1、模式后移2字符，相当于x*被忽略；
* 2、字符串后移1字符，模式后移2字符；
* 3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位；
*/
public class S52 {
public boolean match(char[] str, char[] pattern) {
if (str == null || pattern == null)
return false;
int strIndex = 0;
int patternIndex = 0;
return matchCore(str, strIndex, pattern, patternIndex);
}
private boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
//有效性监测,str到尾,pattern到尾
if (strIndex == str.length && patternIndex == pattern.length) {
return true;
}
//pattern先到尾失败
if (strIndex != str.length && patternIndex == pattern.length) {
return false;
}
//模式第二个是*,且字符串第一个和模式第一个匹配,分三种匹配模式,如不匹配,，模式后移
if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length)) {
return matchCore(str, strIndex, pattern, patternIndex + 2)//模式后移2，视为x*匹配0个字符
|| matchCore(str, strIndex + 1, pattern, patternIndex + 2)//视为模式匹配1个字符
|| matchCore(str, strIndex + 1, pattern, patternIndex);//*匹配1个，再匹配str中的下一个
} else {
return matchCore(str, strIndex, pattern, patternIndex + 2);
}
}
//模式第2个不是*，且字符串第1个跟模式第1个匹配，则都后移1位，否则直接返回false
if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length)) {
return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
}
return false;
}
}
to be continued...
