玉刚写作平台-常见算法之(Array、String、List)

打个比方，在金庸的武侠世界里，数据结构和算法它就像一门上乘的内功心法，一旦掌握了它，各种武功信手拈来（张无忌就是典型的例子）；对于程序员来说，它能决定你在技术这条道路上能走多远。现在去大公司面试，都会有算法题。本文主要涉及数组、字符串、List这几个数据结构，我们一起来分析和解答几道常见算法题，后面我会分享一下我的学习心得和一些解题套路。

题目1：翻转句子

题目：给定一个英文句子，每个单词之间都是由一个或多个空格隔开，请翻转句子中的单词顺序（包括空格的顺序），但单词内字符的顺序保持不变。例如输入”www google com “，则应输出” com google www”。

如果你经常关注算法相关文章，这道题应该会比较熟悉，各种博客和书籍上都有出现，不熟悉也没关系，现在我们就一起来尝试解答下。要注意一下和网上流传的题目的不同点：每个单词之间都是由 一个或多个空格隔开 ，而网上大多是单词间由空格分隔， 有且只有一个空格。

解题思路

试想一下，如果将整个字符串翻转，结果是句子是反转了，但单词内的字符顺序也翻转了。如果要保证单词内顺序不变，只需要再将每个单词翻转一下就满足要求了。

理一下思路：

第一步翻转所有字符。比如翻转”www google com “中所有的字符得到” moc elgoog www”，可以看出不仅翻转了句子中单词的顺序，连单词内的字符顺序也翻转了。
第二步再翻转每个单词中字符的顺序，就得到了” com google www”。这正是符合题目的输出。

此思路的关键是： 1. 实现一个函数/方法，翻转字符串中的一段。 2. 判断句子中的单词，注意空格。

测试用例

功能测试：多个单词、1个单词、单词间只有一个空格、单词间有多个空格。
特殊输入测试：空字符、字符串中只有空格、null对象（指针）。

编码实现

Java代码

/**
 * @param chars 原字符串
 * @param start 大于等于0
 * @param end   小于 length
 * @return
 */
private char[] v1_0_reverse(char[] chars, int start, int end) {

    // str 判断null， 索引有效值判断
    if (chars == null || start < 0 || end >= chars.length || start >= end) {
        return chars;
    }

    while (start < end) {
        // 收尾字符互换，直到替换完成。
        char temp = chars[start];
        chars[start] = chars[end];
        chars[end] = temp;
        start++;
        end--;
    }
    return chars;
}

private String v1_0_solution(String sentence) {
    if (sentence == null || sentence.isEmpty()) {
        return sentence;
    }

    int length = sentence.length();
    // 第一步翻转所有字符
    char[] chars = v1_0_reverse(sentence.toCharArray(), 0, length - 1);
    System.out.println(new String(chars));

    // 第二步翻转每个单词（重点：怎么找到单词）
    int start = 0, end = 0;
    while (start < length) {
        if (chars[start] == ' ') {
            // 遇到空格就向右边继续查找
            start++;
            end++;
        } else if (end == length || chars[end] == ' ') {
            // 遇到空格或者已经到了字符串末尾，此时翻转找到的单词内部字符，这里需要注意end-1
            chars = v1_0_reverse(chars, start, end - 1);
            System.out.println(new String(chars));
            // 重新制定检查索引start
            start = end++;
        } else {
            // end加1，为了检查单词是否结束
            end++;
        }
    }
    return new String(chars);
}

C++ 代码实现

// 反转字符串
void Reverse(char *pBegin, char *pEnd)
{
    if(pBegin == NULL || pEnd == NULL)
        return;

    while(pBegin < pEnd)
    {
        char temp = *pBegin;
        *pBegin = *pEnd;
        *pEnd = temp;

        pBegin ++, pEnd --;
    }
}

// 翻转句子中单词顺序，但保证单词内字符顺序不变。
char* ReverseSentence(char *pData)
{
    if(pData == NULL)
        return NULL;

    char *pBegin = pData;

    char *pEnd = pData;
    while(*pEnd != '\0')
        pEnd ++;
    pEnd--;

    // 翻转整个句子
    Reverse(pBegin, pEnd);

    // 翻转句子中的每个单词
    pBegin = pEnd = pData;
    while(*pBegin != '\0')
    {
        if(*pBegin == ' ')
        {
            pBegin ++;
            pEnd ++;
        }
        else if(*pEnd == ' ' || *pEnd == '\0')
        {
            Reverse(pBegin, --pEnd);
            pBegin = ++pEnd;
        }
        else
        {
            pEnd ++;
        }
    }
    return pData;
}

如果你在面试的时候遇到这道题，并且很容易就想到了这个算法，有经验的面试官就会在这道题基础上加点难度，继续考查面试者。so，第二道题来了：

题目：接上题，面试官继续提问，我们得到的” com google www”需要被用作一个URL的参数，所以这里需要的处理是去掉开头结尾的无效空格，并将两个单词中间的每一个空格都替换为”%20”。例如” com google www”应被转换为”com%20%20google%20www”，请给出转换函数。

解题思路

第一步去掉收尾的无效空格；比如” com google www”去掉后得到”com google www”。
第二步将两个单词中间的每一个空格都替换为”%20”。

测试用例

功能测试：前后有无空格情况、中间一个或多个空格情况。
特殊输入测试：空字符、字符串中只有空格、null对象（指针）。

编码实现

Java代码

private String v1_1_solution(String sentence) {
    if (sentence == null || sentence.isEmpty()) {
        return sentence;
    }

    // 去掉字符串收尾的空格
    sentence = trim(sentence);
    int len = sentence.length();
    char[] chars = sentence.toCharArray();
    int count = getSpaceCount(sentence);
    int newLen = 2 * count + len;
    // 扩容，内部使用System.arraycopy 方法实现。
    chars = Arrays.copyOf(chars, newLen);

    int index = len - 1;
    int newIndex = newLen - 1;
    while (index >= 0 && newIndex > index) {
        if (chars[index] == ' ') {
            chars[newIndex--] = '0';
            chars[newIndex--] = '2';
            chars[newIndex--] = '%';
        } else {
            chars[newIndex--] = chars[index];
        }
        index--;
    }

    return new String(chars);
}

/**
 * 剔除字符串收尾的空格
 *
 * @param origin
 * @return
 */
private String trim(String origin) {
    char[] chars = origin.toCharArray();
    int length = chars.length;
    int st = 0;
    while (st < length && chars[st] == ' ') {
        st++;
    }

    while (st < length && chars[length - 1] == ' ') {
        length--;
    }

    // 如果收尾有空格，就截取生成新的字符串
    if (st > 0 || length < chars.length) {
        origin = new String(chars, st, (length - st));
    }
    return origin;
}

private int getSpaceCount(String sentence) {
    char[] chars = sentence.toCharArray();
    int count = 0;
    for (char c : chars) {
        if (c == ' ') {
            count++;
        }
    }
    return count;
}

C++实现

// todo

题目2：调整数组中元素顺序

题目：给定一个整数数组，请实现一个函数来调整数组中数字的顺序，使得所有奇数都位于偶数之前。

解题思路

此题比较简单，我最先想到的解法是这样：我们维护两个指针(索引)，一个指针指向数组的第一个数字，称之为头指针，向右移动；一个指针指向最后一个数字，称之为尾指针，向左移动。

这样，两个指针分别从数组的头部和尾部向数组的中间移动，如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数，我们就交换这两个数字。

循环结束条件：两个指针重叠时，已完成排序，此时退出循环。

VjYzei7.png!web

可以看出此算法，一次循环搞定，所以时间复杂度O(n), 由于在原数组上操作，所以空间复杂度O(1)。

测试用例

功能测试：全是奇数、全是偶数、奇偶数存在但已排好序/未排好序。
特殊输入测试： null对象、数组元素为0、有负数情况。

编码

Java实现

private int[] v2_0_solution(int[] nums) {
     if (nums == null || nums.length <= 1) {
         return nums;
     }
     int st = 0;
     int end = nums.length - 1;

     while (st < end) {
         // find even number
         if (isOdd(nums[st])) {
             st++;// 奇数，索引右移
         } else if (!isOdd(nums[end])) {
             end--;// 偶数，索引左移
         } else {
             // 奇偶数互换
             int temp = nums[st];
             nums[st] = nums[end];
             nums[end] = temp;
             st++;
             end--;
         }
     }
     return nums;
 }

 // 与1做按位运算，不为0就是奇数，反之为偶数
 private boolean isOdd(int n) {
     return (n & 1) != 0;
 }

C++实现

//判断是否为奇数
bool IsOdd(int data)
{
    return data & 1 != 0;
}

//奇偶互换
void OddEvenSort(int *pData, unsigned int length)
{
    if (pData == NULL || length == 0)
        return;

    int *pBegin = pData;
    int *pEnd = pData + length - 1;

    while (pBegin < pEnd)
    {
        //如果pBegin指针指向的是奇数，正常，向右移
        if (IsOdd(*pBegin))  
        {
            pBegin++;
        }
        //如果pEnd指针指向的是偶数，正常，向左移
        else if (!IsOdd(*pEnd))
        {
            pEnd--;
        }
        else
        {
            //否则都不正常，交换
            //swap是STL库函数，声明为void swap(int& a, int& b);
            swap(*pBegin, *pEnd);
        }
    }
}

有经验的面试官又来了，题目难度需要升下级，:no_mouth:~

题目：接上题，面试官会继续要求改造此函数使其能够保证原先输入数组的奇数内部顺序以及偶数内部顺序，即如果输入为{2，1，3，6，4，7，8，5}，则输出应为{1，3，7，5，2，6，4，8}，奇数之间的相互顺序和偶数之间的相互顺序不得被改变。

解题思路

要想保证原数组内元素的顺序，可使用O(n)的temp数组空间按顺序缓存偶数，奇数依次放到原数组前面，最后将temp中偶数取出放在原数组后面。

来画图理解下~

测试用例

同上一题。这里就省略了。

编码

Java实现

private int[] v2_1_solution(int[] nums) {
     if (nums == null || nums.length <= 1) {
         return nums;
     }

     int st = 0;
     int evenCount = 0;
     // 申请的内存空间temp
     int[] temp = new int[nums.length];
     for (int i = 0; i < nums.length; i++) {
         if (!isOdd(nums[i])) {
             evenCount += 1;
             temp[evenCount - 1] = nums[i];
         } else {
             if (st < i) {
                 // 将奇数依次放在原数组前面
                 nums[st] = nums[i];
             }
             st++;
         }
     }
     // 将temp中偶数取出放在原数组后面
     if (evenCount > 0) {
         for (int i = st; i < nums.length; i++) {
             nums[i] = temp[i - st];
         }
     }
     return nums;
 }

C++实现

// todo

题目3：利用数组实现一个简易版的List

题目：请利用数组实现一个简易版的List，需要实现poll和push两个接口，前者为移除并获得队头元素，后者为向队尾添加一个元素，并要求能够自动扩容。

解题思路

此题关键是在怎么实现poll和push两个接口上。

poll（获取并移动对头元素）：移动数组并置空最后一个元素。
push（添加元素）：按索引添加到数组中，size大于数组长度就先扩容。

测试用例

功能测试：添加、移除元素
特殊测试：添加大量数据（测试扩容）、移除所有元素、null数据

编码

Java实现

private static final int DEFAULT_CAPACITY = 16;
private Object[] elementData;
// 实际存储的元素数量
//  The size of the List (the number of elements it contains).
private int size;

public CustomList() {
    elementData = new Object[DEFAULT_CAPACITY];
}

public CustomList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = new Object[DEFAULT_CAPACITY];
    } else {
        throw new IllegalArgumentException("Illegal Capacity: " +
                initialCapacity);
    }
}

/**
 * 移除并获得队头元素
 *
 * @return
 */
public Object poll() {
    if (size <= 0){
        throw new IndexOutOfBoundsException(" list is empty .");
        }
    // 获取队头第一个元素
    Object oldValue = elementData[0];

    // 数组元素左移一位 & 最后一位元素置空
    System.arraycopy(elementData, 1, elementData, 0, size - 1);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

/**
 * 向队尾添加一个元素
 *
 * @param item
 */
public void push(Object item) {
    ensureExplicitCapacity(size + 1);  // Increments modCount!!
    elementData[size++] = item;
}

@Override
public String toString() {
    return Arrays.toString(elementData);
}

// 这里扩容参考的ArrayList，具体实现请点击文末源代码链接前往查看。
private void ensureExplicitCapacity(int minCapacity) {
    // 期望的最小容量大于现有数组的长度，则进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

C++实现

// todo

题目4：数组中出现次数超过一半的数

题目：一个整数数组中有一个数字出现的次数超过了数组长度的一半，请找出这个数字。如输入一个长度为9的数组{1，2，3，2，2，2，5，4，2}，由于2出现了5次，超过了数组长度的一半，因此应输出2。

解题思路

如果我们将数组排序，那么排序后位于数组中间的的数字一定是那个出现次数超过数组长度一半的数字。

测试用例

存在（或者不存在）次数超过数组长度一半的数。
特殊用例： null、空元素、只有一个数。
编码
Java实现

// todo

C++ 实现

todo

有经验的面试官又来了，题目难度需要升下级，:no_mouth:~

题目：这个题目有很多变种，其中一个引申为输入的是一个对象数组，该对象无法比较大小，只能利用equals()方法比较是否相等，此时该如何解（若要用到O(n)的辅助空间，能否避免？）。

解题思路

数组中有一个元素出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有元素出现次数的和还要多。

因此我们可以考虑在遍历数组的时候保存两个值：一个是数组中的一个元素，一个是次数。当我们遍历到下一个元素的时候，如果下一个原色和我们之前保存的元素相等（equals返回true），则次数加1；如果下一个元素和我们之前保存的不相等，则次数减1。如果次数为0，我们需要保存下一个元素，并把次数设为1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时对应的那个元素。

此思路：空间复杂度O(1),时间复杂度O(n)。

编码

Java实现

 private Object v4_1_solution(Object[] objects) {
     if (objects == null || objects.length < 1) {
         throw new IllegalArgumentException(" array is empty. ");
     }
     // 假设第一个元素就是超过长度一半的那个
     Object result = objects[0];
     int times = 1;

     // 从第二个元素开始遍历
     for (int i = 1; i < objects.length; i++) {
         if (times == 0) {
             // 重新设置
             result = objects[i];
             times = 1;
         } else if (objects[i].equals(result)) {
             times++;
         } else {
             times--;
         }
     }
     if (checkMoreThanHalf(objects, result)) {
         return result;
     } else {
         throw new IllegalArgumentException(" array is invalid ");
     }
 }

 private boolean checkMoreThanHalf(Object[] objects, Object obj) {
     int times = 0;
     for (int i = 0; i < objects.length; i++) {
         if (objects[i].equals(obj)) {
             times++;
         }
     }
     return times * 2 > objects.length;
 }

// 测试类，重点在于实现了equals和hashcode方法。
 private static class TestObject {
     String unique;

     public TestObject(String unique) {
         this.unique = unique;
     }

     @Override
     public boolean equals(Object o) {
         if (this == o) return true;
         if (o == null || getClass() != o.getClass()) return false;

         TestObject that = (TestObject) o;

         return unique != null ? unique.equals(that.unique) : that.unique == null;
     }

     @Override
     public int hashCode() {
         return unique != null ? unique.hashCode() : 0;
     }

     @Override
     public String toString() {
         return "TestObject{" +
                 "unique='" + unique + '\'' +
                 '}';
     }
 }

C++实现

todo

学习心得&解题套路

细心的读者可能发现了，文中解题过程大致是这样的：分析思路->测试用例->编码->调试并通过测试。

关于解题思路（详见剑指offer）
- 画图让抽象问题形象化
- 举例让抽象问题具体化
- 分解让复杂问题简单化
学习资源(信息大爆炸，好资源很重要)
- 各种数据结构及算法书籍：大话数据结构、剑指offer、算法导论等等。
- 在线编程： LeetCode 、牛客网、七月在线

总结

你可能会问怎样才能很好的掌握算法编程呢？我的答案是： 有事没事刷道题吧。勤加练习，终成大神。 文中所有代码均编译运行并通过测试用例检查。代码获取请前往： https://github.com/yangjiantao/DSAA 。由于作者水平有限，文中错误之处在所难免，敬请读者指正。

编程能力就像任何其他技能一样，也是一个可以通过刻意练习大大提高的。 — 摘抄至LeetCode。

题目1：翻转句子

解题思路

测试用例

编码实现

解题思路

测试用例

编码实现

题目2：调整数组中元素顺序

解题思路

测试用例

编码

解题思路

测试用例

编码

题目3：利用数组实现一个简易版的List

解题思路

测试用例

编码

题目4：数组中出现次数超过一半的数

解题思路

测试用例

编码

解题思路

编码

学习心得&解题套路

总结

Recommend

Improving data safety on Linux systems using ZFS and BTRFS

Shippable and Packet Collaborate on Native Arm CI/CD

悦读：The Tail At Scale

Backblaze Durability is 99.999999999% — And Why It Doesn’t Matter

Reproducing Popular iOS Controls Part 2: Robinhood

Microsoft is making the Windows command line a lot better

Cloud Spanner adds import/export functionality to ease data movement

全球的IPv6部署急剧增加，但中国几乎没有一个地方部署？

5G标准确立！是中国主导吗？这才是真相

繁星纪念 - 利用互联网纪念逝去的人 - NEXT

About Joyk