面试常考编程题

1. 给定一个数组，求最大的连续子序列和，O(n)时间与O(1)空间

2. 有一个坐标轴，上面有很多点，每个点有坐标，求长度为L的绳子最多能够覆盖几个点。

两个指针,start，end。
如果points[front]-points[rear]<=L，头start向前移动一步。
如果points[front]-points[rear]>L，尾巴end向前移动一步。
每个数最多遍历2遍，因此时间复杂度为O(n)。

int maxCover(int* a, int n, int l)
 5 {
 6     int maxCover = 1;
 7     int begin = 0;
 8     int end = 1;
 9     while(end < n)
10     {
11         if(a[end] - a[begin] > l)
12         {
13             maxCover = (end - begin) > maxCover?(end - begin):maxCover;
14             begin++;
15         }
16         else
17             end++;
18     }
19     return maxCover;
20 }

3. 求一个数组中第k 大的数

4. 最长公共序列

class LCS {
public:
    int findLCS(string A, int n, string B, int m) {
        // write code here
        int dp[n + 1][m + 1];
        for(int i = 0; i <= n; i++){
            dp[i][0] = 0;
        }
        for(int j = 0; j <= m; j++){
            dp[0][j] = 0;
        }
        
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (A[i] == B[j]){
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                }
                else{
                    dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
                }
            }
        }
        return dp[n][m];
    }
};

5. 最长递增子序列（Longest Increasing Subsequence）是指找到一个给定序列的最长子序列的长度，使得子序列中的所有元素单调递增。

例如：{ 3，5，7，1，2，8 } 的 LIS 是 { 3，5，7，8 }，长度为 4。

思路：建立一个大小与 nums 长度相等的数组dp，用于记录每个子序列的最长长度，即 dp[i] 表示nums 第 0 个到第 i 个元素中以 nums[i]为最大值的最长子序列长度（注意序列的最后一个值为 nums[i]）：

感觉底下的这个图不对。。

//  状态转移方程    dp[i] = max{dp[j]+1，dp[i]}, j<i && a[j]<a[i].

class Solution {
public://动态规划。时间复杂度为O(n^2)。
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n <= 1) return n;
        vector<int> dp(n, 1);                   // 初始化为1
        for(int i = 1; i < n; i++){             //dp[i]表示LIS的长度。nums[i]作为LIS的最后一个元素。
            for(int j = 0;j < i; j++)
            {
                if(nums[i] > nums[j])
                {                                 //满足递增
                    dp[i]=max(dp[i], dp[j] + 1);  //利用状态转移方程
                }
            }
        }
        int res=0;
        for(int i = 0;i < n; i++)
        {//求得最大的dp[i]
            res = max(res, dp[i]);
        }
        return res;
    }
};

使用一个数组h[],其中h[i]表示原数组以arr[i]结尾的最长递增子序列的长度。
从i=0到i=n-1过程重复进行n次，求得h=[1,1,2,1,3,2,4,3]。求h[i]的时候，需要考察那些比i小的j,如果arr[i]>arr[j],那么h[i]至少应为h[j]+1，这样对前边的遍历之后即可知道h[i]。
h的各个元素求得之后，遍历一遍求最大即可。

6. 连续子数组的最大和

附加问题：只用加法实现1+2+3+...+n，

（循环、判断语句也不用）

1、利用递归来代替循环结构；
2、利用&&与运算的特性来代替if结构。

int add(int n, int &sum)    
{    
    n && add(n-1, sum);    
    return (sum += n);    
}

7. 问题一：位运算实现加法

位的异或运算跟求'和'的结果一致：

异或 1^1=0 1^0=1 0^0=0

求和 1+1=0 1+0=1 0+0=0

位的与运算跟求'进位‘的结果一致：

位与 1&1=1 1&0=0 0&0=0

进位 1+1=1 1+0=0 0+0=0

于是我们决定用异或运算和与运算来表示加法。

int add(int a, int b) //递归形式  
{  
    if(b==0) //递归结束条件：如果右加数为0，即不再有进位了，则结束。  
        return a;  
    int s = a^b;  
    int c = (a&b)<<1; //进位左移1位，达到进位的目的。  
    return add(s, c); //再把'和'和'进位'相加。递归实现。  
}

8. 问题二：位运算实现减法

减法其实是用加法来实现的。在ALU中，当我求a-b，其实是求[a-b]补。因为有[a-b]补=[a]补 - [b]补= [a]补+[-b]补。所以我就要先求出-b。求一个数的负的操作是将其连符号位一起取反然后加1。

于是有办法做减法了：先把减数求负，然后做加法

int negtive(int i)  
{  
    return add(~i, 1);  
}  

int subtraction(int a, int b) //减法运算：利用求负操作和加法操作  
{  
    return add(a, negtive(b));  
}

9. 问题三：位运算实现乘法

乘法操作时即使用补码也要需要考虑符号位了，所以我要先把符号拿出来单独计算。为了方便，先引入两个工具函数，

int getsign(int i) //取一个数的符号，看是正还是负  
{  
    return (i>>31);  
}  
  
int bepositive(int i) //将一个数变为正数，如果本来就是正，则不变；如果是负，则变为相反数。注意对于-2147483648，求负会溢出。  
{  
    if(i>>31)  
        return negtive(i);  
    else  
        return i;  
}

循环加法替代乘法。a*b，就是把a累加b次。时间复杂度为O(N)。

int multiply(int a, int b)  
{  
    bool flag = true;  
    if(getsign(a) == getsign(b)) //积的符号判定  
        flag = false;  
  
    a = bepositive(a);//先把乘数和被乘数变为正数  
    b = bepositive(b);  
    int ans = 0;  
    while(b)  
    {  
        ans = add(ans, a);  
        b = subtraction(b, 1);  
    }  
  
    if(flag)  
        ans = negtive(ans);  
    return ans;  
}

思路二：

在二进制数上做乘法，如下图：

这一过程就是根据乘数的每一位为0或1时，将被乘数错位的加在积上。时间复杂度为O(logN)。

int multiply(int a, int b)  
{  
    bool flag = true;  
    if(getsign(a) == getsign(b)) //积的符号判定  
        flag = false;  
  
    a = bepositive(a);  
    b = bepositive(b);  
    int ans = 0;  
    while(b)  
    {  
        if(b&1)  
            ans = add(ans, a);  
        a = (a<<1); //把a错位加在积上  
        b = (b>>1); //从最低位开始依次判断b的每一位  
    }  
  
    if(flag)  
        ans = negtive(ans);  
    return ans;  
}

72. Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        // 初始化空字符串的情况
        for(int i = 1; i <= m; i++){
            dp[i][0] = i;
        }
        for(int i = 1; i <= n; i++){
            dp[0][i] = i;
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                // 增加操作：str1a变成str2后再加上b，得到str2b 需要的次数
                int insertion = dp[i][j-1] + 1;
                // 删除操作：str1a删除a后，再由str1变为str2b  需要的次数
                int deletion = dp[i-1][j] + 1;
                // 替换操作：先由str1变为str2，然后str1a的a替换为b，得到str2b  需要的次数（需要先判断是否相等，相等的话加0，不相等就加1）
                int replace = dp[i-1][j-1] + (word1.charAt(i - 1) == word2.charAt(j - 1) ? 0 : 1);
                // 三者中取最小的一个操作作为当前的dp
                dp[i][j] = Math.min(replace, Math.min(insertion, deletion));   
            }
        }
        return dp[m][n];
    }
}