8.位操作符：

从一个给定的数n中找位i（i从0开始，然后向右开始）

1 2 3 4 5 6 7 8 9

public static boolean getBit(int num, int i){     int result = num & (1<<i);        if(result == 0){         return false;     }else{         return true;     } }

例如，获取10的第二位：

1 2 3 4

i=1, n=10 1<<1= 10 1010&10=10 10 is not 0, so return true;

典型的位算法：

Find Single Number

 

The problem:

 

Given an array of integers, every element appears twice except for one. Find that single one.

 

Thoughts

 

The key to solve this problem is bit manipulation. XOR will return 1 only on two different bits. So if two numbers are the same, XOR will return 0. Finally only one number left.

 

Java Solution

 

public class Solution {
         public int singleNumber(int[] A) {
             int x=0;         for(int a: A){
                 x = x ^ a;        }         return x;    }} Maximum Binary Gap

Problem: Get maximum binary Gap.

For example, 9′s binary form is 1001, the gap is 2.

Thoughts

The key to solve this problem is the fact that an integer x & 1 will get the last digit of the integer.

Java Solution

public class Solution {
     	public static int solution(int N) {
     		int max = 0;		int count = -1;		int r = 0; 		while (N > 0) {
     			// get right most bit & shift right			r = N & 1;			N = N >> 1; 			if (0 == r && count >= 0) {
     				count++;			} 			if (1 == r) {
     				max = count > max ? count : max;				count = 0;			}		} 		return max;	} 	public static void main(String[] args) {
     		System.out.println(solution(9));	}}

9.概率

通常要解决概率相关问题，都需要很好地格式化问题，下面提供一个简单的例子：

有50个人在一个房间，那么有两个人是同一天生日的可能性有多大？（忽略闰年，即一年有365天）

算法：

1 2 3 4 5 6 7 8 9 10

public static double caculateProbability(int n){     double x = 1;        for(int i=0; i<n; i++){         x *=  (365.0-i)/365.0;     }        double pro = Math.round((1-x) * 100);     return pro/100; }

结果：

1	calculateProbability(50) = 0.97

10.组合和排列

组合和排列的主要差别在于顺序是否重要。

例1：

1、2、3、4、5这5个数字，输出不同的顺序，其中4不可以排在第三位，3和5不能相邻，请问有多少种组合？

例2：

有5个香蕉、4个梨、3个苹果，假设每种水果都是一样的，请问有多少种不同的组合？

基于它们的一些常见算法

排列1

Given a collection of numbers, return all possible permutations.

For example,[1,2,3] have the following permutations:[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Java Solution 1

We can get all permutations by the following steps:

[1][2, 1][1, 2][3, 2, 1][2, 3, 1][2, 1, 3][3, 1, 2][1, 3, 2][1, 2, 3]

Loop through the array, in each iteration, a new number is added to different locations of results of previous iteration. Start from an empty List.

public ArrayList
         
          
           > permute(int[] num) {
          	ArrayList
           
            
             > result = new ArrayList
             
              
               >();  //start from an empty list result.add(new ArrayList
               
                ());  for (int i = 0; i < num.length; i++) { //list of list in current iteration of the array num ArrayList
                
                 
                  > current = new ArrayList
                  
                   
                    >();  for (ArrayList
                    
                      l : result) { // # of locations to insert is largest index + 1 for (int j = 0; j < l.size()+1; j++) { // + add num[i] to different locations l.add(j, num[i]);  ArrayList
                     
                       temp = new ArrayList
                      
                       (l); current.add(temp);  //System.out.println(temp);  // - remove num[i] add l.remove(j); } }  result = new ArrayList
                       
                        
                         >(current); }  return result;}
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         

Java Solution 2

We can also recursively solve this problem. Swap each element with each element after it.

public ArrayList
    
     
      > permute(int[] num) {
     	ArrayList
      
       
        > result = new ArrayList
        
         
          >(); permute(num, 0, result); return result;} void permute(int[] num, int start, ArrayList
          
           
            > result) {   if (start >= num.length) { ArrayList
            
              item = convertArrayToList(num); result.add(item); }  for (int j = start; j <= num.length - 1; j++) { swap(num, start, j); permute(num, start + 1, result); swap(num, start, j); }} private ArrayList
             
               convertArrayToList(int[] num) { ArrayList
              
                item = new ArrayList
               
                (); for (int h = 0; h < num.length; h++) { item.add(num[h]); } return item;} private void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp;} 排列2
               
              
             
            
           
          
         
        
       
      
     
    

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,[1,1,2] have the following unique permutations:[1,1,2], [1,2,1], and [2,1,1].

Thoughts

Basic idea: For each number in the array, swap it with every element after it. To avoid duplicate, need to check it first.

Java Solution

public ArrayList
    
     
      > permuteUnique(int[] num) {
     	ArrayList
      
       
        > result = new ArrayList
        
         
          >(); permuteUnique(num, 0, result); return result;} private void permuteUnique(int[] num, int start, ArrayList
          
           
            > result) {   if (start >= num.length ) { ArrayList
            
              item = convertArrayToList(num); result.add(item); }  for (int j = start; j <= num.length-1; j++) { if (containsDuplicate(num, start, j)) { swap(num, start, j); permuteUnique(num, start + 1, result); swap(num, start, j); } }} private ArrayList
             
               convertArrayToList(int[] num) { ArrayList
              
                item = new ArrayList
               
                (); for (int h = 0; h < num.length; h++) { item.add(num[h]); } return item;} private boolean containsDuplicate(int[] arr, int start, int end) { for (int i = start; i <= end-1; i++) { if (arr[i] == arr[end]) { return false; } } return true;} private void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp;} 排列顺序
               
              
             
            
           
          
         
        
       
      
     
    

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,

We get the following sequence (ie, for n = 3):

"123""132""213""231""312""321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Thoughts

Naively loop through all cases will not work.

Java Solution 1

public class Solution {
          	public String getPermutation(int n, int k) {
           		// initialize all numbers		ArrayList
         
           numberList = new ArrayList
          
           ();		for (int i = 1; i <= n; i++) {
          			numberList.add(i);		} 		// change k to be index		k--; 		// set factorial of n		int mod = 1;		for (int i = 1; i <= n; i++) {
          			mod = mod * i;		} 		String result = ""; 		// find sequence		for (int i = 0; i < n; i++) {
          			mod = mod / (n - i);			// find the right number(curIndex) of			int curIndex = k / mod;			// update k			k = k % mod; 			// get number according to curIndex			result += numberList.get(curIndex);			// remove from list			numberList.remove(curIndex);		} 		return result.toString();	}}
          
         

Java Solution 2

public class Solution {
     	public String getPermutation(int n, int k) {
     		boolean[] output = new boolean[n];		StringBuilder buf = new StringBuilder(""); 		int[] res = new int[n];		res[0] = 1; 		for (int i = 1; i < n; i++)			res[i] = res[i - 1] * i; 		for (int i = n - 1; i >= 0; i--) {
     			int s = 1; 			while (k > res[i]) {
     				s++;				k = k - res[i];			} 			for (int j = 0; j < n; j++) {
     				if (j + 1 <= s && output[j]) {
     					s++;				}			} 			output[s - 1] = true;			buf.append(Integer.toString(s));		} 		return buf.toString();	}}