11.二進(jìn)制中1的個(gè)數(shù)
12.數(shù)值的整數(shù)次方
13.調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
14.鏈表中倒數(shù)第K個(gè)節(jié)點(diǎn)
15.反轉(zhuǎn)鏈表
16.合并兩個(gè)排序的鏈表
17.樹的子結(jié)構(gòu)
18.二叉樹的鏡像
19.順時(shí)針打印矩陣
20.包含min函數(shù)的棧
11.二進(jìn)制中1的個(gè)數(shù)
輸入一個(gè)整數(shù)耍缴，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)荷鼠。其中負(fù)數(shù)用補(bǔ)碼表示俊柔。
public static int NumberOf1(int n) {
String x=Integer.toBinaryString(n);
int m=0;
for(int i=0;i<x.length();i++)
if(x.charAt(i)=='1')
m++;
System.out.println(x);
return m;
}
如果一個(gè)整數(shù)不為0，那么這個(gè)整數(shù)至少有一位是1械蹋。如果我們把這個(gè)整數(shù)減1，那么原來處在整數(shù)最右邊的1就會變?yōu)?齐莲，原來在1后面的所有的0都會變成1(如果最右邊的1后面還有0的話)嚣鄙。其余所有位將不會受到影響。
舉個(gè)例子：一個(gè)二進(jìn)制數(shù)1100鳍怨，從右邊數(shù)起第三位是處于最右邊的一個(gè)1呻右。減去1后，第三位變成0鞋喇，它后面的兩位0變成了1声滥，而前面的1保持不變，因此得到的結(jié)果是1011.我們發(fā)現(xiàn)減1的結(jié)果是把最右邊的一個(gè)1開始的所有位都取反了。這個(gè)時(shí)候如果我們再把原來的整數(shù)和減去1之后的結(jié)果做與運(yùn)算落塑，從原來整數(shù)最右邊一個(gè)1那一位開始所有位都會變成0纽疟。如1100&1011=1000.也就是說，把一個(gè)整數(shù)減去1憾赁，再和原整數(shù)做與運(yùn)算污朽，會把該整數(shù)最右邊一個(gè)1變成0.那么一個(gè)整數(shù)的二進(jìn)制有多少個(gè)1，就可以進(jìn)行多少次這樣的操作龙考。
public static int NumberOf2(int n) {
int count=0;
while(n!=0){
count++;
n=n&(n-1);
}
return count;
}
12.數(shù)值的整數(shù)次方
給定一個(gè)double類型的浮點(diǎn)數(shù)base和int類型的整數(shù)exponent蟆肆。求base的exponent次方。
13.調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面
輸入一個(gè)整數(shù)數(shù)組晦款，實(shí)現(xiàn)一個(gè)函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序炎功，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于位于數(shù)組的后半部分缓溅，并保證奇數(shù)和奇數(shù)蛇损，偶數(shù)和偶數(shù)之間的相對位置不變。
方法一
1.要想保證原有次序坛怪，則只能順次移動或相鄰交換淤齐。
2.i從左向右遍歷，找到第一個(gè)偶數(shù)酝陈。
3.j從i+1開始向后找床玻，直到找到第一個(gè)奇數(shù)。
4.將[i,...,j-1]的元素整體后移一位沉帮，最后將找到的奇數(shù)放入i位置锈死，然后i++。
5.終止條件：j向向后遍歷查找失敗穆壕。
public void reOrderArray(int [] a) {
if(a==null||a.length==0)
return;
int i=0,j;
while(i<a.length){
while(i<a.length&&!isEven(a[i]))
i++;
j=i+1;
while(j<a.length&&isEven(a[j]))
j++;
if(j<a.length){
int tmp=a[j];
for(int k=j-1;k>=i;k--){
a[k+1]=a[k];
}
a[i++]=tmp;
}else{//查找失敗
break;
}
}
}
boolean isEven(int n){
if(n%2==0)
return true;
return false;
}
方法二：
整體思路：
首先統(tǒng)計(jì)奇數(shù)的個(gè)數(shù)
然后新建一個(gè)等長數(shù)組待牵，設(shè)置兩個(gè)指針，奇數(shù)指針從0開始喇勋，偶數(shù)指針從奇數(shù)個(gè)數(shù)的末尾開始 遍歷缨该，填數(shù)
public void reOrderArray2(int [] a) {
if(a.length==0||a.length==1)
return;
int oddCount=0,oddBegin=0;
int b[]=new int[a.length];
for(int i=0;i<a.length;i++)
if((a[i]&1)==1)
oddCount++;
for(int i=0;i<a.length;i++){
if((a[i]&1)==1)
b[oddBegin++]=a[i];
else
b[oddCount++]=a[i];
}
for(int i=0;i<a.length;i++)
a[i]=b[i];
}
14.鏈表中倒數(shù)第K個(gè)節(jié)點(diǎn)
輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)川背。
//公共部分
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
方法一：兩個(gè)指針贰拿，先讓第一個(gè)指針和第二個(gè)指針都指向頭結(jié)點(diǎn)，然后再讓第一個(gè)指正走(k-1)步熄云，到達(dá)第k個(gè)節(jié)點(diǎn)膨更。然后兩個(gè)指針同時(shí)往后移動，當(dāng)?shù)谝粋€(gè)結(jié)點(diǎn)到達(dá)末尾的時(shí)候缴允，第二個(gè)結(jié)點(diǎn)所在位置就是倒數(shù)第k個(gè)節(jié)點(diǎn)了
public ListNode FindKthToTail(ListNode head,int k){
if(head==null||k<=0)
return null;
ListNode pre=head;
ListNode last=head;
for(int i=1;i<k;i++){
if(pre.next!=null)
pre=pre.next;
else
return null;
}
while(pre.next!=null){
pre=pre.next;
last=last.next;
}
return last;
}
方法二：全部進(jìn)棧然后出棧第k個(gè)
public ListNode FindKthToTail2(ListNode head,int k) {
if(head==null||k<=0)
return null;
Stack<ListNode> stack=new Stack<>();
ListNode node=head;
while(node!=null){
stack.push(node);
node=node.next;
}
if(k>stack.size())
return null;
while(k!=1&&!stack.isEmpty()){
stack.pop();
k--;
}
return stack.pop();
}
15.反轉(zhuǎn)鏈表
輸入一個(gè)鏈表荚守，反轉(zhuǎn)鏈表后，輸出鏈表的所有元素。
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
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;
}
16.合并兩個(gè)排序的鏈表
輸入兩個(gè)單調(diào)遞增的鏈表矗漾，輸出兩個(gè)鏈表合成后的鏈表锈候，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
非遞歸方法
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode head=new ListNode(-1);
head.next=null;
ListNode root=head;
while(list1!=null&&list2!=null){
if(list1.val<list2.val){
head.next=list1;
head=list1;
list1=list1.next;
}else{
head.next=list2;
head=list2;
list2=list2.next;
}
}
if(list1!=null)
head.next=list1;
if(list2!=null)
head.next=list2;
return root.next;
}
遞歸方法
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1==null)
return list2;
else if(list2==null)
return list1;
ListNode mergeHead=null;
if(list1.val<list2.val){
mergeHead=list1;
mergeHead.next=Merge(list1.next,list2);
}else{
mergeHead=list2;
mergeHead.next=Merge(list1,list2.next);
}
return mergeHead;
}
17.樹的子結(jié)構(gòu)
輸入兩棵二叉樹A敞贡，B泵琳，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹不是任意一個(gè)樹的子結(jié)構(gòu)）
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean result=false;
if(root1!=null&&root2!=null){
if(root1.val==root2.val){
result=DoesTree1HaveTree2(root1,root2);
}
if(!result)
result=HasSubtree(root1.left, root2);
if(!result)
result=HasSubtree(root1.right, root2);
}
return result;
}
public boolean DoesTree1HaveTree2(TreeNode root1,TreeNode root2){
if(root1==null&&root2!=null)
return false;
if(root2==null)
return true;
if(root1.val!=root2.val)
return false;
return DoesTree1HaveTree2(root1.left, root2.left)&&DoesTree1HaveTree2(root1.right, root2.right);
}
18.二叉樹的鏡像
public void Mirror(TreeNode root){
if(root==null)
return;
if(root.left==null&&root.right==null)
return;
TreeNode pTemp=root.left;
root.left=root.right;
root.right=pTemp;
if(root.left!=null)
Mirror(root.left);
if(root.right!=null)
Mirror(root.right);
}
19.順時(shí)針打印矩陣
輸入一個(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.
public ArrayList<Integer> printMatrix(int [][] array) {
ArrayList<Integer> result=new ArrayList<Integer>();
if(array.length==0)
return result;
int n=array.length,m=array[0].length;
if(m==0)
return result;
int layers=(Math.min(n, m)-1)/2+1;
for(int i=0;i<layers;i++){
for(int k=i;k<m-i;k++)//左到右
result.add(array[i][k]);
for(int j=i+1;j<n-i;j++)//右上到右下
result.add(array[j][m-i-1]);
for(int k=m-i-2;(k>=i)&&(n-i-1!=i);k--)//右到左
result.add(array[n-i-1][k]);
for(int j=n-i-2;(j>i)&&(m-i-1!=i);j--)//左上到左下
result.add(array[j][i]);
}
return result;
}
20.包含min函數(shù)的棧
定義棧的數(shù)據(jù)結(jié)構(gòu)势木，請?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧最小元素的min函數(shù)。
private Stack<Integer> data=new Stack<Integer>();
private Stack<Integer> min=new Stack<Integer>();
Integer temp=null;
public void push(int node) {
if(temp!=null){
if(node<=temp){
temp=node;
min.push(node);
}
data.push(node);
}else{
temp=node;
data.push(node);
min.push(node);
}
}
public void pop() {
int num=data.pop();
int num2=min.pop();
if(num!=num2)
min.push(num2);
}
public int top() {
return data.peek();
}
public int min() {
return min.peek();
}
