@[toc]

合并两个有序的数组

题目描述

给出两个有序的整数数组A 和B ，请将数组B 合并到数组A 中，变成一个有序的数组
注意：
可以假设 A数组有足够的空间存放B 数组的元素， A和B 中初始的元素数目分别为 m和n

题解：

将A和B从最后一位开始比，然后存入A中（下标从第m+n-1倒着开始）。当有一个用完后，将另一个数组内的元素全部按顺序存入A中

代码：

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;//
        while (i >= 0 && j >= 0)
        {
            if (A[i] > B[j])
            {
                A[k] = A[i];
                i--;
                k--;
            }
            else
            {
                A[k] = B[j];
                j--;
                k--;
            }
        }
        while (i >= 0) A[k--] = A[i--];
        while (j >= 0) A[k--] = B[j--];
    }
};

反转字符串

题目描述

写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）

题解：

有reverse现成的翻转函数，直接套进去就可以
如果不用函数的话，也不难，倒着循环str，存入新的string内就行

代码：

class Solution {
public:
    /**
     * 反转字符串
     * @param str string字符串 
     * @return string字符串
     */
    string solve(string str) {
        // write code here
        reverse(str.begin(),str.end());
        return str;
    }
};

子数组的最大累加和问题

题目描述

给定一个数组arr，返回子数组的最大累加和
例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.
[要求]
时间复杂度为O(n)，空间复杂度为O(1)

题解：

我们从前向后推，如果当前值加上前一个值小于当前值，那我们就不加了，如果大于我就加上，这样维护的是每个位置所能累加的最大值，我们在这个过程中用maxx取最大情况

代码：

class Solution {
public:
    /**
     * max sum of the subarray
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxsumofSubarray(vector<int>& arr) {
        // write code here
        int maxx=arr[0];
        for(int i=1;i<arr.size();i++)
        {
            arr[i]=max(arr[i],arr[i]+arr[i-1]);
            maxx=max(arr[i],maxx);
        }
        return maxx;
    }
};

求平方根

题目描述

实现函数 int sqrt(int x).
计算并返回x的平方根

题解：

要求返回平方根，我们就找一个i，使得ii<=x&&(i+1)(i+1)>x
这样的i就是我们要找的答案
注意，x有可能为负数，当<=0时返回0

代码：

class Solution {
public:
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    int sqrt(int x) {
        // write code here
        if(x<=0)return 0;
        for(int i=1;i<=x;i++)
        {
            if(i*i<=x&&(i+1)*(i+1)>x)return i;
        }
    }
};

数组中只出现一次的数字

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

题解：

用map来记录每个数字出现几次，然后再循环一遍看哪个数字出现一次，赋给num1和num2就行
还有个高级做法是用位运算，异或^,这里就不细讲了

代码：

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        map<int,int>a;
        for(int i=0;i<data.size();i++)
        {
            a[data[i]]++;
        }
        int ans=0;
         for(int i=0;i<data.size();i++)
        {
            if(a[data[i]]==1)
            {
                if(ans==0)*num1=data[i];
                else *num2=data[i];
                ans++;

            }
        }
    }
};