一、字符串的排列

题干:

输入一个字符串,打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。

示例:

输入:s = "abc"
输出:["abc","acb","bac","bca","cab","cba"]

限制:

1 <= s 的长度 <= 8

题解:

全排列问题可采用递归的思路,固定某个位置,求出其他位置的全排列

我们可以通过交换来获得所有可能的情况。比如第一个位置上的字符,假如 A 和 A 交换,就相当于第一个位置上固定了 A;假如 A 和 B 交换,B来到第一个位置,就相当于第一个位置上固定了 B;假如 A 和 C 交换,C来到第一个位置,就相当于第一个位置上固定了 C。递归的过程中都是同理。

此外,因为可能有字符重复,我们得到的全排列自然也会有重复,那么我们可以用 set (集合)来去重,并且还可以达到按照字母顺序排序的目的。

代码

class Solution {
public:
    set<string> num;
    void num_swap(string s,int cnt)
    {
        if(cnt==s.size()-1)
        {
            num.insert(s);
            return;
        }
        for(int i=cnt;i<s.size();i++)
        {
            // for循环和swap的含义:对于“ABC”,
            // 第一次'A' 与 'A'交换,字符串为"ABC", pos为0, 相当于固定'A'
            // 第二次'A' 与 'B'交换,字符串为"BAC", pos为0, 相当于固定'B'
            // 第三次'A' 与 'C'交换,字符串为"CBA", pos为0, 相当于固定'C'  
            swap(s[cnt],s[i]);
            num_swap(s,cnt+1);
            swap(s[cnt],s[i]);
            // 回溯的原因:比如第二次交换后是"BAC",需要回溯到"ABC"
            // 然后进行第三次交换,才能得到"CBA"
        }
    }
    vector<string> permutation(string s) {
        num_swap(s,0);
        vector<string> ans=vector<string>({num.begin(), num.end()});
        return ans;
    }
};

二、数组中出现次数超过一半的数字

题干

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例 1:

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

限制:

1 <= 数组长度 <= 50000

题解

如果有一个数超过数组长度一半,意味着他可以把其他数字全部抵消,海能保证有剩余,因此,我们设定第一个数为最终的ans结果,在设置一个cnt次数表示目前该数出现的次数,若果下一个不是该数,并且次数为0,则更换ans,若果不是该数且次数不为0,则只减少次数,ans值不变。对数组进行一遍遍历,即可求出结果。

代码

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int cur=0;
        int ans=nums[0];
        for(int i=1;i<nums.size();i++)
        {
            if(nums[i]!=ans)
            {
                if(cur!=0)
                {
                    cur--;
                }
                else
                {
                    ans=nums[i];
                }
            }
            else
                cur++;
        }
    return ans;
    }
};

本文来源:

博客园:https://www.cnblogs.com/xiaofengzai/p/16710179.html

发表回复

您的电子邮箱地址不会被公开。