数组中重复的数据

问题描述

给定一个整数数组 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
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());
        }
    }
};