清风的技术小屋

华为2018校园实习招聘编程题

Posted on 2018-03-23 Edited on 2020-08-09

题目一在字符串中找出连续最长的数字串

问题描述

给定一个字符串，输出字符串中最长的数字串，并把这个数字串的长度输出。

请在一个字符串中找出连续最长的数字串，并把这个串的长度返回；如果存在长度相同的连续数字串，返回最后一个连续数字串。

注意：数字串只需要是数字组成的就可以，并不要求顺序，比如数字串"1234"的长度就小于数字串"1359055"，如果没有数字，就返回空字符串 ("") 而不是NULL。

输入描述

一个字符串

输出描述

1 2	输出最长的数字串，输出最长数字串中数字个数中间以逗号 (,) 隔开

示例 1

输入

1	abcd12345ed125ss123058789

输出

1	123058789,9

备注

如果存在长度相同的连续数字串，则输出最后一个连续数字串。

数字串只需要是数字组成的就可以，并不要求顺序，比如数字串"1234"的长度就小于数字串"1359055"。

如果没有数字，就返回空字符串 ("") 而不是NULL。

解决方案

可以设定两对指针，每对指针包含字符串的起始位置和结束位置的后一个位置，第一对指针保存着最长的数字串，第二对指针保存当前找到的数字串，通过指针相减可以得到字符串长度，通过比对长度大小不断更新指针的位置。实现代码如下：

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string str;
    while (cin >> str) {
        bool numeric;
        int long_start, long_end, long_len;
        int tmp_start, tmp_end;

        long_start = long_end = -1;
        long_len = 0;
        tmp_start = tmp_end = 0;

        numeric = false;
        int i;
        for (i=0; i<str.size(); i++) {
            if (str[i] >= '0' && str[i] <= '9') {
                if (numeric == false)
                    tmp_start = i;
                numeric = true;
            } else {
                if (numeric == true) {
                    tmp_end = i;
                    if ((tmp_end - tmp_start) >= long_len) {
                        long_start = tmp_start;
                        long_end = tmp_end;
                        long_len = tmp_end - tmp_start;
                    }
                }
                numeric = false;
            }
        }
        if (i == str.size() && numeric == true) {
            tmp_end = i;
            if ((tmp_end - tmp_start) >= long_len) {
                long_start = tmp_start;
                long_end = tmp_end;
                long_len = tmp_end - tmp_start;
            }
        }

        if (long_len > 0) {
            for (i=long_start; i<long_end; i++)
                cout << str[i];
            cout << "," << long_len << endl;
        } else {
            cout << ",0" << endl;
        }
    }

    return 0;
}

题目二字节流解析

问题描述

根据数值占用BIT数，按顺序从输入字节流中解析出对应数值，解析顺序按输入数组astElement索引升序

1 2	void Decode(unsigned int uiInputLen, unsigned char aInputByte[], unsigned int uiElementNum, ELEMENT_STRU astElement[]);

其中

unsigned int uiInputLen : 字节数组 (流) 长度
unsigned char aInputByte : 字节数组 (流)
unsigned int uiElementNum : 解析数值个数
ELEMENT_STRU astElement[] : 数值的结构数组指针，含义如下
Struct
{
    unsigned int uiElementLength; //表示uiElementValue占用BIT数，范围1~32
    unsigned int uiElementValue; //从字节流中按顺序解析的数值，用于输出
} ELEMENT_STRU;

输入描述

字节数组长度uiInputLen为3;
字节数组aInputByte[3]为{0x62, 0x80, 0x00}，对应二进制为 "0110 0010, 1000 0000, 0000 0000";
解析数值个数uiElementNum为2;
数值[0]的值占4个bit，即 astElement[0].uiElementLength = 4;
数值[1]的值占5个bit，即 astElement[1].uiElementLength = 5;

输出描述

1 2	数值[0]的值为6，二进制为 "0110"，即 astElement[0].uiElementValue = 6; 数值[1]的值为5，二进制为 "0010 1"，即 astElement[1].uiElementValue = 5;

示例 1

输入

3
0x62 0x80 0x00
2
4
5

输出

1
2

6
5

解决方案

这道题目主要是对数字进行进制转换，输入为一个十六进制字符串，然后需要转换成对应的二进制字符串，我的做法是将字符串转换成十进制整数 (使用stoi函数)，然后将这个十进制整数转化成二进制字符串，将转换后的二进制字符串保持到数组aInputByte，这里我不固定数组aInputByte大小，根据输入的参数uiInputLen动态设定数组大小，数据转换完毕后，调用Decode函数进行解析。

PS: 十六进制字符串转二进制字符串应该可以直接用映射关系来转换，因为每个十六进制字符对应的二进制是固定的。

#include <iostream>
#include <string>
using namespace std;

struct ELEMENT_STRU {
    unsigned int uiElementLength;
    unsigned int uiElementValue;
};

void Decode(unsigned int uiInputLen, unsigned char aInputByte[],
            unsigned int uiElementNum, ELEMENT_STRU astElement[])
{
    unsigned int uiElementValue, uiElementLength, pow2;
    int start, end;
    start = 0;
    for (int i=0; i<uiElementNum; i++) {
        uiElementLength = astElement[i].uiElementLength;
        uiElementValue = 0;
        pow2 = 1;
        end = start + uiElementLength;
        for (int j=end-1; j>=start; j--) {
            if (aInputByte[j] == '1')
                uiElementValue = uiElementValue + pow2;
            pow2 = 2 * pow2;
        }
        astElement[i].uiElementValue = uiElementValue;
        start = end;
    }
}

int main()
{
    string str;
    unsigned int uiInputLen, num, uiElementNum,flag;
    unsigned int numberBytes;
    int start, end;
    unsigned char *aInputByte = NULL;
    ELEMENT_STRU *astElement = NULL;
    while (cin >> uiInputLen) {
        aInputByte = (unsigned char *)malloc(sizeof(unsigned char) * 32 * uiInputLen);
        start = 0;
        end = 0;
        for (int i=1; i<=uiInputLen; i++) {
            cin >> str;
            if (str.size() == 3)        // 0xX
                numberBytes = 4;
            else if (str.size() == 4)   // 0xXX
                numberBytes = 8;
            else if (str.size() == 5)   // 0xXXX
                numberBytes = 12;
            else if (str.size() == 6)   // 0xXXXX
                numberBytes = 16;

            end = start + numberBytes;

            flag = 1;
            num = stoi(str, 0, 16);
            for (int j=end-1; j>=start; j--) {
                if (flag & num)
                    aInputByte[j] = '1';
                else
                    aInputByte[j] = '0';
                flag = flag << 1;
            }

            start = end;
        }

        cin >> uiElementNum;
        astElement = (ELEMENT_STRU*)malloc(sizeof(ELEMENT_STRU)*uiElementNum);
        for (int i=0; i<uiElementNum; i++) {
            cin >> num;
            astElement[i].uiElementLength = num;
        }

        Decode(uiInputLen, aInputByte, uiElementNum, astElement);

        for (int i=0; i<uiElementNum; i++)
            cout << astElement[i].uiElementValue << endl;

        free(aInputByte);
        free(astElement);
    }
    return 0;
}

题目三长整数相乘

问题描述

长整数相乘

输入描述

1	输入两个长整数，以空格隔开

输出描述

输出相乘后的结果

示例 1

输入

1 2	-12341234 43214321

输出

1	-533318047612114

解决方案

LeetCode有类似大整数相乘题目 43. Multiply Strings，和本题区别在于，LeetCode那题假设两个整数都是非负的，这题的整数可以是负数，在LeetCode 43题解题基础上加个符号判断即可解出该题。

LeetCode 237 - Delete Node in a Linked List

Posted on 2018-03-23 Edited on 2020-08-09

问题描述

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

题目的意思是给单链表的节点指针 (不包括尾节点)，然后删除该节点。

解决方案

如果按照常规单链表删除节点的操作，首先要找到要删除节点的前一个节点，然后再删除节点，但是这里只给定了待删除节点的指针，因此按照常规删除方法是不可行的，虽然待删除节点的前一节点我们不可知，但是我们可以知道该节点的下一个节点，如果我们把下一节点的内容复制到需要删除的节点上覆盖原有的内容，再把下一节点删除，那是不是就相当于把当前需要删除的节点删除了？根据题目描述，题目提供的节点不包括尾节点，因此不用考虑下一节点是 NULL 的情况。按照上面思路，可以有如下代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution
{
public:
    /*
     * the node is not the last node
     */
    void deleteNode(ListNode* node)
    {
        if (node == NULL)
            return;

        ListNode *next_node = node->next;
        node->val = next_node->val;
        node->next = next_node->next;
        delete next_node;
    }
};

常用排序算法总结

Posted on 2018-03-14 Edited on 2020-08-09

在介绍排序算法之前，先约定数组表示为 \(A\)，大小为 \(N\)，数组下标从 \(0\) 开始，排序的数组是从小到大排列

插入排序

在数组是反序的情况下，时间复杂度为 \(O(N^2)\)，在数组已排序的情况下，时间复杂度为 \(O(N)\)

void insertion_sort(int *nums, int n)
{
    int p, tmp;
    for (int i=1; i<n; i++)
    {
        tmp = nums[i];
        for (p=i; p > 0 && nums[p-1] > tmp; p--)
            nums[p] = nums[p-1];
        nums[p] = tmp;
    }
}

归并排序

时间复杂度为 \(O(NlogN)\)

void merge(int *nums, int *tmp, int left_start, int right_start, int right_end)
{
    int left_pos, right_pos, pos;

    left_pos = left_start;
    right_pos = right_start;
    pos = left_start;
    while (left_pos < right_start && right_pos <= right_end) {
        if (nums[left_pos] <= nums[right_pos])
            tmp[pos++] = nums[left_pos++];
        else
            tmp[pos++] = nums[right_pos++];
    }

    while (left_pos < right_start) {
        tmp[pos++] = nums[left_pos++];
    }
    while (right_pos <= right_end) {
        tmp[pos++] = nums[right_pos++];
    }

    // copy array tmp back to array nums
    for (int i=left_start; i<=right_end; i++)
        nums[i] = tmp[i];
}

void msort(int *nums, int *tmp, int left, int right)
{
    if (left < right)
    {
        int center = (left + right) / 2;
        msort(nums, tmp, left, center);
        msort(nums, tmp, center+1, right);
        merge(nums, tmp, left, center+1, right);
    }
}

void merge_sort(int *nums, int n)
{
    int *tmp = new int[n];
    msort(nums, tmp, 0, n-1);
    delete[] tmp;
}

快速排序

平均时间复杂度为 \(O(NlogN)\)，最坏的情形下，时间复杂度为 \(O(N^2)\)

int partition(int *nums, int left, int right)
{
    int i = left - 1;
    int tmp;
    int pivot = nums[right];

    for (int j=left; j<=right-1; j++) {
        if (nums[j] <= pivot) {
            i = i + 1;

            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

    i = i + 1;
    tmp = nums[i];
    nums[i] = pivot;
    nums[right] = tmp;

    return i;
}

void qsort(int *nums, int left, int right)
{
    if (left < right) {
        int p = partition(nums, left, right);
        qsort(nums, left, p-1);
        qsort(nums, p+1, right);
    }
}

void quick_sort(int *nums, int n)
{
    qsort(nums, 0, n-1);
}

LeetCode 1 - Two Sum

Posted on 2018-03-12 Edited on 2020-08-09

问题描述：

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9. Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

时间复杂度为 O(n) 解法

首先分析下问题，根据问题描述，可以得知数组是无序的。如果用暴力方法解决问题，也就是先在数组中固定一个数字，再判断数组中其余的 \(n-1\) 个数字与它的和是不是等于目标值，这样时间复杂度是 \(O(n^2)\)。这里关键地方就是在于固定一个数字时，如何快速在数组中寻找与它的和等于目标值，而不是通过遍历方法一个个找，这样时间复杂度要 \(O(n)\)，想到快速查找，第一时间可以想到的是哈希表 (Hash Map)，因为这个查找元素的时间复杂度为 \(O(1)\)。

对于哈希表，我们可以用数组中的数字作为哈希表的key，用数字的下标作为哈希表的value。当我们从头遍历数组时，对于访问到的数字，我们首先判断哈希表中是否存在与它的和等于目标值的key，如果不存在，插入该数字到哈希表中，如果存在，算法返回两个数字对应的数组的下标。可以看出，这个算法只需要遍历一次数组，因此算法复杂度为 \(O(n)\)。

#include <unordered_map>
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> nums_map;
        unordered_map<int, int>::const_iterator iter;
        vector<int> indices;
        for (int i=0; i<nums.size(); i++) {
            if ((iter = nums_map.find(target - nums[i])) == nums_map.end()) {
                nums_map.insert(make_pair(nums[i], i));
            } else {
                indices.push_back(iter->second);
                indices.push_back(i);
                break;
            }
        }

        return indices;
    }
};

int main()
{
    int target = 9;
    vector<int> nums;
    nums.push_back(2);
    nums.push_back(7);
    nums.push_back(11);
    nums.push_back(15);

    Solution sol;
    vector<int> indices = sol.twoSum(nums, target);
    if (indices.size() == 0) {
        cout << "Not found" << endl;
    } else {
        cout << "Find: [" << indices[0] << ", " << indices[1] << "]" << endl;
    }
    return 0;
}

LeetCode 136 - Single Number

Posted on 2018-03-12 Edited on 2020-08-09

问题描述：

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

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

时间复杂度为 O(n) 算法

算法要用到异或运算，异或运算的规律如下所示：

0 xor 0 = 0

0 xor 1 = 1

1 xor 0 = 1

1 xor 1 = 0

很容易验证一个异或运算的性质：任何一个数字异或它自己都等于0，试想有个数组 \([A, B, A, C, B]\)，数字 \(A\) 和数字 \(B\) 重复出现两次，数字 \(C\) 只出现一次，如果我们将数组所有数字进行异或运算，会出现什么情况？首先，可以写出一个表达式 \[ A \text{ xor } B \text{ xor } A \text{ xor } C \text{ xor B} \]

由于异或运算满足交换律和结合律，因此可以得到下面这个表达式 \[ (A \text{ xor } A ) \text{ xor } ( B \text{ xor } B) \text{ xor C} \] 由于 \(A \text{ xor } A = 0\) 以及 \(B \text{ xor } B = 0\)，并且0与任何数异或都为原来的数，因此上面的表达式最终化简为 \[ (A \text{ xor } A ) \text{ xor } ( B \text{ xor } B) \text{ xor C} = C \] 可见，对数组所有数进行异或运算，最终结果就是那个只出现一次的数。知道算法原理，我们可以很容易写出实现代码

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (auto it=nums.begin(); it!=nums.end(); ++it)
            ret ^= *it;

        return ret;
    }
};

int main()
{
    Solution solu;

    vector<int> v1 = {2, 3, 2, -1, 3};
    cout << "Single Number is: " << solu.singleNumber(v1) << endl;

    return 0;
}

LeetCode 88 - Merge Sorted Array

Posted on 2018-03-10 Edited on 2020-08-09

问题描述：

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note: You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

题目中说数组nums1大小为 m，数组nums2的大小为 n，要将数组nums2中的元素全部放到数组nums1中且保证数组nums1有序（这里有序假设是从小到大）。

时间复杂度为 O(nm) 的解法

初看到这个题目，一个最直观的想法就是设定两个指针分别指向两个数组开始的元素（令指针p1指向数组nums1，p2指向数组p2），然后从头开始遍历两个数组。

如果指针p1指向的元素小于等于指针p2指向的元素，指针p1加一。
如果指针p1指向的元素大于指针p2指向的元素，将指针p2指向的元素插入到指针p1指向的位置，指针p1指向的位置后面的元素都后移一位，指针p1和指针p2都加一。

这样操作直到数组nums1或数组nums2的元素遍历完，如果是数组nums1的元素先被遍历完，则将数组nums2剩下的元素都复制到数组nums1中，如果是数组nums2的元素先被遍历完，算法停止。在最坏的情况下，数组nums2的元素都小于数组nums1的元素，每次插入数组nums2的元素，都要移动数组nums1的 \(O(m)\) 个字符，那么算法复杂度为 \(O(nm)\)。

时间复杂度为 O(n + m) 的解法

换个思路，我们不从头开始遍历数组，而是从数组后面开始遍历数组。这里我们准备三个指针：p、p1和p2，指针p指向数组nums1的第 n + m 个元素，指针p1指向数组nums1最后一个元素，指针p2指向数组nums2的最后一个元素。

如果指针p1指向的元素小于指针p2指向的元素，将指针p2指向的元素复制到指针p指向的位置，指针p和p2减一。
如果指针p1指向的元素大于等于指针p2指向的元素，将指针p1指向的元素复制到指针p指向的位置，指针p和p1减一。

这样操作直到数组nums1或数组nums2被遍历完，如果是数组nums1先被遍历完，将数组nums2剩余的元素复制到数组nums1中，如果是数组nums2先被遍历完，则算法停止。从上面分析我们可以看出，只需要遍历一次数组nums1和数组nums2就行，不需要移动元素，因此这个算法的时间复杂度为 \(O(n + m)\)。

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

        if (m <= 0)
            nums1 = nums2;
        if (n <= 0)
            return;

        int p, p1, p2;
        p1 = m - 1;
        p2 = n - 1;
        p = m + n - 1;

        while (p >= 0 && p1 >= 0 && p2 >= 0) {
            if (nums1[p1] >= nums2[p2]) {
                nums1[p] = nums1[p1];
                p1--;
            } else if (nums1[p1] < nums2[p2]) {
                nums1[p] = nums2[p2];
                p2--;
            }
            p--;
        }

        if (p2 >= 0) {
            while (p >=0 && p2 >=0)
                nums1[p--] = nums2[p2--];
        }
    }
};

int main()
{
    Solution solu;

    vector<int> nums1 = {1, 3, 5, 7, 0, 0, 0};
    vector<int> nums2 = {2, 4, 6};
    solu.merge(nums1, 4, nums2, nums2.size());

    for (auto it=nums1.begin(); it!=nums1.end(); ++it)
        cout << *it << " ";
    cout << endl;

    vector<int> nums3 = {0, 0, 3, 0, 0, 0, 0, 0, 0};
    vector<int> nums4 = {-1, 1, 1, 1, 2, 3};
    solu.merge(nums3, 3, nums4, nums4.size());

    for (auto it=nums3.begin(); it!=nums3.end(); ++it)
        cout << *it << " ";
    cout << endl;

    return 0;
}

LeetCode 215 - Kth Largest Element in an Array

Posted on 2018-03-09 Edited on 2020-08-09

问题描述：

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. For example, Given [3,2,1,5,6,4] and k = 2, return 5.

Note: You may assume k is always valid, 1 ≤ k ≤ array's length.

这道题目最简单的思路莫过于把输入的 \(n\) 个数进行排序，排序之后第 \(k\) 个数字 (如果数是从大到小排序) 就所要求的第 \(k\) 大的数字，这种思路的时间复杂度是 \(O(nlog(n))\) 。但是这样还不是最快的做法，接下来讨论更快的算法。

时间复杂度为 O(nlog(k)) 的算法

我们可以先创建一个大小为 \(k\) 的数据容器来存储最大的 \(k\) 个数，接下来每次从输入的 \(n\) 个数中读入一个数。如果容器中已有的数字少于 \(k\) 个，则直接把这次读入的数放入容器之中；如果容器中已有 \(k\) 个数字了，也就是容器已经满了，此时只能替换容器中的数字了。找出容器中 \(k\) 个数的最小值，然后拿这次待插入的数与其比较，如果待插入的数字比容器中的最小值要大，则用这个数替换当前已有的最小值，如果待插入的数字比这个最小值要小，那么这个数不能是最大的 \(k\) 个数之一，则抛弃这个数字。

因此，当容器满了以后，我们要做三件事：一是在 \(k\) 个数中找到最小数；二是有可能在这个容器中删除最小数；三是有可能要插入一个新的数字。如果使用一棵二叉树来实现这个容器，那么我们能在 \(O(log(k))\) 的时间内实现这三步操作。因此，对于 \(n\) 个输入数字而言，总的时间效率是 \(O(n log(k))\)。

由于每次都需要找到 \(k\) 个数中的最小值，很自然可以想到用最小堆。当然，我们还可以考虑是用红黑树来实现这个容器，红黑树可以保证查找、删除和插入这些操作都只需要 \(O(log(k))\) 时间，在STL中，set 和 multiset 都是基于红黑树实现。

基于最小堆实现


#include <queue>
#include <iostream>
using namespace std;

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> k_numbers;
        int min_number;

        for (auto it=nums.begin(); it!=nums.end(); ++it) {
            if (k_numbers.size() < k) {
                k_numbers.push(*it);
            } else {
                min_number = k_numbers.top();
                if (*it > min_number) {
                    k_numbers.pop();
                    k_numbers.push(*it);
                }
            }
        }

        return k_numbers.top();
    }
};

int main()
{
    Solution solu;
    vector<int> nums = {3, 2, 1, 5, 6, 4};

    cout << "The 2th max number is " << solu.findKthLargest(nums, 2) << endl;

    return 0;
}

基于红黑树实现


#include <vector>
#include <set>
#include <iostream>
using namespace std;

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        multiset<int> k_numbers;
        multiset<int>::iterator set_iterator;

        for (auto it=nums.begin(); it!=nums.end(); ++it) {
            if (k_numbers.size() < k) {
                k_numbers.insert(*it);
            } else {
                set_iterator = k_numbers.begin();
                if (*it > *set_iterator) {
                    k_numbers.erase(set_iterator);
                    k_numbers.insert(*it);
                }
            }
        }

        return *(k_numbers.begin());
    }
};

int main()
{
    Solution solu;
    vector<int> nums = {3, 2, 1, 5, 6, 4};

    cout << "The 2th max number is " << solu.findKthLargest(nums, 2) << endl;

    return 0;
}

剑指offer - 变态跳台阶

Posted on 2018-03-08 Edited on 2020-08-09

题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级 …… 它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

先从最简单的情况说起。如果只有1级台阶，跳法只有一种。如果有2级台阶，那就有两种跳法：一种是分两次跳，每次跳1级；另一种就是一次跳2级。如果有3级台阶，那就有四种跳法：一种是分三次跳，每次跳1级；一种是先跳2级，再跳1级；一种是先跳1级，再跳2级；还有一种是一次跳3级。

接下来讨论一般情况。我们把n级台阶时的跳法看成n的函数，记为\(f(n)\)。根据前面分析，可以得到 \[ \begin{aligned} f(1) & = 1 = 2^0 \\ f(2) & = 2 = 2^{2-1} \\ f(3) & = 4 = 2^{3-1} \end{aligned} \]

可以看出一个规律，那就是\(f(n) = 2^{n-1}\)，那么怎么证明呢？先分析下n级台阶怎么跳，青蛙第一次跳有n中选择，可以第一次跳1级，此时后面台阶的跳法数目等于\(f(n-1)\)，如果第一次跳2级，此时后面台阶的跳法数目等于\(f(n-2)\)，一直到第一次直接跳\(n\)级，此时剩余台阶数为0，则跳法数目为\(f(0)\)，这里约定\(f(0)=1\)，为了后面分析方便。综上可以得到一个递推公式： \[ f(n) = f(n-1) + f(n-2) + \cdots + f(2) + f(1) + f(0) \] 接下来用数学归纳法证明\(f(n)=2^{n-1}\)。如果前\(n\)项满足公式\(f(n)=2^{n-1}\)，那么对于\(f(n+1)\)，可以得到 \[ \begin{align} f(n+1) &= f(n) + f(n-1) + \cdots + f(1) + f(0) \\ & = 2^{n-1} + 2^{n-2} + \cdots + 2^0 + 1 \\ & = \frac{1 - 2^n}{1 - 2} + 1 \\ & = 2^n \end{align} \] 可看出\(f(n+1)\)仍然满足公式。知道通向公式后，剩下的实现就很简单了，贴上C++代码。

#include <iostream>
using namespace std;

class Solution {
public:
    int jumpFloorII(int number) {
        if (number == 0)
            return 0;

        int f = 1;
        for (int i=1; i<number; i++)
            f *= 2;

        return f;
    }
};

int main()
{
    Solution solu;

    cout << "f(0)= " << solu.jumpFloorII(0) << endl;
    cout << "f(1)= " << solu.jumpFloorII(1) << endl;
    cout << "f(2)= " << solu.jumpFloorII(2) << endl;
    cout << "f(5)= " << solu.jumpFloorII(5) << endl;
    return 0;
}

大量图片文件生成SequenceFile

Posted on 2017-03-12 Edited on 2020-08-09

本文主要介绍如何将大量图片数据集合起来，然后生成一个SequenceFile，这么做的原因是避免Hadoop处理大量小文件导致性能下降。SequenceFile的key-value内容以及数据类型为：

1 2	key : 储存图片文件名，数据类型为Text value : 储存图片数据，数据类型为ArrayPrimitiveWritable

为什么要用ArrayPrimitiveWritable来存储图片数据，主要是我想将图片数据用一个int数组来存储，数组元素就是图像的像素，数据范围在[0, 255]，当然，你可以使用byte数组来存储图片数据。

Java获取指定目录下的所有文件

Posted on 2017-03-11 Edited on 2020-08-09

本文介绍了如何使用Java来获取指定目录下的所有文件。

获取指定目录下的所有文件

使用递归方法遍历目录，如果访问的是文件夹，则进入递归，否则将文件加入到文件列表中，同时可以设定遍历深度（从深度1开始）。

import java.io.File;
import java.util.ArrayList;

public class ListFiles {

    /**
     * 获取指定目录下的所有文件（不包括文件夹)
     * @param path 文件夹的File对象或者文件夹路径字符串
     * @param depth 遍历深度，从深度1开始
     * @return 指定目录下所有的文件的File对象的集合
     */
    public static ArrayList<File> getAllFiles(Object path, int depth) {
        File directory = null;
        if (path instanceof File) {
            directory = (File)path;
        } else {
            directory = new File(path.toString());
        }

        ArrayList<File> files = new ArrayList<File>();
        if (directory.isFile()) {
            files.add(directory);
        } else if (directory.isDirectory()) {
            depth--;
            if (depth >= 0) {
                File[] fileList = directory.listFiles();
                for (File file : fileList) {
                    files.addAll(getAllFiles(file, depth));
                }
            }
        }

        return files;
    }
}

测试代码如下：

import org.junit.Test;

import java.io.File;
import java.util.ArrayList;

public class ListFilesTest {
    @Test
    public void getAllFiles() throws Exception {
        String path = "/Users/luowanqian/Documents/Datasets/LFWCrop/lfwcrop_grey/faces";

        ArrayList<File> files = ListFiles.getAllFiles(path, 1);
        int n = 0;
        for (File file : files) {
            n++;
            System.out.println(file.toString());
        }
        System.out.println("Total : " + n);
    }

}

运行结果如下：

...
/Users/luowanqian/Documents/Datasets/LFWCrop/lfwcrop_grey/faces/Zoran_Djindjic_0004.pgm
/Users/luowanqian/Documents/Datasets/LFWCrop/lfwcrop_grey/faces/Zorica_Radovic_0001.pgm
/Users/luowanqian/Documents/Datasets/LFWCrop/lfwcrop_grey/faces/Zulfiqar_Ahmed_0001.pgm
/Users/luowanqian/Documents/Datasets/LFWCrop/lfwcrop_grey/faces/Zumrati_Juma_0001.pgm
/Users/luowanqian/Documents/Datasets/LFWCrop/lfwcrop_grey/faces/Zurab_Tsereteli_0001.pgm
/Users/luowanqian/Documents/Datasets/LFWCrop/lfwcrop_grey/faces/Zydrunas_Ilgauskas_0001.pgm
Total : 13233

题目一 在字符串中找出连续最长的数字串

问题描述

解决方案

题目二 字节流解析

问题描述

解决方案

题目三 长整数相乘

问题描述

解决方案

问题描述

解决方案

插入排序

归并排序

快速排序

时间复杂度为 O(n) 解法

时间复杂度为 O(n) 算法

时间复杂度为 O(nm) 的解法

时间复杂度为 O(n + m) 的解法

时间复杂度为 O(nlog(k)) 的算法

基于最小堆实现

基于红黑树实现

获取指定目录下的所有文件

Reference

题目一在字符串中找出连续最长的数字串

题目二字节流解析

题目三长整数相乘