for( i = 0; i < n; i++ )
{
	c = p[2 + i];
	if( c == 0 || ( c > 126 && c < 160 ) )
	{
		c = '.';  //could also check ||(c>0 && c<32)
	}
	st_cur->probes[st_cur->probe_index][i] = c;
}

static char *
get_ssid_utf8 (NMAccessPoint *ap)
{
	char *ssid_utf8 = NULL;
	const GByteArray *ssid;

	if (ap) {
		ssid = nm_access_point_get_ssid (ap);
		if (ssid)
			ssid_utf8 = nm_utils_ssid_to_utf8 (ssid);
	}
	if (!ssid_utf8)
		ssid_utf8 = g_strdup (_("(none)"));

	return ssid_utf8;
}

char *
nm_utils_ssid_to_utf8 (const GByteArray *ssid)
{
	char *converted = NULL;
	char *lang, *e1 = NULL, *e2 = NULL, *e3 = NULL;

	g_return_val_if_fail (ssid != NULL, NULL);

	if (g_utf8_validate ((const gchar *) ssid->data, ssid->len, NULL))
		return g_strndup ((const gchar *) ssid->data, ssid->len);

	/* LANG may be a good encoding hint */
	g_get_charset ((const char **)(&e1));
	if ((lang = getenv ("LANG"))) {
		char * dot;

		lang = g_ascii_strdown (lang, -1);
		if ((dot = strchr (lang, '.')))
			*dot = '\0';

		get_encodings_for_lang (lang, &e1, &e2, &e3);
		g_free (lang);
	}

	converted = g_convert ((const gchar *) ssid->data, ssid->len, "UTF-8", e1, NULL, NULL, NULL);
	if (!converted && e2)
		converted = g_convert ((const gchar *) ssid->data, ssid->len, "UTF-8", e2, NULL, NULL, NULL);

	if (!converted && e3)
		converted = g_convert ((const gchar *) ssid->data, ssid->len, "UTF-8", e3, NULL, NULL, NULL);

	if (!converted) {
		converted = g_convert_with_fallback ((const gchar *) ssid->data, ssid->len,
		                                     "UTF-8", e1, "?", NULL, NULL, NULL);
	}

	return converted;
}

class Solution {
public:
    int singleNumber(int A[], int n) {
        int result = 0;
        for (int i = 0; i < n; i++)
        {   
            result ^= A[i];
        }   
        return result;
    }
};

class Solution {
public:
    int singleNumber(int A[], int n) {
        int count[32] = {0};
        int result = 0;
        for (int i = 0; i < 32; i++) {
            for (int j = 0; j < n; j++{
                if ((A[j] >> i) & 1) {
                    count[i]++;
                }   
            }   
            result |= ((count[i] % 3) << i); 
        }   
        return result;
    }
};

int singleNumber(int A[], int n) {
    int ones = 0, twos = 0, threes = 0;
    for (int i = 0; i < n; i++) {
        twos |= ones & A[i];
        ones ^= A[i];// 异或3次 和 异或 1次的结果是一样的
       //对于ones 和 twos 把出现了3次的位置设置为0 （取反之后1的位置为0）
        threes = ones & twos;
        ones &= ~threes;
        twos &= ~threes;
    }
    return ones;
}

class Solution {
public:
    void oddInOddEvenInEven(vector<int>& arr, int len) {
        int odd = 1;
        int even = 0;
        while (odd < len && even < len)
        {
            if (arr[odd] % 2 == 0)
            {
                while (arr[even] % 2 == 0)
                {
                    even += 2;
                }
                if (even < len)
                {
                    int tmp = arr[even];
                    arr[even] = arr[odd];
                    arr[odd] = tmp;
                }
                else
                {
                    break;
                }
            }
            else
            {
                odd += 2;
            }
        }
    }
};

class Solution {
public:
    int getFirstUnFormedNum(vector<int>& arr, int len) {
        set<int> res;
        for (int i=0; i<len; i++)
        {
            set<int> tmp = res;
            for (set<int>::iterator iter = res.begin(); iter != res.end(); iter++)
            {
                tmp.insert(*iter + arr[i]);
            }
            res = tmp;
            res.insert(arr[i]);
        }

        set<int>::iterator iter = res.begin();
        int before = *iter;
        iter++;
        for (; iter != res.end(); iter++)
        {
            if (*iter - before > 1)
            {
                return before + 1;
            }
            before = *iter;
        }
        return before + 1;
    }
};

class Solution {
public:
    int getMaxABSLeftAndRight(vector<int> vec, int len) {
        if (len == 0)
        {
            return 0;
        }

        // find the max in array
        int max = vec[0];
        for (int i=1; i<(int)vec.size(); i++)
        {
            if (vec[i] > max)
            {
                max = vec[i];
            }
        }

        // compare the head and tail in array
        if (vec[0] < vec[len - 1])
        {
            return max - vec[0];
        }
        return max - vec[len - 1];
    }
};

class Solution {
public:
    void relocateList(struct ListNode* head) {
        if (head == NULL || head->next == NULL)
        {
            return ;
        }

        // use one loop, find the right head
        ListNode *right_head = head;
        ListNode *node = head;
        while (node != NULL)
        {
            if (node->next == NULL)
            {
                break;
            }
            if (node->next->next == NULL)
            {
                right_head = right_head->next;
                break;
            }
            right_head = right_head->next;
            node = node->next->next;
        }

        ListNode *left_node = head;
        ListNode *right_node = right_head;
        while (left_node->next != right_head)
        {
            ListNode *tmp = left_node->next;
            left_node->next = right_node;
            right_node = right_node->next;
            left_node->next->next = tmp;
            left_node = left_node->next->next;
        }

        left_node->next = right_node;
    }
};

int majorityElement(vector<int> &num) {
        std::map<int, int> result_map;
        for (vector<int>::iterator iter = num.begin(); iter != num.end(); iter++)
        {
            if (result_map.find(*iter) == result_map.end())
            {
                result_map.insert(map<int, int>::value_type(*iter, 1));
            }
            else
            {
                result_map[*iter]++;                                                                                                                                            
            }
        }

        int max_count = 0;
        int result;
        for (std::map<int, int>::iterator iter = result_map.begin(); iter != result_map.end(); iter++)
        {
            if (iter->second > max_count)
            {
                result = iter->first;
                max_count = iter->second;
            }
        }
        return result;
    }

int majorityElementSort(vector<int> &num) {
   sort(num.begin(), num.end());
   return num[num.size() / 2];
}

#include <stdio.h>
#include <vector>
#include <iostream>

int partition(std::vector<int> &numbers, int low, int high)
{
    int pivotkey = numbers[low];
    while (low < high)
    {
        while (low < high && numbers[high] >= pivotkey)
        {
            --high;
        }
        numbers[low] = numbers[high];
        while (low < high && numbers[low] <= pivotkey)
        {
            ++low;
        }
        numbers[high] = numbers[low];
        numbers[low] = pivotkey;
    }
    return low;
}


void quick_sort(std::vector<int> &numbers, int low, int high)
{
    if (low < high)
    {
        int pivotloc = partition(numbers, low, high);
        quick_sort(numbers, low, pivotloc - 1);
        quick_sort(numbers, pivotloc + 1, high);
    }
}

void quick_sort(std::vector<int> &numbers)
{
    quick_sort(numbers, 0, numbers.size() - 1);
}

int main()
{
    std::vector<int> numbers = {49, 38, 65, 97, 76, 13, 27, 49};
    quick_sort(numbers);
    for (int i=0; i<numbers.size(); i++)
    {
        printf("%d\t", numbers[i]);
    }
    printf("\n");
}

/**
 * 归并排序使用递归算法的效率比较低，具体应用中会采用非递归算法代替
 */
void merge(std::vector<int> &numbers, std::vector<int> &extra, int low, int high, int middle)
{
    int i = low, j = middle+1, k = low;
    for (; i<=middle && j<=high; k++)
    {
        if (numbers[i] <= numbers[j])
        {
            extra[k] = numbers[i];
            i++;
        }
        else
        {
            extra[k] = numbers[j];
            j++;
        }
    }
    
    while (i <= middle)
    {
        extra[k++] = numbers[i++];
    }

    while (j <= middle)
    {
        extra[k++] = numbers[j++];
    }

    for (int m = low; m <= high; m++)
    {
        numbers[m] = extra[m];
    }
}


void merge_sort(std::vector<int> &numbers, std::vector<int> &extra, int low, int high)
{
    if (low == high)
    {
        return ;
    }
    int middle = (low + high) / 2;
    merge_sort(numbers, extra, low, middle);
    merge_sort(numbers, extra, middle + 1, high);
    merge(numbers, extra, low, high, middle);
}

void merge_sort(std::vector<int> &numbers)
{
    // 申请额外的存储空间来用于排序处理
    std::vector<int> extra = numbers;
    merge_sort(numbers, extra, 0, numbers.size() - 1);
}

int main()
{
    std::vector<int> numbers = {49, 38, 65, 97, 76, 13, 27, 49};
    merge_sort(numbers);

    for (int i=0; i<numbers.size(); i++)
    {
        printf("%d\t", numbers[i]);
    }
    printf("\n");
}

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

/**
 * 使用归并排序方法，核心思想为将数组拆分为两半，分别对两半进行排序，排序完成后再进行一次排序，排序算法就可以采用插入排序的方式。
 * 对两半排序的算法仍然采用归并排序算法，即问题为递归问题
 * 在使用线性存储结果的归并排序算法中，会使用额外的空间来存储临时结果，空间复杂度为O(n)，而在链式存储中，空间复杂度为O(1)
 * 归并排序的时间复杂度为O(nlogn)
 * 如果存储结构为双向链表，可以使用快速排序
 */
ListNode* sortList(ListNode* head)
{
    if (head == nullptr || head->next == nullptr)
    {
        return head;
    }

    if (head->next->next == nullptr)
    {
        // 仅有两个元素，对两个元素进行排序后直接返回
        if (head->val < head->next->val)
        {
            return head;
        }
        else
        {
            ListNode *tmp = head->next;
            tmp->next = head;
            tmp->next->next = nullptr;
            return tmp;
        }
    }

    // 为了找到中间节点，这里采用快慢指针的方式，否则需要使用先遍历一次取长度，然后找到中间位置的两次遍历方式
    ListNode *fast = head;
    ListNode *slow = head;
    ListNode *slow_prev = nullptr;
    while (fast != nullptr && fast->next != nullptr)
    {
        fast = fast->next->next;
        slow_prev = slow;
        slow = slow->next;
    }
    fast = slow_prev->next;
    slow_prev->next = nullptr;

    // 分别对两段链表进行排序
    slow = sortList(head);
    fast = sortList(fast);

    // 对两段链表进行合并
    ListNode *node = nullptr, *result = nullptr;
    while (slow != nullptr && fast != nullptr)
    {
        if (slow->val < fast->val)
        {
            if (result != nullptr)
            {
                node->next = slow;
                node = node->next;
            }
            else
            {
                node = slow;
                result = slow;
            }
            slow = slow->next;
        }
        else
        {
            if (result != nullptr)
            {
                node->next = fast;
                node = node->next;
            }
            else
            {
                node = fast;
                result = fast;
            }
            fast = fast->next;
        }
    }
    if (slow != nullptr)
    {
        node->next = slow;
    }

    if (fast != nullptr)
    {
        node->next = fast;
    }

    return result;
}

ListNode* insertionSortList(ListNode* head) 
{
    if (head == NULL)
    {
        return NULL;
    }
    
    // 初始化
    ListNode *node = head->next;
    ListNode *new_head = head;
    new_head->next = NULL;
    while (node != NULL)
    {
        ListNode *node_next = node->next;   // 先将当前遍历的下一个节点保存
        
        // 将当前节点插入到新链表中
        ListNode *new_node_tmp = new_head;
        if (node->val < new_node_tmp->val)
        {
            // 当前节点插入新链表的第一个位置
            node->next = new_head;
            new_head = node;
        }
        else
        {
            // 将当前节点插入到中间
            while (new_node_tmp->next != NULL)
            {
                if (node->val < new_node_tmp->next->val)
                {
                    node->next = new_node_tmp->next;
                    new_node_tmp->next = node;
                    break;
                }
                new_node_tmp = new_node_tmp->next;
            }
            
            // 将该节点插入到最后位置
            if (new_node_tmp->next == NULL)
            {
                new_node_tmp->next = node;
                node->next = NULL;
            }
        }
            
        // 开始遍历当前节点的下一个节点
        node = node_next;
    }
    return new_head;
}

/**
 * 问题的关键是找到状态方式，找到状态方程后问题就迎刃而解
 * 状态方程如下：
 * b[j]表示第j处，以a[j]结尾的子序列的最大和
 * b[j]=max(a[j] + b[j-1], a[j])
 * b数据的最大值即为问题的解
 * 问题转换为求解b数组
 * 时间复杂度为O(1)，空间复杂度为(n)，空间复杂度可以降为O(1)，为了使程序易读，不做调整
 */
int maxSubArray(int A[], int n) {
	if (n == 0)
	{
		return 0;
	}
	int *b = new int[n];
	b[0] = A[0];
	int max_b = b[0];
	for (int i=1; i<n; i++)
	{
		b[i] = std::max(A[i] + b[i-1], A[i]);
		if (max_b < b[i])
		{
			max_b = b[i];
		}
	}
	delete[] b;
	return max_b;
}

class Solution {
public:
    int compare_array[4];

    int maxSubArray(int A[], int n) {
        return maxSubArray(A, 0, n - 1);
    }

    /**
     * leetcode not support stdarg.h
     */
    int max(int count, ...)
    {
        va_list ap;
        va_start(ap, count);
        int max = INT_MIN;
        for (int i=0; i<count; i++)
        {
            int temp = va_arg(ap, int);
            if (max < temp)
            {
                max = temp;
            }
        }
        va_end(ap);
        return max;
    }

    int max_compare_array()
    {
        int max_num = compare_array[0];
        for (int i=1; i<4; i++)
        {
            if (max_num < compare_array[i])
            {
                max_num = compare_array[i];
            }
        }
        return max_num;
    }

    int maxSubArray(int A[], int begin, int end)
    {
        //printf("begin : %d, end : %d\n", begin, end);
        if (begin == end)
        {
            return A[begin];
        }
        else if ((end - begin) == 1)
        {
            //return max(3, A[begin], A[begin] + A[end], A[end]);
            compare_array[0] = A[begin];
            compare_array[1] = A[begin] + A[end];
            compare_array[2] = A[end];
            compare_array[3] = INT_MIN;
            return max_compare_array();
        }
        int middle = (begin + end) / 2;
        // 处理左边子数组
        int max_left = maxSubArray(A, begin, middle);
        // 处理右边子数组
        int max_right = maxSubArray(A, middle + 1, end);
        // 处理跨越中点的情况
        int max_cross = maxCrossMiddle(A, begin, end);

        printf("begin : %d, end : %d, max_left = %d, max_right = %d, max_cross = %d\n", begin, end, max_left, max_right, max_cross);

        // 返回三者中的最大值
        compare_array[0] = max_left;
        compare_array[1] = max_right;
        compare_array[2] = max_cross;
        compare_array[3] = INT_MIN;
        return max_compare_array();
    }

    /**
     * 处理跨越中点的情况
     */
    int maxCrossMiddle(int A[], int begin, int end)
    {
        if (begin == end)
        {
            return A[begin];
        }
        int middle = (begin + end) / 2;
        // 求得[begin -- middle-1]的最大值
        int max_left = A[middle - 1];
        int sum = 0;
        for (int i=middle - 1; i>=begin && i >= 0; i--)
        {
            sum += A[i];
            if (max_left < sum)
            {
                max_left = sum;
            }
        }

        // 求得[middle+1 -- end]的最大值
        int max_right = A[middle + 1];
        sum = 0;
        for (int i=middle + 1; i<=end; i++)
        {
            sum += A[i];
            if (max_right< sum)
            {
                max_right = sum;
            }
        }

        compare_array[0] = A[middle];
        compare_array[1] = A[middle] + max_left;
        compare_array[2] = A[middle] + max_right;
        compare_array[3] = A[middle] + max_left + max_right;
        return max_compare_array();
    }
};

int maxSubArray(int A[], int n) {
	if (n == 0)
	{
	    return 0;
	}
	int current_sum = 0;
	int max_sum = INT_MIN;

	for (int i=0; i<n; i++)
	{
	    if (current_sum <= 0)
	    {
		current_sum = A[i];
	    }
	    else
	    {
		current_sum += A[i];
	    }
	    if (current_sum > max_sum)
	    {
		max_sum = current_sum;
	    }
	}
	return max_sum;
}