題2: 實(shí)現(xiàn)單例類 - done
題3: 二維數(shù)據(jù)查找 - done
題14: 調(diào)整數(shù)組順序糙及，使奇數(shù)在前偶數(shù)在后 - done
題20: 順時(shí)針打印數(shù)組- done
題29: 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字 - done
題30: 最小的K個(gè)數(shù) - done
題31: 連續(xù)子數(shù)組和的最大值 - done
題41: 有序數(shù)組查找“和為s”的兩個(gè)數(shù) - done
題51: 數(shù)組中重復(fù)的數(shù)字 - done
分析規(guī)律+快排定位的方法
題5: 單鏈表反向打印 - done
題13: 在O(1)時(shí)間刪除單鏈表節(jié)點(diǎn) - done
題15: 單鏈表查找倒數(shù)第k個(gè)節(jié)點(diǎn) - done
題16: 單鏈表反轉(zhuǎn) - done
題17: 合并兩個(gè)升序單鏈表 - done
題37: 兩個(gè)單鏈表的第一個(gè)公共節(jié)點(diǎn) - done
遞歸+多個(gè)指針
題7: 兩個(gè)棧實(shí)現(xiàn)隊(duì)列 - done
題7.1: 兩個(gè)隊(duì)列實(shí)現(xiàn)棧 - done
題9: 斐波那契數(shù)列 - done
題10: 二進(jìn)制中1的個(gè)數(shù) - done
題40: 數(shù)組中只出現(xiàn)一次的數(shù) - done
題45: 約瑟夫問題 - done
題47: 不用加減乘除實(shí)現(xiàn)加法 - done
題47.1: 不使用新的變量练俐，交換兩個(gè)變量的值 - done
總結(jié)出數(shù)學(xué)公式+位運(yùn)算+遞歸
題35: 第一個(gè)只出現(xiàn)一次的字符 - done
題58: 二叉樹的下一個(gè)節(jié)點(diǎn)
題58: 判斷一個(gè)二叉樹是否對(duì)稱
題60: 二叉樹打印成多行
題61: 之字形打印二叉樹
題62: 二叉搜索樹的第k個(gè)節(jié)點(diǎn)
題62.1: 二叉樹中序遍歷
題2: 實(shí)現(xiàn)單例類
單例模式：
- 單例類確保該類只有唯一一個(gè)實(shí)例
- 單例類自己創(chuàng)建這一實(shí)例
- 單例類給所有其他對(duì)象提供這一實(shí)例
最簡(jiǎn)單的實(shí)現(xiàn)方式
// 餓漢式單例
public class Single {
private static Single single = new Single();
private Single() {
}
public static Single getSingle() {
return single;
}
}
解釋
- static變量也叫靜態(tài)變量朝聋，靜態(tài)變量被所有的對(duì)象所共享禾锤，在內(nèi)存中只有一個(gè)副本颖系。餓漢式單例在類加載初始化時(shí)就創(chuàng)建好一個(gè)靜態(tài)的對(duì)象供外部使用哩治，除非系統(tǒng)重啟，這個(gè)對(duì)象不會(huì)改變衷快，所以本身就是線程安全的。
- 構(gòu)造方法限定為private避免了類在外部被實(shí)例化
- Single類的唯一實(shí)例只能通過getSingle()方法訪問
缺點(diǎn)
無論這個(gè)類是否被使用姨俩，都會(huì)被實(shí)例化蘸拔，浪費(fèi)內(nèi)存
較好的實(shí)現(xiàn)方式
public class Single1 {
// volatile保證不同線程對(duì)這個(gè)變量進(jìn)行操作時(shí)的可見性
// 即一個(gè)線程修改了某個(gè)變量的值师郑，這新值對(duì)其他線程來說是立即可見的
private volatile static Single1 single1 = null;
private Single1() {
}
public static Single1 getSingle1() {
// 如果每次執(zhí)行g(shù)etSingle1都加鎖，很影響性能
// 因此先判斷调窍，如果null宝冕，加鎖初始化，如果非null邓萨，直接返回
if (single1 == null) {
synchronized (Single1.class) { // 鎖地梨，保證線程安全
if (single1 == null) {
single1 = new Single1();
}
}
}
return single1;
}
}
https://www.cnblogs.com/limingluzhu/p/5156659.html
題3: 二維數(shù)組查找
題14: 調(diào)整數(shù)組順序，使奇數(shù)在前偶數(shù)在后
// 調(diào)整數(shù)組順序缔恳，使奇數(shù)在前偶數(shù)在后
private static void handleArr(int[] arr) {
if (arr == null) {
return;
}
int start = 0;
int end = arr.length - 1;
int tem;
while (start != end) {
if ((arr[start] & 1) == 1) { // 奇數(shù)
start++;
}else { // 偶數(shù)
tem = arr[start];
arr[start] = arr[end];
arr[end] = tem;
end--;
}
}
}
題20: 順時(shí)針打印數(shù)組
思路：確定圈數(shù)宝剖，針對(duì)圈中每條邊分別打印，注意邊界
// 順時(shí)針打印數(shù)組
private static void circlePrintArr(int[][] arr) {
if (arr == null || arr.length <= 0 || arr[0].length <= 0) {
return;
}
int row = arr.length; // 總行數(shù)
int col = arr[0].length; // 總列數(shù)
int totalCir = (Math.min(row, col) + 1) >> 1; // 一共打印的圈數(shù)
for (int start = 0; start < totalCir; start++) {
printCircle(arr, row, col, start);
}
}
// row總行數(shù)歉甚，col總列數(shù)万细，start當(dāng)前圈數(shù)
private static void printCircle(int[][] arr, int row, int col, int start) {
// 邊界：左上角arr[start][start]
// 邊界：右下角arr[endX][endY]
int endX = row - start - 1;
int endY = col - start - 1;
// 打印上邊
for (int i = start; i <= endY; i++) {
System.out.print(arr[start][i] + " ");
}
// 打印右邊
for (int i = start + 1; i <= endX; i++) {
System.out.print(arr[i][endY] + " ");
}
// 打印下邊
if (endX > start) {
for (int i = endY - 1; i >= start; i--) {
System.out.print(arr[endX][i] + " ");
}
}
// 打印左邊
if (endY > start) {
for (int i = endX - 1; i >= start + 1; i--) {
System.out.print(arr[i][start] + " ");
}
}
}
題29: 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字
描述：數(shù)組中又一個(gè)數(shù)字出現(xiàn)的次數(shù)，大于數(shù)組長(zhǎng)度的一半纸泄，找出這個(gè)數(shù)
思路一：
- 快排定位方法
- 定位一次赖钞，如果定位不在中間，則重長(zhǎng)的子數(shù)組在進(jìn)行定位聘裁，直到定位在中間
思路二：
時(shí)間復(fù)雜度O(n) - 維護(hù)兩個(gè)數(shù)仁烹，一個(gè)存值，一個(gè)存值出現(xiàn)的次數(shù)
- 遍歷數(shù)組咧虎，相同-加次數(shù)卓缰，不同-減次數(shù)，次數(shù)為0-更新值
// 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字
private static Integer moreThanHalfNum(int[] arr) {
if (arr == null || arr.length <= 1) {
return null;
}
int key = arr[0];
int cnt = 1;
for (int i = 1; i < arr.length; i++) {
if (cnt == 0) {
key = arr[i];
cnt++;
}else if (arr[i] == key) {
cnt++;
}else {
cnt--;
}
}
return key;
}
題30: 最小的K個(gè)數(shù)
思路：利用快排的定位方法
- 定位砰诵，判斷左邊個(gè)數(shù)如果不為k-1征唬，繼續(xù)定位，直到左邊個(gè)數(shù)為k-1
// 最小的k個(gè)數(shù)
private static void leastKNumbers(int[] arr, int k) {
if (arr == null || k <= 0 || arr.length < k) {
return;
}
int start = 0;
int end = arr.length - 1;
int pos = Sort.position(arr, start, end);
while (pos != k - 1) {
if (pos > k - 1) {
end = pos - 1;
}else {
start = pos + 1;
}
pos = Sort.position(arr, start, end);
}
for (int i = 0; i < k; i++) {
System.out.print(arr[i] + " ");
}
}
題31: 連續(xù)子數(shù)組和的最大值
思路：時(shí)間復(fù)雜度O(n)
- 用f(i)來表示茁彭，所有以i結(jié)尾的子數(shù)組中总寒，子數(shù)組和的最大值
- 那么題目答案轉(zhuǎn)換為，求max(f(i))
- 如果f(i-1)小于0理肺，那么f(i) = arr[i]摄闸，如果f(i-1)大于0，那么f(i) = f(i-1) + arr[i]
// 連續(xù)子數(shù)組妹萨，和的最大值
private static Integer findMax(int[] arr) {
if (arr == null || arr.length == 0) {
return null;
}
int sum = 0; // f(i)
int arrMax = 0x80000000; // max(f(i))
for (int i = 0; i <= arr.length - 1; i++) {
if (sum <= 0) {
sum = arr[i];
}else {
sum = sum + arr[i];
}
if (sum > arrMax) {
arrMax = sum;
}
}
return arrMax;
}
題41: 有序數(shù)組查找“和為s”的兩個(gè)數(shù)
思路：頭尾兩個(gè)指針
// 有序數(shù)組查找“和為s”的兩個(gè)數(shù)
private static boolean findNumWithSum(int[] arr, int sum) {
if (arr == null || arr.length < 2) {
return false;
}
int start = 0;
int end = arr.length - 1;
int curSum;
while (end > start) {
curSum = arr[start] + arr[end];
if (curSum == sum) {
System.out.println(arr[start]);
System.out.println(arr[end]);
return true;
}else if (curSum > sum) {
end--;
}else {
start++;
}
}
return false;
}
題51: 數(shù)組中重復(fù)的數(shù)字
描述：長(zhǎng)度為n的數(shù)組年枕，沒個(gè)數(shù)都在[0, n-1]內(nèi)，求數(shù)組中是否有重復(fù)數(shù)字
思路：分析數(shù)組規(guī)律乎完，如果數(shù)組中沒有重復(fù)數(shù)字熏兄，那么下標(biāo)為i的位置，值也為i
// 數(shù)組中重復(fù)的數(shù)字
private static boolean isRepeat(int[] arr) {
if (arr == null || arr.length == 0) {
return false;
}
int tem;
for (int i = 0; i < arr.length; i++) {
while (arr[i] != i) {
if (arr[i] == arr[arr[i]]) {
System.out.println(arr[i]);
return true;
}
tem = arr[i];
arr[i] = arr[tem];
arr[tem] = tem;
}
}
return false;
}
題5: 單鏈表反向打印
提示：遞歸
private static void reverseList(Node node) {
if (node == null) {
return;
}
if (node.next == null) {
System.out.println(node.num);
return;
}
reverseList(node.next);
System.out.println(node.num);
}
題13: 在O(1)時(shí)間刪除單鏈表節(jié)點(diǎn)
描述：假定待刪除節(jié)點(diǎn)在給定鏈表內(nèi)
思路：有O(1)的時(shí)間要求，不能遍歷摩桶，可以用“待刪除節(jié)點(diǎn)的next節(jié)點(diǎn)”的內(nèi)容桥状，覆蓋“待刪除節(jié)點(diǎn)”的內(nèi)容。
比如
- 給定鏈表：n1 -> n2 -> n3 -> n4 -> null
-
刪除節(jié)點(diǎn)：n2
此時(shí)一定不能用n2 = n3硝清，因?yàn)閚2 = n3達(dá)到的效果如下圖辅斟，n2原來指向b93，執(zhí)行n2 = n3后芦拿，n2指向80c士飒，而原鏈表并沒有變化
IMG_4117.JPG
而應(yīng)該用n3的內(nèi)容覆蓋n2的內(nèi)容，然后刪除n3
// O(1)時(shí)間內(nèi)刪除單鏈表節(jié)點(diǎn)
private static void delNode(Node head, Node delNode) {
if (head == null || delNode == null) {
return;
}
Node tem;
// 待刪除節(jié)點(diǎn)不是尾節(jié)點(diǎn)
if (delNode.next != null) {
tem = delNode.next;
delNode.num = tem.num;
delNode.next = tem.next;
}else if (head != delNode){ // 待刪除節(jié)點(diǎn)不是頭節(jié)點(diǎn)防嗡，是尾節(jié)點(diǎn)
tem = head;
while (tem.next != delNode) {
tem = tem.next;
}
tem.next = null;
delNode = null;
}else { // 鏈表長(zhǎng)度1变汪，刪除頭節(jié)點(diǎn)
head = null;
delNode = null;
}
tem = null;
}
雖然有一種場(chǎng)景需要遍歷n-1侠坎，但是平均時(shí)間復(fù)雜度仍然是O(1)蚁趁，不再解釋
題15: 單鏈表查找倒數(shù)第k個(gè)節(jié)點(diǎn)
思路：先做條件判斷，以免程序崩潰
- 鏈表為空
- k <= 0
- k大于鏈表長(zhǎng)度
// 單鏈表倒數(shù)第k個(gè)節(jié)點(diǎn)
private static Node findKTail(Node head, int k) {
if (head == null || k <= 0) {
return null;
}
Node fast = head;
// 快慢指針实胸，快指針先走k-1步
for (int i = 0; i < k - 1; i++) {
fast = fast.next;
if (fast == null) { // k大于鏈表長(zhǎng)度
return null;
}
}
Node slow = head;
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
題16: 單鏈表反轉(zhuǎn)
思路：三個(gè)指針
private Node singleListRoll(Node node) {
if (node == null) {
return null;
}
Node pre = null;
Node cur = node;
Node nex;
while(cur != null) {
nex = cur.next;
cur.next = pre;
pre = cur;
cur = nex;
}
return pre;
}
題17: 合并兩個(gè)升序單鏈表
思路：用遞歸做
// 合并兩個(gè)升序鏈表
private static Node merge1(Node h1, Node h2) {
if (h1 == null) {
return h2;
}
if (h2 == null) {
return h1;
}
Node h = null;
if (h1.num <= h2.num) {
h = h1;
h.next = merge1(h1.next, h2);
}else {
h = h2;
h.next = merge1(h1, h2.next);
}
return h;
}
題37: 兩個(gè)單鏈表的第一個(gè)公共節(jié)點(diǎn)
思路：時(shí)間復(fù)雜度O(n)
- 先得到兩個(gè)鏈表長(zhǎng)度
- 長(zhǎng)鏈表先走
- 兩個(gè)鏈表一起走他嫡，第一個(gè)相同
// 兩個(gè)單鏈表第一個(gè)相同節(jié)點(diǎn)
private static Node findFirstNode(Node h1, Node h2) {
if (h1 == null || h2 == null) {
return null;
}
int l1 = nodeLength(h1);
int l2 = nodeLength(h2);
Node longNode = h1;
Node shorNode = h2;
int dif = l1 - l2;
if (l2 > l1) {
longNode = h2;
shorNode = h1;
dif = l2 - l1;
}
for (int i = 0; i < dif; i++) {
longNode = longNode.next;
}
while (longNode != null && shorNode != null) {
if (longNode == shorNode) {
break;
}
longNode = longNode.next;
shorNode = shorNode.next;
}
return longNode;
}
private static int nodeLength(Node node) {
int l = 0;
Node n = node;
while (n != null) {
l++;
n = n.next;
}
return l;
}
題7: 兩個(gè)棧實(shí)現(xiàn)隊(duì)列
思路：
- 兩個(gè)棧，一個(gè)做“入椔辏”钢属，一個(gè)做“出棧”
- “出椕徘”為空淆党，“入棧”數(shù)據(jù)導(dǎo)入到“出椦攘梗”染乌，繼續(xù)
public class WQueue {
private Stack<Integer> stack1 = new Stack<Integer>();
private Stack<Integer> stack2 = new Stack<Integer>();
// 在隊(duì)列尾部插入元素
public void appendTail(int num) {
stack1.push(num);
}
// 從隊(duì)列頂部刪除一個(gè)元素
public Integer deleteHead() throws Exception {
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.pop()); // push入棧，pop出棧
}
}
if (stack2.empty()) {
throw new Exception("something wrong");
}
return stack2.pop();
}
}
題7.1: 兩個(gè)隊(duì)列實(shí)現(xiàn)棧
思路：
- 任何時(shí)候都維持“一個(gè)隊(duì)列空懂讯，另一個(gè)隊(duì)列非空”
- 出棧時(shí)荷憋，把“非空隊(duì)列”除隊(duì)尾外的數(shù)據(jù)，導(dǎo)入“空隊(duì)列”褐望，刪除“非空隊(duì)列”對(duì)尾元素
// 兩個(gè)隊(duì)列實(shí)現(xiàn)棧
public class WStack {
private Queue<Integer> queue1 = new LinkedList<Integer>();
private Queue<Integer> queue2 = new LinkedList<Integer>();
// 入棧
public void append(int num) {
if (queue1.isEmpty()) {
queue2.offer(num); // offer入隊(duì)列勒庄，poll出隊(duì)列
}else {
queue1.offer(num);
}
}
// 出棧
public Integer delete() {
Integer res = null;
if (!queue1.isEmpty()) {
while (queue1.size() > 1) {
queue2.offer(queue1.poll());
}
res = queue1.poll();
}else if (!queue2.isEmpty()) {
while (queue2.size() > 1) {
queue1.offer(queue2.poll());
}
res = queue2.poll();
}
return res;
}
}
題9: 斐波那契數(shù)列
f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)
解法一：遞歸
// 斐波那契數(shù)列
private static int fibo(int n) {
if (n < 0) {
return 0;
}
if (n <= 1) {
return n;
}
return fibo(n - 1) + fibo(n - 2);
}
上述解法存在很多重復(fù)計(jì)算，比如計(jì)算f(7)瘫里，需要計(jì)算3次f(4)实蔽，隨著n的增大，重復(fù)計(jì)算節(jié)點(diǎn)會(huì)指數(shù)遞增谨读，而直接計(jì)算反而好些
解法二：直接計(jì)算
// 斐波那契數(shù)列
private static int fibo1(int n) {
if (n < 0) {
return 0;
}
if (n <= 1) {
return n;
}
int n1 = 0;
int n2 = 1;
int sum = n1 + n2;
for (int i = 2; i <= n; i++) {
sum = n1 + n2;
n1 = n2;
n2 = sum;
}
return sum;
}
很多問題可以轉(zhuǎn)化為斐波那契數(shù)列盐须，遇到問題先分析規(guī)律，先走一步找規(guī)律
題10: 二進(jìn)制中1的個(gè)數(shù)
輸入int數(shù)，輸出二進(jìn)制中1的個(gè)數(shù)
思路：
- 不能用除以2贼邓，因?yàn)樨?fù)數(shù)的時(shí)候會(huì)出錯(cuò)阶冈，比如-1的二進(jìn)制是32個(gè)1，應(yīng)該輸出32
- 每一位都做&運(yùn)算
// 二進(jìn)制中1的個(gè)數(shù)
private static int numOf1(int n) {
int cnt = 0;
int flag = 1;
while (flag != 0) {
if ((n & flag) == flag) {
cnt++;
}
flag = flag << 1;
}
return cnt;
}
tips：把一個(gè)整數(shù)減去1塑径，在和原來的整數(shù)做&運(yùn)算女坑，得到的結(jié)果相當(dāng)于把整數(shù)的二進(jìn)制表示中最右邊的一個(gè)1變?yōu)?，很多問題可以用這個(gè)思路解決
題40: 數(shù)組中只出現(xiàn)一次的數(shù)
描述：給定數(shù)組统舀，只有兩個(gè)數(shù)只出現(xiàn)一次匆骗，其余數(shù)均出現(xiàn)了兩次，找出這兩個(gè)數(shù)
思路：
- 任何一個(gè)數(shù)字異或它自己都等于0誉简，異或滿足結(jié)合律
- 如果數(shù)組中“只有一個(gè)數(shù)字只出現(xiàn)一次”碉就，那么把整個(gè)數(shù)組異或一邊，就能得到要找的數(shù)字
- 如果數(shù)組中“只有一個(gè)數(shù)字只出現(xiàn)一次”闷串，嘗試把數(shù)字分為兩部分瓮钥，每部分“只有一個(gè)數(shù)字出現(xiàn)一次”
- 這兩個(gè)數(shù)字是不同的，因此他們異或的結(jié)果烹吵，二進(jìn)制一定有一位是1碉熄，把這一位作為標(biāo)識(shí)位，把數(shù)組分為兩部分肋拔，問題解決
// 數(shù)組中只出現(xiàn)一次的數(shù)字
private static void findTwoInt(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum ^= arr[i];
}
// 找出key1 ^ key2 中為1的位(倒數(shù)第index位)
int index = 1;
while ((sum & 1) != 1) {
sum = sum >> 1;
index++;
}
int key1 = 0;
int key2 = 0;
for (int i = 0; i < arr.length; i++) {
if (splitArr(arr[i], index)) {
key1 ^= arr[i];
}else {
key2 = key2 ^ arr[i];
}
}
System.out.println(key1 + " " + key2);
}
private static boolean splitArr(int num, int index) {
num = num >> (index - 1);
return (num & 1) == 1;
}
題45: 約瑟夫問題
描述：0,1...n-1這n個(gè)人按順序排成一個(gè)圓圈锈津，從0開始報(bào)數(shù)，報(bào)到m-1的人退出凉蜂，剩下的人繼續(xù)從0開始報(bào)數(shù)琼梆，求最后勝利者的編號(hào)
比如：0,1,2,3,4這五個(gè)數(shù)，m=3窿吩，則依次刪除2,0,4,1茎杂，最后3勝出
思路：總結(jié)出數(shù)學(xué)規(guī)律
- 用f(n)表示最后勝出的人
- 那么第一個(gè)一定是(m-1)%n退出，然后從k=m%n開始爆存，繼續(xù)報(bào)數(shù)
k, k+1, k+2 ... n-2, n-1, 0, 1, 2 ... k-2 -
剩下的問題就完全變?yōu)榱薾-1個(gè)人的新約瑟夫環(huán)問題蛉顽，我們把他們的編號(hào)做一下轉(zhuǎn)換
IMG_4119.JPG - 原問題的解f(n)，等于左邊環(huán)的解（也就是第2步的環(huán)的解先较，這個(gè)好理解）
- 另外不管編號(hào)如何變化携冤，最后勝出者的位置是不變的（也就是第3步，左右兩個(gè)環(huán)的解位置相同）
- 左邊編號(hào)x'闲勺，到右邊編號(hào)x曾棕，有映射關(guān)系x'=(x+k)%n
- 假設(shè)最后的解位于圖標(biāo)出的位置，即
-- f(n)=x'
-- f(n-1)=x
-- x'=(x+k)%n - 于是菜循，f(n)=[f(n-1)+k]%n=[f(n-1)+m]%n (n>1的時(shí)候)
// 約瑟夫環(huán)
private static int lastWin(int n, int m) {
if (n <= 0 || m <= 0) {
return -1;
}
int last = 0;
for (int i = 2; i <= n; i++) {
last = (last + m) % i;
}
return last;
}
題47: 不用加減乘除實(shí)現(xiàn)加法
思路：
- 二進(jìn)制翘地，加法用異或代替，進(jìn)位用與代替
- 如果進(jìn)位到了符號(hào)位，比如0x40000000+0x40000000衙耕，那么將得到0x80000000昧穿，也就是1073741824+1073741824=-2147483648，這是不合理的橙喘，但是如果直接用十進(jìn)制加法得到的也是這個(gè)結(jié)果时鸵，因?yàn)檫@種情況溢出了，所以我們的算法還是正確的
// 不用加減乘除做加法
private static int sum(int i1, int i2) {
int sum; // 不考慮進(jìn)位的和
int carry; // 進(jìn)位
do {
sum = i1 ^ i2;
carry = (i1 & i2) << 1;
i1 = sum;
i2 = carry;
}while (carry != 0); // 直到?jīng)]有進(jìn)位
return sum;
}
題47.1: 不使用新的變量厅瞎，交換兩個(gè)變量的值
描述：交換a饰潜、b
思路：
- a=a+b; b=a-b; a=a-b;
- a=a^b; b=a^b; a=a^b; // 異或的結(jié)合率
題35: 第一個(gè)只出現(xiàn)一次的字符
思路：空間換時(shí)間
// 第一個(gè)只出現(xiàn)一次的字符
private static Character firstSingle(String str) {
if (str == null || str.length() == 0) {
return null;
}
int[] arr = new int[256]; // 下標(biāo)-字符的asscii碼，值-字符出現(xiàn)次數(shù)
for (int i = 0; i < str.length(); i++) {
arr[str.charAt(i)] ++;
}
for (int i = 0; i < str.length(); i++) {
if (arr[str.charAt(i)] == 1) {
return str.charAt(i);
}
}
return null;
}
題58: 二叉樹的下一個(gè)節(jié)點(diǎn)
描述：給定一個(gè)二叉樹的其中一個(gè)節(jié)點(diǎn)和簸，樹中的節(jié)點(diǎn)除了有指向左右子節(jié)點(diǎn)的指針彭雾，還有一個(gè)指向父節(jié)點(diǎn)的指針，找出中序遍歷的下一個(gè)節(jié)點(diǎn)
題58: 判斷一個(gè)二叉樹是否對(duì)稱
思路：定義一種遍歷方式锁保，根-右-左薯酝。判斷先序遍歷和此遍歷得到的序列是否一致
private static boolean isSymm(TreeNode root) {
return isSymm(root, root);
}
private static boolean isSymm(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) {
return true;
}
if (root1 == null || root2 == null) {
return false;
}
if (root1.data != root2.data) {
return false;
}
return isSymm(root1.left, root2.right) && isSymm(root1.right, root2.left);
}
題60: 二叉樹打印成多行
描述：給定一個(gè)二叉樹，每一層打印一行身诺，每一層打印順序從左到右
思路：用一個(gè)隊(duì)列存放節(jié)點(diǎn)蜜托，用變量控制是否換行
// 二叉樹打印成多行
private static void printTree(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int curUnHandle = 1; // 當(dāng)前層未打印個(gè)數(shù)
int nextTotal = 0; // 下一層總個(gè)數(shù)
TreeNode node;
while (!queue.isEmpty()) {
node = queue.poll();
System.out.print(node.data + " ");
curUnHandle--;
if (node.left != null) {
queue.offer(node.left);
nextTotal++;
}
if (node.right != null) {
queue.offer(node.right);
nextTotal++;
}
if (curUnHandle == 0) {
System.out.println();
curUnHandle = nextTotal;
nextTotal = 0;
}
}
}
題61: 之字形打印二叉樹
描述：給定一個(gè)二叉樹抄囚，按之字形打印二叉樹霉赡，即第一行從左到右，第二行從右到左幔托，依次類推
思路：分析規(guī)律穴亏，兩個(gè)棧
// 二叉樹之字形打印
private static void printTree2(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack1 = new Stack<TreeNode>(); // 先左后右
Stack<TreeNode> stack2 = new Stack<TreeNode>(); // 先右后左
stack1.push(root);
TreeNode node;
while (!stack1.empty() || !stack2.empty()) {
if (!stack1.empty()) {
while(!stack1.empty()) {
node = stack1.pop();
System.out.print(node.data + " ");
if (node.left != null) {
stack2.push(node.left);
}
if (node.right != null) {
stack2.push(node.right);
}
}
System.out.println();
}else {
while (!stack2.empty()) {
node = stack2.pop();
System.out.print(node.data + " ");
if (node.right != null) {
stack1.push(node.right);
}
if (node.left != null) {
stack1.push(node.left);
}
}
System.out.println();
}
}
}
題62: 二叉搜索樹的第k個(gè)節(jié)點(diǎn)
描述：給定二叉排序樹，找出其中第k大的節(jié)點(diǎn)重挑。
思路：二叉排序樹的中序遍歷是從小到大的數(shù)列
題62.1: 二叉樹中序遍歷
// 二叉樹中序遍歷-遞歸
private static void midPrintTree1(TreeNode node) {
if (node == null) {
return;
}
midPrintTree1(node.left);
System.out.print(node.data + " ");
midPrintTree1(node.right);
}
// 二叉樹中序遍歷-非遞歸
private static void midPrintTree2(TreeNode node) {
if (node == null) {
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
while(node != null || !stack.empty()) {
while(node != null) {
// 前序遍歷在這里打印即可
stack.push(node);
node = node.left;
}
if(!stack.empty()) {
node = stack.pop();
System.out.print(node.data + " ");
node = node.right;
}
}
}
