剑指Offer（十一）：二进制中1的个数
绝对最佳答案及分析： public class Solution { public int NumberOf1(int n) { int count = 0; while(n!= 0){ count++; n = n & (n - 1); } return count; } } 答案正确:恭喜！您提交的程序通过了所有的测试用例 分析一下代码： 这段小小的代码，很是巧妙。 如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。 举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。
剑指Offer（十二）：数值的整数次方
核心：是使用flag来表示exponent的正负号，
public class Solution { public double Power(double base, int exponent) { //数字的正数次方 int flag=1; if(base==0) return 0; if(exponent<0){ exponent=-exponent; flag=0; } double result=1; for(int i=0;i<exponent;i++){ result*=base; } if(flag==1){ return result; }else{ return result=1/result; } } }
剑指Offer（十九）：顺时针打印矩阵
import java.util.ArrayList; public class Solution { ArrayList<Integer> list=new ArrayList<Integer>(); public ArrayList<Integer> printMatrix(int [][] matrix) { int rows=matrix.length; /矩阵的行数 int cols=matrix[0].length; 矩阵的列数 int start=0; while(rows>start*2&&cols>start*2){ shundayin(matrix,rows,cols,start); start++; } return list; } public void shundayin(int[][] matrix,int rows,int cols,int start){ /首先从左到右进行遍历 for(int i=start;i<cols-start;i++){ list.add(matrix[start][i]); } //接着从右到下进行遍历 for(int j=start+1;j<rows-start;j++){ list.add(matrix[j][cols-start-1]); } //接着从下到左进行遍历 for(int k=cols-start-2;k>=start&&rows-start-1!=start;k--){ list.add(matrix[rows-start-1][k]); } //接着从左到上开始比遍历 for(int n=rows-start-2;n>start&&cols-start-1!=start;n--){ list.add(matrix[n][start]); } } }
剑指Offer（二十九）：最小的K个数
//方法一：冒泡排序
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> al = new ArrayList<Integer>(); if (k > input.length) { return al; } for (int i = 0; i < k; i++) { for (int j = 0; j < input.length - i - 1; j++) { if (input[j] < input[j + 1]) { int temp = input[j]; input[j] = input[j + 1]; input[j + 1] = temp; } } al.add(input[input.length - i - 1]); } return al; }
//大根堆的方式：
import java.util.ArrayList; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> list=new ArrayList<Integer>(); if(input.length==0||input==null||input.length<k){ return list; } for(int i=(k-1)/2;i>=0;i--){ Adjust(input,i,k-1); } for(int i=k;i<input.length;i++){ if(input[0]>input[i]){ input[0]=input[i]; Adjust(input,0,k-1); } } for(int i=0;i<k;i++){ list.add(input[i]); } return list; } ///构建一个大根堆 public void Adjust(int[] input,int start,int end){ int temp=input[start]; int child=start*2+1; while(child<=end){ if(child+1<=end&&input[child]<input[child+1]) child++; if(input[child]<temp) break; input[start]=input[child]; start=child; child=start*2+1; } input[start]=temp; } }
//大根堆 注释
1 //构建大根堆：将array看成完全二叉树的顺序存储结构 2 private int[] buildMaxHeap(int[] array){ 3 //从最后一个节点array.length-1的父节点（array.length-1-1）/2开始，直到根节点0，反复调整堆 4 for(int i=(array.length-2)/2;i>=0;i--){ 5 adjustDownToUp(array, i,array.length); 6 } 7 return array; 8 } 9 10 //将元素array[k]自下往上逐步调整树形结构 11 private void adjustDownToUp(int[] array,int k,int length){ 12 int temp = array[k]; 13 for(int i=2*k+1; i<length-1; i=2*i+1){ //i为初始化为节点k的左孩子，沿节点较大的子节点向下调整 14 if(i<length && array[i]<array[i+1]){ //取节点较大的子节点的下标 15 i++; //如果节点的右孩子>左孩子，则取右孩子节点的下标 16 } 17 if(temp>=array[i]){ //根节点 >=左右子女中关键字较大者，调整结束 18 break; 19 }else{ //根节点 <左右子女中关键字较大者 20 array[k] = array[i]; //将左右子结点中较大值array[i]调整到双亲节点上 21 k = i; //【关键】修改k值，以便继续向下调整 22 } 23 } 24 array[k] = temp; //被调整的结点的值放人最终位置 25 }
