S1
package SwordToOffer;
/**
* 題目描述
在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序交惯，每一列都按照從上到下遞增的順序排序。
請(qǐng)完成一個(gè)函數(shù)卸夕，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)睦袖。
* @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;
/**
* 請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)葵第，將一個(gè)字符串中的空格替換成“%20”。
* 例如纪岁，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為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;
/**
* 輸入一個(gè)鏈表则果，從尾到頭打印鏈表每個(gè)節(jié)點(diǎn)的值
*
* @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;
/**
* 輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果幔翰，請(qǐng)重建出該二叉樹。 假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字西壮。
* 例如輸入前序遍歷序列{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;
/**
* 用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列款青，完成隊(duì)列的Push和Pop操作做修。 隊(duì)列中的元素為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;
/**
* 把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾抡草，我們稱之為數(shù)組的旋轉(zhuǎn)饰及。 輸入一個(gè)非遞減排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素渠牲。
* 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)旋炒，該數(shù)組的最小值為1步悠。 NOTE：給出的所有元素都大于0签杈，若數(shù)組大小為0，請(qǐng)返回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;
/**
* 大家都知道斐波那契數(shù)列答姥，現(xiàn)在要求輸入一個(gè)整數(shù)n，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)谚咬。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級(jí)臺(tái)階鹦付，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法择卦。
*
* @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級(jí)臺(tái)階敲长，也可以跳上2級(jí)……它也可以跳上n級(jí)郎嫁。 求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。
*
* @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的小矩形橫著或者豎著去覆蓋更大的矩形祈噪。 請(qǐng)問用n個(gè)2*1的小矩形無(wú)重疊地覆蓋一個(gè)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;
/**
* 輸入一個(gè)整數(shù)辑鲤，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)盔腔。其中負(fù)數(shù)用補(bǔ)碼表示。
*
* @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;
/**
* 給定一個(gè)double類型的浮點(diǎn)數(shù)base和int類型的整數(shù)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;
}
//更簡(jiǎn)單的
// return Math.pow(base, exponent);
}
}
s13
package SwordToOffer;
/**
* 輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來(lái)調(diào)整該數(shù)組中數(shù)字的順序宁赤， 使得所有的奇數(shù)位于數(shù)組的前半部分舀透，所有的偶數(shù)位于位于數(shù)組的后半部分，
* 并保證奇數(shù)和奇數(shù)礁击，偶數(shù)和偶數(shù)之間的相對(duì)位置不變盐杂。
*
* @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;
/**
* 輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)哆窿。
*
* @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;
/**
* 輸入一個(gè)鏈表链烈，反轉(zhuǎn)鏈表后，輸出鏈表的所有元素挚躯。
*
* @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;
/**
* 輸入兩個(gè)單調(diào)遞增的鏈表强衡，輸出兩個(gè)鏈表合成后的鏈表， 當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則码荔。
*
* @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的子結(jié)構(gòu)缩搅。（ps：我們約定空樹不是任意一個(gè)樹的子結(jié)構(gòu)）
*
* @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;
/**
* 輸入一個(gè)矩陣硼瓣，按照從外向里以順時(shí)針的順序依次打印出每一個(gè)數(shù)字究飞， 例如，如果輸入如下矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14
* 15 16 則依次打印出數(shù)字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;
/**
* 定義棧的數(shù)據(jù)結(jié)構(gòu)堂鲤，請(qǐng)?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧最小元素的min函數(shù)亿傅。
*
* @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;
/**
* 輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序瘟栖，請(qǐng)判斷第二個(gè)序列是否為該棧的彈出順序葵擎。
* 假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序半哟， 序列4酬滤，5,3,2,1是該壓棧序列對(duì)應(yīng)的一個(gè)彈出序列签餐，
* 但4,3,5,1,2就不可能是該壓棧序列的彈出序列。 （注意：這兩個(gè)序列的長(zhǎng)度是相等的）
*
* @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;
/**
* 從上往下打印出二叉樹的每個(gè)節(jié)點(diǎn)盯串，同層節(jié)點(diǎn)從左至右打印贱田。(二叉樹的層次遍歷)
*
* @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;
/**
* 輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果嘴脾。如果是則輸出Yes,否則輸出No男摧。 假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。
*
* @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--;// 找到比根節(jié)點(diǎn)小的點(diǎn)
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;
/**
* 輸入一顆二叉樹和一個(gè)整數(shù)译打，打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑. 路徑定義為從樹的根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑耗拓。
*
* @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;
/**
* 輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值，以及兩個(gè)指針奏司， 一個(gè)指向下一個(gè)節(jié)點(diǎn)乔询，另一個(gè)特殊指針指向任意一個(gè)節(jié)點(diǎn)）， 返回結(jié)果為復(fù)制后復(fù)雜鏈表的head韵洋。
* （注意竿刁，輸出結(jié)果中請(qǐng)不要返回參數(shù)中的節(jié)點(diǎn)引用，否則判題程序會(huì)直接返回空）
*
* @author panfei
*
*/
public class S25 {
public RandomListNode Clone(RandomListNode pHead) {
if (pHead == null)
return null;
// 開辟一個(gè)新節(jié)點(diǎn)
RandomListNode pCloneHead = new RandomListNode(pHead.label);
pCloneHead.next = pHead.next;
pCloneHead.random = pHead.random;
// 遞歸其他節(jié)點(diǎn)
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;
/**
* 輸入一棵二叉搜索樹搪缨，將該二叉搜索樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表食拜。 要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹中結(jié)點(diǎn)指針的指向副编。
*
* @author panfei
*
*/
public class S26 {
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree == null)
return null;
if (pRootOfTree.left == null && pRootOfTree.right == null) {
return pRootOfTree;
}
// 將左子樹構(gòu)造成雙鏈表,并返回鏈表頭節(jié)點(diǎn)
TreeNode left = Convert(pRootOfTree.left);
TreeNode p = left;
// 定位至左子樹雙聯(lián)表最后一個(gè)節(jié)點(diǎn)
while (p != null && p.right != null) {
p = p.right;
}
// 如果左子樹鏈表不為空的話,將當(dāng)前root追加到左子樹鏈表
if (left != null) {
p.right = pRootOfTree;
pRootOfTree.left = p;
}
// 將右子樹構(gòu)造成雙聯(lián)表,并返回鏈表頭節(jié)點(diǎn)
TreeNode right = Convert(pRootOfTree.right);
// 如果右子樹鏈表不為空的話负甸，將該鏈表追加到root節(jié)點(diǎn)之后
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;
/**
* 輸入一個(gè)字符串(長(zhǎng)度不超過9(可能有字符重復(fù)),字符只包括大小寫字母),按字典序打印出該字符串中字符的所有排列。
* 例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來(lái)的所有字符串a(chǎn)bc,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) {// 解空間的一個(gè)葉節(jié)點(diǎn)
list.add(String.valueOf(c));// 找到一個(gè)解
} 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);// 復(fù)位
}
}
}
}
public static void swap(char[] c, int i, int j) {
char temp = c[i];
c[i] = c[j];
c[j] = temp;
}
}
s28
package SwordToOffer;
/*
* 數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長(zhǎng)度的一半呻待，請(qǐng)找出這個(gè)數(shù)字。
* 例如輸入一個(gè)長(zhǎng)度為9的數(shù)組{1,2,3,2,2,2,5,4,2}队腐。
* 由于數(shù)字2在數(shù)組中出現(xiàn)了5次蚕捉，超過數(shù)組長(zhǎng)度的一半，因此輸出2柴淘。如果不存在則輸出0迫淹。
*
* --------其他思路:先排序,若存在符合條件的數(shù),則一定是數(shù)組中間的那個(gè)數(shù)
*/
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個(gè)整數(shù)，找出其中最小的K個(gè)數(shù)悠就。例如輸入4,5,1,6,2,7,3,8這8個(gè)數(shù)字千绪，則最小的4個(gè)數(shù)字是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偶爾會(huì)拿些專業(yè)問題來(lái)忽悠那些非計(jì)算機(jī)專業(yè)的同學(xué)梗脾。 今天測(cè)試組開完會(huì)后,他又發(fā)話了:在古老的一維模式識(shí)別中,常常需要計(jì)算連續(xù)子向量的最大和,
* 當(dāng)向量全為正數(shù)的時(shí)候 ,問題很好解決。但是, 如果向量中包含負(fù)數(shù),是否應(yīng)該包含某個(gè)負(fù)數(shù),并期望旁邊的正數(shù)會(huì)彌補(bǔ)它呢盹靴？
* 例如:{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個(gè)開始,到第3個(gè)為止)炸茧。 你會(huì)不會(huì)被他忽悠兹鸶尽？(子向量的長(zhǎng)度至少是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的整數(shù)中1出現(xiàn)的次數(shù),并算出100~1300的整數(shù)中1出現(xiàn)的次數(shù)梭冠？
* 為此他特別數(shù)了一下1~13中包含1的數(shù)字有1辕狰、10、11控漠、12蔓倍、13因此共出現(xiàn)6次, 但是對(duì)于后面問題他就沒轍了。
* ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負(fù)整數(shù)區(qū)間中1出現(xiàn)的次數(shù)盐捷。
*
* @author panfei
*
*備注：給一個(gè)最簡(jiǎn)單的代碼偶翅，具體解釋可以去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;
/**
* 輸入一個(gè)正整數(shù)數(shù)組碉渡，把數(shù)組里所有數(shù)字拼接起來(lái)排成一個(gè)數(shù)聚谁，打印能拼接出的所有數(shù)字中最小的一個(gè)。
* 例如輸入數(shù)組{3滞诺，32形导，321}，則打印出這三個(gè)數(shù)字能排成的最小數(shù)字為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的數(shù)稱作丑數(shù)（Ugly Number）。例如6淋叶、8都是丑數(shù)憔披， 但14不是，因?yàn)樗蜃?爸吮。 習(xí)慣上我們把1當(dāng)做是第一個(gè)丑數(shù)芬膝。
* 求按從小到大的順序的第N個(gè)丑數(shù)
*
* @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;
/**
* 在一個(gè)字符串(1<=字符串長(zhǎng)度<=10000，全部由字母組成)中 找到第一個(gè)只出現(xiàn)一次的字符,并返回它的位置
*
* @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;
/**
* 在數(shù)組中的兩個(gè)數(shù)字形娇，如果前面一個(gè)數(shù)字大于后面的數(shù)字锰霜，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)Α? * 輸入一個(gè)數(shù)組,求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)P。
* 并將P對(duì)1000000007取模的結(jié)果輸出桐早。 即輸出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;
/**
* 輸入兩個(gè)鏈表癣缅，找出它們的第一個(gè)公共結(jié)點(diǎn)。
*
* @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;
/**
* 統(tǒng)計(jì)一個(gè)數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)哄酝。
*
* @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;
/**
* 輸入一棵二叉樹友存，求該樹的深度。 從根結(jié)點(diǎn)到葉結(jié)點(diǎn)依次經(jīng)過的結(jié)點(diǎn)（含根陶衅、葉結(jié)點(diǎn)）形成樹的一條路徑屡立， 最長(zhǎng)路徑的長(zhǎng)度為樹的深度。
*
* @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;
/**
* 一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外勇皇，其他的數(shù)字都出現(xiàn)了兩次。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字焚刺。
*
* @author panfei
*
*/
public class S40 {
// num1,num2分別為長(zhǎng)度為1的數(shù)組敛摘。傳出參數(shù)
// 將num1[0],num2[0]設(shè)置為返回結(jié)果
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];
}
}
}
/**
* 數(shù)組a中只有一個(gè)數(shù)出現(xiàn)一次，其他數(shù)都出現(xiàn)了2次乳愉，找出這個(gè)數(shù)字
*/
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;
}
/**
* 數(shù)組a中只有一個(gè)數(shù)出現(xiàn)一次兄淫，其他數(shù)字都出現(xiàn)了3次，找出這個(gè)數(shù)字
*/
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;
/**
* 小明很喜歡數(shù)學(xué),有一天他在做數(shù)學(xué)作業(yè)時(shí),要求計(jì)算出9~16的和,他馬上就寫出了正確答案是100蔓姚。
* 但是他并不滿足于此,他在想究竟有多少種連續(xù)的正數(shù)序列的和為100(至少包括兩個(gè)數(shù))拖叙。
* 沒多久,他就得到另一組連續(xù)正數(shù)和為100的序列:18,19,20,21,22。現(xiàn)在把問題交給你,你能不能也很快的找出所有和為S的連續(xù)正數(shù)序列? 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;
/**
* 輸入一個(gè)遞增排序的數(shù)組和一個(gè)數(shù)字S赂乐，在數(shù)組中查找兩個(gè)數(shù)薯鳍， 是的他們的和正好是S，如果有多對(duì)數(shù)字的和等于S挨措，輸出兩個(gè)數(shù)的乘積最小的挖滤。
*
* @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;
/**
* 匯編語(yǔ)言中有一種移位指令叫做循環(huán)左移（ROL），現(xiàn)在有個(gè)簡(jiǎn)單的任務(wù)浅役，就是用字符串模擬這個(gè)指令的運(yùn)算結(jié)果斩松。
* 對(duì)于一個(gè)給定的字符序列S，請(qǐng)你把其循環(huán)左移K位后的序列輸出觉既。
* 例如惧盹，字符序列S=”abcXYZdef”,要求輸出循環(huán)左移3位后的結(jié)果，即“XYZdefabc”瞪讼。是不是很簡(jiǎn)單钧椰？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;
/**
* 诺障迹客最近來(lái)了一個(gè)新員工Fish，每天早晨總是會(huì)拿著一本英文雜志希柿，寫些句子在本子上诊沪。
* 同事Cat對(duì)Fish寫的內(nèi)容頗感興趣，有一天他向Fish借來(lái)翻看曾撤，但卻讀不懂它的意思端姚。 例如，“student. a am
* I”挤悉。后來(lái)才意識(shí)到渐裸，這家伙原來(lái)把句子單詞的順序翻轉(zhuǎn)了， 正確的句子應(yīng)該是“I am a student.”。
* Cat對(duì)一一的翻轉(zhuǎn)這些單詞順序可不在行橄仆，你能幫助他么？
*
* @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今天心情特別好,因?yàn)樗ベI了一副撲克牌,發(fā)現(xiàn)里面居然有2個(gè)大王,2個(gè)小王(一副牌原本是54張^_^)...
* 他隨機(jī)從中抽出了5張牌,想測(cè)測(cè)自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買體育彩票,嘿嘿Ｐ普丁盆顾！“紅心A,黑桃3,小王,大王,方片5”,“Oh
* My God!”不是順子.....LL不高興了,他想了想,決定大\小
* 王可以看成任何數(shù)字,并且A看作1,J為11,Q為12,K為13。上面的5張牌就可以變成“1,2,3,4,5”(大小王分別看作2和4),“So
* Lucky!”畏梆。LL決定去買體育彩票啦您宪。 現(xiàn)在,要求你使用這幅牌模擬上面的過程,然后告訴我們LL的運(yùn)氣如何。為了方便起見,你可以認(rèn)為大小王是0奠涌。
*
* @author panfei
*
*/
public class S45 {
/**
* 需要滿足:1.除0外沒有重復(fù)的數(shù) 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;
/**
* 每年六一兒童節(jié),畔芫蓿客都會(huì)準(zhǔn)備一些小禮物去看望孤兒院的小朋友,今年亦是如此。 HF作為帕锍客的資深元老,自然也準(zhǔn)備了一些小游戲捏卓。
* 其中,有個(gè)游戲是這樣的:首先,讓小朋友們圍成一個(gè)大圈。 然后,他隨機(jī)指定一個(gè)數(shù)m,讓編號(hào)為0的小朋友開始報(bào)數(shù)慈格。
* 每次喊到m-1的那個(gè)小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,
* 從他的下一個(gè)小朋友開始,繼續(xù)0...m-1報(bào)數(shù)....這樣下去....
* 直到剩下最后一個(gè)小朋友,可以不用表演,并且拿到诺∏纾客名貴的“名偵探柯南”典藏版(名額有限哦!!^_^)。
* 請(qǐng)你試著想下,哪個(gè)小朋友會(huì)得到這份禮品呢浴捆？(注：小朋友的編號(hào)是從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等關(guān)鍵字及條件判斷語(yǔ)句（A?B:C）。
*
* @author panfei
*
*/
public class S47 {
/**
*
解題思路：
* 1.需利用邏輯與的短路特性實(shí)現(xiàn)遞歸終止窝撵。
* 2.當(dāng)n==0時(shí)科阎，(n>0)&&((sum+=Sum_Solution(n-1))>0)只執(zhí)行前面的判斷，為false忿族，然后直接返回0锣笨；
* 3.當(dāng)n>0時(shí)，執(zhí)行sum+=Sum_Solution(n-1)道批，實(shí)現(xiàn)遞歸計(jì)算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;
/**
* 寫一個(gè)函數(shù)，求兩個(gè)整數(shù)之和隆豹，要求在函數(shù)體內(nèi)不得使用+椭岩、-、*、/四則運(yùn)算符號(hào)
*
* @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;
}
/**
* 首先看十進(jìn)制是如何做的： 5+7=12判哥，三步走 第一步：相加各位的值献雅，不算進(jìn)位，得到2塌计。 第二步：計(jì)算進(jìn)位值挺身，得到10.
* 如果這一步的進(jìn)位值為0，那么第一步得到的值就是最終結(jié)果锌仅。
*
* 第三步：重復(fù)上述兩步章钾，只是相加的值變成上述兩步的得到的結(jié)果2和10，得到12热芹。
*
* 同樣我們可以用三步走的方式計(jì)算二進(jìn)制值相加： 5-101贱傀，7-111
* 第一步：相加各位的值，不算進(jìn)位伊脓，得到010府寒，二進(jìn)制每位相加就相當(dāng)于各位做異或操作，101^111报腔。
*
* 第二步：計(jì)算進(jìn)位值椰棘，得到1010，相當(dāng)于各位做與操作得到101榄笙，再向左移一位得到1010邪狞，(101&111)<<1。
*
* 第三步重復(fù)上述兩步茅撞， 各位相加 010^1010=1000帆卓，進(jìn)位值為100=(010&1010)<<1。 繼續(xù)重復(fù)上述兩步：1000^100 =
* 1100米丘，進(jìn)位值為0剑令，跳出循環(huán)，1100為最終結(jié)果拄查。
*/
}
s49
/**
* 將一個(gè)字符串轉(zhuǎn)換成一個(gè)整數(shù)吁津，要求不能使用字符串轉(zhuǎn)換整數(shù)的庫(kù)函數(shù)。 數(shù)值為0或者字符串不是一個(gè)合法的數(shù)值則返回0
*
* @author panfei
*
*/
public class S49 {
public int StrToInt(String str) {
char[] c = str.toCharArray();
return 0;
}
}
s50
package SwordToOffer;
/**
* 在一個(gè)長(zhǎng)度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)堕扶。 數(shù)組中某些數(shù)字是重復(fù)的碍脏，但不知道有幾個(gè)數(shù)字是重復(fù)的。
* 也不知道每個(gè)數(shù)字重復(fù)幾次稍算。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字典尾。
* 例如，如果輸入長(zhǎng)度為7的數(shù)組{2,3,1,0,2,5,3}糊探，那么對(duì)應(yīng)的輸出是第一個(gè)重復(fù)的數(shù)字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++
// 這里要特別注意~返回任意重復(fù)的一個(gè)河闰，賦值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;
/**
* 給定一個(gè)數(shù)組A[0,1,...,n-1],請(qǐng)構(gòu)建一個(gè)數(shù)組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]中的一部分印机，然后倒過來(lái)按上三角中的分布規(guī)律矢腻，把另一部分也乘進(jìn)去门驾。
*/
public class S51 {
public int[] multiply(int[] A) {
int[] B = new int[A.length];
if (A.length != 0) {
B[0] = 1;
//計(jì)算下三角連乘
for (int i = 1; i < A.length; i++) {
B[i] = B[i - 1] * A[i - 1];
}
int temp = 1;
//計(jì)算上三角
for (int j = A.length - 2; j >= 0; j--) {
temp *= A[j + 1];
B[j] *= temp;
}
}
return B;
}
}
s52
package SwordToOffer;
/**
* 請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來(lái)匹配包括'.'和'*'的正則表達(dá)式。模式中的字符'.'表示任意一個(gè)字符多柑，而'*'表示它前面的字符可以出現(xiàn)任意次（包含0次）奶是。
* 在本題中，匹配是指字符串的所有字符匹配整個(gè)模式竣灌。例如聂沙，字符串"aaa"與模式"a.a"和"ab*ac*a"匹配，但是與"aa.a"和"ab*a"均不匹配
* <p>
* 思路:
* <p>
* 當(dāng)模式中的第二個(gè)字符不是“*”時(shí)：
* 1初嘹、如果字符串第一個(gè)字符和模式中的第一個(gè)字符相匹配及汉，那么字符串和模式都后移一個(gè)字符，然后匹配剩余的屯烦。
* 2坷随、如果字符串第一個(gè)字符和模式中的第一個(gè)字符相不匹配，直接返回false驻龟。
* <p>
* 而當(dāng)模式中的第二個(gè)字符是“*”時(shí)：
* 如果字符串第一個(gè)字符跟模式第一個(gè)字符不匹配温眉，則模式后移2個(gè)字符，繼續(xù)匹配翁狐。如果字符串第一個(gè)字符跟模式第一個(gè)字符匹配类溢，可以有3種匹配方式：
* 1、模式后移2字符露懒，相當(dāng)于x*被忽略闯冷；
* 2、字符串后移1字符懈词，模式后移2字符窃躲；
* 3、字符串后移1字符钦睡，模式不變蒂窒，即繼續(xù)匹配字符下一位躁倒，因?yàn)?可以匹配多位；
*/
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) {
//有效性監(jiān)測(cè),str到尾,pattern到尾
if (strIndex == str.length && patternIndex == pattern.length) {
return true;
}
//pattern先到尾失敗
if (strIndex != str.length && patternIndex == pattern.length) {
return false;
}
//模式第二個(gè)是*,且字符串第一個(gè)和模式第一個(gè)匹配,分三種匹配模式,如不匹配,洒琢，模式后移
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個(gè)字符
|| matchCore(str, strIndex + 1, pattern, patternIndex + 2)//視為模式匹配1個(gè)字符
|| matchCore(str, strIndex + 1, pattern, patternIndex);//*匹配1個(gè)，再匹配str中的下一個(gè)
} else {
return matchCore(str, strIndex, pattern, patternIndex + 2);
}
}
//模式第2個(gè)不是*衰抑，且字符串第1個(gè)跟模式第1個(gè)匹配象迎，則都后移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...
