草庐IT

9.20Leetcode记录

清风紫雪 2023-04-17 原文

一、字符串的排列

题干：

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

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

示例:

输入：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;
    }
};

 

Leetcode9.20spanstylecolorC++

有关9.20Leetcode记录的更多相关文章

  1. ruby - Sinatra:运行 rspec 测试时记录噪音 - 2

    Sinatra新手；我正在运行一些rspec测试，但在日志中收到了一堆不需要的噪音。如何消除日志中过多的噪音？我仔细检查了环境是否设置为:test，这意味着记录器级别应设置为WARN而不是DEBUG。spec_helper:require"./app"require"sinatra"require"rspec"require"rack/test"require"database_cleaner"require"factory_girl"set:environment,:testFactoryGirl.definition_file_paths=%w{./factories./test/

  2. ruby-on-rails - Rails 5 Active Record 记录无效错误 - 2

    我有两个Rails模型，即Invoice和Invoice_details。一个Invoice_details属于Invoice，一个Invoice有多个Invoice_details。我无法使用accepts_nested_attributes_forinInvoice通过Invoice模型保存Invoice_details。我收到以下错误:(0.2ms)BEGIN(0.2ms)ROLLBACKCompleted422UnprocessableEntityin25ms(ActiveRecord:4.0ms)ActiveRecord::RecordInvalid(Validationfa

  3. kvm虚拟机安装centos7基于ubuntu20.04系统 - 2

    需求：要创建虚拟机，就需要给他提供一个虚拟的磁盘，我们就在/opt目录下创建一个10G大小的raw格式的虚拟磁盘CentOS-7-x86_64.raw命令格式：qemu-imgcreate-f磁盘格式磁盘名称磁盘大小qemu-imgcreate-f磁盘格式-o?1.创建磁盘qemu-imgcreate-fraw/opt/CentOS-7-x86_64.raw10G执行效果#ls/opt/CentOS-7-x86_64.raw2.安装虚拟机使用virt-install命令，基于我们提供的系统镜像和虚拟磁盘来创建一个虚拟机，另外在创建虚拟机之前，提前打开vnc客户端，在创建虚拟机的时候，通过vnc

  4. ruby-on-rails - 事件记录 : Select max of limit - 2

    我正在尝试将以下SQL查询转换为ActiveRecord，它正在融化我的大脑。deletefromtablewhereid有什么想法吗？我想做的是限制表中的行数。所以，我想删除少于最近10个条目的所有内容。编辑:通过结合以下几个答案找到了解决方案。Temperature.where('id这给我留下了最新的10个条目。 最佳答案 从您的SQL来看，您似乎想要从表中删除前10条记录。我相信到目前为止的大多数答案都会如此。这里有两个额外的选择:基于MurifoX的版本:Table.where(:id=>Table.order(:id).

  5. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  6. Ruby 守护进程导致 ActiveRecord 记录器 IOError - 2

    我目前正在用Ruby编写一个项目，它使用ActiveRecordgem进行数据库交互，我正在尝试使用ActiveRecord::Base.logger记录所有数据库事件具有以下代码的属性ActiveRecord::Base.logger=Logger.new(File.open('logs/database.log','a'))这适用于迁移等(出于某种原因似乎需要启用日志记录，因为它在禁用时会出现NilClass错误)但是当我尝试运行包含调用ActiveRecord对象的线程守护程序的项目时脚本失败并出现以下错误/System/Library/Frameworks/Ruby.frame

  7. ruby-on-rails - 在 Rails 中更高效地查找或创建多条记录 - 2

    我有一个应用需要发送用户事件邀请。当用户邀请friend(用户)参加事件时，如果尚不存在将用户连接到该事件的新记录，则会创建该记录。我的模型由用户、事件和events_user组成。classEventdefinvite(user_id,*args)user_id.eachdo|u|e=EventsUser.find_or_create_by_event_id_and_user_id(self.id,u)e.save!endendend用法Event.first.invite([1,2,3])我不认为以上是完成我的任务的最有效方法。我设想了一种方法，例如Model.find_or_cr

  8. ruby - 在模块/类之间共享全局记录器 - 2

    在许多ruby​​类之间共享记录器实例的最佳(正确)方法是什么？现在我只是将记录器创建为全局$logger=Logger.new变量，但我觉得有更好的方法可以在不使用全局变量的情况下执行此操作。如果我有以下内容:moduleFooclassAclassBclassC...classZend在所有类之间共享记录器实例的最佳方式是什么？我是以某种方式在Foo模块中声明/创建记录器还是只是使用全局$logger没问题？ 最佳答案 在模块中添加常量:moduleFooLogger=Logger.newclassAclassBclassC..

  9. ruby - Sinatra 中的全局救援和日志记录异常 - 2

    如何在出现异常时指定全局救援，如果您将Sinatra用于API或应用程序，您将如何处理日志记录？ 最佳答案 404可以在not_found方法的帮助下处理，例如:not_founddo'Sitedoesnotexist.'end500s可以通过调用带有block的错误方法来处理，例如:errordo"Applicationerror.Plstrylater."end错误的详细信息可以通过request.env中的sinatra.error访问，如下所示:errordo'Anerroroccured:'+request.env['si

  10. ruby-on-rails - 在不重新查询数据库的情况下重新排序 Rails 中的事件记录？ - 2

    例如，假设我有一个名为Products的模型，并且在ProductsController中，我有以下代码用于product_listView以显示已排序的产品。@products=Product.order(params[:order_by])让我们想象一下，在product_listView中，用户可以使用下拉菜单按价格、评级、重量等进行排序。数据库中的产品不会经常更改。我很难理解的是，每次用户选择新的order_by过滤器时，rails是否必须查询，或者rails是否能够以某种方式缓存事件记录以在服务器端重新排序？有没有一种方法可以编写它，以便在用户排序时rails不会重新查询结果

随机推荐