高频面试系列

接雨水、旋转图像、颠倒字符串中的单词、缺失的第一个正数、螺旋矩阵、比较版本号、Pow(x, n)、数组中的逆序对

42.接雨水

备忘录优化

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if(n==0) return 0;
        int res = 0;
        //数组充当备忘录
        vector<int> l_max(n);
        vector<int> r_max(n);

        // base case
        l_max[0] = height[0];
        r_max[n-1] = height[n-1];

        //从左往右计算 l_max
        for(int i=1;i<n;i++){
            l_max[i] = max(l_max[i-1], height[i]);
        }
        //从右往左计算 r_max
        for(int i=n-2;i>=0;i--){
            r_max[i] = max(r_max[i+1], height[i]);
        }

        //计算答案
        for(int i=1;i<n-1;i++){
            res += min(l_max[i], r_max[i])-height[i];
        }
        return res;
    }   
};
//时间复杂度：O(n)
//空间复杂度：O(n)

func trap(height []int) int {
    n := len(height)
    if n == 0 {
        return 0
    }
    res := 0
    //数组充当备忘录
    l_max := make([]int, n)
    r_max := make([]int, n)

    // base case
    l_max[0] = height[0]
    r_max[n-1] = height[n-1]

    //从左往右计算 l_max
    for i := 1; i < n; i++ {
        l_max[i] = max(l_max[i-1], height[i])
    }
    //从右往左计算 r_max
    for i := n - 2; i >= 0; i-- {
        r_max[i] = max(r_max[i+1], height[i])
    }

    //计算答案
    for i := 1; i < n-1; i++ {
        res += min(l_max[i], r_max[i]) - height[i]
    }
    return res
}
//时间复杂度：O(n)
//空间复杂度：O(n)

双指针解法

class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();
        if(n==0) return 0;

        int l_max = height[0];
        int r_max = height[n-1];

        int left=0;
        int right=n-1;
        int res=0;
        while(left<=right){
            //l_max 是 height[0...left] 中的最高的柱子高度
            l_max = max(l_max, height[left]);
            //r_max 是 height[right...n-1]中的最高的柱子高度
            r_max = max(r_max, height[right]);

            //res += min(l_max, r_max)-height[i];
            if(l_max<r_max){
                res += l_max-height[left];
                left++;
            }else{
                res += r_max-height[right];
                right--;
            }
        }
        return res;
    }   
};
//时间复杂度：O(n)
//空间复杂度：O(1)

func trap(height []int) int {
    n := len(height)
    if n == 0 {
        return 0
    }

    l_max := height[0]
    r_max := height[n-1]

    left := 0
    right := n - 1
    res := 0
    for left <= right {
        //l_max 是 height[0...left] 中的最高的柱子高度
        l_max = max(l_max, height[left])
        //r_max 是 height[right...n-1]中的最高的柱子高度
        r_max = max(r_max, height[right])

        //res += min(l_max, r_max)-height[i];
        if l_max < r_max {
            res += l_max - height[left]
            left++
        } else {
            res += r_max - height[right]
            right--
        }
    }
    return res
}
//时间复杂度：O(n)
//空间复杂度：O(1)

48.旋转图像

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        //思路：先水平翻转，再沿主对角线翻转
        int n=matrix.size();

        for(int i=0;i<n/2;i++){
            for(int j=0;j<n;j++){
                swap(matrix[i][j], matrix[n-i-1][j]);
            }
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};

func rotate(matrix [][]int) {
    //思路：先水平翻转，再沿主对角线翻转
    n := len(matrix)

    for i := 0; i < n/2; i++ {
        for j := 0; j < n; j++ {
            matrix[i][j], matrix[n-i-1][j] = matrix[n-i-1][j], matrix[i][j]
        }
    }

    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        }
    }
}

151.颠倒字符串中的单词

class Solution {
public:
    string reverseWords(string s) {
        int i=s.size()-1;
        string res;
        while(i>=0){      //从后往前遍历s
            int count=0;   //记录每个单词的长度  
            while(i>=0 && s[i]==' ') i--;   //空格跳过
            while(i>=0 && s[i]!=' '){       //非空格，则count++
                i--;
                count++;
            }
            if(count) res += s.substr(i+1, count) + " ";  
        }
        return res.substr(0, res.size()-1); //目的是去掉尾随空格
    }
};

func reverseWords(s string) string {
    i := len(s) - 1
    res := ""
    for i >= 0 {      //从后往前遍历s
        count := 0   //记录每个单词的长度
        for i >= 0 && s[i] == ' ' {   //空格跳过
            i--
        }
        for i >= 0 && s[i] != ' ' {   //非空格，则count++
            i--
            count++
        }
        if count > 0 {
            res += s[i+1:i+1+count] + " "
        }
    }
    if len(res) > 0 {
        return res[:len(res)-1]  //目的是去掉尾随空格
    }
    return res
}

41.缺失的第一个正数

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n=nums.size();
        for(int i=0;i<n;i++){
            while(nums[i]>0 && nums[i]<=n && nums[nums[i]-1]!=nums[i]){
                swap(nums[i], nums[nums[i]-1]);
            }
        }
        for(int i=0;i<n;i++){
            if(nums[i]!=i+1){
                return i+1;
            }
        }
        return n+1;
    }
};

func firstMissingPositive(nums []int) int {
    n := len(nums)
    for i := 0; i < n; i++ {
        for nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i] {
            nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
        }
    }
    for i := 0; i < n; i++ {
        if nums[i] != i+1 {
            return i + 1
        }
    }
    return n + 1
}

54.螺旋矩阵

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        vector<int> res;
        if(m==0 || n==0) return res;

        //定义左右上下边界的位置
        int left = 0;
        int right = n-1;
        int up = 0;
        int down = m-1;
        
        while(true){
            
            //从左往右走
            for(int i=left;i<=right;i++) res.push_back(matrix[up][i]);
            if(++up > down) break; //更新上边界
            
            //从上往下走
            for(int i=up;i<=down;i++) res.push_back(matrix[i][right]);
            if(--right<left) break; //更新右边界

            //从右往左走
            for(int i=right;i>=left;i--) res.push_back(matrix[down][i]);
            if(--down<up) break; //更新下边界

            //从下往上走
            for(int i=down;i>=up;i--) res.push_back(matrix[i][left]);
            if(++left>right) break; //更新左边界
        }
        return res;
    }
};

func spiralOrder(matrix [][]int) []int {
    m := len(matrix)
    n := len(matrix[0])
    res := []int{}
    if m == 0 || n == 0 {
        return res
    }

    //定义左右上下边界的位置
    left := 0
    right := n - 1
    up := 0
    down := m - 1

    for {
        //从左往右走
        for i := left; i <= right; i++ {
            res = append(res, matrix[up][i])
        }
        up++
        if up > down {
            break
        } //更新上边界

        //从上往下走
        for i := up; i <= down; i++ {
            res = append(res, matrix[i][right])
        }
        right--
        if right < left {
            break
        } //更新右边界

        //从右往左走
        for i := right; i >= left; i-- {
            res = append(res, matrix[down][i])
        }
        down--
        if down < up {
            break
        } //更新下边界

        //从下往上走
        for i := down; i >= up; i-- {
            res = append(res, matrix[i][left])
        }
        left++
        if left > right {
            break
        } //更新左边界
    }
    return res
}

165.比较版本号

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int m=version1.size();
        int n=version2.size();
        int i=0, j=0;
        while(i<m || j<n){
            long num1=0, num2=0;
            // 将一段连续的字符串转换成数字, num = num*10 是为了去前导 0
            while(i<m && version1[i]!='.') num1=num1*10 + version1[i++]-'0';
            while(j<n && version2[j]!='.') num2=num2*10 + version2[j++]-'0';
            if(num1>num2) return 1;
            else if(num1<num2) return -1;
            i++;
            j++;
        }
        return 0;
    }
};

func compareVersion(version1 string, version2 string) int {
    m := len(version1)
    n := len(version2)
    i, j := 0, 0
    for i < m || j < n {
        num1, num2 := 0, 0
        // 将一段连续的字符串转换成数字, num = num*10 是为了去前导 0
        for i < m && version1[i] != '.' {
            num1 = num1*10 + int(version1[i]-'0')
            i++
        }
        for j < n && version2[j] != '.' {
            num2 = num2*10 + int(version2[j]-'0')
            j++
        }
        if num1 > num2 {
            return 1
        } else if num1 < num2 {
            return -1
        }
        i++
        j++
    }
    return 0
}

50.Pow(x, n)

class Solution {
public:
    double myPow(double x, int n) {
        //快速幂+递归
        long long N=n;
        return N>=0 ? helper(x, N) : 1.0/helper(x, -N);
    }
    double helper(double x, long long N){
        if(N==0){
            return 1.0;
        }
        double y=helper(x, N/2);
        return N%2 == 0 ? y*y : y*y*x;
    }
};

func myPow(x float64, n int) float64 {
    //快速幂+递归
    N := int64(n)
    if N >= 0 {
        return helper(x, N)
    }
    return 1.0 / helper(x, -N)
}

func helper(x float64, N int64) float64 {
    if N == 0 {
        return 1.0
    }
    y := helper(x, N/2)
    if N%2 == 0 {
        return y * y
    }
    return y * y * x
}

剑指offer51.数组中的逆序对

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        int n=nums.size();
        vector<int> temp(n);
        return mergeSort(nums, temp, 0, n-1);
    }

    //归并排序
    int mergeSort(vector<int>& nums, vector<int>& temp, int low, int high){
        if(low>=high) return 0;
        int mid=low+(high-low)/2;
        int res = mergeSort(nums, temp, low, mid) + mergeSort(nums, temp, mid+1, high);

        int i=low;
        int j=mid+1;
        for(int k=low;k<=high;k++){
            temp[k]=nums[k];
        }

        for(int k=low;k<=high;k++){
            if(i==mid+1){
                nums[k]=temp[j++];
            }else if(j==high+1){
                nums[k]=temp[i++];
            }else if(temp[i]<=temp[j]){
                nums[k]=temp[i++];
            }else{
                nums[k]=temp[j++];
                res += mid-i+1;
            }
        }
        return res;
    }
};

func reversePairs(nums []int) int {
    n := len(nums)
    temp := make([]int, n)
    return mergeSort(nums, temp, 0, n-1)
}

//归并排序
func mergeSort(nums []int, temp []int, low int, high int) int {
    if low >= high {
        return 0
    }
    mid := low + (high-low)/2
    res := mergeSort(nums, temp, low, mid) + mergeSort(nums, temp, mid+1, high)

    i := low
    j := mid + 1
    for k := low; k <= high; k++ {
        temp[k] = nums[k]
    }

    for k := low; k <= high; k++ {
        if i == mid+1 {
            nums[k] = temp[j]
            j++
        } else if j == high+1 {
            nums[k] = temp[i]
            i++
        } else if temp[i] <= temp[j] {
            nums[k] = temp[i]
            i++
        } else {
            nums[k] = temp[j]
            j++
            res += mid - i + 1
        }
    }
    return res
}

386.字典排序

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> res(n);
        int number=1;
        for(int i=0;i<n;i++){
            res[i]=number;
            if(number*10<=n){
                number*=10;
            }else{
                while(number%10==9 || number+1>n){
                    number/=10;
                }
                number++;
            }
        }
        return res;
    }
};

func lexicalOrder(n int) []int {
    res := make([]int, n)
    number := 1
    for i := 0; i < n; i++ {
        res[i] = number
        if number*10 <= n {
            number *= 10
        } else {
            for number%10 == 9 || number+1 > n {
                number /= 10
            }
            number++
        }
    }
    return res
}

440.字典序的第k小数字

class Solution {
public:
    int findKthNumber(int n, int k) {
        int cur=1;
        --k; //初始化为 cur=1，k需要自减1
        while(k>0){
            long long step=0, first=cur, last=cur+1;
            //统计这颗子树下所有节点数（step）
            while(first<=n){
                 //不能超过n的值，并不是所有节点都有十个子节点
                step += min((long long)n+1, last)-first;  
                first *= 10;
                last *= 10;
            }
            if(step<=k){ //不在子树中
                ++cur;
                k -= step;
            }else{ //在子树中，进入子树
                cur *= 10;
                --k;
            }
        }
        return cur;
    }
};

func findKthNumber(n int, k int) int {
    cur := 1
    k-- //初始化为 cur=1，k需要自减1
    for k > 0 {
        step := int64(0)
        first := int64(cur)
        last := int64(cur + 1)
        //统计这颗子树下所有节点数（step）
        for first <= int64(n) {
            //不能超过n的值，并不是所有节点都有十个子节点
            step += min(int64(n)+1, last) - first
            first *= 10
            last *= 10
        }
        if step <= int64(k) { //不在子树中
            cur++
            k -= int(step)
        } else { //在子树中，进入子树
            cur *= 10
            k--
        }
    }
    return cur
}

43.字符串相乘

class Solution {
public:
    string multiply(string num1, string num2) {
        if(num1=="0" || num2=="0") return "0";

        int m=num1.size();
        int n=num2.size();
        vector<int> res(m+n);

        for(int i=m-1;i>=0;i--){
            int x = num1[i]-'0';
            for(int j=n-1;j>=0;j--){
                int y = num2[j]-'0';
                res[i+j+1] += x * y;
            }
        }
        //进位
        for(int i=m+n-1;i>0;i--){
            res[i-1] += res[i]/10;
            res[i] = res[i]%10;
        }
        
        //将数组res转换成字符串
        //最高位为0，则索引从1开始，否则从0开始
        int index = res[0] == 0 ? 1 : 0;
        string s;
        while(index < m+n){
            s.push_back(res[index]+'0');
            index++;
        }

        return s;
    }
};

func multiply(num1 string, num2 string) string {
    if num1 == "0" || num2 == "0" {
        return "0"
    }

    m := len(num1)
    n := len(num2)
    res := make([]int, m+n)

    for i := m - 1; i >= 0; i-- {
        x := int(num1[i] - '0')
        for j := n - 1; j >= 0; j-- {
            y := int(num2[j] - '0')
            res[i+j+1] += x * y
        }
    }
    //进位
    for i := m + n - 1; i > 0; i-- {
        res[i-1] += res[i] / 10
        res[i] = res[i] % 10
    }

    //将数组res转换成字符串
    //最高位为0，则索引从1开始，否则从0开始
    index := 0
    if res[0] == 0 {
        index = 1
    }
    s := ""
    for index < m+n {
        s += string(res[index] + '0')
        index++
    }

    return s
}

7. 整数反转

class Solution {
public:
    int reverse(int x) {
        int res = 0;
        while(x){
            if(res>INT_MAX/10 || res<INT_MIN/10){
                return 0;
            }
            res = res*10 + x%10;
            x = x/10;
        }
        return res;
    }
};

func reverse(x int) int {
    res := 0
    for x != 0 {
        if res > math.MaxInt32/10 || res < math.MinInt32/10 {
            return 0
        }
        res = res*10 + x%10
        x = x / 10
    }
    return res
}