31. 下一个排列

整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。

例如,arr = [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地,如果数组的所有排列根据其字典顺序从小到大排列在一个容器中,那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列,那么这个数组必须重排为字典序最小的排列(即,其元素按升序排列)。

例如,arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地,arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ,因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ,找出 nums 的下一个排列。

必须 原地 修改,只允许使用额外常数空间。

示例 1:

输入:nums = [1,2,3]
输出:[1,3,2]

示例 2:

输入:nums = [3,2,1]
输出:[1,2,3]

示例 3:

输入:nums = [1,1,5]
输出:[1,5,1]

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n=nums.size();
        int i;
        for(i=n-1;i>0;i--)
        {
            if(nums[i-1]<nums[i])   
            {
                break;
            }
        }
        if(i<=0)
        {
            reverse(nums.begin(),nums.end());
            return;
        }
        for(int k=n-1;k>=i;k--)
        {
            if(nums[k]>nums[i-1]) 
            {
                swap(nums[k], nums[i-1]);
                break;
            }
        }
        reverse(nums.begin()+i,nums.end());
    }
};
  • 倒序遍历数组找到num[i-1]<num[i]的数,
  • 倒序遍历数组找到num[k]>nums[i-1]的数
  • 交换num[i-1]和num[k]
  • 反转num[i-1]后的数

32. 最长有效括号

给你一个只包含 ‘(’ 和 ‘)’ 的字符串,找出最长有效(格式正确且连续)括号子串的长度。

示例 1:

输入:s = “(()”
输出:2
解释:最长有效括号子串是 “()”

示例 2:

输入:s = “)()())”
输出:4
解释:最长有效括号子串是 “()()”

示例 3:

输入:s = “”
输出:0

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> sk;
        sk.push(-1);
        int maxlen=0;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='(') sk.push(i);
            else
            {
                sk.pop();
                if(sk.empty())
                {
                    sk.push(i);
                }
                else
                {
                    maxlen=max(maxlen,i-sk.top());
                }
            }
        }
        return maxlen;
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]。

进阶:

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?

示例 1:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]

示例 2:

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]

示例 3:

输入:nums = [], target = 0
输出:[-1,-1]

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int l=0,r=nums.size()-1;
        if(nums.empty()) return{-1,-1};
        while(l<r)
        {
            int mid=l+(r-l)/2;
            if(nums[mid]>=target) r=mid;
            else l=mid+1;
        }
        if(nums[l]!=target) return {-1,-1};
        int start=l;
        l=0,r=nums.size()-1;
        while(l<r)
        {
            int mid=l+(r-l)/2+1;
            if(nums[mid]<=target) l=mid;
            else r=mid-1;
        }
        int end=l;
        return {start,end};
    }
};
  • 二分法

33. 搜索旋转排序数组

整数数组 nums 按升序排列,数组中的值 互不相同 。

在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1 。

示例 1:

输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4

示例 2:

输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1

示例 3:

输入:nums = [1], target = 0
输出:-1

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l=0,r=nums.size()-1;
        while(l<r)
        {
            int mid=l+(r-l)/2;
            if(nums[mid]<=nums.back())  r=mid;
            else l=mid+1;
        }
        int minIndex=r;
        if(target<=nums.back())
        {
            r=nums.size()-1;
        }
        else
        {
            l=0;
            r--;
        }
        while(l<r)
        {
            int mid=l+(r-l)/2;
            if(nums[mid]>=target) r=mid;
            else l=mid+1;
        }
        if(nums[l]!=target) return-1;
        return l;
        
    }
};
  • 用二分法先找最小值分段
  • 在判断target在那段,再用二分法找

46. 全排列

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1:

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2:

输入:nums = [0,1]
输出:[[0,1],[1,0]]

示例 3:

输入:nums = [1]
输出:[[1]]

class Solution {
public:

    vector<int>v;
    vector<vector<int>> ans;
    vector<bool> av;
    vector<vector<int>> permute(vector<int>& nums) {
        av=vector<bool>(nums.size(),false);
        dfs(nums,0);
        return ans;
    }
    void dfs(vector<int> &nums,int n)
    {

        if(n==nums.size())
        {
            ans.push_back(v);
            return;
        }

        for(int i=0;i<nums.size();i++)
        {
            if(av[i]==false)
            {
                v.push_back(nums[i]);
                av[i]=true;
                dfs(nums,n+1);
                v.pop_back();
                av[i]=false;
            }
        }
    }
};
  • dfs+回溯

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

示例 1:

输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。

示例 2:

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3:

输入: candidates = [2], target = 1
输出: []

class Solution {
public:
    vector<int> vec,judge;
    vector<vector<int>> ans;
    vector<vector<int>> combinationSum(vector<int>& c, int target) {
        dfs(c,target,0);
        return ans;
    }

    void dfs(vector<int>&nums,int target,int begin)
    {
        int sum=0;
        for(int i:vec)
        {
            sum+=i;
        }
        if(sum==target)
        {
            ans.push_back(vec);
            return;
        }
        else if(sum>target) return;

        for(int i=begin;i<nums.size();i++)
        {
            vec.push_back(nums[i]);
            dfs(nums,target,i);
            vec.pop_back();
        }
    }
};
  • 设置begin为去重

77. 组合

给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1:

输入:n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2:

输入:n = 1, k = 1
输出:[[1]]

class Solution {
public:
    vector<int> vec;
    vector<vector<int>> ans;
    vector<vector<int>> combine(int n, int k) {
        dfs(n,k,1);
        return ans;
    }

    void dfs(int n,int k,int index)
    {
        if(vec.size()==k)
        {
            ans.push_back(vec);
            return;
        }

        for(int i=index;i<=n;i++)
        {
            vec.push_back(i);
            dfs(n,k,i+1);
            vec.pop_back();
            
        }
    }
};

78. 子集

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1:

输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2:

输入:nums = [0]
输出:[[],[0]]

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> vec;
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums,0);
        return ans;
    }

    void dfs(vector<int> &nums,int n)
    {
        ans.push_back(vec);
        for(int i=n;i<nums.size();i++)
        {
            vec.push_back(nums[i]);
            dfs(nums,i+1);
            vec.pop_back();
        }
    }
};
  • 无需找结束条件

48. 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 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]]

class Solution {
public:
    void rotate(vector<vector<int>>& m) {
        int line=m.size();
        int col=m[0].size();

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

        for(int i=1;i<line;i++)
        {
            for(int j=0;j<i;j++)
            {
                swap(m[i][j],m[j][i]);
            }
        }
    }
};
  • 先按列反转数字,再以对角线交换数字

49. 字母异位词分组

给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母通常恰好只用一次。

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

示例 2:

输入: strs = [“”]
输出: [[“”]]

示例 3:

输入: strs = [“a”]
输出: [[“a”]]

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> um;
        vector<vector<string>> vec;
        for(auto &i:strs)
        {
            string s=i;
            sort(s.begin(),s.end());
            um[s].push_back(i);
        }
        for(auto ite=um.begin();ite!=um.end();ite++)
        {
            vec.push_back(ite->second);
        }
        return vec;
    }
};
  • 有相同字母的字符串排序完后完全相同
  • 则先排序,再入哈希表

56. 合并区间

以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。

示例 1:

输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入:intervals = [[1,4],[4,5]]
输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& a) {
        sort(a.begin(),a.end());
        vector<vector<int>> vec;
        vec.push_back(a[0]);
        int index=0;
        for(int i=1;i<a.size();i++)
        {
            if(a[i][0]<=vec[index][1] && a[i][1]>vec[index][1])     //正常情况,有交集但非子集 [1,4] [3,6]
            {
                vec[index][1]=a[i][1];
            }
            else if(a[i][0]<=vec[index][1] && a[i][1]<vec[index][1])  // 左为大区间   [1,4] [2,3]
            {
                continue;
            }
            else if((a[i][0]==vec[index][0] && a[i][1]==vec[index][1])) //完全相等    [1,4] [1,4]
            {
                continue;
            }
            else if((a[i][0]<=vec[index][1] && a[i][0]>vec[index][0]))     //右为大区间   [1,4] [0,8]
            {
                continue;
            }
            else            // 无交集  
            {
                vec.push_back(a[i]);
                index++;
            }
        }
        return vec;
    }
};
  • 先排序
  • 把第一个、区间加入数组,从第二个开始遍历,判断两个区间情况。
  • 两个区间共有五种情况,见注释
  • 二维数组排序时:
    • 按照每个数组第一个数字大小或ASCII大小排序,若相等则比较第二个

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

示例 1:

输入:m = 3, n = 7
输出:28

示例 2:

输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。

  1. 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向下

示例 3:

输入:m = 7, n = 3
输出:28

示例 4:

输入:m = 3, n = 3
输出:6

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(n));
        dp[0][0]=1;
        int i,j;
        for(i=1;i<m;i++)
        {
            dp[i][0]=1;
        }
        for(j=1;j<n;j++)
        {
            dp[0][j]=1;
        }
        for(int i=1;i<m;++i)
        {
            for(int j=1;j<n;++j)
            {
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[i-1][j-1];

    }
};
  • 动态规划

75. 颜色分类

class Solution {
public:
    void sortColors(vector<int>& nums) {
        unordered_map<int,int> um;
        um[0]=0;
        um[1]=0;
        um[2]=0;
        for(auto i:nums)
        {   
            um[i]++;
        }
        int i=0;
        while(um[0]--)
        {
            nums[i]=0;
            i++;
        }
        while(um[1]--)
        {
            nums[i]=1;
            i++;
        }
        while(um[2]--)
        {
            nums[i]=2;
            i++;
        }

    }
};
  • 哈希表 O(n)
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int l=0;
        int r=nums.size()-1;
        for(int i=0;i<=r;i++)
        {
            
            if(nums[i]==0)
            {
                swap(nums[i],nums[l]);
                l++;
            }
            if(nums[i]==2)
            {
                swap(nums[i],nums[r]);
                r--;
                if(nums[i]!=1)  i--;
            }        
        }
    }
};
  • 时间复杂度 O(n) 空间复杂度O(1)
  • 如果i与r换完数字后nums[i]是0或2,需要i–重新遍历,不然就会漏掉这个结果
  • 判断nums[i]=0必须放在判断nums[i]=2之前,防止第一个数字为2,运行后i会回退到1造成越界

###79. 单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1:

输入:board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出:true

示例 2:

输入:board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “SEE”
输出:true

示例 3:

输入:board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCB”
输出:false

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int line=board.size();
        int col=board[0].size();
        int sl,sc;
        vector<vector<bool>> visited(board.size(),vector<bool>(board[0].size(),false));
       
        for(int i=0;i<line;i++)
        {
            for(int j=0;j<col;j++)
            {
                if(board[i][j]!=word[0]) 
                {
                   continue;
                }

                if(dfs(board,i,j,word,0,visited)) return true;
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board,int line,int col,string s,int n,vector<vector<bool>>&visited )
    {
        bool ans;
        if(n==s.size())
        {
            return 1;
        }
        if(line>=board.size()||line<0||col>=board[0].size()||col<0|| visited[line][col]==true) return 0;
        if(board[line][col]!=s[n] || visited[line][col]==true) return false;

        visited[line][col]=true;
        if(dfs(board,line+1,col,s,n+1,visited)||
                dfs(board,line-1,col,s,n+1,visited)||
                dfs(board,line,col+1,s,n+1,visited)||
                dfs(board,line,col-1,s,n+1,visited))
                return true;
        visited[line][col]=false;
        return false;
    }
};
  • dfs+回溯
  • 访问数组

98. 验证二叉搜索树

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下:

节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:root = [2,1,3]
输出:true

示例 2:

输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。

class Solution {
public:
    long long  preVal=LONG_LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if(root==NULL) return true;
        if(isValidBST(root->left)==false) return false;
        if(root->val<=preVal) return false;
        preVal=root->val;
        return isValidBST(root->right);
    }
};
  • 二叉搜索树中序遍历的当前节点一定比之前的节点大

144. 二叉树的前序遍历

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*>sk;
        vector<int> vec;
        if(root==NULL) return {};
        sk.push(root);
        while(!sk.empty())
        {
            root=sk.top();
            vec.push_back(root->val);
            sk.pop();
            if(root->right!=NULL) sk.push(root->right);
            if(root->left!=NULL)  sk.push(root->left);
        }
        return vec;
    } 
};
  • 非递归
  • 根进栈
  • 更新根,出栈,右进栈,左进栈
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> vec;
        pre(root,vec);
        return vec;
    } 

    void pre(TreeNode *root,vector<int> &vec)
    {
        if(root==NULL ) return;
        vec.push_back(root->val);
        pre(root->left,vec);
        pre(root->right,vec);
    }
};
  • 递归遍历

94. 二叉树的中序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> vec;
        inorder(root, vec);
        return vec;
    }

    void inorder(TreeNode *root,vector<int> &vec)
    {
        if(root==NULL) return;
        inorder(root->left,vec);
        vec.push_back(root->val);
        inorder(root->right,vec);
    }
};
  • 递归遍历
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>vec;
        stack<TreeNode*> sk;
        while(root!=NULL|| !sk.empty())
        {
            while(root!=NULL)
            {
                sk.push(root);
                root=root->left;
            }
            root=sk.top();
            sk.pop();
            vec.push_back(root->val);
            root=root->right;
        }
        return vec;
    }
};
  • 非递归

145. 二叉树的后序遍历

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> vec;
        post(root,vec);
        return vec;
    }

    void post(TreeNode*root,vector<int>& vec)
    {
        if(root==NULL) return ;
        post(root->left, vec);
        post(root->right, vec);
        vec.push_back(root->val);
    }
};
  • 递归
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*>sk1;
        stack<TreeNode*>sk2;
        vector<int>vec;
        sk1.push(root);
        if(root==NULL) return {};
        while(!sk1.empty())
        {
            root=sk1.top();
            sk1.pop();
            sk2.push(root);
            if(root->left!=NULL) sk1.push(root->left);
            if(root->right!=NULL) sk1.push(root->right);
        }

        while(!sk2.empty())
        {
            vec.push_back(sk2.top()->val);
            sk2.pop();
        }
        return vec;
    }
};
  • 非递归
  • 根进栈1
  • 更新根,根出栈,入栈2
  • 左进栈1,右进栈1
  • 重复

102. 二叉树的层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> vec;
        vector<int> v;
        if(root==NULL) return {};
        q.push(root);
        while(!q.empty())
        {
            int size=q.size();
            for(int i=0;i<size;i++)
            {
                root=q.front();
                q.pop();
                v.push_back(root->val);
                if(root->left!=NULL) q.push(root->left);
                if(root->right!=NULL) q.push(root->right);
            }
            vec.push_back(v);
            v.clear();
        }
        return  vec;
    }
};
  • 队列+BFS
  • 队列中元素数量为下一层的节点个数

101. 对称二叉树

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return f(root,root);
    }
    
    bool f(TreeNode *p,TreeNode *q)
    {
        if(p==NULL &&q==NULL) return true;
        if(p==NULL || q==NULL) return false;
        if(p->val!=q->val) return false;
        return f(p->left,q->right)&&f(p->right,q->left);

    }
};

141. 环形链表

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow=head;
        ListNode* fast=head;
        while(fast!=NULL)
        {
            slow=slow->next;
            if(fast->next==NULL) return false;
            fast=fast->next->next;
            if(fast==slow) return true;
        } 
        return false;
    }
};
  • 快慢指针

136. 只出现一次的数字

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans=nums[0];
        for(int i=1;i<nums.size();i++)
        {
             ans=ans^nums[i];
        }
        return ans;
    }
};
  • 两个相同的数异或等于0
  • 0与任何数异或等于它本身

114. 二叉树展开为链表

给你二叉树的根结点 root ,请你将它展开为一个单链表:

展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1:

输入:root = [1,2,5,3,4,null,6]
输出:[1,null,2,null,3,null,4,null,5,null,6]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [0]
输出:[0]

class Solution {
public:
    void flatten(TreeNode* root) {
        queue<int> q;
        if(root==NULL) return;
        TreeNode *head=root;
        pre(root,q);
        q.pop();
        while(!q.empty())
        {
            if(head->right==NULL)
            {
                TreeNode *root=new TreeNode(q.front());
                head->right=root;
                q.pop();
            }
            else
            {
                head->right->val=q.front();
                q.pop();
            }    
            head->left=NULL;
            head=head->right;
        }
    }

    void pre(TreeNode*root,queue<int> &q)
    {
        if(root==NULL) return ;
        q.push(root->val);
        pre(root->left,q);
        pre(root->right,q);
    }
};
  • 前序遍历

Q.E.D.