数组中重复的数据

问题描述

给定一个整数数组 a,其中1 ≤ a[i] ≤ n (n为数组长度), 其中有些元素出现两次而其他元素出现一次。
找到所有出现两次的元素。

你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗?

示例:
输入:
[4,3,2,7,8,2,3,1]
输出:
[2,3]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-all-duplicates-in-an-array

思路

  • 将数组进行排序
  • 除最后一个元素以外,如果某一元素和其下一个元素相等,那么其肯定是重复元素,将其存入数组ret中。
    需要注意的一点是,需要跳过重复元素,即当nums[i]==nums[i+1]时,跳过num[i+1]这个元素

题解

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        int n=nums.size();
        sort(nums.begin(),nums.end());
        vector<int> ret;
        for(int i=0;i<n-1;i++){
            if(nums[i]==nums[i+1]){
                ret.push_back(nums[i]);
        }
            if(nums[i+1]==nums[i]){
                i++;
            }
        }
        return ret;
    }
};

除自身以外数组的乘积

问题描述:

给定长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
说明: 请不要使用除法,且在 O(n) 时间复杂度内完成此题。

进阶:
你可以在常数空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组不被视为额外空间。)

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/product-of-array-except-self

思路:

数组中除自身之外其他各元素的乘积等于自身左边元素的乘积,乘以自身右边的乘积。

题解:

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> ret(n);
        int ji=1;
        for(int i=0;i<n;i++){
            ret[i]=ji;
            ji=ji*nums[i];
        }
        ji=1;
        for(int i=n-1;i>=0;i--){
           ret[i]*=ji;
           ji*=nums[i];
        }
        return ret;
    }
};

最小路径和

问题描述

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

示例:
输入:

[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-path-sum

思路

基本思路是动态规划。

  • 从题目中描述可以看到,每次只能向下或者向右移动一步,所以状态转移方程应该为
    grid[i][j]+=min(grid[i][j-1],grid[i-1][j])
  • 本题要求的路径是从左上角到右下角,第一行,和第一列要单独考虑

题解

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size();
        if(m == 0)
            return 0;
        int n=grid[0].size();
        for(int i=1;i<n;i++){
            grid[0][i]+=grid[0][i-1];
        }
        for(int i=1;i<m;i++){
            grid[i][0]+=grid[i-1][0];
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                grid[i][j]+=min(grid[i][j-1],grid[i-1][j]);
            }
        }
        return grid[m-1][n-1];
    }
};

从中序与后序遍历序列构造二叉树

问题描述:

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如,给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树:

3

/ \
9 20

/  \

15 7

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal

思路:

题解:

旋转图像

问题描述:

给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。

说明:
你必须在原地旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵,使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

示例 2:
给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
原地旋转输入矩阵,使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/rotate-image

思路:

本题将图像顺时针旋转90°。
第一步:将二维矩阵转置(将矩阵的行与列交换)
第二部:将矩阵按行翻转

翻转函数:

头文件:#include <algorithm>
reverse(vec.begin(),vec.end());

题解:

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                int tmp=matrix[i][j];
                matrix[i][j]=matrix[j][i];
                matrix[j][i]=tmp;
            }
        }
       for(int i=0;i<n;i++){
            reverse(matrix[i].begin(),matrix[i].end());
        }
    }
};