欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

lintcode

程序员文章站 2022-07-15 12:15:35
...

463. 整数排序

  • STL通用算法:
class Solution {
public:
    /**
     * @param A an integer array
     * @return void
     */
    void sortIntegers(vector<int>& A) {
        // Write your code here
        sort(A.begin(), A.end());
    }
};

要使用此函数只需用#include <algorithm> sort即可使用。

sort(begin,end),对给定区间的元素进行排序。

  • 冒泡:
class Solution {
public:
    /**
     * @param A: an integer array
     * @return: nothing
     */
    void sortIntegers(vector<int> &A) {
        // write your code here
        int i, j, temp;
        int length = A.size();
        for(i = length - 1; i > 0; i--){
            for(j = 0; j < i; j++){
                if(A[j] > A[j+1]){
                    temp = A[j+1];
                    A[j+1] = A[j];
                    A[j] = temp;
                }
            }
        }
    }
};

使用到A.size()函数,即求A的长度。

1. A + B 问题

不使用+号等数学运算符,这里用位运算。

| 或   & 和   ^异或(不同为1)

 当无进位时,a|b即为答案,有进位时,答案为忽略进位相加值+进位得到的值

class Solution {
public:
    int aplusb(int a, int b) {
        int c = 0, d = 0;
        while((a & b) != 0){
            c = (a&b) << 1; // 应该进位的值
            d = a ^ b; //忽略进位相加
            a = c;
            b = d;
        }
        return a | b;
    }
};

2. 尾部的零

设计一个算法,计算出n阶乘中尾部零的个数。

假如你把1 × 2 ×3× 4 ×……×N中每一个因数分解质因数,结果就像: 
1 × 2 × 3 × (2 × 2) × 5 × (2 × 3) × 7 × (2 × 2 ×2) ×…… 
10可以分解为2 × 5——因此只有质数2和5相乘能产生0,别的任何两个质数相乘都不能产生0,而且2,5相乘只产生一个0。 
所以,分解后的整个因数式中有多少对(2, 5),结果中就有多少个0,而分解的结果中,2的个数显然是多于5的,因此,有多少个5,就有多少个(2, 5)对。 

所以,讨论1000的阶乘结尾有几个0的问题,就被转换成了1到1000所有这些数的质因数分解式有多少个5的问题。

 

class Solution {
public:
    long long trailingZeros(long long n) {
        long long count = 0;
        while(n != 0){
            count = count + n/5;
            n = n / 5;
        }
        return count;
    }
};

6. 合并排序数组 II

合并两个排序的整数数组A和B变成一个新的数组。

这里注意定义完动态数组C,不能直接通过数组下标访问,会发生越界错误。正确方法应该是使用C.push_back(),这里使用了归并排序。

class Solution {
public:
    vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {
        // write your code here
        int i = 0, j = 0, k;
        vector<int> C;
        int lenA = A.size();
        int lenB = B.size();
        for(k = 0; k < (lenA + lenB); k++){
            if((i<lenA) && (j<lenB)){
                if(A[i] <= B[j]){
                    C.push_back(A[i]);
                    i++;
                }
                else{
                    C.push_back(B[j]);
                    j++;
                }
            }
            else if (i < lenA){
                C.push_back(A[i]);
                i++;
            }
            else{
                C.push_back(B[j]);
                j++;
            }
        }
        return C;
    }
};

8. 旋转字符串

offset=0 => "abcdefg"
offset=1 => "gabcdef"
offset=2 => "fgabcde"

这里注意offset远大于str的情况,先除余处理,否则会超时。这里用到了str.substr(),

例子:string a=str.substr(0,4); //获得字符串s中 从第0位开始的长度为4的字符串

class Solution {
public:
    void rotateString(string &str, int offset) {
        // write your code here
        if(str.size() == 0)
        return;
        offset = offset % str.size();
        str = str.substr(str.size() - offset, offset) + str.substr(0, str.size() - offset);
    }
};

另一种方法:

class Solution {
public:
    void rotateString(string &str, int offset) {
        // write your code here
        int i, j, k = 0;
        string a(str);
        if(str.size() == 0){
            return;
        }
        offset %= str.size();
        for(i = str.size()-offset; i < str.size(); i++){
            a[k++] = str[i];
        }
        
        for(j = 0; j < str.size()-offset; j++){
            a[k++] = str[j];
        }
        str = a;
        return;
    }
};

9. Fizz Buzz 问题

如果这个数被3整除,打印fizz.
如果这个数被5整除,打印buzz.

如果这个数能同时被3和5整除,打印fizz buzz.

只要注意将int转类型为string 用to_string

class Solution {
public:
    vector<string> fizzBuzz(int n) {
        // write your code here
        vector<string> a;
        int i;
        for(i = 1; i <= n; i++){
            if(i%3==0 && i%5 ==0){
                a.push_back("fizz buzz");
            }
            else if(i % 3 == 0){
                a.push_back("fizz");
            }
            else if(i % 5 == 0){
                a.push_back("buzz");
            }
            else{
                a.push_back(to_string(i)); // 将int转类型为string 用to_string
            }
        }
        return a;
    }
};

13. Implement strStr()

如果 source = "source" 和 target = "target",返回 -1。

如果 source = "abcdabcdefg" 和 target = "bcd",返回 1。

注意这里传入为地址参数。空指针为nullptr;strlen()先简单理解为串长度。

class Solution {
public:
    int strStr(const char *source, const char *target) {
        // write your code here
        if(source==nullptr || target==nullptr){
            return -1;
        }
        int lens = strlen(source);
        int lent = strlen(target);
        for(int i=0; i <= lens - lent; i++){
            int j = 0;
            for(j = 0; j < lent; j++){
                if(source[i+j] != target[j]) break;
            }
            if(j == lent) return i;
        }
        return -1;
    }
};

156. 合并区间

[                     [
  (1, 3),               (1, 6),
  (2, 6),      =>       (8, 10),
  (8, 10),              (15, 18)
  (15, 18)            ]

]

这里接触到的新知识:1、类内定义函数需要static。2、sort函数的第三个参数为自己定义的函:cmp。3、动态数组最后一个元素用result.back()调用

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */

class Solution {
public:
    static bool cmp(const Interval &A, const Interval &B){
    return (A.start < B.start);
}
    vector<Interval> merge(vector<Interval> &intervals) {
        // write your code here
        sort(intervals.begin(), intervals.end(), cmp);
        int len = intervals.size();
        if(len <= 1) return intervals;
        vector<Interval> result;
        int i = 0;
        result.push_back(intervals[0]);
        for(i = 1; i < len; i++){
            if(result.back().end >= intervals[i].start){
                result.back().end = max(result.back().end, intervals[i].end);
            }
            else{
                result.push_back(intervals[i]);
            }
        }
        return result;
    }
};

173. 链表插入排序

Given 1->3->2->0->null, return 0->1->2->3->null

第一次接触链表,需要注意的是1、定义节点是ListNode *p = new ListNode(0); 2、比较的时候利用temp->next->val,否则会丢失上一个节点,比较麻烦,这也是为什么经常使用头结点的原因

/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    ListNode * insertionSortList(ListNode * head) {
        // write your code here
        if(head == NULL) return head;
        ListNode *result = new ListNode(0);
        while(head != NULL){
            ListNode *temp = result;
            ListNode *next = head->next;
            while(temp->next!=NULL && temp->next->val<head->val){
                temp = temp->next;
            }
            head->next = temp->next;
            temp->next = head;
            head = next;
        }
        return result->next;
    }
};

464. 整数排序 II

快速排序:

class Solution {
public:
    void sortIntegers2(vector<int> &A) {
        // write your code here
        QuickSort(A, 0, A.size() - 1);
    }
private:
    void QuickSort(vector<int> &A, int l, int r){
        if(l >= r){
            return;
        }
        int i = l, j = r;
        int pivot = A[(l+r)/2];
        while(i <= j){
            while(A[j] > pivot && i<=j){
                j--;
            }
            while(A[i] < pivot && i<=j){
                i++;
            }
            if(i <= j){
                int temp = A[j];
                A[j] = A[i];
                A[i] = temp;
                i++;
                j--;
            }
        }
        QuickSort(A, i, r);
        QuickSort(A, l, j);
    }
};

547. 两数组的交

nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2].

这里有几个新的知识点:1、迭代器vector<int>::iterator it; 2、unique函数。last = unique(result.begin(), result.end()); unique的作用是从输入序列中“删除”所有相邻的重复元素,作用结果保留在result数组中。其实它并不真正把重复的元素删除,是把重复的元素移到后面去了,然后依然保存到了原数组中,然后 返回去重后最后一个元素的地址,因为unique去除的是相邻的重复元素,所以一般用之前都会要排一下序。3、erase():第一个参数为起始地址,第二个参数为终止地址,删除指定位置的元素。

class Solution {
public:
    vector<int> intersection(vector<int> nums1, vector<int> nums2) {
        // write your code here
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        vector<int> result;
        vector<int>::iterator it1 = nums1.begin(), it2 = nums2.begin();
        while(it1 != nums1.end() && it2 != nums2.end()){
            if(*it1 > *it2){
                it2++;
            }
            else if(*it1 < *it2){
                it1++;
            }
            else{
                result.push_back(*it1);
                it1++;
                it2++;
            }
        }
        auto last = unique(result.begin(), result.end());
        result.erase(last, result.end());
        return result;
    }
};

846. 多关键字排序

给出 [[2,50],[1,50],[3,100]],

返回 [[3,100],[1,50],[2,50]]

冒泡排序的思想,这里注意交换的时候是交换数组,第一次做的时候直接交换了array[j][1]和array[j+1][1]。。。无语

class Solution {
public:
    vector<vector<int>> multiSort(vector<vector<int>> &array) {
        // Write your code here
        vector<int> tmp;
        for(int i = array.size() - 1; i > 0; i--){
            for(int j = 0; j < i; j++){
                if(array[j][1] < array[j+1][1]){
                    tmp = array[j+1];
                    array[j+1] = array[j];
                    array[j] = tmp;
                }
                else if(array[j][1] == array[j+1][1]){
                    if(array[j][0] > array[j+1][0]){
                        tmp = array[j+1];
                        array[j+1] = array[j];
                        array[j] = tmp;
                    }
                }
            }
        }
        return array;
    }
};

49. 字符大小写排序

给出"abAcD",一个可能的答案为"acbAD"

str.substr()的使用

#include<iostream>
#include<string>
using namespace std;
class Solution {
public:
     bool isLower(char c){
         return (c >= 'a' && c <= 'z');
     }
    void sortLetters(string &chars) {
        // write your code here
        if(chars.size() <= 1) return;
        sort(chars.begin(), chars.end());
        int i = 0;
        while(isLower(chars[i]) == false){
            i++;
        }
        // 定义串方法:
        // string tmp(chars); 这样就可以使用串tmp了
        chars = chars.substr(i, chars.size() - i) + chars.substr(0, i);
    }
};

57. 三数之和

样例
如S = {-1 0 1 2 -1 -4}, 你需要返回的三元组集合的是:
(-1, 0, 1)

(-1, -1, 2)

本题难点在于得到最终结果时,可能会出现重复答案,在初步得到答案需要删除答案中重复部分,即利用前面所学unique()和result.erase();这里有惊喜,发现定义变量使用auto是万能的?

class Solution {
public:
    vector<vector<int>> threeSum(vector<int> &numbers) {
        // write your code here
        sort(numbers.begin(), numbers.end());
        vector<vector<int>> result;
        int i, j ,k;
        for(i = 0; i < numbers.size(); i++){
            for(j = i + 1; j < numbers.size(); j++){
                for(k = j + 1; k < numbers.size(); k++){
                    if(numbers[i] + numbers[j] + numbers[k] == 0){
                        vector<int> chars;
                        chars.push_back(numbers[i]);
                        chars.push_back(numbers[j]);
                        chars.push_back(numbers[k]);
                        result.push_back(chars);
                        sort(result.begin(), result.end());
                        auto last = unique(result.begin(), result.end());
                        result.erase(last, result.end());
                    }
                }
            }
        }
        return result;
    }
};

14.二分查找

这里使用了递归;注意存在多个目标值,取最小的小标。

class Solution {
public:
    int Search(vector<int> &nums, int target, int left, int right){
        if(left > right) return -1;
        if(left == right && target == nums[left]){
            return left;
        }
        int mid;
        mid = (left+right) / 2;
        if(target == nums[mid]){
            Search(nums, target, left, mid); //这里进入二次判断是否目标值的下标是最小的
        }
        else if(target < nums[mid]){
            Search(nums, target, left, i-1);
        }
        else{
            Search(nums, target, i+1, right);
        }
    }
    int binarySearch(vector<int> &nums, int target) {
        // write your code here
        Search(nums, target, 0, nums.size()-1);
    }
};