Counting sort

Question:
A sort algorithm in O(n+k), not comparing value method.
Space: O(n+k).
Answer:

//针对c数组的大小，优化过的计数排序
public class CountSort{
 public static void main(String []args){
  //排序的数组
  int a[] = {100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 95};
  int b[] = countSort(a);
  for(int i : b){
   System.out.print(i + "  ");
  }
  System.out.println();
 }
 public static int[] countSort(int []a){
  int b[] = new int[a.length];
  int max = a[0], min = a[0];
  for(int i : a){
   if(i > max){
    max = i;
   }
   if(i < min){
    min = i;
   }
  }
  //这里k的大小是要排序的数组中，元素大小的极值差+1
  int k = max - min + 1;
  int c[] = new int[k];
  for(int i = 0; i < a.length; ++i){
   c[a[i]-min] += 1;//优化过的地方，减小了数组c的大小
  }   //c[a[i]-min]== count.for position.

  for(int i = 1; i < c.length; ++i){
   c[i] = c[i] + c[i-1];
  }    //accumulated pos.
  for(int i = a.length-1; i >= 0; --i){
   b[--c[a[i]-min]] = a[i];//按存取的方式取出c的元素
  }
  return b;
 }
}

Permutations II -- Leetcode

Question:

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].

 Answer:
class Solution {
public:
    void DFS(vector<int>& num, int begin, vector<vector<int>> &res, vector<int> subres, vector<bool> &flag){
        if(begin == num.size())
        {
            res.push_back(subres);
            return;
        }
        for (int i = 0; i < num.size(); ++i)
        {
            if(!flag[i])//当前元素没有被选
            {
                //如果前面一个元素没有被选，且和当前元素相同则为避免重复则不选这个元素
                if (i > 0 && num[i - 1] == num[i] && !flag[i - 1])
                    continue;
                flag[i] = true;
                subres.push_back(num[i]);
                DFS(num, begin + 1, res, subres, flag);
                flag[i] = false;
                subres.pop_back();
            }
        }
    }
     
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > res;
        res.clear();
        if(num.size() == 0)
            return ans;
        vector<bool> flag(num.size(), false);
        vector<int> subres;
        sort(num.begin(), num.end());//一定要先排序
        DFS(num, 0, res, subres, flag);
        return res;
    }
};

Permutations -- Leetcode

Question:

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].

Answer:

class Solution {

public:

    vector<vector<int> > permute(vector<int> &num)  

    {  

        vector<vector<int> > res;  

        res.clear();  

        if (num.size() == 0)return res;  

     

        Permutation(0, num.size(), num, res);  

        return res;  

    }  

      

    void Permutation(int begin, int n, vector<int> &num, vector<vector<int> > &res){  

        if(begin == n){  

            res.push_back(num);  

            return;  

        }  

        for (int j = begin; j < n; ++j) {  

            swap(num[begin], num[j]);  

            Permutation(begin + 1,n, num, res);  

            swap(num[begin], num[j]);  

        }

        return;

    }  

};

Permutation of string

Backtracking Time Complexity: O(n*n!) # include <stdio.h>   void swap (char *x, char *y) {     char temp;     temp = *x;     *x = *y;     *y = temp; }    /* Function to print permutations of string    This function takes three parameters:    1. String    2. Starting index of the string    3. Ending index of the string. */ void permute(char *a, int i, int n) {    int j;    if (i == n)      printf("%s\n", a); //Base case    else    {         for (j = i; j <= n; j++) //Recursion case        {           swap((a+i), (a+j));           permute(a, i+1, n);           swap((a+i), (a+j)); //Backtrack!!!        }    } }   int main() {    char a[] = "ABC";     permute(a, 0, 2);    getchar();    return 0; }

Output:

ABC
ACB
BAC
BCA
CBA
CAB