- 數(shù)組中的逆序?qū)?/li>
題目要求：
如果前面一個(gè)數(shù)字大于后面的數(shù)字，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)ρ仿铡］斎胍粋€(gè)數(shù)組姆泻，
求出這個(gè)數(shù)組中的逆序?qū)倲?shù)。例如輸入{7,5,6,4}冒嫡，一共有5個(gè)逆序?qū)δ床謩e是
（7,6），（7,5）孝凌，（7,4）方咆，（6,4），（5,4）蟀架。
解題思路：
思路1：暴力解決瓣赂。順序掃描數(shù)組，對(duì)于每個(gè)元素片拍，與它后面的數(shù)字進(jìn)行比較煌集，因此這種
思路的時(shí)間復(fù)雜度為o(n^2)。
思路2：
上述思路在進(jìn)行比較后捌省，并沒(méi)有將相關(guān)信息留下苫纤，其實(shí)在比較之后可以進(jìn)行局部的排序，
從而降低比較的次數(shù)，降低時(shí)間復(fù)雜度卷拘。
可通過(guò)如下步驟求逆序?qū)€(gè)數(shù)：先把數(shù)組逐步分隔成長(zhǎng)度為1的子數(shù)組喊废，統(tǒng)計(jì)出子數(shù)組內(nèi)部
的逆序?qū)€(gè)數(shù)，然后再將相鄰兩個(gè)子數(shù)組合并成一個(gè)有序數(shù)組并統(tǒng)計(jì)數(shù)組之間的逆序?qū)?shù)目恭金，
直至合并成一個(gè)大的數(shù)組操禀。其實(shí)，這是二路歸并的步驟横腿，只不過(guò)在歸并的同事要多進(jìn)行一步
統(tǒng)計(jì)颓屑。因此時(shí)間復(fù)雜度o(nlogn)，空間復(fù)雜度o(n)耿焊，如果使用原地歸并排序揪惦，可以將空間
復(fù)雜度降為o(1)。
本文使用經(jīng)典二路歸并排序?qū)崿F(xiàn)罗侯。以{7,5,6,4}為例器腋，過(guò)程如下：
[7 5 6 4]
/ \ 分：將長(zhǎng)度為4的數(shù)組分成長(zhǎng)度為2的數(shù)組
[7 5] [6 4]
/ \ / \ 分：將長(zhǎng)度為2的數(shù)組分成長(zhǎng)度為1的數(shù)組
[7] [5] [6] [4]
\ / \ / 和：1->2，并記錄子數(shù)組內(nèi)的逆序?qū)? [5 7] [4 6]
\ / 和：2->4钩杰，并記錄子數(shù)組內(nèi)的逆序?qū)? [4 5 6 7]
public class P249_InversePairs {
public static int inversePairs(int[] data){
if(data==null || data.length<2)
return 0;
return mergeSortCore(data, 0, data.length - 1);
}
public static int mergeSortCore(int[] data,int start,int end){
if(start>=end)
return 0;
int mid = start+(end-start)/2;
int left = mergeSortCore(data,start,mid);
int right = mergeSortCore(data,mid+1,end);
int count = mergerSortMerge(data,start,mid,end);
return left+right+count;
}
//start~mid, mid+1~end
public static int mergerSortMerge(int[] data,int start,int mid,int end){
int[] temp = new int[end-start+1];
for(int i=0;i<=end-start;i++)
temp[i] = data[i+start];
int left = 0,right = mid+1-start,index = start,count = 0;
while (left<=mid-start && right<=end-start){
if(temp[left]<=temp[right])
data[index++] = temp[left++];
else{
data[index++] = temp[right++];
count += (mid-start)-left+1;
}
}
while (left<=mid-start)
data[index++] = temp[left++];
while (right<=end-start)
data[index++] = temp[right++];
return count;
}
public static void main(String[] args){
System.out.println(inversePairs(new int[]{7,5,6,4}));
System.out.println(inversePairs(new int[]{5,6,7,8,1,2,3,4}));
}
}
- 兩個(gè)鏈表的第一個(gè)公共節(jié)點(diǎn)
題目要求：
輸入兩個(gè)單鏈表纫塌，找出它們的第一個(gè)公共節(jié)點(diǎn)。以下圖為例讲弄，對(duì)一個(gè)公共節(jié)點(diǎn)為6所在的節(jié)點(diǎn)措左。
1 -> 2 -> 3 -> 6 -> 7
4 -> 5 ↗
解題思路：
1 暴力求解 o(mn) o(1)
2 分別存入兩個(gè)棧，求棧中最深的相同節(jié)點(diǎn) o(m+n) o(m+n)
3 長(zhǎng)鏈表先行|n-m|步避除，轉(zhuǎn)化為等長(zhǎng)鏈表 o(m+n) o(1)
解法1：比較直接怎披，不再贅述。
解法2：從鏈表的尾部向前看瓶摆，發(fā)現(xiàn)尾部是相同的凉逛，向前走會(huì)分叉，找到分叉點(diǎn)即可群井。
按照這個(gè)思路状飞，如果這是雙向鏈表，即得到尾節(jié)點(diǎn)并能夠得到每個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)书斜，
那這個(gè)題就很簡(jiǎn)單了诬辈。對(duì)于單鏈表，本身是前節(jié)點(diǎn)->后節(jié)點(diǎn)菩佑，想要得到后節(jié)點(diǎn)->前節(jié)點(diǎn)自晰，
可以借助于棧的后進(jìn)先出特性凝化。兩個(gè)單鏈表分別入棧稍坯，得到[1,2,3,6,7],[4,5,6,7]，
然后不斷出棧即可找到分叉點(diǎn)。
解法3：對(duì)于單鏈表瞧哟，如果從頭結(jié)點(diǎn)開(kāi)始找公共節(jié)點(diǎn)混巧，一個(gè)麻煩點(diǎn)是兩個(gè)鏈表長(zhǎng)度可能
不一致，因此兩個(gè)指針不同步（指兩個(gè)指針無(wú)法同時(shí)指向公共點(diǎn)）勤揩。解決這個(gè)麻煩點(diǎn)咧党，
整個(gè)問(wèn)題也就能順利解決。那么陨亡，能否讓兩個(gè)鏈表長(zhǎng)度一致傍衡？長(zhǎng)鏈表先行幾步即可，
因?yàn)殚L(zhǎng)鏈表頭部多出的那幾個(gè)節(jié)點(diǎn)一定不會(huì)是兩鏈表的公共節(jié)點(diǎn)负蠕。以題目中的圖為例蛙埂，
可以讓1所在的鏈表先向前移動(dòng)1個(gè)節(jié)點(diǎn)到2，這樣就轉(zhuǎn)化為求下面這兩個(gè)鏈表的第一個(gè)
公共節(jié)點(diǎn)：
2 -> 3 -> 6 -> 7
4 -> 5 ↗
一個(gè)指針指向2遮糖，另一個(gè)指向4绣的，然后同時(shí)遍歷，這應(yīng)該很容易了吧欲账。需要對(duì)兩個(gè)鏈表先
進(jìn)行一次遍歷求出長(zhǎng)度屡江，然后再同時(shí)遍歷求公共點(diǎn)，時(shí)間復(fù)雜度o(n)赛不，空間復(fù)雜度o(1)惩嘉。
三種解法的代碼實(shí)現(xiàn)如下。
package chapter5;
import structure.ListNode;
import java.util.Stack;
public class P253_CommonNodesInLists {
//思路一：暴力解決俄删，時(shí)間復(fù)雜度o(mn)宏怔，空間復(fù)雜度o(1)
//思路二：借助于兩個(gè)棧，時(shí)間復(fù)雜度o(m+n)畴椰，空間復(fù)雜度o(m+n)
//思路三：轉(zhuǎn)化為等長(zhǎng)鏈表臊诊，時(shí)間復(fù)雜度o(m+n)，空間復(fù)雜度o(1)
public static ListNode<Integer> findFirstCommonNode(ListNode<Integer> head1,ListNode<Integer> head2){
for(ListNode<Integer> node1=head1;node1!=null;node1=node1.next){
for(ListNode<Integer> node2=head2;node2!=null;node2=node2.next){
if(node1==node2)
return node1;
}
}
return null;
}
public static ListNode<Integer> findFirstCommonNode2(ListNode<Integer> head1,ListNode<Integer> head2){
Stack<ListNode<Integer>> stack1 = new Stack<>();
Stack<ListNode<Integer>> stack2 = new Stack<>();
for(ListNode<Integer> node1=head1;node1!=null;node1=node1.next)
stack1.push(node1);
for(ListNode<Integer> node2=head2;node2!=null;node2=node2.next)
stack2.push(node2);
ListNode<Integer> commonNode = null;
while (!stack1.isEmpty() && !stack2.isEmpty()){
if(stack1.peek()==stack2.peek()){
commonNode = stack1.pop();
stack2.pop();
}
else
break;
}
return commonNode;
}
public static ListNode<Integer> findFirstCommonNode3(ListNode<Integer> head1,ListNode<Integer> head2){
ListNode<Integer> node1 = head1,node2 = head2;
int size1 = 0,size2 = 0;
for (;node1!=null;node1 = node1.next)
size1++;
for (;node2!=null;node2 = node2.next)
size2++;
node1 = head1;
node2 = head2;
while (size1>size2){
node1 = node1.next;
size1--;
}
while (size2>size1){
node2 = node2.next;
size2--;
}
while (node1!=null){
if(node1!=node2){
node1 = node1.next;
node2 = node2.next;
}
else
break;
}
return node1;
}
public static void main(String[] args){
// 1->2->3->6->7
// 4->5↗
ListNode<Integer> node1 = new ListNode<>(1);
ListNode<Integer> node2 = new ListNode<>(2);
ListNode<Integer> node3 = new ListNode<>(3);
ListNode<Integer> node4 = new ListNode<>(4);
ListNode<Integer> node5 = new ListNode<>(5);
ListNode<Integer> node6 = new ListNode<>(6);
ListNode<Integer> node7 = new ListNode<>(7);
node1.next = node2;
node2.next = node3;
node3.next = node6;
node4.next = node5;
node5.next = node6;
node6.next = node7;
ListNode<Integer> commonNode = findFirstCommonNode(node1,node4);
System.out.println(commonNode.val);
ListNode<Integer> commonNode2 = findFirstCommonNode2(node1,node4);
System.out.println(commonNode2.val);
ListNode<Integer> commonNode3 = findFirstCommonNode2(node1,node4);
System.out.println(commonNode3.val);
}
}
- 數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)
題目要求：
統(tǒng)計(jì)一個(gè)數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)斜脂。例如抓艳，輸入{1,2,3,3,3,3,4,5}
和數(shù)字3，由于3在這個(gè)數(shù)組中出現(xiàn)了4次帚戳，因此輸出4玷或。
解題思路：
排序數(shù)組，定位某一個(gè)數(shù)值的位置片任，很容易想到二分查找偏友。分成兩部分：求第一個(gè)
出現(xiàn)該值的位置start，求最后一個(gè)出現(xiàn)該值得位置end对供，end-start+1即為所求位他。
二分法比較關(guān)鍵的一個(gè)邏輯如下：
mid = left + (right - left + 1) / 2;
if (data[mid] > k)
right = mid-1;
else if(data[mid] < k)
left = mid+1;
else
right = mid;
mid = left + (right - left + 1) / 2;
if (data[mid] > k)
right = mid-1;
else if(data[mid] < k)
left = mid+1;
else
left = mid;
此處要注意求mid時(shí)如下兩種寫法的差別：
（1） mid = left + (right - left) / 2;
（2） mid = left + (right - left + 1) / 2;
如果left氛濒，right之前的數(shù)字個(gè)數(shù)為奇數(shù)，那兩者沒(méi)差異鹅髓，比如left=2舞竿，right=6，
中間有3,4,5窿冯，那么(1)(2)求出的mid都是4骗奖。如果中間數(shù)字的個(gè)數(shù)是偶數(shù)，比如left=2醒串，
right=5执桌，中間有3,4,(1)求出的mid都是3，(2)求出的mid都是4芜赌，即(1)求出的mid偏左鼻吮，
(2)求出的偏右。極端特殊情況下，比如有個(gè)數(shù)組data[7,7,7,7,7]，求k=7出現(xiàn)的次數(shù)秃症。
使用(1)的迭代過(guò)程為
left=0雹有，right=4，mid=2
left=0，right=2，mid=1
left=0，right=1畜伐，mid=0 (注意這里)
left=0，right=0躺率，left==right 且 data[left]=k玛界，返回0
使用(2)的迭代過(guò)程為
left=0，right=4悼吱，mid=2
left=2慎框，right=4，mid=3
left=3后添，right=4笨枯，mid=4(注意這里)
left=4，right=4遇西，left==right 且 data[left]=k馅精，返回4
4-0+1 = 5，即為所求粱檀。
另一個(gè)在用二分查找時(shí)洲敢，要注意的點(diǎn)是求mid時(shí)的寫法：
（a） mid = (left + right) / 2;
（b） mid = left + (right - left) / 2;
推薦用(b)，最好不要出現(xiàn)(a)茄蚯，當(dāng)left压彭、right都是比較大的數(shù)時(shí)称近，完成同樣的功能，
(a)可能造成上溢哮塞，但(b)不會(huì)。
package chapter6;
public class P263_NumberOfK {
//遍歷的話時(shí)間復(fù)雜度為o(n)
//考慮到數(shù)組是排序好的凳谦，可使用二分法忆畅，時(shí)間復(fù)雜度o(logn)
public static int getNumberOfK(int[] data,int k){
int start = getStartOfK(data,k);
if(start==-1)
return 0;
int end = getEndOfK(data,start,k);
return end-start+1;
}
public static int getStartOfK(int[] data,int k){
if(data[0]>k || data[data.length-1]<k)
return -1;
int left = 0,right = data.length-1,mid;
while (left<=right) {
if(right==left){
if(data[left]==k)
return left;
else
return -1;
}
//當(dāng)長(zhǎng)度為2，mid取左值
mid = left + (right - left) / 2;
if (data[mid] > k)
right = mid-1;
else if(data[mid] < k)
left = mid+1;
else
right = mid;
}
return -1;
}
public static int getEndOfK(int[] data,int start, int k){
int left = start,right = data.length-1,mid;
while (left<=right){
if(left==right){
if(data[left]==k)
return left;
else
return -1;
}
//當(dāng)長(zhǎng)度為2尸执，mid取右值
mid = left + (right - left + 1) / 2;
if (data[mid] > k)
right = mid-1;
else if(data[mid] < k)
left = mid+1;
else
left = mid;
}
return -1;
}
public static void main(String[] args){
int[] data1 = new int[]{1,2,3,3,3,3,5,6};
int[] data2 = new int[]{1,2,3,3,3,3,4,5};
int[] data3 = new int[]{3,3,3,3,3,3,3,3};
System.out.println(getNumberOfK(data1,4));
System.out.println(getNumberOfK(data2,3));
System.out.println(getNumberOfK(data3,3));
}
}
53.2：0~n中缺失的數(shù)字
題目要求：
一個(gè)長(zhǎng)度為n的遞增排序數(shù)組中的所有數(shù)字都是唯一的家凯，并且每個(gè)數(shù)字都在范圍
0~n之內(nèi)。在范圍0~n內(nèi)的n個(gè)數(shù)字有且只有一個(gè)數(shù)字不在該數(shù)組中如失，請(qǐng)找出绊诲。
解題思路：
用二分法找到數(shù)組中第一個(gè)數(shù)值不等于下標(biāo)的數(shù)字。
package chapter6;
public class P266_GetMissingNumber {
public static int getMissingNumber(int[] data){
int left = 0,right = data.length-1,mid;
while (left<=right){
//mid=left+(right-left)/2 用位運(yùn)算替換除法
//注意加減法優(yōu)先級(jí)高于位運(yùn)算
mid = left+((right-left)>>1);
if(data[mid]==mid)
left = mid+1;
else
right = mid-1;
}
return left;
}
public static void main(String[] args){
int[] data1 = new int[]{0,1,2,3,4,5}; //6
int[] data2 = new int[]{0,1,3,4,5}; //2
int[] data3 = new int[]{1,2}; //0
System.out.println(getMissingNumber(data1));
System.out.println(getMissingNumber(data2));
System.out.println(getMissingNumber(data3));
}
}
53.3：數(shù)組中數(shù)值和下標(biāo)相等的元素
題目要求：
假設(shè)一個(gè)單調(diào)遞增的數(shù)組里的每個(gè)元素都是整數(shù)且是唯一的褪贵。編寫一個(gè)程序掂之，
找出數(shù)組中任意一個(gè)數(shù)值等于其下標(biāo)的元素。例如脆丁，輸入{-3,-1,1,3,5}世舰，輸出3。
解題思路：
很基本的二分查找槽卫。跟压。。
package chapter6;
public class P267_IntegerIdenticalToIndex {
public static int getNumberSameAsIndex(int[] data){
if(data==null ||data.length==0)
return -1;
int left = 0,right = data.length-1;
if(data[left]>0||data[right]<0)
return -1;
int mid;
while (left<=right){
mid = left+((right-left)>>1);
if(data[mid]==mid)
return mid;
else if(data[mid]<mid)
left = mid+1;
else
right = mid-1;
}
return -1;
}
public static void main(String[] args){
System.out.println(getNumberSameAsIndex(new int[]{-3,-1,1,3,5})); //3
System.out.println(getNumberSameAsIndex(new int[]{0,1,2,3,4})); //0~4
System.out.println(getNumberSameAsIndex(new int[]{4,5,6,7,8})); //-1
}
}
- 二叉搜索樹(shù)的第k大節(jié)點(diǎn)
題目要求：
找出二叉搜索樹(shù)的第k大節(jié)點(diǎn)歼培。例如震蒋，在下圖的樹(shù)里，第3大節(jié)點(diǎn)的值為4躲庄，
輸入該樹(shù)的根節(jié)點(diǎn)查剖，3，則輸出4噪窘。
5
/ \
3 7
/ \ / \
2 4 6 8
解題思路：
二叉搜索樹(shù)的中序遍歷是有序的梗搅。可以引入一個(gè)計(jì)數(shù)器效览，每訪問(wèn)一個(gè)節(jié)點(diǎn)无切，
計(jì)數(shù)器+1，當(dāng)計(jì)數(shù)器等于k時(shí)丐枉，被訪問(wèn)節(jié)點(diǎn)就是該二叉搜索樹(shù)的第k大節(jié)點(diǎn)哆键。
package chapter6;
import structure.TreeNode;
import java.util.Stack;
public class P269_KthNodeInBST {
public static TreeNode<Integer> kthNode(TreeNode<Integer> root,int k){
//棧頂元素保證一直是cur的父節(jié)點(diǎn)
if(root==null || k<0)
return null;
Stack<TreeNode<Integer>> stack = new Stack<>();
TreeNode<Integer> cur = root;
int count = 0;
while (!stack.isEmpty()||cur!=null){
if(cur!=null){
stack.push(cur);
cur = cur.left;
}
else{
cur = stack.pop();
count++;
if(count==k)
return cur;
cur = cur.right;
}
}
return null;
}
public static void main(String[] args){
TreeNode<Integer> root = new TreeNode<>(5);
root.left = new TreeNode<>(3);
root.left.left = new TreeNode<>(2);
root.left.right = new TreeNode<>(4);
root.right = new TreeNode<>(7);
root.right.left = new TreeNode<>(6);
root.right.right = new TreeNode<>(8);
System.out.println(kthNode(root,3).val);//4
System.out.println(kthNode(root,6).val);//7
System.out.println(kthNode(root,8));//null
}
}
- 二叉樹(shù)的深度
題目要求：
求二叉樹(shù)的深度。僅僅包含一個(gè)根節(jié)點(diǎn)的二叉樹(shù)深度為1瘦锹。
解題思路：
二叉樹(shù)root的深度比其子樹(shù)root.left與root.right的深度的最大值大1籍嘹。
因此可以通過(guò)上述結(jié)論遞歸求解闪盔。
如果不使用遞歸，可以通過(guò)層序遍歷（廣度優(yōu)先遍歷）解決辱士。
package chapter6;
import structure.TreeNode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class P271_TreeDepth {
//遞歸
public static int treeDepth(TreeNode<Integer> root){
if(root==null)
return 0;
int left = treeDepth(root.left);
int right = treeDepth(root.right);
return left>right?(left+1):(right+1);
}
//非遞歸泪掀，廣度優(yōu)先/層序遍歷
public static int treeDepth2(TreeNode<Integer> root){
if(root==null)
return 0;
Queue<TreeNode<Integer>> queue = new LinkedList<>();
queue.offer(root);
int depth = 0;
while (!queue.isEmpty()){
int size = queue.size();
TreeNode<Integer> cur = null;
for(int i=0;i<size;i++){
cur = queue.poll();
if(cur.left!=null) queue.offer(cur.left);
if(cur.right!=null) queue.offer(cur.right);
}
depth++;
}
return depth;
}
public static void main(String[] args){
TreeNode<Integer> root = new TreeNode<>(1);
root.left = new TreeNode<>(2);
root.left.left = new TreeNode<>(4);
root.left.right = new TreeNode<>(5);
root.left.right.left = new TreeNode<>(7);
root.right = new TreeNode<>(3);
root.right.right = new TreeNode<>(6);
System.out.println(treeDepth(root));
System.out.println(treeDepth2(root));
}
}
55.2：平衡二叉樹(shù)
題目要求：
輸入二叉樹(shù)的根節(jié)點(diǎn)，判斷該樹(shù)是否是平衡二叉樹(shù)颂碘。如果某二叉樹(shù)的任意節(jié)點(diǎn)的
左右子樹(shù)深度之差不超過(guò)1异赫，則該樹(shù)是平衡二叉樹(shù)。
解題思路：
思路1：依據(jù)平衡二叉樹(shù)的定義解決头岔。借助于上一題二叉樹(shù)的深度塔拳，從根節(jié)點(diǎn)開(kāi)始
逐點(diǎn)判斷樹(shù)的左右子樹(shù)的深度差值是否滿足要求。由于此解法是從根到葉的判斷峡竣，
每一次獲取節(jié)點(diǎn)有需要從當(dāng)前節(jié)點(diǎn)遍歷到葉節(jié)點(diǎn)靠抑，因此需要多次遍歷。
思路2：如果用后序遍歷适掰，那么訪問(wèn)某一個(gè)節(jié)點(diǎn)時(shí)已經(jīng)訪問(wèn)了它的左右子樹(shù)颂碧。同時(shí)，
在訪問(wèn)節(jié)點(diǎn)時(shí)記錄下它的深度类浪，并由左右子樹(shù)的深度推出父親節(jié)點(diǎn)的深度稚伍，這樣
我們就能通過(guò)遍歷一遍完成整棵樹(shù)的平衡性判斷。
對(duì)于某一個(gè)子樹(shù)戚宦，需要給出它的平衡性的判斷个曙，還要給出它的深度，此處我將平衡
性的判斷作為返回值受楼，深度通過(guò)長(zhǎng)度為1的數(shù)組傳遞出去垦搬，見(jiàn)
boolean isBalanced2Core(TreeNode<Integer> node,int[] depth)。
package chapter6;
import structure.TreeNode;
public class P273_isBalanced {
//借助于深度艳汽，判斷是否是平衡二叉樹(shù),由于是從根到葉逐點(diǎn)判斷猴贰，需要多次遍歷樹(shù)
public static boolean isBalanced(TreeNode<Integer> node){
if(node==null)
return true;
int left = treeDepth(node.left);
int right = treeDepth(node.right);
int diff = left - right;
if(diff<-1||diff>1)
return false;
return isBalanced(node.left)&&isBalanced(node.right);
}
public static int treeDepth(TreeNode<Integer> root){
if(root==null)
return 0;
int left = treeDepth(root.left);
int right = treeDepth(root.right);
return left>right?(left+1):(right+1);
}
//用后序遍歷，并記錄每個(gè)節(jié)點(diǎn)的深度河狐，從而可以通過(guò)一次遍歷完成整棵樹(shù)的判斷
public static boolean isBalanced2(TreeNode<Integer> node){
if(node==null)
return true;
return isBalanced2Core(node,new int[]{0});
}
public static boolean isBalanced2Core(TreeNode<Integer> node,int[] depth){
if(node==null){
depth[0] = 0;
return true;
}
int[] left = new int[]{0};
int[] right = new int[]{0};
if(isBalanced2Core(node.left,left)&&isBalanced2Core(node.right,right)){
int diff = left[0]-right[0];
if(diff<=1&&diff>=-1){
depth[0] = 1+(left[0]>right[0]?left[0]:right[0]);
return true;
}
else
return false;
}
return false;
}
public static void main(String[] args){
TreeNode<Integer> root = new TreeNode<>(1);
root.left = new TreeNode<>(2);
root.left.left = new TreeNode<>(4);
root.left.right = new TreeNode<>(5);
root.left.right.left = new TreeNode<>(7);
root.right = new TreeNode<>(3);
root.right.right = new TreeNode<>(6);
System.out.println(isBalanced(root));
System.out.println(isBalanced2(root));
}
}
- 數(shù)組中只出現(xiàn)一次的兩個(gè)數(shù)字
題目要求：
一個(gè)整數(shù)數(shù)組里除了兩個(gè)數(shù)字出現(xiàn)一次米绕，其他數(shù)字都出現(xiàn)兩次。請(qǐng)找出這兩個(gè)數(shù)字馋艺。
要求時(shí)間復(fù)雜度為o(n)栅干，空間復(fù)雜度為o(1)。
解題思路：
這道題可以看成“數(shù)組中只出現(xiàn)一次的一個(gè)數(shù)字”的延伸捐祠。如果所有數(shù)字都出現(xiàn)兩次碱鳞，
只有一個(gè)數(shù)字是出現(xiàn)1次，那么可以通過(guò)把所有所有進(jìn)行異或運(yùn)算解決踱蛀。因?yàn)閤^x = 0窿给。
但如果有兩個(gè)數(shù)字出現(xiàn)一次贵白，能否轉(zhuǎn)化成上述問(wèn)題？依舊把所有數(shù)字異或崩泡，最終的
結(jié)果就是那兩個(gè)出現(xiàn)一次的數(shù)字a,b異或的結(jié)果禁荒。因?yàn)閍，b不想等角撞，因此結(jié)果肯定不為0呛伴，
那么結(jié)果的二進(jìn)制表示至少有一位為1，找到那個(gè)1的位置p靴寂，然后我們就可以根據(jù)第p位
是否為1將所有的數(shù)字分成兩堆，這樣我們就把所有數(shù)字分成兩部分召耘，且每部分都是只包
含一個(gè)只出現(xiàn)一次的數(shù)字百炬、其他數(shù)字出現(xiàn)兩次，從而將問(wèn)題轉(zhuǎn)化為最開(kāi)始我們討論的
“數(shù)組中只出現(xiàn)一次的一個(gè)數(shù)字”問(wèn)題污它。
實(shí)例分析(以2,4,3,6,3,2,5,5為例)：
相關(guān)數(shù)字的二進(jìn)制表示為：
2 = 0010 3 = 0011 4 = 0100
5 = 0101 6 = 0110
步驟1 全體異或：2^4^3^6^3^2^5^5 = 4^6 = 0010
步驟2 確定位置：對(duì)于0010剖踊，從右數(shù)的第二位為1，因此可以根據(jù)倒數(shù)第2位是否為1進(jìn)行分組
步驟3 進(jìn)行分組：分成[2,3,6,3,2]和[4,5,5]兩組
步驟4 分組異或：2^3^6^3^2 = 6衫贬，4^5^5 = 4德澈，因此結(jié)果為4，6固惯。
package chapter6;
public class P275_NumberAppearOnce {
public static int[] findNumsAppearOnce(int[] data){
int result = 0;
for(int i=0;i<data.length;i++)
result^=data[i];
int indexOf1 = findFirstBit1(result);
int ret[] = new int[]{0,0};
if(indexOf1<0)
return ret;
for(int i=0;i<data.length;i++){
if((data[i]&indexOf1)==0)
ret[0]^=data[i];
else
ret[1]^=data[i];
}
return ret;
}
public static int findFirstBit1(int num){
if(num<0)
return -1;
int indexOf1 = 1;
while (num!=0){
if((num&1)==1)
return indexOf1;
else{
num = num>>1;
indexOf1*=2;
}
}
return -1;
}
public static void main(String[] args){
int[] data = new int[]{2,4,3,6,3,2,5,5};
int[] result = findNumsAppearOnce(data); // 4,6
System.out.println(result[0]);
System.out.println(result[1]);
}
}
- 和為s的數(shù)字
題目要求：
輸入一個(gè)遞增排序的數(shù)組和一個(gè)數(shù)字s梆造，在數(shù)組中查找兩個(gè)數(shù)，使它們的和為s葬毫。
如果有多對(duì)和為s镇辉，輸入任意一對(duì)即可。
解題思路：
使用兩個(gè)指針?lè)謩e指向數(shù)組的頭贴捡、尾忽肛。如果和大于s，頭部指針后移烂斋，如果和小于s屹逛，尾部指針前移。
package chapter6;
public class P280_TwoNumbersWithSum {
public static int[] findNumbersWithSum(int[] data,int sum){
int[] result = new int[]{0,0};
if(data==null || data.length<2)
return result;
int curSum = data[0]+data[data.length-1];
int left = 0,right = data.length-1;
while (curSum!=sum && left<right){
if(curSum>sum)
right--;
else
left++;
curSum = data[left]+data[right];
}
if(curSum==sum){
result[0] = data[left];
result[1] = data[right];
}
return result;
}
public static void main(String[] args){
int[] data = new int[]{1,2,4,7,11,15};
int[] result = findNumbersWithSum(data,15);
System.out.println(result[0]);
System.out.println(result[1]);
}
}
57.2：和為s的連續(xù)正數(shù)序列
題目要求：
輸入一個(gè)整數(shù)s汛骂，打印所有和為s的連續(xù)正數(shù)序列(至少兩個(gè))罕模。例如，輸入15帘瞭，
由于1+2+3+4+5=4+5+6=7+8=15手销，所以打印出三個(gè)連續(xù)序列15,46,7~8。
解題思路：
與上一題類似图张，依舊使用兩個(gè)指針small锋拖，big诈悍，值分別為1，2兽埃。如果從small
加到big的和等于s侥钳，即找到了一組解，然后讓big后移柄错，繼續(xù)求解舷夺。如果和小于s，
big后移售貌，如果和大于s给猾，small前移。直到small大于s/2停止颂跨。
package chapter6;
public class P282_ContinuousSequenceWithSum {
public static void findContinuousSequence(int sum){
if(sum<3)
return;
int small = 1,big = 2,middle = sum>>1;
int curSum = small+big;
while (small<=middle){
if(curSum==sum){
printContinousSequence(small,big);
big++;
curSum+=big;
}
else if(curSum<sum){
big++;
curSum+=big;
}
else{
curSum-=small;
small++;
}
}
}
public static void printContinousSequence(int small,int big){
for(int i=small;i<=big;i++){
System.out.print(i);
System.out.print(" ");
}
System.out.println();
}
public static void main(String[] args){
findContinuousSequence(15);
}
}
- 翻轉(zhuǎn)單詞順序
題目要求：
輸入一個(gè)英文句子敢伸，翻轉(zhuǎn)單詞順序，單詞內(nèi)字符不翻轉(zhuǎn)恒削，標(biāo)點(diǎn)符號(hào)和普通字母
一樣處理池颈。例如輸入輸入“I am a student.”，則輸出“student. a am I”钓丰。
解題思路：
首先字符串整體翻轉(zhuǎn)躯砰，得到“.tneduts a ma I”；然后以空格作為分隔符進(jìn)行切分携丁，
對(duì)于切分下來(lái)的每一部分再進(jìn)行翻轉(zhuǎn)琢歇，得到“student. a am I”。
package chapter6;
public class P284_ReverseWordsInSentence {
public static String reverse(String str){
StringBuilder stringBuilder = new StringBuilder(str);
reverseSubString(stringBuilder,0,stringBuilder.length()-1);
int start = 0,end = stringBuilder.indexOf(" ");
while (start<stringBuilder.length()&&end!=-1){
reverseSubString(stringBuilder,start,end-1);
start = end+1;
end = stringBuilder.indexOf(" ",start);
}
if(start<stringBuilder.length())
reverseSubString(stringBuilder,start,stringBuilder.length()-1);
return stringBuilder.toString();
}
//翻轉(zhuǎn)stringBuilder[start,end]
public static void reverseSubString(StringBuilder stringBuilder,int start,int end){
for(int i=start;i<=start+(end-start)/2;i++){
char temp = stringBuilder.charAt(i);
stringBuilder.setCharAt(i,stringBuilder.charAt(end-i+start));
stringBuilder.setCharAt(end-i+start,temp);
}
}
public static void main(String[] args){
System.out.println(reverse("I am a student."));
}
}
58.2：左旋轉(zhuǎn)字符串
題目要求：
實(shí)現(xiàn)一個(gè)函數(shù)完成字符串的左旋轉(zhuǎn)功能梦鉴。比如矿微，輸入abcdefg和數(shù)字2，輸出為cdefgab尚揣。
解題思路：
類似于58.翻轉(zhuǎn)單詞順序涌矢。首先對(duì)于字符串“abcdefg”整體翻轉(zhuǎn)，得到“gfedcba”快骗；
然后對(duì)于后2個(gè)字符“ba”進(jìn)行翻轉(zhuǎn)娜庇，對(duì)于剩下的字符“gfedc”進(jìn)行翻轉(zhuǎn)，得到“cdefgab”方篮。
package chapter6;
public class P286_LeftRotateString {
public static String leftRotateString(String str,int i){
if(str==null||str.length()==0||i<=0||i>=str.length())
return str;
StringBuilder stringBuilder = new StringBuilder(str);
reverseSubString(stringBuilder,0,stringBuilder.length()-1);
reverseSubString(stringBuilder,0,stringBuilder.length()-i-1);
reverseSubString(stringBuilder,stringBuilder.length()-i,stringBuilder.length()-1);
return stringBuilder.toString();
}
//翻轉(zhuǎn)stringBuilder[start,end]
public static void reverseSubString(StringBuilder stringBuilder,int start,int end){
for(int i=start;i<=start+(end-start)/2;i++){
char temp = stringBuilder.charAt(i);
stringBuilder.setCharAt(i,stringBuilder.charAt(end-i+start));
stringBuilder.setCharAt(end-i+start,temp);
}
}
public static void main(String[] args){
String str = "abcdefg";
System.out.println(leftRotateString(str,2));
}
}
- 滑動(dòng)窗口的最大值
題目要求：
給定一個(gè)數(shù)組和滑動(dòng)窗口的大小名秀，請(qǐng)找出所有滑動(dòng)窗口的最大值。例如藕溅，
輸入數(shù)組{2,3,4,2,6,2,5,1}和數(shù)字3匕得，那么一共存在6個(gè)滑動(dòng)窗口，
他們的最大值分別為{4,4,6,6,6,5}。
解題思路：
思路1：使用暴力求解汁掠。假設(shè)滑動(dòng)窗口長(zhǎng)度為k略吨，每到一個(gè)點(diǎn)都向前遍歷k-1
個(gè)節(jié)點(diǎn)，那么總時(shí)間復(fù)雜度為o(nk)考阱。
思路2：長(zhǎng)度為k的滑動(dòng)窗口其實(shí)可以看成一個(gè)隊(duì)列翠忠，而滑動(dòng)窗口的移動(dòng)可以
看成隊(duì)列的出隊(duì)和入隊(duì)，因此本題可以轉(zhuǎn)化為求長(zhǎng)度為k的隊(duì)列的最大值乞榨。借助之前
做過(guò)的9.用兩個(gè)棧實(shí)現(xiàn)隊(duì)列和30.包含min函數(shù)的棧秽之，我們可以實(shí)現(xiàn)求隊(duì)列的最大值。
下面我們分析下時(shí)間與空間復(fù)雜度吃既。用兩個(gè)棧實(shí)現(xiàn)長(zhǎng)度為k的隊(duì)列的入隊(duì)時(shí)間
復(fù)雜度o(1)考榨，出隊(duì)時(shí)間復(fù)雜度o(k),空間復(fù)雜度為o(k)；包含最值函數(shù)的棧
（最大深度為k）的時(shí)間復(fù)雜度為o(1),空間復(fù)雜度為o(k)鹦倚。因此長(zhǎng)度為k的
隊(duì)列的一次出隊(duì)+入隊(duì)操作（即窗口前移一位）時(shí)間復(fù)雜度為o(k)河质，空間復(fù)
雜度為o(k)。而這個(gè)窗口需要完成在長(zhǎng)度為n的數(shù)組上從頭到尾的滑動(dòng)申鱼，因此愤诱，
本解法的時(shí)間復(fù)雜度為o(nk)云头，空間復(fù)雜度o(k)捐友。
思路3：把可能成為最大值數(shù)字的下標(biāo)放入雙端隊(duì)列deque，從而減少遍歷次數(shù)溃槐。
首先匣砖，所有在沒(méi)有查看后面數(shù)字的情況下，任何一個(gè)節(jié)點(diǎn)都有可能成為某個(gè)狀態(tài)
的滑動(dòng)窗口的最大值昏滴，因此猴鲫，數(shù)組中任何一個(gè)元素的下標(biāo)都會(huì)入隊(duì)。關(guān)鍵在于出隊(duì)谣殊，
以下兩種情況下拂共，該下標(biāo)對(duì)應(yīng)的數(shù)字不會(huì)是窗口的最大值需要出隊(duì)：(1)該下標(biāo)已
經(jīng)在窗口之外，比如窗口長(zhǎng)度為3姻几，下標(biāo)5入隊(duì)宜狐，那么最大值只可能在下標(biāo)3,4,5中
出現(xiàn)，隊(duì)列中如果有下標(biāo)2則需要出隊(duì)蛇捌；(2)后一個(gè)元素大于前面的元素抚恒，那么前面
的元素出對(duì)，比如目前隊(duì)列中有下標(biāo)3络拌、4俭驮，data[3] = 50,data[4]=40，下標(biāo)5入
隊(duì)春贸，但data[5] = 70混萝，則隊(duì)列中的3遗遵，4都需要出隊(duì)。
數(shù)組{2,3,4,2,6,2,5,1}的長(zhǎng)度為3的滑動(dòng)窗口最大值求解步驟如下
步驟 插入數(shù)字 滑動(dòng)窗口 隊(duì)列中的下標(biāo) 最大值
1 2 2 0(2) N/A
2 3 2,3 1(3) N/A
3 4 2,3,4 2(4) 4
4 2 3,4,2 2(4),3(2) 4
5 6 4,2,6 4(6) 6
6 2 2,6,2 4(6),5(2) 6
7 5 6,2,5 4(6),6(5) 6
8 1 2,5,1 6(5),7(1) 5
時(shí)間復(fù)雜度在o(n)~o(nk)之間譬圣，空間復(fù)雜度o(k)瓮恭。
思路3的代碼實(shí)現(xiàn)如下：
package chapter6;
import java.util.ArrayDeque;
import java.util.Deque;
public class P288_MaxInSlidingWindow {
//把可能會(huì)成為最大值的下標(biāo)存儲(chǔ)下來(lái)，從而降低掃描次數(shù)
public static int[] maxInWindows(int[] data,final int size){
if(data==null ||data.length==0||data.length<size)
return new int[0];
int[] result = new int[data.length-size+1];
Deque<Integer> deque = new ArrayDeque<>();
for(int i=0;i<size-1;i++){
while (!deque.isEmpty()&&data[i]>=data[deque.getLast()])
deque.removeLast();
deque.addLast(i);
}
for(int i=size-1;i<data.length;i++){
while (!deque.isEmpty()&&i-deque.getFirst()+1>size)
deque.removeFirst();
while (!deque.isEmpty()&&data[deque.getLast()]<=data[i])
deque.removeLast();
deque.addLast(i);
result[i-(size-1)] = data[deque.getFirst()];
}
return result;
}
public static void main(String[] args){
int[] data = new int[]{2,3,4,2,6,2,5,1};
int[] result = maxInWindows(data,3);
for(int i=0;i<result.length;i++){
System.out.print(result[i]);
System.out.print("\t");
}
}
}
59.2：隊(duì)列的最大值
題目要求：
定義一個(gè)隊(duì)列并實(shí)現(xiàn)函數(shù)max得到隊(duì)列里的最大值厘熟。要求max屯蹦，pushBack，
popFront的時(shí)間復(fù)雜度都是o(1)绳姨。
解題思路：
兩個(gè)思路均延續(xù)自59.滑動(dòng)窗口的最大值
思路1：借助之前做過(guò)的9.用兩個(gè)棧實(shí)現(xiàn)隊(duì)列和30.包含min函數(shù)的棧登澜，
我們可以實(shí)現(xiàn)求隊(duì)列的最大值。入隊(duì)時(shí)間復(fù)雜度o(1)飘庄，出隊(duì)時(shí)間復(fù)雜度
o(n),獲取最大值時(shí)間復(fù)雜度o(1)脑蠕，空間復(fù)雜度o(n)。
思路2：將上一題的滑動(dòng)窗口看成一個(gè)隊(duì)列即可跪削。入隊(duì)時(shí)間復(fù)雜度o(1)谴仙，
出隊(duì)時(shí)間復(fù)雜度o(1)，調(diào)整記錄下標(biāo)的雙端隊(duì)列的時(shí)間復(fù)雜度最差為o(n)碾盐，
獲取最值得時(shí)間復(fù)雜度為o(1)晃跺。
思路2的代碼實(shí)現(xiàn)如下：
package chapter6;
import java.util.*;
public class P292_QueueWithMax {
public static class QueueWithMax<T extends Comparable> {
private Deque<InternalData<T>> queueData;
private Deque<InternalData<T>> queueMax;
private int currentIndex;
public QueueWithMax() {
this.queueData = new ArrayDeque<>();
this.queueMax = new ArrayDeque<>();
this.currentIndex = 0;
}
public T max(){
if(queueMax.isEmpty())
return null;
return queueMax.getFirst().value;
}
public void pushBack(T value){
//如果當(dāng)前value比queueMax.getLast大則removeLast
while (!queueMax.isEmpty()&&value.compareTo(queueMax.getLast().value)>=0)
queueMax.removeLast();
InternalData<T> addData = new InternalData<>(value,currentIndex);
queueMax.addLast(addData);
queueData.addLast(addData);
currentIndex++;
}
public T popFront(){
if(queueData.isEmpty())
return null;
InternalData<T> delData = queueData.removeFirst();
//如果queueData中刪除的queueData和queueMax頭元素的index相同
//才在queueMax中移除頭元素
if(delData.index==queueMax.getFirst().index)
queueMax.removeFirst();
return delData.value;
}
private static class InternalData<M extends Comparable> {
public M value;
public int index;
public InternalData(M value,int index){
this.value = value;
this.index = index;
}
}
}
public static void main(String[] args) {
QueueWithMax<Integer> queue = new QueueWithMax<>();
queue.pushBack(3);
System.out.println(queue.max());
queue.pushBack(5);
System.out.println(queue.max());
queue.pushBack(1);
System.out.println(queue.max());
System.out.println("開(kāi)始出隊(duì)后，調(diào)用max");
System.out.println(queue.max());
queue.popFront();
System.out.println(queue.max());
queue.popFront();
System.out.println(queue.max());
queue.popFront();
System.out.println(queue.max());
}
}
- n個(gè)骰子的點(diǎn)數(shù)
題目要求：
把n個(gè)骰子仍在地上毫玖，所有骰子朝上一面的點(diǎn)數(shù)之和為s掀虎。輸入n，打印出s
的所有可能的值的出現(xiàn)概率付枫。
解題思路：
新加入一個(gè)骰子烹玉，它出現(xiàn)1-6的概率是相等的，可以看成各出現(xiàn)一次阐滩，那么
出現(xiàn)和為s的次數(shù)等于再加入之前出現(xiàn)和為s-1,s-2,s-3,s-4,s-5,s-6這
6種情況的次數(shù)之和二打。如此循環(huán)，直到加入n個(gè)骰子結(jié)束掂榔。
package chapter6;
public class P294_DicesProbability {
public static void printProbability(int number){
if(number<=0)
return;
int result[][] = new int[2][6*number+1];
for(int i=1;i<=6;i++)
result[1][i] = 1;
for (int num=2;num<=number;num++){
for(int i=num;i<6*num+1;i++){
for(int j=i-6;j<i;j++)
if(j>0)
result[num%2][i] += result[(num-1)%2][j];
}
}
double sum = 0;
for(int i=number;i<6*number+1;i++)
sum += result[number%2][i];
System.out.println("number = "+number);
for(int i=number;i<6*number+1;i++)
System.out.println("probability "+i+":"+result[number%2][i]/sum);
}
public static void main(String[] args){
printProbability(2);
printProbability(0);
printProbability(11);
}
}
- 撲克牌中的順子
題目要求：
抽取5張牌继效，判斷是不是一個(gè)順子。2-10為數(shù)字本身衅疙，A為1莲趣，J為11，
Q為12饱溢，K為13喧伞，大小王可堪稱任意數(shù)字。
解題思路：
將1-10,J,Q,K記作1-13，大小王記作0潘鲫，0可以轉(zhuǎn)化為任意的1-13的數(shù)字翁逞，
判斷輸入的5個(gè)數(shù)字是否能組成連續(xù)的5個(gè)數(shù)字即可。
package chapter6;
public class P298_ContinousCards {
public static boolean isContinous(int[] data){
if(data==null || data.length!=5)
return false;
int[] table = new int[14];
for(int i=0;i<data.length;i++){
if(data[i]>13||data[i]<0)
return false;
table[data[i]]++;
}
int start = 1;
while (table[start]==0)
start++;
int king = table[0];
for(int i=start;i<start+5;i++){
if(i>13)
break;
if(table[i]>1||table[i]<0)
return false;
else if(table[i]==0){
if(king==0)
return false;
else
king--;
}
}
return true;
}
public static void main(String[] args){
int[] data1 = new int[]{4,2,7,12,1}; //false
int[] data2 = new int[]{0,5,6,12,0}; //false
int[] data3 = new int[]{6,5,8,7,4}; //true
int[] data4 = new int[]{0,5,6,9,8}; //true
int[] data5 = new int[]{0,13,0,12,0}; //true
System.out.println(isContinous(data1));
System.out.println(isContinous(data2));
System.out.println(isContinous(data3));
System.out.println(isContinous(data4));
System.out.println(isContinous(data5));
}
}
- 圓圈中最后剩下的數(shù)字
題目要求：
0溉仑，1挖函，2...n-1這n個(gè)數(shù)字拍成一個(gè)圓圈，從數(shù)字0開(kāi)始浊竟，每次從這個(gè)圓圈里
刪除第m個(gè)數(shù)字怨喘，求剩下的最后一個(gè)數(shù)字。例如0振定，1必怜，2后频，3梳庆，4這5個(gè)數(shù)字組成
的圈，每次刪除第3個(gè)數(shù)字，一次刪除2镇草，0瘤旨，4梯啤，1，因此最后剩下的是3存哲。
解題思路：
最直接的思路是用環(huán)形鏈表模擬圓圈因宇，通過(guò)模擬刪除過(guò)程，可以得到最后剩
下的數(shù)字祟偷，那么這道題目就變成了刪除鏈表中某一個(gè)節(jié)點(diǎn)察滑。假設(shè)總節(jié)點(diǎn)數(shù)為n，
刪除一個(gè)節(jié)點(diǎn)需要走m步修肠，那么這種思路的時(shí)間復(fù)雜度為o(mn)贺辰，空間復(fù)雜度o(n)。
思路2比較高級(jí)，較難理解饲化，可遇不可求莽鸭。將圓圈表示成一個(gè)函數(shù)表達(dá)式，將刪除
節(jié)點(diǎn)的過(guò)程表示成函數(shù)映射的變化吃靠，時(shí)間復(fù)雜度o(n)硫眨，空間復(fù)雜度o(1)!有興趣
的話可以搜素”約瑟夫環(huán)“去詳細(xì)了解。
package chapter6;
import structure.ListNode;
public class P300_LastNumberInCircle {
public static int lastRemaining(int n,int m){
if(n<1||m<1)
return -1;
ListNode<Integer> head = new ListNode<>(0);
ListNode<Integer> cur = head;
for(int i=1;i<n;i++){
ListNode<Integer> node = new ListNode<>(i);
cur.next = node;
cur = cur.next;
}
cur.next = head;
cur = head;
while (true){
//長(zhǎng)度為1結(jié)束循環(huán)
if(cur.next==cur)
return cur.val;
//向后移動(dòng)
for(int i=1;i<m;i++)
cur=cur.next;
//刪除當(dāng)前節(jié)點(diǎn)
cur.val = cur.next.val;
cur.next = cur.next.next;
//刪除后巢块，cur停在被刪節(jié)點(diǎn)的后一節(jié)點(diǎn)處
}
}
//另一個(gè)思路分析過(guò)程較復(fù)雜礁阁，不強(qiáng)求了∽迳荩可搜約瑟夫環(huán)進(jìn)行了解氮兵。
public static void main(String[] args){
System.out.println(lastRemaining(5,3)); //3
System.out.println(lastRemaining(6,7)); //4
System.out.println(lastRemaining(0,7)); //-1
}
}
- 股票的最大利潤(rùn)
題目要求：
求買賣股票一次能獲得的最大利潤(rùn)。例如歹鱼，輸入{9泣栈，11，8弥姻，5南片，7，12庭敦，16疼进，14}，
5的時(shí)候買入秧廉，16的時(shí)候賣出伞广，則能獲得最大利潤(rùn)11。
解題思路：
遍歷過(guò)程中記錄最小值min疼电，然后計(jì)算當(dāng)前值與min的差值diff嚼锄，
并更新maxDiff，maxDiff=max(diff)蔽豺。
package chapter6;
public class P304_MaximalProfit {
public static int maxDiff(int[] data){
if(data==null||data.length<2)
return 0;
int min = data[0];
int maxDiff = data[1] - min;
if(data[1]<min)
min = data[1];
for(int i=2;i<data.length;i++){
if(data[i]-min>maxDiff)
maxDiff = data[i]-min;
if(data[i]<min)
min = data[i];
}
return maxDiff;
}
public static void main(String[] args){
int[] data1 = new int[]{9,11,8,5,7,12,16,14};
int[] data2 = new int[]{9,8,7,6,5,4,3,1};
System.out.println(maxDiff(data1)); //11
System.out.println(maxDiff(data2)); //-1
}
}
- 求1+2+...+n
題目要求：
求1+2+...+n区丑，要求不能使用乘除法，for修陡，while沧侥，if，else魄鸦，switch宴杀，case等關(guān)鍵詞及條件判斷語(yǔ)句？：拾因。
解題思路：
不能用循環(huán)旺罢，那么可以使用遞歸調(diào)用求和斯棒。但又不能使用if，結(jié)束條件如何生效主经？可以使用如下形式替代if語(yǔ)句
替代if的一種方式：boolean b=判斷條件&&(t=遞歸執(zhí)行語(yǔ)句)>0
b并沒(méi)有實(shí)際的用途荣暮，只是為了使表達(dá)式完成。當(dāng)判斷條件不滿足罩驻，遞歸也就結(jié)束了穗酥。
package chapter6;
public class P307_Accumulate {
public static int getSum(int num){
int t=0;
boolean b = (num>0)&&((t=num+getSum(num-1))>0);
return t;
}
public static void main(String[] args){
System.out.println(getSum(10));
}
}
- 不用加減乘除做加法
題目要求：
寫一個(gè)函數(shù)，求兩個(gè)正數(shù)之和惠遏，要求在函數(shù)體內(nèi)不能使用四則運(yùn)算符號(hào)砾跃。
解題思路：
不能用四則運(yùn)算，那只能通過(guò)位運(yùn)算了节吮。其實(shí)四則運(yùn)算是針對(duì)十進(jìn)制抽高，
位運(yùn)算是針對(duì)二進(jìn)制，都能用于運(yùn)算透绩。下面以0011（即3）與0101（即5）
相加為例說(shuō)明
1.兩數(shù)進(jìn)行異或： 0011^0101=0110 這個(gè)數(shù)字其實(shí)是把原數(shù)中不需
進(jìn)位的二進(jìn)制位進(jìn)行了組合
2.兩數(shù)進(jìn)行與： 0011&0101=0001 這個(gè)數(shù)字為1的位置表示需要進(jìn)位翘骂，
而進(jìn)位動(dòng)作是需要向前一位進(jìn)位
3.左移一位： 0001<<1=0010
此時(shí)我們就完成0011 + 0101 = 0110 + 0010的轉(zhuǎn)換
如此轉(zhuǎn)換下去，直到其中一個(gè)數(shù)字為0時(shí)帚豪，另一個(gè)數(shù)字就是原來(lái)的兩個(gè)數(shù)字的和
package chapter6;
public class P310_AddTwoNumbers {
public static int add(int a,int b){
int sum = a^b;
int carry = (a&b)<<1;
int temp;
while (carry!=0){
temp = sum;
sum = sum^carry;
carry = (carry&temp)<<1;
}
return sum;
}
public static void main(String[] args){
System.out.println(add(3,5)); //8
System.out.println(add(3,-5)); //-2
System.out.println(add(0,1)); //1
}
}
不使用新的變量完成交換兩個(gè)原有變量的值
題目要求：
不使用新的變量完成交換兩個(gè)原有變量的值碳竟。
解題思路：
有加減法與亦或法兩種，其實(shí)思路是一致的狸臣。推薦亦或法莹桅，不僅僅是代碼上更簡(jiǎn)單，
而且亦或的運(yùn)算在理論上也要比加減法更快烛亦。
package chapter6;
public class P312_ExchangeTwoNumbers {
public static void main(String[] args){
//基于加減法
int a = 3;
int b = 5;
a = a + b;
b = a - b;
a = a - b;
System.out.println("a="+a+",b="+b);
//基于異或法
a = 3;
b = 5;
a = a ^ b;
b = a ^ b;
a = a ^ b;
System.out.println("a="+a+",b="+b);
}
}
- 構(gòu)建乘積數(shù)組
題目要求：
給定數(shù)組A[0,1...n-1]诈泼，求B[0,1...n-1]，要求
B[i] = A[0]*A[1]...A[i-1]*A[i+1]...A[n-1]煤禽，不能使用除法铐达。
解題思路：
如果沒(méi)有不能用除法的限制，可以通過(guò)∑A/A[i]求得B[i]呜师，
同時(shí)要注意A[i]等于0的情況娶桦。
既然不能使用除法贾节，那就只好用純乘法計(jì)算汁汗。如果每一個(gè)B中的元素都用
乘法計(jì)算，那么時(shí)間復(fù)雜度為0(n^2)栗涂。
使用純乘法知牌，還有更高效的思路。定義C[i]=A[0]*A[1]...A[i-1]斤程，
那么C[i]=C[i-1]*A[n-1]角寸；定義D[i]=A[i+1]*...A[n-2]*A[n-1],
那么D[i] =D[i+1]*A[i+1]菩混；因此C[i],D[i]都可以遞推地求出來(lái)，
且B[i]=C[i]*D[i]扁藕。步驟如下：
1.計(jì)算C數(shù)組沮峡；
2.依次求得D[0],D[1]...D[n-1]，同時(shí)完成B[i]=C[i]\*D[i]的計(jì)算亿柑。
如果最終結(jié)果存放于result[]中邢疙，第一步的C的值就可以先放到result中，
而D的元素可以存放于一個(gè)變量temp中望薄，
通過(guò)result[i] = temp\*result[i]求得B疟游。
時(shí)間復(fù)雜度o(n)，由于計(jì)算B必然要申請(qǐng)長(zhǎng)度為n的空間痕支，除此之外颁虐，
該方法僅申請(qǐng)了幾個(gè)變量，空間復(fù)雜度o(1)卧须。
package chapter6;
public class P313_ConstructArray {
public static int[] multiply(int[] data){
if(data==null||data.length<2)
return null;
int[] result = new int[data.length];
//求得數(shù)組C另绩，存于result中
result[0] = 1;
for(int i=1;i<result.length;i++)
result[i] = result[i-1]*data[i-1];
//先求得數(shù)組D中元素，再與C中元素相乘花嘶，存于result中
int temp = 1;
for(int i=data.length-2;i>=0;i--){
//數(shù)組D中的元素值
temp = temp * data[i+1];
//計(jì)算B[i]=C[i]*D[i]
result[i] = result[i] * temp;
}
return result;
}
public static void main(String[] args){
int[] data = new int[]{1,2,3,4,5};
int[] result = multiply(data);
for(int i=0;i<result.length;i++){
System.out.print(result[i]);
System.out.print(" ");
}
}
}
- 把字符串轉(zhuǎn)換成整數(shù)
題目要求：
如題板熊。
解題思路：
此題比較麻煩的點(diǎn)是特殊情況較多，需要考慮完全察绷。
1.如果字符串前后有空格干签，要去除；
2.如果是空串或null拆撼，要特殊處理容劳；
3.如果頭部有多個(gè)正負(fù)號(hào)，要特殊處理闸度；
4.如果數(shù)值超出int的范圍竭贩，要特殊處理；比int的最大值還要大莺禁，已經(jīng)上溢留量，
這肯定不能通過(guò)數(shù)字的大小比較，所以需要在字符串的狀態(tài)下判斷是否上溢或下溢哟冬。
5.遇到非數(shù)字的字符，則轉(zhuǎn)換停止浩峡；
剛剛發(fā)現(xiàn)一個(gè)新的情況未做處理可岂，在數(shù)字之前有多個(gè)0,如果0之后的數(shù)字有溢出情況恃轩，
而前面的0又沒(méi)有去處舆床，這種溢出就不會(huì)被捕獲停局，還缺這個(gè)情況的判斷拷邢。這種思路真心
不好，一條主線是轉(zhuǎn)換成整數(shù)平斩，中間穿插出很多特殊情況的分支亚享，感覺(jué)就像在打補(bǔ)丁。
package chapter7;
public class P318_StringToInt {
// atoi的需求是這樣的：
// 如果前面有空格绘面，需要剔除空格虹蒋；
// 剔除空格后，第一個(gè)字符串如果是+號(hào)飒货，認(rèn)為是正數(shù)魄衅；如果是-號(hào)，認(rèn)為是負(fù)數(shù)塘辅；
// 后面的字符如果不是數(shù)字晃虫，那么返回0，如果是數(shù)字扣墩，返回實(shí)際的數(shù)字哲银。遇到不是數(shù)字的字符，轉(zhuǎn)換結(jié)束呻惕。
// 此外荆责，要考慮空串問(wèn)題，數(shù)值溢出問(wèn)題[2^(-31) ~ 2^31-1]亚脆。
public static int strToInt(String str) throws Exception{
if(str==null || str.length()==0)
throw new Exception("待轉(zhuǎn)換字符串為null或空串");
String MAX_INT_PLUS_1 = Integer.toString(Integer.MIN_VALUE).substring(1);
StringBuilder stringBuilder = new StringBuilder(str.trim());
int flag = 0; //記錄無(wú)符號(hào)的正（2）正（1）做院，負(fù)（-1）,初始值（0）
if(stringBuilder.charAt(0)=='-')
flag = -1;
else if(stringBuilder.charAt(0)=='+')
flag = 1;
else if(stringBuilder.charAt(0)>='0'&&stringBuilder.charAt(0)<='9')
flag = 2;
else
return 0;
int endIndex = 1;
while (endIndex<stringBuilder.length()&&stringBuilder.charAt(endIndex)>='0'&&stringBuilder.charAt(endIndex)<='9')
endIndex++;
if(flag==2){
if(stringBuilder.substring(0,endIndex).toString().compareTo(MAX_INT_PLUS_1)>=0)
throw new Exception("數(shù)值上溢,待轉(zhuǎn)換字符串為"+str);
return Integer.parseInt(stringBuilder.substring(0,endIndex));
}
else{
if(flag==1&&stringBuilder.substring(1,endIndex).compareTo(MAX_INT_PLUS_1)>=0)
throw new Exception("數(shù)值上溢,待轉(zhuǎn)換字符串為"+str);
if(flag==-1&&stringBuilder.substring(1,endIndex).compareTo(MAX_INT_PLUS_1)>0)
throw new Exception("數(shù)值下溢,待轉(zhuǎn)換字符串為"+str);
if(flag==-1&&stringBuilder.substring(1,endIndex).compareTo(MAX_INT_PLUS_1)==0)
//此處注意，此種情況不能用絕對(duì)值*（-1）濒持，該絕對(duì)值已經(jīng)超出正數(shù)的最大值
return Integer.MIN_VALUE;
return flag*Integer.parseInt(stringBuilder.substring(1,endIndex));
}
}
public static void funcTest(){
try {
System.out.println(strToInt(" 100")); //100
System.out.println(strToInt("-100")); //-100
System.out.println(strToInt("0")); //0
System.out.println(strToInt("-0"));//0
System.out.println(strToInt("1.23")); //1
System.out.println(strToInt("-1.23")); //-1
System.out.println(strToInt(".123")); //0
}
catch (Exception e){
e.printStackTrace();
}
}
public static void edgeTest(){
try {
System.out.println(strToInt("2147483647")); //2147483647
}
catch (Exception e){
System.out.println(e.getMessage());
}
try {
System.out.println(strToInt("-2147483647")); //-2147483647
}
catch (Exception e){
System.out.println(e.getMessage());
}
try {
System.out.println(strToInt("2147483647")); //2147483647
}
catch (Exception e){
System.out.println(e.getMessage());
}
try {
System.out.println(strToInt("2147483648")); //上溢
}
catch (Exception e){
System.out.println(e.getMessage());
}
try {
System.out.println(strToInt("-2147483648")); //-2147483648
}
catch (Exception e){
System.out.println(e.getMessage());
}
try {
System.out.println(strToInt("-2147483649")); //下溢
}
catch (Exception e){
System.out.println(e.getMessage());
}
try {
System.out.println(strToInt(null)); //待轉(zhuǎn)換字符串為null或空串
}
catch (Exception e){
System.out.println(e.getMessage());
}
try {
System.out.println(strToInt("")); //待轉(zhuǎn)換字符串為null或空串
}
catch (Exception e){
System.out.println(e.getMessage());
}
}
public static void main(String[] args){
funcTest();
edgeTest();
}
}
- 樹(shù)中兩個(gè)節(jié)點(diǎn)的最低公共祖先
題目要求：
輸入一棵樹(shù)的根節(jié)點(diǎn)键耕，輸入兩個(gè)被觀察節(jié)點(diǎn)，求這兩個(gè)節(jié)點(diǎn)的最低(最近)公共祖先柑营。
解題思路：
此題比較開(kāi)放屈雄，主要是對(duì)于“樹(shù)”沒(méi)有做明確說(shuō)明，所以原書中就對(duì)樹(shù)的可能情況做了假設(shè)官套，
然后就衍生出多種思路
1）如果是二叉酒奶，搜索樹(shù)：
遍歷找到比第一個(gè)節(jié)點(diǎn)大，比第二個(gè)節(jié)點(diǎn)小的節(jié)點(diǎn)即可
2）如果是父子間有雙向指針的樹(shù)：
由下往上看奶赔，轉(zhuǎn)化為找兩個(gè)鏈表的第一個(gè)公共節(jié)點(diǎn)問(wèn)題
3）如果只是一個(gè)包含父到子的指針的普通樹(shù)：
3.1）如果不能使用額外空間惋嚎，從根節(jié)點(diǎn)開(kāi)始判斷他的子樹(shù)是否包含那兩個(gè)節(jié)點(diǎn)，
找到最小的的子樹(shù)即可
時(shí)間復(fù)雜度o(n^2)(此為最差纺阔，平均不太好算瘸彤。。笛钝。),空間復(fù)雜度為o(1)
3.2) 如果能用額外空間质况，可以遍歷兩次(深度優(yōu)先)獲取根節(jié)點(diǎn)到那兩個(gè)節(jié)點(diǎn)的路徑，
然后求兩個(gè)路徑的最后一個(gè)公共節(jié)點(diǎn)玻靡。 時(shí)間復(fù)雜度o(n)结榄，空間復(fù)雜度o(logn)
(1)(2)比較簡(jiǎn)單。下面僅對(duì)(3)囤捻，以下圖所示的樹(shù)為例臼朗，進(jìn)行思路實(shí)現(xiàn)與求解驗(yàn)證
A
/ \
B C
/ \
D E
/ \ / | \
F G H I J
import java.util.*;
public class P326CommonParentInTree {
public static class CommonTreeNode{
public char val;
public List<CommonTreeNode> children;
public CommonTreeNode(char val){
this.val = val;
children = new LinkedList<>();
}
public void addChildren(CommonTreeNode... children){
for(CommonTreeNode child:children)
this.children.add(child);
}
}
// 3.1所述的解法
public static CommonTreeNode getLastParent1(CommonTreeNode root,CommonTreeNode node1,CommonTreeNode node2){
if(root==null || node1==null || node2==null || !isInSubTree(root,node1,node2))
return null;
CommonTreeNode curNode = root;
while (true){
for(CommonTreeNode child:curNode.children){
if(isInSubTree(child,node1,node2)){
curNode = child;
break;
}
if(child==curNode.children.get(curNode.children.size()-1))
return curNode;
}
}
}
public static boolean isInSubTree(CommonTreeNode root,CommonTreeNode node1,CommonTreeNode node2){
Queue<CommonTreeNode> queue = new LinkedList<>();
CommonTreeNode temp = null;
int count = 0;
queue.add(root);
while (count!=2 && !queue.isEmpty()){
temp = queue.poll();
if(temp==node1||temp==node2)
count++;
if(!temp.children.isEmpty())
queue.addAll(temp.children);
}
if(count==2)
return true;
return false;
}
// 3.2所述的解法
public static CommonTreeNode getLastParent2(CommonTreeNode root,CommonTreeNode node1,CommonTreeNode node2){
List<CommonTreeNode> path1 = new ArrayList<>();
List<CommonTreeNode> path2 = new ArrayList<>();
getPath(root,node1,path1);
getPath(root,node2,path2);
CommonTreeNode lastParent = null;
for(int i=0;i<path1.size()&&i<path2.size();i++){
if(path1.get(i)==path2.get(i))
lastParent = path1.get(i);
else
break;
}
return lastParent;
}
public static boolean getPath(CommonTreeNode root,CommonTreeNode node,List<CommonTreeNode> curPath){
if(root==node)
return true;
curPath.add(root);
for(CommonTreeNode child:root.children){
if(getPath(child,node,curPath))
return true;
}
curPath.remove(curPath.size()-1);
return false;
}
public static void main(String[] args){
CommonTreeNode root = new CommonTreeNode('A');
CommonTreeNode b = new CommonTreeNode('B');
CommonTreeNode c = new CommonTreeNode('C');
CommonTreeNode d = new CommonTreeNode('D');
CommonTreeNode e = new CommonTreeNode('E');
CommonTreeNode f = new CommonTreeNode('F');
CommonTreeNode g = new CommonTreeNode('G');
CommonTreeNode h = new CommonTreeNode('H');
CommonTreeNode i = new CommonTreeNode('I');
CommonTreeNode j = new CommonTreeNode('J');
root.addChildren(b,c);
b.addChildren(d,e);
d.addChildren(f,g);
e.addChildren(h,i,j);
System.out.println(getLastParent1(root,f,h).val);
System.out.println(getLastParent2(root,f,h).val);
System.out.println(getLastParent1(root,h,i).val);
System.out.println(getLastParent2(root,h,i).val);
}
}
