数字在排序数组中出现的次数

题目描述

统计一个数字在排序数组中出现的次数。
解法:由于数组是有序的,可以采用二分查找的思想,分别查找连续k值得左边界和有边界,
class Solution {
public:
    int GetStartOfK(vector<int> data, int k){  // 查找左边界
        if(data.size() == 0)
            return -1;
        int start = 0, end = data.size()-1;
        int mid = 0;
        while(start <= end){
            mid = (start+end)/2;
            if(data[mid] >= k)        // 大于等于k时,end向start紧靠,找到左边界
                end = mid - 1;
            else
                start = mid + 1;
        }
        if(data[start] == k)
            return start;
        else
            return -1;
    }
    int GetEndOfK(vector<int> data, int k){  //查找右边界
        if(data.size() == 0)
            return -1;
        int start = 0, end = data.size() - 1;
        int mid = 0;
        while(start <= end){
            mid = (start+end)/2;
            if(data[mid] <= k)         // 小于等于k时, start向end紧靠,找到右边界
                start = mid + 1;
            else
                end = mid - 1;
        }
        if(data[end] == k)
            return end;
        else
            return -1;
    }
    int GetNumberOfK(vector<int> data ,int k) {
        int count = 0;
        if(data.size() > 0){
            int start = GetStartOfK(data, k);
            int end = GetEndOfK(data, k);
            if(start > -1 && end > -1)
                count = end - start + 1;
        }
        return count;
    }
};

 

Merge k Sorted Lists

问题描述:
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
分而治之的思想:   404ms

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty())
            return NULL;
        return dac(lists,0,lists.size()-1);
    }
private:
    ListNode* dac(vector<ListNode*>& lists,int low,int high)
    {
        int mid=(low+high)/2;
        if(low==high)
            return lists[low];
        ListNode* l1=dac(lists,low,mid);
        ListNode* l2=dac(lists,mid+1,high);
        return mergeTwoLists(l1,l2);
    }
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1)
            return l2;
        if(!l2)
            return l1;
        if(l1->val<l2->val)
            l1->next=mergeTwoLists(l1->next,l2);
        else
            l2->next=mergeTwoLists(l1,l2->next);
    }
};

使用优先队列priority_queue找到最小的元素   436ms

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
struct cmp{
    bool operator()(const ListNode* l, const ListNode* r){
        return l->val > r->val;
    }
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> q;
        for(auto l : lists){
            if(l) q.push(l);
        }
        if(q.empty())
            return NULL;
        ListNode* result = q.top();      // head
        q.pop();
        if(result->next)
            q.push(result->next);
        ListNode* pointer = result;
        while(!q.empty()){
            pointer->next = q.top();      // the min
            q.pop();
            pointer = pointer->next;
            if(pointer->next)             // the responding ListNode* is not empty
                q.push(pointer->next);
        }
        return result;
    }
};

使用make_heap 480ms

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
//struct cmp{
//   bool operator()(const ListNode* l, const ListNode* r){
//        return l->val > r->val;
//    }
//};
bool cmp(const ListNode* l, const ListNode* r){
    return l->val > r->val;
}
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
       ListNode head(0);
       ListNode *curr = &head;
       vector<ListNode*> v;
        for(auto l : lists){
            if(l) v.push_back(l);
        }
        make_heap(v.begin(), v.end(), cmp);
        while(v.size()>0){
            curr->next = v.front();      // the min
            pop_heap(v.begin(), v.end(), cmp);
            v.pop_back();
            curr = curr->next;
            if(curr->next){             // the responding ListNode* is not empty
                v.push_back(curr->next);
                make_heap(v.begin(), v.end(), cmp);
            }
        }
        return head.next;
    }
};

 

Merge Two Sorted Lists

ListNode* MergeSort(ListNode *left, ListNode*right){
        ListNode* newNode = new ListNode(0);                             //
        ListNode* p = newNode;
        while(left != NULL && right != NULL){
            if(left->val <= right->val){
                p->next = left;
                p = p->next;
                left = left->next;
            }else{
                p->next = right;
                p = p->next;
                right = right->next;
            }
        }
        if(left != NULL)
            p->next = left;
        if(right != NULL)
            p->next = right;
        return newNode->next;
    }

延伸:
在两个有序链表中查找第K大元素。 思路:和有序链表合并思路一样,不过在合并过程中需添加计数,同时需要注意相同大小元素只记1次。

求数组的字数组之和的最大值

思路:给定一个数组A, 找其中和最大的子串,可以可以从A[0]开始,往后累加和放在start中,如果start<0,将可以抛弃当前元素值,不再进行累加,maxSum保存最大的子串和。。并从下一个位置重复上述过程。

/*******************************************
   Author        : Jun Zhang
   Email         : ewalker.zj@gmail.com
   Last Modified : 2015-08-02 14:08
   Filename      : subMax.cpp
   Description   :
*******************************************/
#include<iostream>
int subMax(int *data, int n)
{
   	int start = data[0];           // record the current sum, >0
   	int maxSum = data[0];          // the maxSum
   	for(int i = 1; i < n; i++)
   	{
      		if(start < 0)             // preSum < 0
         			start = 0;            // new start position
      		start += data[i];
      		if(start > maxSum)
         			maxSum = start;
   	}
   	return maxSum;
}
int main()
{
   	int buf[10] = {2, -4, 5, 6, 2, -3, 8, 1, -12, -3};
   	std::cout<<subMax(buf, 10)<<std::endl;
   	return 0;
}

时间复杂度O(n),空间复杂度O(1)
3种变形:
1、求字数组和的绝对值的最大值
2、返回最大字数组位置
 

//需返回最大字数组的位置
struct outInfo
{
   	int begin;
   	int end;
   	int sum;
   	struct outInfo *next;
};
int subMax1(int *data, int n)
{
   	int start data[0];
   	int maxSum = data[0];
   	int pos;
   	int begin = 0, end;
   	int new;
   	outInfo *p, *info, *head;
   	head = (outInfo*)malloc(sizeof(outInfo));
   	p = head;
   	int ret = 0;
   for(int i = 1; i < n; i++)
   	{
     		if(start < 0)
     		{
       			if(ret == 0){
       				start = 0;
				       //此处可以保存当前字数组信息
       				ret = -1;
       				if(maxSum > p->sum)          // 子数组和大于当前存储值,覆盖
       				{
					          p->begin = begin;
          					p->end = end;
          					p->sum = maxSum;
       				}
       				else if(maxSum == p->sum)    // 相同的子数组和
       				{
          					info = (outInfo*)malloc(sizeof(outInfo));
          					info->begin = begin;
          					info->end = end;
          					info->sum = maxSum;
          					info->next = NULL;
          					p->next = info;
          					p = p->next;
       				}
     			}
   		}
  		if((ret == -1))&&(data[i] > 0))
  		{
			     begin = i;                // new begin;
			     ret = 0;
  		}
		  start += data[i];
  		if(start > maxSum)
  		{
     			maxSum = start;
     			end = i;
  		}
	}
  	if(ret == 0)
  	{
     		if(maxSum > p->sum)
     		{
        			p->begin = begin;
        			p->end = end;
        			p->sum = maxSum;
     		}
		     else if(maxSum == p->sum)
     		{
        			info =(outInfo*)malloc(sizeof(outInfo));
        			info->begin = begin;
        			info->end = end;
        			info->sum = maxSum;
        			info->next = NULL;
        			p = p->next;
     		}
   	}
	return maxSum;
}

 
3、数组收尾相连

Count Primes

问题:

找出不大于非负整数n的所有素数的个数

解答:
思路     先去掉偶数(n/2, 不包括2但包括1),然后从i=3开始的奇数进行扫描(以j=i*i为起点,step = 2*i为步长进行扫描)

class Solution {
public:
    int countPrimes(int n) {
        if(n <=2)
            return 0;
        int res = n>>1, m = sqrt(n-1);    // initilize res to n/2, remove all even number(not 2) and 1
        bool *table = new bool[n];
        for(int i = 3; i <= m; i +=2){
            if(!table[i]){                // odd prime
                for(int step = i<<1, j = i*i; j < n; j += step){   // start from i*i, step 2*i
                    if(!table[j]){
                        table[j] = 1;
                        res--;
                    }
                }
            }
        }
        return res;
    }
};

 

Sort List

问题描述:

Sort a linked list in O(n log n) time using constant space complexity.

解决代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return head;
        ListNode *first = head, *second = head->next, *mid= NULL;
        while(second->next != NULL && second->next->next != NULL){       // find the mid position
            first = first->next;
            second = second->next->next;
        }
        mid = first->next;
        first->next = NULL;
        ListNode *left = sortList(head);
        ListNode *right = sortList(mid);
        return MergeSort(left, right);
    }
    ListNode* MergeSort(ListNode *left, ListNode*right){
        ListNode* newNode = new ListNode(0);                             //
        ListNode* p = newNode;
        while(left != NULL && right != NULL){
            if(left->val <= right->val){
                p->next = left;
                p = p->next;
                left = left->next;
            }else{
                p->next = right;
                p = p->next;
                right = right->next;
            }
        }
        if(left != NULL)
            p->next = left;
        if(right != NULL)
            p->next = right;
        return newNode->next;
    }
};

有人采取自底向上的策略,给出了非递归解法,时间O(nlgn) 空间O(1):

/**
 * Merge sort use bottom-up policy,
 * so Space Complexity is O(1)
 * Time Complexity is O(NlgN)
 * stable sort
*/
class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if(!head || !(head->next)) return head;
        //get the linked list's length
        ListNode* cur = head;
        int length = 0;
        while(cur){
            length++;
            cur = cur->next;
        }
        ListNode dummy(0);
        dummy.next = head;
        ListNode *left, *right, *tail;
        for(int step = 1; step < length; step <<= 1){
            cur = dummy.next;
            tail = &dummy;
            while(cur){
                left = cur;
                right = split(left, step);
                cur = split(right,step);
                tail = merge(left, right, tail);
            }
        }
        return dummy.next;
    }
private:
    /**
     * Divide the linked list into two lists,
     * while the first list contains first n ndoes
     * return the second list's head
     */
    ListNode* split(ListNode *head, int n){
        //if(!head) return NULL;
        for(int i = 1; head && i < n; i++) head = head->next;
        if(!head) return NULL;
        ListNode *second = head->next;
        head->next = NULL;
        return second;
    }
    /**
      * merge the two sorted linked list l1 and l2,
      * then append the merged sorted linked list to the node head
      * return the tail of the merged sorted linked list
     */
    ListNode* merge(ListNode* l1, ListNode* l2, ListNode* head){
        ListNode *cur = head;
        while(l1 && l2){
            if(l1->val > l2->val){
                cur->next = l2;
                cur = l2;
                l2 = l2->next;
            }
            else{
                cur->next = l1;
                cur = l1;
                l1 = l1->next;
            }
        }
        cur->next = (l1 ? l1 : l2);
        while(cur->next) cur = cur->next;
        return cur;
    }
};

https://leetcode.com/discuss/28594/bottom-recurring-with-space-complextity-time-complextity

单链表反转

题目:反转一个单链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *reverseHead = NULL;
        ListNode *node = head;
        ListNode *pre= NULL;
        while(node != NULL)
        {
            ListNode *next = node->next;
            if(next == NULL)
                reverseHead = node;
            node->next = pre;
            pre = node;
            node = next;
        }
        return reverseHead;
/** another version
        if(!pHead)
            return pHead;
        
        ListNode* curr = pHead;
        ListNode* prev = NULL;
        ListNode* next;
        while(curr->next){
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        
        curr->next = prev;
        return curr;
*/
    }
};

逆序输出单链表

void PrintReverseLink(ListNode *head)
{
    if(head->next != NULL){
       PrintReverseLink(head->next);
       printf("%d ",head->next->val);
    }
}

 

ListNode *reverse(ListNode *p, ListNode* &head)
{
   if(p == NULL || p->next == NULL)
   {
      head = p;
      return p;
    }
    else
    {
      ListNode *data = reverse(p->next, head);
      data->next = p;
      return data;
    }
}

 

string 和 integer之间转换

Implement atoi to convert a string to an integer.

class Solution {
public:
    int myAtoi(string str) {
        if(str.size() == 0)
            return 0;
        int pos = 0;
        while(str[pos] == ' ')
            pos ++;
        bool isPositive = true;
        if(str[pos] == '-'){
            isPositive = false;
            pos++;
        }
        else if(str[pos] == '+'){
            isPositive = true;
            pos++;
        }
        if(str[pos] < '0' || str[pos] >'9')
            return 0;
        int val = 0;
        while(str[pos] >= '0' && str[pos] <= '9')
        {
            if(val > INT_MAX/10 ||((val == INT_MAX/10) && str[pos] - '0' >= 8))
                return isPositive?INT_MAX:INT_MIN;
            val = val *10 + str[pos]-'0';
            ++pos;
        }
        if(isPositive)
            return val;
        else
            return -val;
    }
};

interger to string

string itos(int x){
   int val = (x>=0)? x:-x;
   string res;
   while(val){
      res = char(val%10+'0') + res;
      val = val/10;
   }
   if(x < 0)
      res = '-'+res;
   return res;
}

 
还可以通过stringstream实现转换(需include<sstream>)

string str = "123234afi";
int num;
stringstream ss;
ss<<str;
ss>>num;   // num返回123234;如果str="123 23",num 返回123;如果str = "ab123",num返回0
int num = -234;
stringstream ss;
string file;
ss<<num;
ss>>file;

stringstream重新使用时应该清理掉
ss.str(“”);
ss.clear();
另外,C++11引入to_string()能将数值类型转换为string类型。

string to_string (int val);
string to_string (long val);
string to_string (long long val);
string to_string (unsigned val);
string to_string (unsigned long val);
string to_string (unsigned long long val);
string to_string (float val);
string to_string (double val);
string to_string (long double val);
Convert numerical value to string
Returns a string with the representation of val.

二进制中1的个数

题目:实现一个函数,输入一个整数,输出该数二进制表示中1的个数
思路1:循环移位,看最后一位是否为1。

int nof1(unsigned int num)  // 使用unsigned int,就可以处理负数
{
	int count = 0;
	while(num)
	{
		count += num & 0x1u;          //判断最后一位是否为1
		num >>= 1;
	}
	return count;
}

思路2:使用n-1将最右边那个值为1的bit变为0。使用 n = n & (n-1)。 适合值为1的bit比较稀疏的情况。

int nof1(int n)
{
	int count = 0;
	while(n)
	{
		count++;
		n = n & (n-1);          //将最右边那个值为1的bit变为0
	}
	return count;
}

相关题目:
1、写一条语句判断一个整数是不是2的整数次方  (思路:只有一位是1,减1后与自身做与运算)
2、计算两个整数的二进制表示中,不同位的个数 (思路:异或后,统计异或结果中1的位数)
 

统计一行字符中有多少个单词

思路:如果一个字符是字母,而它之前字符不是字母,则表示新单词开始,此时单词计数加1;如果一个字符是字母,并且它之前的字符也是字母,则表示还是原来单词,单词计数不变。 使用一个标签,表示当前字符是否处于一个单词中。

#include<stdio.h>
#include<iostream>
#include<string.h>
int wordcount(char data[], int size)
{
	if(size <= 1)
		return 0;
	int i = 0, word = 0, count = 0;
	while( i < size)
	{
		while( i < size && (data[i] < 'A' ||(data[i] > 'Z'&&data[i] < 'a')||data[i] > 'z'))
			i++;
		while( i < size && ((data[i] >= 'A'&&data[i]<= 'Z')||(data[i] >= 'a'&&data[i]<= 'z')))
		{
			i ++;
			if(word == 0)
			{
				word = 1;
				count ++;
			}
		}
		word = 0;
	}
	return count;
}
int main()
{
	char data[100];
	gets(data);
	std::cout<<wordcount(data, strlen(data))<<std::endl;
}