1.題目描述：在一個(gè)二維數(shù)組中莽使，每一行都按照從左到右遞增的順序排序燎字，每一列都按照從上到下遞增的順序排序煤痕。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)橡类，判斷數(shù)組中是否含有該整數(shù)蛇尚。
//建議畫(huà)個(gè)圖理解下
public class Solution {
public boolean Find(int target, int [][] array) {
if(array==null || array.length == 0){
return false;
}
int row = 0;
int col = array[0].length-1; //數(shù)組最后一列的下標(biāo)
while(row <=array.length-1 && col >=0){
if(array[row][col] > target){//當(dāng)該列最小的一個(gè)值都大于target
col --; //向左移一列
}else if(array[row][col] < target){//當(dāng)該最小的一個(gè)小于target
row ++; //向下移一行
}else{ //如果該值等于target,返回true
return true;
}
}
return false;
}
}
2.題目描述:請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，將一個(gè)字符串中的空格替換成“%20”顾画。例如取劫，當(dāng)字符串為We Are Happy.則經(jīng)過(guò)替換之后的字符串為We%20Are%20Happy
public class Solution {
public String replaceSpace(StringBuffer str) {
if(str == null || str.length() <= 0){
return "";
}
int spaceCount = 0;
for(int i=0; i<str.length(); i++){//計(jì)算空格個(gè)數(shù)
if(str.charAt(i)==' '){
spaceCount++;
}
}
//設(shè)置初始下標(biāo)
int index = str.length()-1;
int length = str.length()+spaceCount * 2;//設(shè)置新的StringBuilder大小
//新StringBuilder最后一個(gè)字符下標(biāo)
int newIndex = length - 1;
str.setLength(length);
while(index >=0){
//當(dāng)前下標(biāo)的字符
char c = str.charAt(index);
if(c != ' '){
str.setCharAt(newIndex--, c);
}else{
str.setCharAt(newIndex--,'0');
str.setCharAt(newIndex--,'2');
str.setCharAt(newIndex--,'%');
}
index --;
}
return str.toString();
}
}
3.題目描述:輸入一個(gè)鏈表，從尾到頭打印鏈表每個(gè)節(jié)點(diǎn)的值
import java.util.ArrayList;
public class Solution {
private ArrayList<Integer> list = new ArrayList<>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode != null){
printListFromTailToHead(listNode.next);//遞歸
list.add(listNode.val);
}
return list;
}
}
4.題目描述:輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果研侣，請(qǐng)重建出該二叉樹(shù)谱邪。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}庶诡，則重建二叉樹(shù)并返回
import java.util.*;
public class Solution {
private Map<Integer,Integer> map = new HashMap<>();
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
for(int i=0; i<pre.length; i++){
map.put(in[i],i);//存放中序中值對(duì)應(yīng)的下標(biāo)
}
return rebuild(pre,0, pre.length-1, 0, pre.length-1);
}
public TreeNode rebuild(int[] pre, int pi, int pj, int ni, int nj){
if(pi>pj)
return null;
int index = map.get(pre[pi]);//前序該值該中序中的位置
TreeNode root = new TreeNode(pre[pi]);//創(chuàng)建根節(jié)點(diǎn)
root.left = rebuild(pre, pi+1, pi+ index-ni, ni, index-1);//建立根節(jié)點(diǎn)的左子樹(shù)
root.right = rebuild(pre,pi+index-ni+1,pj, index+1, nj);//建立根節(jié)點(diǎn)右子樹(shù)
return root;//返回根節(jié)點(diǎn)
}
}
5.題目描述:用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列惦银，完成隊(duì)列的Push和Pop操作。 隊(duì)列中的元素為int類(lèi)型末誓。
import java.util.Stack;
import java.util.*;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();//保存插入
Stack<Integer> stack2 = new Stack<Integer>();//處理刪除
public void push(int node) {
stack1.push(node);
}
//如果stack2不為空扯俱，直接從stack2刪除
//如果stack2為空，將stack1的內(nèi)容喇澡，刪除放入stack2中
public int pop() {
if(stack2.size() == 0 && stack1.size() == 0){
throw new EmptyStackException();
}
if(stack2.size() == 0){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
6. 題目描述:把一個(gè)數(shù)組最開(kāi)始的若干個(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榨惰。
import java.util.ArrayList;
public class Solution_1 {
public static void main(String[] args) {
int[] array = {4,1,1, 2, 3};
int i = minNumberInRotateArray(array);
System.out.println(i);
}
//本題考查二分查找
public static int minNumberInRotateArray(int [] array) {
if(array == null || array.length == 0){
return 0;
}
if(array.length == 1){
return array[0];
}
int index1 = 0;
int index2 = array.length-1;
int mid = index1;
while(array[index1] >= array[index2]){
mid = (index2-index1) / 2;
if(index2-index1 == 1){ //當(dāng)兩個(gè)相鄰時(shí)
mid = index2;
break;
}
if(array[index1] <= array[mid] && array[mid] > array[index2]){// 3 3 3 0 2情況
index1 = mid;
}else if(array[index2] >= array[mid] && array[index1] > array[mid]){// 3 0 0 0 2情況
index2 = mid;
}else{// 3 3 3 0 3, 3 0 0 0 3兩種情況無(wú)法判斷哪個(gè)屬于旋轉(zhuǎn)部分
mid = getMin(array,index1, index2);//采用順序查找
break;
}
}
return array[mid];
}
public static int getMin(int[] array, int index1, int index2){
int min = index1;
for(int i=index1+1; i<= index2; i++){
if(array[min] > array[i]){
min = i;
}
}
return min;
}
}
7.題目描述:大家都知道斐波那契數(shù)列拜英，現(xiàn)在要求輸入一個(gè)整數(shù)n，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)琅催。n<=39
public class Solution {
public int Fibonacci(int n) {
if(n < 2){
return n;
}
int f1 = 0;
int f2 = 1;
int f = f2;
for(int i=2; i<= n; i++){
f = f1 + f2;
f1 = f2;
f2 = f;
}
return f2;
}
}
8.題目描述:一只青蛙一次可以跳上1級(jí)臺(tái)階居凶，也可以跳上2級(jí)虫给。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法
public class Solution {
public int JumpFloor(int target) {
if(target <= 2){
return target;
}
int f1 = 1;
int f2 = 2;
int f = f2;
for(int i=3; i<=target; i++){
f = f1 +f2;
f1 = f2;
f2 = f;
}
return f2;
}
}
9.題目描述:一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)侠碧。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法抹估。
import java.util.*;
public class Solution {
public int JumpFloorII(int target) {
//f(n) = f(n-1) + f(n-2) + ... + f(1); f(n) = 2 * f(n-1);
//f(1) = 1 f(2) = 2 , f(n-1) = 2 xy(n-1)
return (int)Math.pow(2,target-1);
}
}
10.題目描述我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問(wèn)用n個(gè)21的小矩形無(wú)重疊地覆蓋一個(gè)2*n的大矩形弄兜，總共有多少種方法药蜻？
public class Solution {
public int RectCover(int target) {
if(target <=2){
return target;
}
int f1 = 1;
int f2 = 2;
int sum = 0;
for(int i=3; i<= target; i++){
sum = f1 + f2;
f1 = f2;
f2 = sum;
}
return sum;
}
}
11.題目描述:輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)替饿。其中負(fù)數(shù)用補(bǔ)碼表示语泽。
## 位運(yùn)算 ##
/**負(fù)數(shù)是用補(bǔ)碼表示的，補(bǔ)碼求法位原碼取反加一(原碼是數(shù)的絕對(duì)值的二進(jìn)制)
補(bǔ)碼轉(zhuǎn)換成原碼為：取反加一(符號(hào)位不變)
例如: -16 二進(jìn)制8位的 (原碼)0001 0000 反碼:1110 1111 補(bǔ)碼:1111 0000
然后-16 / 2 = -8 相當(dāng)于補(bǔ)碼右移一位: 1111 1000 反碼:1000 0111 原碼: 1000 1000 = -8
移位運(yùn)算:右移時(shí)视卢，如果是負(fù)數(shù)踱卵，左邊補(bǔ)1
*/
public class Solution {
public int NumberOf1(int n) {
//思路: 一個(gè)數(shù)減去1，然后與上這個(gè)數(shù)据过，這樣這個(gè)數(shù)從右到左的第一個(gè)1變?yōu)?
int count = 0;
while(n != 0){
++ count;
n = (n-1) & n;
}
return count;
}
}
12.題目描述：給定一個(gè)double類(lèi)型的浮點(diǎn)數(shù)base和int類(lèi)型的整數(shù)exponent惋砂。求base的exponent次方。
public class Solution {
public double Power(double base, int exponent) {
if(equal(base,0.0)){
throw new IllegalArgumentException("底數(shù)不能為0");
}
int absExponent = exponent;
if(exponent < 0){//將指數(shù)先轉(zhuǎn)換成正的
absExponent = -exponent;
}
double result = PowerWithUnsignedExponent(base, absExponent);
if(exponent < 0){//如果指數(shù)為負(fù)
result = 1.0 / result;
}
return result;
}
//非遞歸下的求法
public static double PowerWithUnsignedExponent(double base, int exponent){
double result = 1;
double temp = base;
while(exponent != 0){
if((exponent & 0x1) == 1){
result =result * temp;
}
exponent >>= 1;
temp *= temp;
}
return result;
}
public boolean equal(double num1, double num2){
if(num1-num2 > -0.0000001 && num1-num2 < 0.0000001){
return true;
}else{
return false;
}
}
}
13題目描述：輸入一個(gè)整數(shù)數(shù)組绳锅，實(shí)現(xiàn)一個(gè)函數(shù)來(lái)調(diào)整該數(shù)組中數(shù)字的順序班利，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于位于數(shù)組的后半部分榨呆，并保證奇數(shù)和奇數(shù)罗标，偶數(shù)和偶數(shù)之間的相對(duì)位置不變。
public class Solution {
public void reOrderArray(int [] array) {
if(array == null || array.length == 0){
return ;
}
int begin = 0;
int end = begin+1;
while(end < array.length){
while(begin < array.length-1 && (array[begin] & 0x1) != 0){//找到偶數(shù)
begin ++;
}
end = begin +1;
while(end <= array.length-1 && (array[end] & 0x1) == 0){//找到奇數(shù)
end ++;
}
if(end == array.length)
break;
int temp = array[end];
for(int i=end; i > begin; i--){//偶數(shù)后移
array[i] = array[i-1];
}
array[begin] = temp;
begin ++;
}
}
}
14.題目描述：輸入一個(gè)鏈表积蜻，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null || k <= 0){
return null;
}
ListNode pHead = head;
ListNode pBehind = null;
for(int i=0; i<k-1; i++){//先走k-1個(gè)節(jié)點(diǎn)
if(pHead.next != null){
pHead = pHead.next;
}else{
return null;
}
}
pBehind = head;
while(pHead.next != null){
pHead = pHead.next;
pBehind = pBehind.next;
}
return pBehind;
}
}
15.題目描述:輸入一個(gè)鏈表闯割，反轉(zhuǎn)鏈表后，輸出鏈表的所有元素
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head == null){
return null;
}
//手動(dòng)畫(huà)個(gè)鏈表竿拆，操作下就能理解了
ListNode preNode = null;
ListNode nextNode = null;
while(head != null){
nextNode = head.next;
head.next = preNode;
preNode = head;
head = nextNode;
}
return preNode;
}
}
16.題目描述：輸入兩個(gè)單調(diào)遞增的鏈表宙拉，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null)
return list2;
else if(list2 == null)
return list1;
ListNode head = null;
//遞歸思想實(shí)現(xiàn)
if(list1.val < list2.val){
head = list1;
head.next = Merge(list1.next, list2);
}else{
head = list2;
head.next = Merge(list1, list2.next);
}
return head;
}
}
17.題目描述：輸入兩棵二叉樹(shù)A丙笋，B谢澈，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹(shù)不是任意一個(gè)樹(shù)的子結(jié)構(gòu)）
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
//使用先序遍歷找到root1 == root2
//當(dāng)root1 = root2時(shí)御板，采用先序遍歷判斷兩個(gè)子樹(shù)是否相同
boolean isChild = false;
if(root1 == null || root2 == null){
return false;
}
if(root1.val == root2.val){
isChild = isTheSame(root1, root2);
}
if(!isChild){
isChild = HasSubtree(root1.left,root2);
}
if(!isChild){
isChild = HasSubtree(root1.right,root2);
}
return isChild;
}
public boolean isTheSame(TreeNode root1, TreeNode root2){
if(root2 == null) //遞歸結(jié)束條件
return true;
if(root1 == null)
return false;
if(root1.val != root2.val)
return false;
return isTheSame(root1.left,root2.left) && isTheSame(root1.right,root2.right);
}
}
18.題目描述:操作給定的二叉樹(shù)锥忿，將其變換為源二叉樹(shù)的鏡像。
public class Solution {
public void Mirror(TreeNode root) {
if(root == null){//遞歸退出條件
return;
}
if(root.left == null && root.right == null)//遞歸退出條件
return;
//交換左右子樹(shù)
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
if(root.left != null){
Mirror(root.left);
}
if(root.right != null){
Mirror(root.right);
}
}
}
19.題目描述：輸入一個(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.
//這題沒(méi)有按照劍指Offer來(lái)
// 1 2 3 4
// 5 6 7 8
// 9 10 11 12
// 13 14 15 16
// 每先從上右下左各取3個(gè)數(shù)，剛好取完外圈
//當(dāng)?shù)竭_(dá)最后一圈時(shí)可能有如下幾種情況:
// a b c 剩下一個(gè)長(zhǎng)大于寬的矩形
//-----------------------------------
// a 剩下一個(gè)寬大于長(zhǎng)的矩形
// b
// c
// ---------------------------------
// a 剩下一個(gè)值
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> list = new ArrayList<>();
if(matrix == null || (matrix.length <=0 && matrix[0].length == 0))
return list;
int columns = matrix[0].length;
int rows = matrix.length;
int rowStart = 0; //第一行
int rowEnd = rows-1; //最后一行
int colStart = 0; //第一列
int colEnd = columns - 1; //最后一列
while(rowStart <= rowEnd && colStart <= colEnd){
if(rowStart < rowEnd && colStart < colEnd){
for(int i= colStart; i<= colEnd-1; i++){//左到右第一行
list.add(matrix[rowStart][i]);
}
for(int i= rowStart; i<= rowEnd-1; i++){//上到下第一列
list.add(matrix[i][colEnd]);
}
for(int i=colEnd; i >= colStart + 1; i--){//右到左第一行
list.add(matrix[rowEnd][i]);
}
for(int i=rowEnd; i >= rowStart + 1; i--){//下到上第一列
list.add(matrix[i][colStart]);
}
}else if(colStart < colEnd && rowStart == rowEnd){//剩下一個(gè)長(zhǎng)大于寬的矩形
for(int i= colStart; i<= colEnd; i++){
list.add(matrix[rowStart][i]);
}
}else if(rowStart < rowEnd && colStart == colEnd){//剩下一個(gè)寬大于長(zhǎng)的矩形
for(int i = rowStart; i<= rowEnd; i++){
list.add(matrix[i][colStart]);
}
}else{// 剩下一個(gè)值
list.add(matrix[rowStart][colStart]);
}
rowStart ++;
colStart ++;
rowEnd --;
colEnd --;
}
return list;
}
}
20.題目描述：定義棧的數(shù)據(jù)結(jié)構(gòu)钉答，請(qǐng)?jiān)谠擃?lèi)型中實(shí)現(xiàn)一個(gè)能夠得到棧最小元素的min函數(shù)础芍。
import java.util.Stack;
public class Solution {
private Stack<Integer> minStack = new Stack();//存放最小的
private Stack<Integer> stack = new Stack();//存放添加的
public void push(int node) {
if(minStack.isEmpty() || node < minStack.peek())
minStack.push(node);
stack.push(node);
}
public void pop() {
if(stack.isEmpty())
return;
if(!minStack.isEmpty() && minStack.peek() == stack.peek()){
minStack.pop();
}
stack.pop();
}
public int top() {
return stack.peek();
}
public int min() {
return minStack.peek();
}
}
21.題目描述：輸入兩個(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)度是相等的）
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack();
int index = 0;
for(int i=0; i<popA.length; i++){
int num = popA[i];
if(stack.isEmpty()){//棧為空時(shí)添加節(jié)點(diǎn)
stack.push(pushA[index++]);
}
while(stack.peek()!= num && index < pushA.length){
stack.push(pushA[index++]);
}
if(stack.peek()!=num && index >= pushA.length)//當(dāng)棧頂元素不等于num且pushA元素已經(jīng)都入棧
return false;
stack.pop();
}
return true;
}
}
22.題目描述:從上往下打印出二叉樹(shù)的每個(gè)節(jié)點(diǎn)嫩实，同層節(jié)點(diǎn)從左至右打印。
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list = new ArrayList();
LinkedList<TreeNode> queue = new LinkedList();
if(root == null)
return list;
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
list.add(node.val);
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
return list;
}
}
23.題目描述:輸入一個(gè)整數(shù)數(shù)組窥岩，判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷的結(jié)果甲献。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同颂翼。
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence == null || sequence.length <=0)
return false;
return isPostBST(sequence, 0, sequence.length-1);
}
public boolean isPostBST(int[] array, int start, int end){
//根節(jié)點(diǎn)的值
int root = array[end];
//找到左子樹(shù)是否滿足后序遍歷
int i=start;
for(; i<end; i++){
if(array[i] > root){
break;
}
}
int j=i;
for(; j<end; j++){
if(array[j] < root)
return false;
}
boolean left = true;
//判斷左子樹(shù)是不是二叉搜索樹(shù)
if(i > start){
left = isPostBST(array,start, start + i -1);
}
boolean right = true;
if(j < end){
right = isPostBST(array, start+i, end-1);
}
return left && right;
}
}
24.題目描述:輸入一顆二叉樹(shù)和一個(gè)整數(shù)晃洒，打印出二叉樹(shù)中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)形成一條路徑朦乏。
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
private ArrayList<ArrayList<Integer>> roads = new ArrayList();//存儲(chǔ)所有路徑
private ArrayList<Integer> road = new ArrayList();//存放當(dāng)前路徑
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root == null)
return roads;
road.add(root.val);
if(root.left == null && root.right == null){//當(dāng)?shù)竭_(dá)葉節(jié)點(diǎn)時(shí)
if(target == root.val)
roads.add(new ArrayList<>(road));
}
if(root.left != null){//當(dāng)左子樹(shù)不為空
FindPath(root.left, target-root.val);
}
if(root.right != null){//當(dāng)右子樹(shù)不為空
FindPath(root.right, target-root.val);
}
road.remove(road.size()-1);
return roads;
}
}
25.題目描述:輸入一個(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ì)直接返回空）
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
//分成三步1.復(fù)制每個(gè)節(jié)點(diǎn)放置在該節(jié)點(diǎn)的后面
//2.修改節(jié)點(diǎn)的random指針
//3.修改節(jié)點(diǎn)的next指針
public static RandomListNode Clone(RandomListNode pHead)
{
if(pHead == null)
return null;
copy(pHead);
changeRandom(pHead);
return changeNext(pHead);
}
public static RandomListNode changeNext(RandomListNode pHead){//修改next指針
RandomListNode root = pHead;
RandomListNode head = pHead.next;
while(root != null){
RandomListNode copy = root.next;
root.next = copy.next;
root = copy.next;
if(root != null)
copy.next = root.next;
else
copy.next = null;
}
return head;
}
public static void changeRandom(RandomListNode pHead){//修改隨機(jī)指針
RandomListNode root = pHead;
while(root != null){
if(root.random != null){
root.next.random = root.random.next;
}
root = root.next.next;
}
}
public static void copy(RandomListNode pHead){//復(fù)制節(jié)點(diǎn)
RandomListNode root = pHead;
while(root != null){
RandomListNode node = new RandomListNode(root.label);//復(fù)制節(jié)點(diǎn)
node.next = root.next;
node.random = root.random;
root.next = node;//修改原節(jié)點(diǎn)嚇一跳指針
root = node.next;//root指向下一個(gè)節(jié)點(diǎn)
}
}
}
26.題目描述:輸入一棵二叉搜索樹(shù)，將該二叉搜索樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表并思。要求不能創(chuàng)建任何新的結(jié)點(diǎn)庐氮，只能調(diào)整樹(shù)中結(jié)點(diǎn)指針的指向。
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
private TreeNode head = null;//記錄鏈表起始節(jié)點(diǎn)
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null){
return null;
}
if(pRootOfTree.left == null && pRootOfTree.right == null)
return pRootOfTree;
if(head == null){//找到初始節(jié)點(diǎn)
head = pRootOfTree;
while(head.left != null){
head = head.left;
}
}
Convert(pRootOfTree.left);//左子樹(shù)構(gòu)成一個(gè)雙向鏈表
Convert(pRootOfTree.right);//右子樹(shù)構(gòu)成一個(gè)雙向鏈表
TreeNode leftLast = null;
if(pRootOfTree.left != null){//找到左子樹(shù)最右邊一個(gè)就節(jié)點(diǎn)
leftLast = pRootOfTree.left;
while(leftLast.right != null){
leftLast = leftLast.right;
}
}
TreeNode rightFirst = null;
if(pRootOfTree.right != null){//找到右子樹(shù)最左邊的一個(gè)點(diǎn)
rightFirst = pRootOfTree.right;
while(rightFirst.left != null){
rightFirst = rightFirst.left;
}
}
if(leftLast != null){//左子樹(shù)最大的點(diǎn)不為空
leftLast.right = pRootOfTree;
pRootOfTree.left = leftLast;
}
if(rightFirst != null){//右子樹(shù)最小的點(diǎn)不為空
rightFirst.left = pRootOfTree;
pRootOfTree.right = rightFirst;
}
return head;
}
}
27.題目描述:輸入一個(gè)字符串,按字典序打印出該字符串中字符的所有排列宋彼。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來(lái)的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba弄砍。
import java.util.*;
public class Solution {
private char [] seqs;
private Integer [] book;
//用于結(jié)果去重
private HashSet<String> result = new HashSet<String>();
/**
* 輸入一個(gè)字符串,按字典序打印出該字符串中字符的所有排列。
* 例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c
* 所能排列出來(lái)的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba输涕。 結(jié)果請(qǐng)按字母順序輸出音婶。
輸入一個(gè)字符串,長(zhǎng)度不超過(guò)9(可能有字符重復(fù)),字符只包括大小寫(xiě)字母。\
* @param str
* @return
*/
public ArrayList<String> Permutation(String str) {
ArrayList<String> arrange = new ArrayList<String>();
if(str == null || str.isEmpty()) return arrange;
char[] strs = str.toCharArray();
seqs = new char[strs.length];
book = new Integer[strs.length];
for (int i = 0; i < book.length; i++) {
book[i] = 0;
}
dfs(strs, 0);
arrange.addAll(result);
Collections.sort(arrange);
return arrange;
}
/**
* 深度遍歷法
*/
private void dfs(char[] arrs, int step){
//走完所有可能 記錄排列
if(arrs.length == step){
String str = "";
for (int i = 0; i < seqs.length; i++) {
str += seqs[i];
}
result.add(str);
return; //返回上一步
}
//遍歷整個(gè)序列,嘗試每一種可能
for (int i = 0; i < arrs.length; i++) {
//是否走過(guò)
if(book[i] == 0){
seqs[step] = arrs[i];
book[i] = 1;
//下一步
dfs(arrs, step + 1);
//走完最后一步 后退一步
book[i] = 0;
}
}
}
}
28.題目描述:數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過(guò)數(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次，超過(guò)數(shù)組長(zhǎng)度的一半瞳收，因此輸出2碉京。如果不存在則輸出0。
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array == null || array.length == 0)
return 0;
int num = 0;
int count = 0;
for(int i=0; i<array.length; i++){
if(count == 0){
num = array[i];
count = 1;
}else if(num == array[i]){
count++;
}else{
count--;
}
}
count = 0;
for(int i=0; i<array.length; i++){
if(array[i] == num)
count++;
}
if((count << 1) <= array.length){
return 0;
}
return num;
}
}
29.題目描述:輸入n個(gè)整數(shù)螟深，找出其中最小的K個(gè)數(shù)谐宙。例如輸入4,5,1,6,2,7,3,8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字是1,2,3,4,
import java.util.*;
public class Solution {
public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList<>();
if(input == null || k <=0 || input.length < k)
return list;
int start = 0;
int end = input.length -1;
int index = partition(input, start, end);
while(index != k-1){
if(index > k-1){
end = index-1;
index = partition(input,start,end);
}else{
start = index + 1;
index = partition(input,start,end);
}
}
for(int i=0; i<k; i++)
list.add(input[i]);
return list;
}
public static int partition(int[] array, int start, int end){
if(array == null || array.length <= 0 || start< 0 || end >= array.length)
throw new RuntimeException("輸入不正確");
int index = (int)(Math.random() *(end-start +1)) + start;//獲取隨機(jī)數(shù)
swap(array,index,start);
while(start < end){
while(array[end] > array[start])
end --;
if(start < end){
swap(array, start, end);
start ++;
}
while(array[start] < array[end])
start ++;
if(start < end){
swap(array,start, end);
end--;
}
}
return start;
}
public static void swap(int[] array, int index, int start){//交換數(shù)組位置
int tmp = array[index];
array[index] = array[start];
array[start] = tmp;
}
}
30.題目描述:HZ偶爾會(huì)拿些專(zhuān)業(yè)問(wèn)題來(lái)忽悠那些非計(jì)算機(jī)專(zhuān)業(yè)的同學(xué)界弧。今天測(cè)試組開(kāi)完會(huì)后,他又發(fā)話了:在古老的一維模式識(shí)別中,常常需要計(jì)算連續(xù)子向量的最大和,當(dāng)向量全為正數(shù)的時(shí)候,問(wèn)題很好解決凡蜻。但是,如果向量中包含負(fù)數(shù),是否應(yīng)該包含某個(gè)負(fù)數(shù),并期望旁邊的正數(shù)會(huì)彌補(bǔ)它呢？例如:{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個(gè)開(kāi)始,到第3個(gè)為止)垢箕。你會(huì)不會(huì)被他忽悠谆ā？(子向量的長(zhǎng)度至少是1)
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
if(array== null || array.length <=0)
throw new RuntimeException("數(shù)組長(zhǎng)度不正確");
int max = Integer.MIN_VALUE;
int curSum = Integer.MIN_VALUE;
for(int i=0; i<array.length; i++){
if(curSum < 0)
curSum = array[i];
else
curSum = array[i] + curSum;
if(curSum > max)
max = curSum;
}
return max;
}
}
