题

输入一个整型数组（正、负数均有），数组中一个或连续的多个整数组成一个子数组，求所有子数组的最大值。
要求时间复杂度为 O(n)
例：输入数组为{1, -2, 3, 10, -4, 7, 2, -5}, 和最大的子数组为{3, 10, -4, 7, 2}, 因此输出为该子数组的和为18

分析

最直接的解法：枚举所有子数组并求它们的和。长为n的数组，共有 n*(n + 1)/2 个子数组。计算出所有子数组之和，最快需要 O(n^2)，显然不符合要求

思路一 举例分析数组规律

通常，举例能够具象化算法，让你能够更直观的看到问题，解算法题时，碰到不好解决的问题，可以尝试举例分析问题规律，降低问题难度

从头到尾逐个累加例中每个数字。初始化和为0：

1. 加1 和为1
2. 加-2 和为-1
3. 加3 上一步的累积和为负数，那么我们不用考虑之前的累积和，从第一个数字开始的子数组也不用考虑 —— 从第三个数开始重新累加 和为3
4. 加10 和为13
5. 加-4 和为9 —— 因为-4为负，加上-4后会是累加和变小，所以可以把上一步的13当做暂时发现的最大子和值
6. 加7 和为16，比之前的最大值13大，更新Result为16
7. 加2 和为18，更新Result为18
8. 加-5 和为13

依据上述步骤，可以确定最大子和是18

思路二 应用动态规划

应用递归思想

1
2

f(i) = pData[i] if i == 0 or f(i - 1) <= 0
      else f(i - 1) + pData[i]

当以第i-1个数字结尾的子数组中所有数字之和小于0时，如果把这个负数与i个数累加，得到的结果比第i个数本身还要小，所以这种清空下以第i个数字结尾的子数组就是第i个数字本身；
如果以第i-1个数字结尾子数组中所有数字的和大于0，与第i个数字累加就得到以第i个数字结尾的子数组中所有数字的和

用递归的方式分析动态规划问题，最终都是使用循环解决

SourceCode – C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

bool g_invalideINput = false;

int FindGreatestSumOfSubArray(int* pData, int nLength){
  if(pData == NULL || nLength <= 0){
    g_invalideINput = true;
    return 0;
  }

  g_invalideINput = false;

  int nCurSum = 0;
  int nGreatestSum = 0x80000000;
  for(int i = 0; i < nLength; ++i){
    if(nCurSum <= 0) nCurSum = pData[i];
    else nCurSum += pData[i];

    if(nCurSum > nGreatestSum)
      nGreatestSum = nCurSum;
  }
  return nGreatestSum;  
}

题

输入n个整数，找出其中最小的k个数
例：输入4、5、1、6、2、7、3、8
则最小的3个数是1、2、3

分析

首先想到最直观的解法是：将数组排序（正序），然后前面k个数字就是最小的k个数
时间复杂度就完全取决于所采用的排序算法，并且不借助辅助空间的话，排序也会对原数组的内容造成影响

思路一

递归地进行如下操作：
基于数组的第k个数来调整，比k小的数都位于数组左边，比k大的数字都位于数组右边——这样就可以使得数组前的k个数字就是最小的k个数字

思路二

创建一个大小为k的数据容器来存储最小的k个数字，接下来每次从输入的n个整数中读入一个数。如果容器中已有的数字少于k个，则直接放入；若容器中已满，则将容器中最大值与读入数字进行比较，保留更小的数在容器中

当容器满时，我们需要做3件事：

1. 找到max
2. 可能需要删除这个max
3. 可能插入一个新数字

如果用一个二叉树来当容器，那么我们能在O(logk)时间内完成上述3步

我们可以选用不同的二叉树来实现。鉴于每次都要找到Max，可以使用最大堆

在最大堆中，根节点总是大于它的任意结点——可以在O(1)时间内找到Max（即为根节点）

亦可以用红黑树来实现。

红黑树通过把结点分为红、黑两种颜色并根据一些规则来保证树在一定程度上是平衡的，从而确保在红黑树中查找、删除、插入操作都只需要O(logk)时间
在STL中 set与 meltiset都是基于红黑树实现的，可以直接利用

SourceCode – C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

typedef multiset<int, greater<int>> intSet;
typedef multiset<int, greater<int>>::iterator setIterator;
void GetLeastNumber(const std::vector<int>& data, intSet& leastNumvers, int k){  
    leastNumvers.clear();

    if(k < 1 || data.size() < k){
      return;
    }

    std::vector<int>::const_iterator iter = data.begin();
    for(; iter != data.end(); ++iter){
      if(leastNumvers.size() < k){
        leastNumvers.insert(*iter);
      }
      else{
        setIterator iterGreatest = leastNumvers.begin();

        if( *iter < *(leastNumvers.begin())){
          leastNumvers.erase(iterGreatest);
          leastNumvers.insert(*iter);
        }
      }
    }
}

是什么

atoi 把字符串转换成整型数
itoa 把一整数转换为字符串

如何处理

1. 如果是负数，先转为正数

2. 从各位开始变为字符，直到最高位，最后反转

   SourceCode – C语言

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

   char *my_itoa(int n){ int i = 0,isNegative = 0; static char s[100]; //必须为static变量，或者是全局变量 if((isNegative = n) < 0){ //先将负数转为正数 n = -n; } do { //从各位开始变为字符，直到最高位，最后反转 s[i++] = n%10 + '0'; n = n/10; } while(n > 0); if(isNegative < 0) { //如果是负数，补上负号 s[i++] = '-'; } s[i] = '\0'; //最后加上字符串结束符 return reverse(s); }

面试中比较偏重基础的可能会考察到这一类的具体实现

是什么

atoi：将字符串转换为数字

如何处理

字符如何隐式的转换为数字：
一个char型的字符减去‘0’就会隐式的转换为数字，一个数字加上‘0’则会隐式的转换为字符，明白了这一点，就可以尝试着写atoi了

SourceCode – C语言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <stdio.h>
#include <assert.h>
#include <ctype.h>

long long int my_atoi(const char *c){
    long long int value = 0;
    int sign = 1;
    if( *c == '+' || *c == '-' ){ //符号判断
        if( *c == '-' ) sign = -1; //记录负数
        c++;
    }
    while (isdigit(*c)){ //处理所有的数字，非数字字符会被过滤掉
        value *= 10; //已经处理过的位左移（* 10实现）
        value += (int) (*c-'0'); //加上心的位，通过-'0'实现
        c++;
    }
    return (value * sign);
}

int main(void){
    assert(5 == my_atoi("5"));
    assert(-2 == my_atoi("-2"));
    assert(-1098273980709871235 == my_atoi("-1098273980709871235"));
}

如何连续最长数字串呢？本篇介绍一种C语言实现：

题

在字符串中找出连续最长的数字串，返回最长长度，并把这个最长数字串赋值给其中一个函数参数outputStr所指内存

例

“abcd12345ed125ss123456789”的首地址传给intputStr后，函数将返回9，outputStr所指的值为123456789

析

我们可以对字符串中的每个数字串计数，然后比较得到最大的。这就是我们所要求的最大连续数字串。需要记住这个最大串的开始位置，还有最大串的长度。

1. 遍历字符串
2. 如果遇到数字，则将计数器+1；否则，我们应该统计刚才的数字串的长度和最大长度比较，如果大于最大长度，则重新设置最大长度，并记住数字串开始位置
3. 返回我们所需要的最大长度和数字串

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <iostream>
#include <cstring>

void find_max_number(char string[],int length,int &count, char *result ){
   /* max_length represents the max length of number string. */
   int max_length = 0;
   /* start means first character's position of number string */
   int start = 0;
   /* i represents iterator of string array */
   int i = 0;
   // here we scan the character array.
   for( ; i < length; i++ ){
      // if character belongs to 0~9 we add counter.
      // otherwise we set counter as 0.
      if( string[i] >= '0' && string[i] <= '9' ){
         count ++;
      } else{
         if( count > max_length ){
            max_length = count;
            start = i - count + 1;
         }
         count  = 0;
      }
   }
   // finally we should set max_length and the position again.
   if( count > max_length ){
      max_length = count;
      start = i - count;
   }
   // the last, we return counter and the string we need.
   count = max_length;
   memcpy( result, &string[start], count*sizeof(char) );
}

int main( int argc, char ** argv ){
   char string[] = "iabcd12345ed125ss123456789";
   char result[20] = {0};
   int count = 0;
   find_max_number( string, strlen(string), count, result );
   std::cout << count << " " << result << std::endl;
   return 0;
}

如何逆转链表呢？本篇介绍两种常见方法：

1. 遍历
2. 递归

遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

private static Node reverseHead(@Nonnull Node head) {
    Node pre = head;
    Node cur = head.nextNode;
    Node next = null;
    while(cur != null){
        next = cur.nextNode;
        cur.nextNode = pre;

        pre = cur;
        cur = next;
    }
    head.nextNode = null;
    head = pre;
    return head;
}

递归

1
2
3
4
5
6
7
8

private static Node reverseByRecur(Node current) {
    if (current == null || current.nextNode == null) return current;  
    Node nextNode = current.nextNode;  
    current.nextNode = null;  
    Node reverseRest = reverseByRecur(nextNode);  
    nextNode.nextNode = current;  
    return reverseRest;  
}

如何逆转链表呢？本篇介绍两种常见方法：

1. 遍历
2. 递归

遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

private static Node reverseHead(@Nonnull Node head) {
    Node pre = head;
    Node cur = head.nextNode;
    Node next = null;
    while(cur != null){
        next = cur.nextNode;
        cur.nextNode = pre;

        pre = cur;
        cur = next;
    }
    head.nextNode = null;
    head = pre;
    return head;
}

递归

1
2
3
4
5
6
7
8

private static Node reverseByRecur(Node current) {
    if (current == null || current.nextNode == null) return current;  
    Node nextNode = current.nextNode;  
    current.nextNode = null;  
    Node reverseRest = reverseByRecur(nextNode);  
    nextNode.nextNode = current;  
    return reverseRest;  
}

[面经] 逆转字符串（Java）

如何逆转字符串呢？本篇介绍几种常见方法：

1. 暴力解法
2. StringBuilder自带的reverse
3. reverse源码
4. 堆栈
5. 集合的reverse方法

暴力解法： 利用String.charAt()，倒序地访问 原String的各个char

1
2
3
4
5
6
7
8
9
10

public static String reverseIt(String source) {
    int i, len = source.length();
    StringBuilder dest = new StringBuilder(len);

    for (i = (len - 1); i >= 0; i--){ // key
        dest.append(source.charAt(i));
    }

    return dest.toString();
}

最不装的：直接利用自带reverse方法

1

new StringBuilder(hi).reverse().toString()

这显然没什么营养，我们看看StringBuilder的reverse()做了什么：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public static String reverse(String input){
    char[] in = input.toCharArray();
    int begin=0;
    int end=in.length-1;
    char temp;
    while(end>begin){ // key
        temp = in[begin];
        in[begin]=in[end];
        in[end] = temp;
        end--;
        begin++;
    }
    return new String(in);
}

当然，如果你想被嫌弃，也可以用堆栈：

1
2
3
4
5
6
7
8
9
10
11
12

public String reverseString(String s) {
    Stack<Character> stack = new Stack<Character>();
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        stack.push(s.charAt(i));
    }
    while (!stack.empty()) { // key
        sb.append(stack.pop());
    }
    return sb.toString();

}

或者想被喷出翔，装一下箱，拆一下箱：

1
2
3
4
5
6
7
8
9
10
11
12

public static void reverseStr(String input){
    char[] hello = input.toCharArray();
    List<Character> trial1 = new ArrayList<>();

    for (char c: hello)
        trial1.add(c);

    Collections.reverse(trial1); // key
    ListIterator li = trial1.listIterator();
    while (li.hasNext())
        System.out.print(li.next());
}

寻找优秀的Programmer

最近读的Stack Overflow CEO 博客集锦 《软件随想录 卷2》

结合其中的两篇：《寻找优秀的程序员》、《寻找优秀的程序员之实战指南》谈谈

因为作者所处位置，他写作两篇blog的角度其实是一个公司管理人员的角度，作为基础的从业程序员，也有一点的借鉴价值

优秀的程序员都在哪

作者的观点

1. 他们不会出现在招聘市场上
2. 平均职业生涯求职只有4次
3. 基本上想上哪工作，就上哪工作，不需要投许多简历
4. 招聘部门想找到合适的人，就如同在一堆干草中找到一根针

我们能找到他们吗？

1. 走出去（不要在大型求职论坛发布没有针对性的招聘广告）
2. 实习生（一些真正优秀的人，往往10左右就已经开始做自己爱的事情）
3. 建立自己的社区
4. 员工推荐：小心陷阱（真实生活中，我一般认为员工推荐是最不可靠的招聘方法之一—— 实际上Google基本只招收员工推荐的人）

实战指南

1. 私人办公室（这一条成本太高了）——作者的坚持这一点的理由是 “这能极大地提高效率”
2. 工作环境
3. 社交生活
   1. 如何被对待
   2. 谁是他们的同事
   3. 独立和自主
   4. 不搞政治
4. 干的是什么活？
   1. 让一流的人挑选他们自己的项目
   2. 使用非热门新技术
5. 能够认同公司吗？
6. 不在乎的一件事：工资（只要公平合理）

更多信息：Joel on software https://www.joelonsoftware.com

众所周知，基础数组的处理效率要比集合的处理效率高出指数倍（内存寻址优势，指哪打哪，直截了当）

在HashMap<K, V> 中K为Integer类型时，简单考虑，使用K作为数组下标可以使用基础数组替代HashMap，但这样处理的话会有一个问题，那就是K值较大时，直接使用数组会导致极大的内存空间浪费（很多数组内容都由null填充）——由此想到“稀疏数组”

SparseArray就是针对这一场景设计的
数组中仅仅保存有内容的空间 这样一来，就既可以利用数组高效的优势，又避免了内存空间的浪费。

取android.util.SparseArray源码中的put API如下：

/**
 * Adds a mapping from the specified key to the specified value,
 * replacing the previous mapping from the specified key if there
 * was one.
 */
public void put(int key, E value) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        mValues[i] = value;
    } else {
        i = ~i;

        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }

        if (mGarbage && mSize >= mKeys.length) {
            gc();

            // Search again because indices may have changed.
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }

        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

可以看到，在查找是否包含时使用了BinarySearch（二分搜索），在插入时又做了一次容量、size检查，有无用内存时手动gc，此gc为private函数，只是对内存进行了整理，无效内容置为null

查看DELETED定义：
private static final Object DELETED = new Object();
在删除时，只是将有效索引的内容至为DELETED，将mGarbage至为true，在下次有增/改操作时进行统一的容量整理；个人感觉这一api逻辑是经验设计，为的是避免连续删除时的频繁容量整理；

结论：

使用HashMap<Integer, V>时，用SparseArray替代，可以极大地提高性能