## 创建git init//创建常用操作git add <filename> //添加文件 git commit -m "<info>" //提交 git status //查看仓库当前状态 git log //查看历史记录 git reset --hard HEAD //回退到上一个版本 git reset --hard <commit id> //定位版本到commit id git reflog //查询操作过的命令（命令历史） git checkout -- <filename> //用版本库版本替代工作区版本（未commit前） git rm <filename> //删除文件 git clone git@<git url>:<git url> //克隆仓库Commit ID由SHA1计算得出，分布式，不能用顺序ID工作区电脑里能看到的目录（被控制的目录及文件）版本库/.git暂存库于版本库下，Git会自动创建第一个分支master，以及一个指向其的指针HEAD远程仓库创建SSH Keyssh-keygen -t rsa -C "youremail@example.com"id_rsa私钥，id_rsa.pub为公钥git push -u origin master //本地库推送到远程 git remote add origin git@server-name:path/repo-name.git //关联一个远程库 加上了-u参数，Git不但会把本地的 master分⽀支内容推送的远程新的master分⽀支，还会把本地的master分⽀支和远程的master 分⽀支关联起来，在以后的推送或者拉取时就可以简化命令分支管理增删查改git branch //查看当前分支 git branch dev //创建dev分支 git checkout dev //切换到dev分支 git checkout -b dev //创建并切换到dev分支 git merge dev //将dev分支的工作成果合并到master分支上 git branch -d dev //删除dev分支 冲突控制先解决冲突后提交，再合并git log --graph //查看分支合并图管理策略git merge --no-ff -m "<comment>" //强制禁用Fast forward（此功能在合并后，删除分支会丢掉分支信息） 保证master分支是稳定的，dev分支不稳定，用于开发，提交提交到dev分支上bug分支git stash //存储当前工作现场（搁置当前未完成工作进行bug修复） git stash list //查看保存的stash现场id列表 git stash apply |<stash@{0}> //恢复stash现场（stash的内容并不删除） git stash pop //恢复现场的同时将其删除Feature 分支增添一个Feature最好开一个新的分支若要丢弃一个没有被合并过的分支，可以通过git branch -D name强⾏行删除多人协作git remote origin <git url> //查看远程库信息 git pull git push origin <branch-name> git branch --set-upstream branch-name origin/branch-name //建⽴立本地分⽀支和远程分⽀支的关联 git checkout -b branch-name origin/branch- name //在本地创建和远程对应的分支创建标签git tag <tag name> //创建标签 git show <tag name> //查看标签信息 git tag -a tagname -m "blablabla..."可以指定标签信息; git tag -s tagname -m "blablabla..."可以⽤用PGP签名标签; git push origin tagname //可以推送⼀一个本地标签; git push origin --tags //可以推送全部未推送过的本地标签; git tag -d tagname //可以删除⼀一个本地标签; git push origin :refs/tags/tagname //可以删除⼀一个远程标签。自定义忽略特殊文件：./gitignore
API配置在Vue中，API配置的作用是用来定义和管理应用程序中的网络请求。API配置允许你将后端接口的地址和其他相关信息集中定义在一个地方，以便在应用程序中进行统一管理和调用。这样做的好处是使代码更加结构化和易于维护，并提供了一种便捷的方式来管理所有的网络请求。通常，一个Vue应用中的API配置会包含以下内容：接口地址：定义后端接口的URL地址，包括基础URL和不同接口的路径。这样在应用中使用这些接口时，只需要关注相对路径而无需担心绝对URL。请求方法：定义不同接口所使用的请求方法，例如GET、POST、PUT、DELETE等。不同的接口可能需要不同的请求方法来进行数据的获取或提交。请求头：定义接口请求时需要携带的请求头信息，例如认证信息、Token等。这些信息可以在API配置中设置为默认值，从而在每次请求时自动携带。参数处理：定义接口请求时需要传递的参数，并提供参数处理的功能，例如序列化、拼接等。响应处理：定义接口响应的处理方式，例如对返回的数据进行解析、错误处理等。通过API配置，你可以将所有与后端接口相关的信息统一管理，方便后续维护和修改。同时，API配置也可以与网络请求库（如axios、fetch等）结合使用，从而实现便捷的网络请求调用。一个典型的Vue应用的API配置可以是一个JavaScript对象，如下所示：javascriptCopy code// api.js export default { user: { login: '/api/login', // 登录接口 getUserInfo: '/api/userInfo', // 获取用户信息接口 updateUser: '/api/updateUser', // 更新用户信息接口 deleteUser: '/api/deleteUser' // 删除用户接口 }, post: { getPosts: '/api/posts', // 获取文章列表接口 createPost: '/api/createPost', // 创建文章接口 updatePost: '/api/updatePost', // 更新文章接口 deletePost: '/api/deletePost' // 删除文章接口 } }在Vue组件中，你可以引入上述API配置，并使用它来发起网络请求，如下所示：javascriptCopy codeimport axios from 'axios'; import apiConfig from './api'; export default { methods: { async login(username, password) { const response = await axios.post(apiConfig.user.login, { username: username, password: password }); // 处理响应数据 // ... }, async getPosts() { const response = await axios.get(apiConfig.post.getPosts); // 处理响应数据 // ... } } }通过使用API配置，你可以在组件中更加清晰地定义和管理网络请求，使得代码更加易读和易于维护。同时，当后端接口地址或其他信息发生变化时，你只需要修改API配置而无需修改每个组件中的请求代码，从而提高了代码的可维护性。关键字在Vue中，export function 是JavaScript中用于导出函数的关键字组合。它的作用是将一个函数定义导出，使得其他模块或组件可以引入并使用这个函数。在Vue应用中，如果你在一个文件中定义了一个函数，并希望在其他文件中使用这个函数，你可以使用 export function 将它导出，然后在其他文件中使用 import 关键字将这个函数导入。举例说明：假设你在一个名为 myFunction.js 的文件中定义了一个函数：javascriptCopy code// myFunction.js export function myFunction() { // 函数的实现 console.log('Hello from myFunction!'); }然后在另一个文件中，你可以使用 import 关键字将这个函数导入并使用：javascriptCopy code// anotherFile.js import { myFunction } from './myFunction.js'; // 调用导入的函数 myFunction(); // 输出：Hello from myFunction!通过使用 export function 关键字，你可以将函数 myFunction 导出，使得其他文件可以方便地引入并使用它。在实际开发中，这种导入导出的方式非常常见，用于在不同文件之间共享函数、组件、常量等内容，从而实现代码的模块化和组织结构的清晰。标签在Vue前端开发中，组件是一种可复用的、自定义的HTML元素，它将页面的不同部分封装成独立的功能模块。Vue中的组件使用自定义标签来表示，这些标签可以像普通HTML元素一样在模板中使用。Vue组件标签具有以下特点：自定义标签名：在Vue中，组件的标签名是自定义的，可以根据项目需求进行命名，但是通常推荐使用连字符命名（kebab-case），例如<my-component>。注册组件：在使用组件之前，需要先在Vue中注册它。可以通过全局注册或局部注册的方式来注册组件。全局注册：在应用启动时，使用Vue.component()全局方法来注册组件。局部注册：在组件的父组件中，通过components选项来局部注册组件。组件模板：组件标签通常有自己的模板，用来定义组件的结构和展示内容。模板可以使用Vue的模板语法，包括插值表达式、指令、事件绑定等。组件数据：组件可以定义自己的数据，这些数据将在组件内部使用。每个组件都有独立的作用域，数据不会相互干扰。组件属性：组件标签可以传递属性，也称为props，用来向组件传递数据。在组件内部，可以通过this来访问传递进来的属性。组件事件：组件可以触发自定义事件，并通过$emit方法向父组件传递消息。组件生命周期：组件有自己的生命周期钩子函数，用于在组件不同阶段执行特定的操作。组件样式：每个组件可以有独立的样式，通常使用CSS进行样式定义。样式可以通过CSS类名或组件的作用域样式来设置。使用Vue的组件标签可以使前端开发更加模块化、可维护和可扩展。通过合理的组件拆分和组合，可以构建复杂的应用界面，并使代码更具有结构和可读性。组件化开发也便于团队协作，不同团队成员可以独立开发和测试自己的组件，最后组合在一起形成完整的应用。
17 打印从 1 到最大的 n 位数输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。示例 1:输入: n = 1 输出: [1,2,3,4,5,6,7,8,9]说明：用返回一个整数列表来代替打印n 为正整数题解class Solution { public: vector<int> printNumbers(int n) { int max=pow(10,n)-1; vector<int> res; for(int i=1;i<=max;i++){ res.push_back(i); } return res; } }; /*若考虑大数则应换dfs全排列做法*/19（10） 正则表达式匹配请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。示例 1:输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。示例 2:输入: s = "aa" p = "a*" 输出: true 解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。示例 3:输入: s = "ab" p = ".*" 输出: true 解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。示例 4:输入: s = "aab" p = "c*a*b" 输出: true 解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。示例 5:输入: s = "mississippi" p = "mis*is*p*." 输出: falses 可能为空，且只包含从 a-z 的小写字母。p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。题解class Solution { public: bool isMatch(string s, string p) { int m = s.size() + 1, n = p.size() + 1; vector<vector<bool>> dp(m, vector<bool>(n, false)); dp[0][0] = true; // 初始化首行 for(int j = 2; j < n; j += 2) dp[0][j] = dp[0][j - 2] && p[j - 1] == '*'; // 状态转移 for(int i = 1; i < m; i++) { for(int j = 1; j < n; j++) { if(p[j - 1] == '*') { if(dp[i][j - 2]) dp[i][j] = true; // 1. else if(dp[i - 1][j] && s[i - 1] == p[j - 2]) dp[i][j] = true; // 2. else if(dp[i - 1][j] && p[j - 2] == '.') dp[i][j] = true; // 3. } else { if(dp[i - 1][j - 1] && s[i - 1] == p[j - 1]) dp[i][j] = true; // 1. else if(dp[i - 1][j - 1] && p[j - 1] == '.') dp[i][j] = true; // 2. } } } return dp[m - 1][n - 1]; } }; /*当 p[j - 1] != '*' 时， dp[i][j] 在当以下任一情况为 true 时等于 true ： dp[i - 1][j - 1] 且 s[i - 1] = p[j - 1]：字符串 s 的前 i-1 个字符和 p 的前 j -1个字符匹配, 且s的第i个字符等于p的第j个字符; dp[i - 1][j - 1] 且 p[j - 1] = '.'： 字符串 s 的前 i-1 个字符和 p 的前 j -1个字符匹配, 且p的第j个字符为'.'; */来源：作者：Krahets链接：https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solutions/494128/jian-zhi-offer-19-zheng-ze-biao-da-shi-pi-pei-dong/20 表示数值的字符串请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。数值（按顺序）可以分成以下几个部分：若干空格一个 小数 或者 整数（可选）一个 'e' 或 'E' ，后面跟着一个 整数若干空格小数（按顺序）可以分成以下几个部分：（可选）一个符号字符（'+' 或 '-'）下述格式之一：至少一位数字，后面跟着一个点 '.'至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字一个点 '.' ，后面跟着至少一位数字整数（按顺序）可以分成以下几个部分：（可选）一个符号字符（'+' 或 '-'）至少一位数字部分数值列举如下：["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]部分非数值列举如下：["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]示例 1：输入：s = "0" 输出：true示例 2：输入：s = "e" 输出：false示例 3：输入：s = "." 输出：false示例 4：输入：s = " .1 " 输出：true提示：1 <= s.length <= 20s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，空格 ' ' 或者点 '.'题解class Solution { public: enum State { STATE_INITIAL, STATE_INT_SIGN, STATE_INTEGER, STATE_POINT, STATE_POINT_WITHOUT_INT, STATE_FRACTION, STATE_EXP, STATE_EXP_SIGN, STATE_EXP_NUMBER, STATE_END }; enum CharType { CHAR_NUMBER, CHAR_EXP, CHAR_POINT, CHAR_SIGN, CHAR_SPACE, CHAR_ILLEGAL }; CharType toCharType(char ch) { if (ch >= '0' && ch <= '9') { return CHAR_NUMBER; } else if (ch == 'e' || ch == 'E') { return CHAR_EXP; } else if (ch == '.') { return CHAR_POINT; } else if (ch == '+' || ch == '-') { return CHAR_SIGN; } else if (ch == ' ') { return CHAR_SPACE; } else { return CHAR_ILLEGAL; } } bool isNumber(string s) { unordered_map<State, unordered_map<CharType, State>> transfer{ { STATE_INITIAL, { {CHAR_SPACE, STATE_INITIAL}, {CHAR_NUMBER, STATE_INTEGER}, {CHAR_POINT, STATE_POINT_WITHOUT_INT}, {CHAR_SIGN, STATE_INT_SIGN} } }, { STATE_INT_SIGN, { {CHAR_NUMBER, STATE_INTEGER}, {CHAR_POINT, STATE_POINT_WITHOUT_INT} } }, { STATE_INTEGER, { {CHAR_NUMBER, STATE_INTEGER}, {CHAR_EXP, STATE_EXP}, {CHAR_POINT, STATE_POINT}, {CHAR_SPACE, STATE_END} } }, { STATE_POINT, { {CHAR_NUMBER, STATE_FRACTION}, {CHAR_EXP, STATE_EXP}, {CHAR_SPACE, STATE_END} } }, { STATE_POINT_WITHOUT_INT, { {CHAR_NUMBER, STATE_FRACTION} } }, { STATE_FRACTION, { {CHAR_NUMBER, STATE_FRACTION}, {CHAR_EXP, STATE_EXP}, {CHAR_SPACE, STATE_END} } }, { STATE_EXP, { {CHAR_NUMBER, STATE_EXP_NUMBER}, {CHAR_SIGN, STATE_EXP_SIGN} } }, { STATE_EXP_SIGN, { {CHAR_NUMBER, STATE_EXP_NUMBER} } }, { STATE_EXP_NUMBER, { {CHAR_NUMBER, STATE_EXP_NUMBER}, {CHAR_SPACE, STATE_END} } }, { STATE_END, { {CHAR_SPACE, STATE_END} } } }; int len = s.length(); State st = STATE_INITIAL; for (int i = 0; i < len; i++) { CharType typ = toCharType(s[i]); if (transfer[st].find(typ) == transfer[st].end()) { return false; } else { st = transfer[st][typ]; } } return st == STATE_INTEGER || st == STATE_POINT || st == STATE_FRACTION || st == STATE_EXP_NUMBER || st == STATE_END; } };44（400） 数字序列中的某一位数字数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。请写一个函数，求任意第n位对应的数字。示例 1：输入：n = 3 输出：3示例 2：输入：n = 11 输出：0限制：0 <= n < 2^31题解int digit = 1;//数位 long start = 1;//开始数字 long count = 9; while(n>count){ n -= count; digit += 1; start *= 10; count = digit*start*9; } long num = start + (n-1)/digit;//第二步 return to_string(num)[(n-1)%digit]-'0';46 把数字翻译成字符串:p给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。示例 1:输入: 12258 输出: 5 解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"提示：0 <= num < 2^31题解class Solution { public: int translateNum(int num) { string str = to_string(num); int len=str.size(); string tmp=""; vector<int> dp(len+1,0); dp[0]=1; dp[1]=1; for(int i=2;i<=len;i++){ tmp=str.substr(i-2,2); dp[i]=(tmp<="25" && tmp >= "10")? dp[i-1]+dp[i-2]:dp[i-1]; } return dp[len]; } };M59 - II 队列的最大值请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。若队列为空，pop_front 和 max_value 需要返回 -1示例 1：输入: ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"] [[],[1],[2],[],[],[]] 输出: [null,null,null,2,1,2]示例 2：输入: ["MaxQueue","pop_front","max_value"] [[],[],[]] 输出: [null,-1,-1]限制：1 <= push_back,pop_front,max_value的总操作数 <= 100001 <= value <= 10^5题解class MaxQueue { queue<int> que; deque<int> deq; public: MaxQueue() { } int max_value() { return deq.empty() ? -1:deq.front(); } void push_back(int value) { que.push(value); while(!deq.empty() && deq.back()<value) deq.pop_back(); deq.push_back(value); } int pop_front() { if(que.empty()) return -1; int val = que.front(); if(val==deq.front()) deq.pop_front(); que.pop(); return val; } }; /** * Your MaxQueue object will be instantiated and called as such: * MaxQueue* obj = new MaxQueue(); * int param_1 = obj->max_value(); * obj->push_back(value); * int param_3 = obj->pop_front(); */来源：https://leetcode.cn/problems/dui-lie-de-zui-da-zhi-lcof/solutions/540181/jian-zhi-offer-59-ii-dui-lie-de-zui-da-z-0pap/M61 扑克牌顺子从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。示例 1:输入: [1,2,3,4,5] 输出: True示例 2:输入: [0,0,1,2,5] 输出: True限制：数组长度为 5 数组的数取值为 [0, 13] .题解class Solution { public: bool isStraight(vector<int>& nums) { // int max=-1; // int min=14;//[0,13]正常取值范围 // int joker=0; // for(int num: nums) // { // if(num==0){joker++;continue;} // if(num>max){max=num;continue;} // if(num<min){min=num;continue;} // } // if(joker==0) // { // if(max-min<5)return true; // else return false; // } // else if(max-min<=5) // { // return true; // } // else return false; set<int> s; for(int i:nums){ if(s.find(i)!=s.end())return 0; if(i)s.insert(i); } return *s.rbegin()-*s.begin()<5; } };64 求 1+2+3+...+n求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。示例 1：输入: n = 3 输出: 6示例 2：输入: n = 9 输出: 45限制：1 <= n <= 10000题解/*使用递归和短路判断终止递归*/ class Solution { public: int res=0; int sumNums(int n) { bool x = n > 1 && sumNums(n-1) > 0; res += n; return res; } };65 不用加减乘除做加法写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。示例:输入: a = 1, b = 1 输出: 2提示：a, b 均可能是负数或 0结果不会溢出 32 位整数题解class Solution { public: int add(int a, int b) { //因为不允许用+号，所以求出异或部分和进位部分依然不能用+ 号，所以只能循环到没有进位为止 while(b!=0) { //保存进位值，下次循环用 int c=(unsigned int)(a&b)<<1;//C++中负数不支持左移位，因为结果是不定的 //保存不进位值，下次循环用， a^=b; //如果还有进位，再循环，如果没有，则直接输出没有进位部分即可。 b=c; } return a; } };来源：https://leetcode.cn/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/solutions/210882/mian-shi-ti-65-bu-yong-jia-jian-cheng-chu-zuo-ji-7/M67（8） 把字符串转换成整数写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。在任何情况下，若函数不能进行有效的转换时，请返回 0。说明：假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。示例 1:输入: "42" 输出: 42示例 2:输入: " -42" 输出: -42 解释: 第一个非空白字符为 '-', 它是一个负号。 我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。示例 3:输入: "4193 with words" 输出: 4193 解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。示例 4:输入: "words and 987" 输出: 0 解释: 第一个非空字符是 'w', 但它不是数字或正、负号。 因此无法执行有效的转换。示例 5:输入: "-91283472332" 输出: -2147483648 解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 因此返回 INT_MIN (−231) 。题解class Solution { public: int strToInt(string str) { bool sign = true; int i=0; while(i<str.size() && str[i]==' ')i++; if(str[i]=='-'){ sign = false; i++; } else if(str[i]=='+')i++; if(str[i]<'0' || str[i]>'9')return 0; int res=0; int num; int border=__INT_MAX__/10; while(i<str.size()){ if(str[i]<'0'||str[i]>'9')break; if(res>border||res==border&&str[i]>'7') return sign==true?__INT_MAX__:INT_MIN; num=str[i]-'0'; res=res*10+num; i++; } return sign==true?res:-res; } };来源：https://leetcode.cn/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/solutions/201301/mian-shi-ti-67-ba-zi-fu-chuan-zhuan-huan-cheng-z-4/
15（191） 二进制中 1 的个数编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量).）。提示：请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。示例 1：输入：n = 11 (控制台输入 00000000000000000000000000001011) 输出：3 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。示例 2：输入：n = 128 (控制台输入 00000000000000000000000010000000) 输出：1 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。示例 3：输入：n = 4294967293 (控制台输入 11111111111111111111111111111101，部分语言中 n = -3） 输出：31 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。提示：输入必须是长度为 32 的 二进制串 。题解/*与运算*/ class Solution { public: int hammingWeight(uint32_t n) { int res=0; for(int i=0;i<32;i++) { if(n&1)res++; n>>=1; } return res; } }; /*n&(n-1)法*/ public: int hammingWeight(uint32_t n) { int res=0; while(n!=0) { n&=(n-1);//每次运算都会消去n最末尾的一个1 res++; } return res; } };56 - I 数组中数字出现的次数（数组中只出现一次的数字）一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。示例 1：输入：nums = [4,1,4,6] 输出：[1,6] 或 [6,1]示例 2：输入：nums = [1,2,10,4,1,4,3,3] 输出：[2,10] 或 [10,2]限制：2 <= nums.length <= 10000题解class Solution { public: vector<int> singleNumbers(vector<int>& nums) { int x = 0, y = 0, n = 0, m = 1; for(int num: nums)//遍历异或 { n^=num; } while((n&m)==0)//记录x^=y首位1 { m<<=1; } for(int num:nums){ if(num&m)x^=num;//划分子数组，能保证相同的数必划分到同一数组中 else y^=num; } return vector<int>{x,y}; } };来源：https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solutions/572857/jian-zhi-offer-56-i-shu-zu-zhong-shu-zi-tykom/56 - II 数组中数字出现的次数 II在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。示例 1：输入：nums = [3,4,3,3] 输出：4示例 2：输入：nums = [9,1,7,9,7,9,7] 输出：1限制：1 <= nums.length <= 100001 <= nums[i] < 2^31题解class Solution { public: int singleNumber(vector<int>& nums) { int ones = 0, twos = 0; for(int num :nums){ ones = ones^num & ~twos; twos = twos^num & ~ones; } return ones; } }; /*相对简单*/ class Solution { public: int singleNumber(vector<int>& nums) { vector<int> counts(32); for(int num:nums){ for(int i=0;i<32;i++){ counts[i]+=num&1; num>>=1; } } int res=0, m=3; for(int i=0;i<32;i++){ res<<=1; res|= counts[31-i]%m; } return res; } };
39（169） 数组中出现次数超过一半的数字数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。示例 1:输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2限制：1 <= 数组长度 <= 50000题解class Solution { public: int majorityElement(vector<int>& nums) { int x = 0, votes = 0, count=0; for(int num : nums){ if(votes==0)x=num; votes+=num==x?1:-1; } // 验证 x 是否为众数 for(int num : nums) if(num == x) count++; return count > nums.size() / 2 ? x : 0; // 当无众数时返回 0 } };62 圆圈中最后剩下的数0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。示例 1：输入: n = 5, m = 3 输出: 3示例 2：输入: n = 10, m = 17 输出: 2限制：1 <= n <= 10^51 <= m <= 10^6题解class Solution { public: int lastRemaining(int n, int m) { int x = 0; for(int i=2;i<=n;i++){ x=(x+m)%i; } return x; } };来源：https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solutions/607638/jian-zhi-offer-62-yuan-quan-zhong-zui-ho-dcow/43（233） 从 1 到 n 整数中 1 出现的次数输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。示例 1：输入：n = 12 输出：5示例 2：输入：n = 13 输出：6限制：1 <= n < 2^31题解class Solution { public: int countDigitOne(int n) { long long digit = 1, res = 0; int high = n / 10, cur = n % 10, low = 0; while (high != 0 || cur != 0) { if (cur == 0) res += high * digit; // 0 else if (cur == 1) res += high * digit + low + 1; // 1 else res += (high + 1) * digit; // 2-9 low += cur * digit; cur = high % 10; high /= 10; digit *= 10; } return res; } };来源：https://leetcode.cn/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solutions/229751/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/
10 - I 斐波那契数列写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。示例 1：输入：n = 2 输出：1示例 2：输入：n = 5 输出：5题解class Solution { public: int fib(int n) { int a = 0, b=1,sum; for(int i=0;i<n;i++){ sum=(a+b)%1000000007; a=b; b=sum; } return a; } };836 矩形覆盖矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。矩形的上下边平行于 x 轴，左右边平行于 y 轴。如果相交的面积为 正 ，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。给出两个矩形 rec1 和 rec2 。如果它们重叠，返回 true；否则，返回 false 。示例 1：输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3] 输出：true示例 2：输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1] 输出：false示例 3：输入：rec1 = [0,0,1,1], rec2 = [2,2,3,3] 输出：false提示：rect1.length == 4rect2.length == 4-109 <= rec1[i], rec2[i] <= 109rec1 和 rec2 表示一个面积不为零的有效矩形题解class Solution { public: bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) { if(rec1[0]==rec1[2]||rec1[1]==rec1[3]||rec2[0]==rec2[2]||rec2[1]==rec2[3]){ return false; } return !(rec1[2]<=rec2[0]|| //1右在2左的左边（左） rec1[3]<=rec2[1]|| //1上在2下的下边（下） rec1[0]>=rec2[2]|| //1左在2右的右边（右） rec1[1]>=rec2[3]); //1下在2上的上边（上） } };10 - II（70）跳台阶一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。示例 1：输入：n = 2 输出：2示例 2：输入：n = 7 输出：21示例 3：输入：n = 0 输出：1提示：0 <= n <= 100题解/*070*/ class Solution { public: int climbStairs(int n) { long long a = 1, b = 1, sum; for(int i = 0;i < n; i++) { sum=a+b; a=b; b=sum; } return a; } }; /*10-II*/ class Solution { public: int numWays(int n) { int a=1, b=1, sum; for(int i=0;i<n;i++){ sum=(a+b)%1000000007; a=b; b=sum; } return a; } };42（53）连续子数组的最大和输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。示例1:输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。提示：1 <= arr.length <= 10^5-100 <= arr[i] <= 100题解class Solution { public: int maxSubArray(vector<int>& nums) { int res = nums[0]; for(int i=1;i<nums.size();i++) { nums[i] += max(nums[i-1],0);//dp 两种情况 res = max(res, nums[i]); } return res; } };47 礼物的最大价值在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？示例 1:输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 12 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物提示：0 < grid.length <= 2000 < grid[0].length <= 200题解class Solution { public: int maxValue(vector<vector<int>>& grid) { int m = grid.size(), n= grid[0].size(); for(int i = 0;i<m;i++){ for(int j = 0;j<n;j++){ if(i==0&&j==0)continue; if(i==0)grid[i][j]+=grid[i][j-1]; else if(j==0)grid[i][j]+=grid[i-1][j]; else grid[i][j] += max(grid[i][j-1], grid[i-1][j]); } } return grid[m-1][n-1]; } };48（3） 最长不含重复字符的子字符串请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。示例 1:输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。提示：s.length <= 40000题解class Solution { public: int lengthOfLongestSubstring(string s) { unordered_map<char, int> dic;//统计s[j]最后一次出现的索引 int i=-1, res=0; for(int j=0;j<s.size();j++) { if(dic.find(s[j])!=dic.end())//若出现过s[j] i=max(i, dic[s[j]]);//更新左指针，若有重复字符在i，j间则更新i dic[s[j]]=j;//更新索引位置 res=max(res,j-i);//保证取得最长的i，j区间 } return res; } };49（264） 丑数我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。示例:输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。说明:1 是丑数。n 不超过1690。题解class Solution { public: int nthUglyNumber(int n) { int a = 0, b = 0, c = 0; int dp[n]; dp[0]=1; for(int i=1;i<n;i++){ int n2=dp[a]*2, n3=dp[b]*3, n5=dp[c]*5; dp[i]=min(min(n2,n3),n5); if(dp[i]==n2)a++; if(dp[i]==n3)b++; if(dp[i]==n5)c++; } return dp[n-1]; } };我的一点理解： 在已有的丑数序列上每一个数都必须乘2， 乘3， 乘5， 这样才不会漏掉某些丑数。假设已有的丑数序列为[1, 2, 3, ..., n1, n2], 如果单纯的让每个丑数乘2， 乘3， 乘5顺序排列的话肯定会有问题，比如如果按照这样的顺序排列下去肯定有问题[12, 13, 15, 22, 23, 25, 32, 33, 35, ... , n1 2, n1 * 3, n1 * 5, n2 * 2, n3 3, n2 5]，因为后面乘2的数据可能会比前面乘3乘5的数据要小，那这个乘2的数应该排在他们的前面， 后面乘3的数据也可能比前面乘5的数据要小，那这个乘3的数应该排在他们的前面。那怎么办呢，每个数都必须乘2， 乘3， 乘5这样才能保证求出所有的丑数，而且还要保证丑数的顺序，这个改如何同时实现呢？通过观察网上的各个题解，终于找到了办法，那就是记录每个丑数是否已经被乘2， 乘3， 乘5了， 具体的做法是设置3个索引a, b, c，分别记录前几个数已经被乘2， 乘3， 乘5了，比如a表示前(a-1)个数都已经乘过一次2了，下次应该乘2的是第a个数；b表示前(b-1)个数都已经乘过一次3了，下次应该乘3的是第b个数；c表示前(c-1)个数都已经乘过一次5了，下次应该乘5的是第c个数；对于某个状态下的丑数序列，我们知道此时第a个数还没有乘2(有没有乘3或者乘5不知道）， 第b个数还没有乘3(有没有乘2或者乘5不知道），第c个数还没有乘5(有没有乘2或者乘3不知道), 下一个丑数一定是从第a丑数乘2， 第b个数乘3， 第c个数乘5中获得，他们三者最小的那个就是下个丑数。求得下个丑数后就得判断这个丑数是谁，是某个数通过乘2得到的，还是某个数乘3得到的，又或是说某个数通过乘5得到的。我们可以比较一下这个新的丑数等于究竟是等于第a个丑数乘2, 还是第b个数乘3， 还是第c个数乘5， 通过比较我们肯定可以知道这个新的丑数到底是哪个数通过乘哪个数得到的。假设这个新的丑数是通过第a个数乘2得到的，说明此时第a个数已经通过乘2得到了一个新的丑数，那下个通过乘2得到一个新的丑数的数应该是第(a+1)个数，此时我们可以说前 a 个数都已经乘过一次2了，下次应该乘2的是第 （a+1） 个数, 所以a++；如果新的丑数是通过第b个数乘3得到的, 说明此时第 b个数已经通过乘3得到了一个新的丑数，那下个需要通过乘3得到一个新的丑数的数应该是第(b+1)个数，此时我们可以说前 b 个数都已经乘过一次3了，下次应该乘3的是第 （b+1） 个数, 所以 b++；同理，如果这个这个新的丑数是通过第c个数乘5得到的, 那么c++;但是注意，如果第a个数乘2后等于第b个数乘3，或者等于第c个数乘5， 说明这个新的丑数是有两种或者三种方式可以得到，这时应该给得到这个新丑数的组合对应的索引都加一，比如新丑数是第a个数乘2后和第b个数乘3得到的，那么 a 和 b都应该加一， 因为此时第a个数已经通过乘2得到了一个新的丑数，第b个数已经通过乘3得到了一个新的丑数, 只不过这两个数相等而已。所以我们给计数器加一的时候不能使用 if else else if， 而应该使用if, if, if, 这样才不会把应该加一的计数器漏掉经过n次循环，就能得到第n 个丑数了。class Solution { public int nthUglyNumber(int n) { int[] dp = new int[n]; // 使用dp数组来存储丑数序列 dp[0] = 1; // dp[0]已知为1 int a = 0, b = 0, c = 0; // 下个应该通过乘2来获得新丑数的数据是第a个， 同理b, c for(int i = 1; i < n; i++){ // 第a丑数个数需要通过乘2来得到下个丑数，第b丑数个数需要通过乘2来得到下个丑数，同理第c个数 int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5; dp[i] = Math.min(Math.min(n2, n3), n5); if(dp[i] == n2){ a++; // 第a个数已经通过乘2得到了一个新的丑数，那下个需要通过乘2得到一个新的丑数的数应该是第(a+1)个数 } if(dp[i] == n3){ b++; // 第 b个数已经通过乘3得到了一个新的丑数，那下个需要通过乘3得到一个新的丑数的数应该是第(b+1)个数 } if(dp[i] == n5){ c++; // 第 c个数已经通过乘5得到了一个新的丑数，那下个需要通过乘5得到一个新的丑数的数应该是第(c+1)个数 } } return dp[n-1]; } }来源：https://leetcode.cn/problems/chou-shu-lcof/solutions/182045/mian-shi-ti-49-chou-shu-dong-tai-gui-hua-qing-xi-t/comments/61618660 n 个骰子的点数把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。示例 1:输入: 1 输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]示例 2:输入: 2 输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]限制：1 <= n <= 11题解class Solution { public: vector<double> dicesProbability(int n) { vector<double> dp(6, 1.0/6.0); for(int i=2;i<=n;i++){ vector<double> tmp(5*i+1,0); for(int j=0;j<dp.size();j++){ for(int k=0;k<6;k++){ tmp[j+k]+=dp[j]/6.0; } } dp=tmp; } return dp; } };来源：https://leetcode.cn/problems/nge-tou-zi-de-dian-shu-lcof/solutions/637778/jian-zhi-offer-60-n-ge-tou-zi-de-dian-sh-z36d/66 构建乘积数组给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。示例:输入: [1,2,3,4,5] 输出: [120,60,40,30,24]提示：所有元素乘积之和不会溢出 32 位整数a.length <= 100000题解/*超时做法*/ vector<int> res; for(int i=0;i<a.size();i++) { int tmp=1; for(int j=0;j<a.size();j++) { if(i==j)continue; tmp*=a[j]; } res.push_back(tmp); } return res; /*dp*/ class Solution { public: vector<int> constructArr(vector<int>& a) { int len = a.size(); vector<int> b(len, 1); if(len==0)return b; int left=1, right=1; for(int i=0;i<len;i++){ b[i]*=left; left*=a[i];//持有左边所有数的乘积 b[(len-1)-i]*=right; right*=a[(len-1)-i];//持有右边所有数的乘积 } return b; } }; /*dp*/ class Solution { public: vector<int> constructArr(vector<int>& a) { int len = a.size(); if(len==0)return {}; vector<int> b(len, 1); b[0]=1; int tmp=1; for(int i=1;i<len;i++){ b[i]=b[i-1]*a[i-1];//计算下三角 } for(int i=len-1-1;i>=0;i--){ //计算上三角 tmp*=a[i+1]; b[i]*=tmp; } return b; } };来源：https://leetcode.cn/problems/gou-jian-cheng-ji-shu-zu-lcof/solutions/208840/mian-shi-ti-66-gou-jian-cheng-ji-shu-zu-biao-ge-fe/
21 调整数组顺序使奇数位于偶数前面输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。示例：输入：nums = [1,2,3,4] 输出：[1,3,2,4] 注：[3,1,2,4] 也是正确的答案之一。提示：0 <= nums.length <= 500000 <= nums[i] <= 10000题解class Solution { public: vector<int> exchange(vector<int>& nums) { int i=0,j=nums.size()-1; while(i<j){ //i为奇数 if(nums[i]%2==1) { i++;continue; } //j为偶数 if(nums[j]%2==0) { j--;continue; } //j为奇数，该情况下i必为偶数 if(nums[j]%2==1) { swap(nums[i],nums[j]); j--; i++; continue; } } return nums; } }; //更简洁的写法 class Solution { public: vector<int> exchange(vector<int>& nums) { int i = 0, j = nums.size() - 1; while (i < j) { while(i < j && (nums[i] & 1) == 1) i++; while(i < j && (nums[j] & 1) == 0) j--; swap(nums[i], nums[j]); } return nums; } }; 作者：Krahets 链接：https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/solutions/115087/mian-shi-ti-21-diao-zheng-shu-zu-shun-xu-shi-qi-4/这题可以想到双指针方法，但一开始没有想到左右指针从左右两端开始，这种方法感觉比一段开始更好。M45 把数组排成最小的数输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。示例 1:输入: [10,2] 输出: "102"示例 2:输入: [3,30,34,5,9] 输出: "3033459"提示:0 < nums.length <= 100说明:输出结果可能非常大，所以你需要返回一个字符串而不是整数拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0示例：输入：nums = [1,2,3,4] 输出：[1,3,2,4] 注：[3,1,2,4] 也是正确的答案之一。提示：0 <= nums.length <= 500000 <= nums[i] <= 10000题解class Solution { public: string minNumber(vector<int>& nums) { vector<string> strs; string res; for(int i=0;i<nums.size();i++) strs.push_back(to_string(nums[i])); sort(strs.begin(), strs.end(), [](string& x, string& y){ return x+y<y+x;}); for(int i=0;i<strs.size();i++) res.append(strs[i]); return res; } }; /*快排实现*/ class Solution { public: string minNumber(vector<int>& nums) { vector<string> strs; for(int i = 0; i < nums.size(); i++) strs.push_back(to_string(nums[i])); quickSort(strs, 0, strs.size() - 1); string res; for(string s : strs) res.append(s); return res; } private: void quickSort(vector<string>& strs, int l, int r) { if(l >= r) return; int i = l, j = r; while(i < j) { while(strs[j] + strs[l] >= strs[l] + strs[j] && i < j) j--; while(strs[i] + strs[l] <= strs[l] + strs[i] && i < j) i++; swap(strs[i], strs[j]); } swap(strs[i], strs[l]); quickSort(strs, l, i - 1); quickSort(strs, i + 1, r); } }; 作者：Krahets 链接：https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/solutions/190476/mian-shi-ti-45-ba-shu-zu-pai-cheng-zui-xiao-de-s-4/快排模板public String minNumber(int[] nums) { String[] strs = new String[nums.length]; for (int i = 0; i < nums.length; i++) { strs[i] = String.valueOf(nums[i]); } quickSort(strs, 0, strs.length - 1); StringBuilder res = new StringBuilder(); for (String s : strs) res.append(s); return res.toString(); } public void quickSort(String[] strs, int low, int high) { if (low < high) { int middle = getMiddle(strs, low, high); quickSort(strs, low, middle - 1); quickSort(strs, middle + 1, high); } } public int getMiddle(String[] strs, int low, int high) { //数组的第一个数为基准元素 String temp = strs[low]; while (low < high) { //从后向前找比基准小的数 while (low < high && (strs[high] + temp).compareTo(temp + strs[high]) >= 0) high--; //把比基准小的数移到低端 strs[low] = strs[high]; //从前向后找比基准大的数 while (low < high && (strs[low] + temp).compareTo(temp + strs[low]) <= 0) low++; //把比基准大的数移到高端 strs[high] = strs[low]; } strs[low] = temp; return low; }51 数组中的逆序对在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。示例 1:输入: [7,5,6,4] 输出: 5题解class Solution { public: int reversePairs(vector<int>& nums) { vector<int> tmp(nums.size()); return mergeSort(0, nums.size()-1, nums, tmp); } private: int mergeSort(int l, int r, vector<int>& nums, vector<int>& tmp){ //终止条件 if(l>=r)return 0; //递归划分 int m = (l+r)/2; int res = mergeSort(l, m, nums, tmp) + mergeSort(m+1,r,nums,tmp); //合并阶段 int i=l, j= m+1;//左右子数组首个元素 for(int k = l;k<=r;k++) tmp[k]=nums[k];//辅助数组 for(int k=l;k<=r;k++){ if(i==m+1)//左子数组合并完成 nums[k]=tmp[j++]; else if(j==r+1||tmp[i]<=tmp[j]) nums[k]=tmp[i++];//排序过程 else{ nums[k]=tmp[j++];//排序过程 res+=m-i+1;//统计逆序对 } } return res; } };思路https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solutions/622496/jian-zhi-offer-51-shu-zu-zhong-de-ni-xu-pvn2h/
12（79） 矩阵中的路径给定一个 $m \times 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提示：$m == board.length$$n = board[i].length$$1 <= m, n <= 6$$1 <= word.length <= 15$$board$ 和 $word$ 仅由大小写英文字母组成题解class Solution { public: bool exist(vector<vector<char>>& board, string word) { rows = board.size(); cols = board[0].size(); for(int i=0;i<rows;i++){ for(int j=0;j<cols;j++){ if(dfs(board,word,i,j,0))return true; } } return false; } private: int rows, cols; bool dfs(vector<vector<char>>& board, string word, int i, int j, int k){ if(i>=rows || i<0 || j>=cols || j<0 || board[i][j]!=word[k])return false; if(k==word.size()-1)return true; board[i][j]='\0'; bool res=dfs(board, word, i+1, j, k+1) || dfs(board, word, i-1, j, k+1) || dfs(board, word, i, j+1, k+1) || dfs(board, word, i, j-1, k+1); board[i][j]=word[k]; return res; } };M13 机器人的运动范围地上有一个m行n列的方格，从坐标 $[0,0]$ 到坐标 $[m-1,n-1]$ 。一个机器人从坐标 $[0, 0] $的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？示例 1：输入：m = 2, n = 3, k = 1 输出：3示例 2：输入：m = 3, n = 1, k = 0 输出：1提示：$1 <= n,m <= 100$$0 <= k <= 20$题解class Solution { public: int movingCount(int m, int n, int k) { vector<vector<bool>> visited(m, vector<bool>(n,0)); return dfs(0,0,0,0,visited,m,n,k); } private: int dfs(int i, int j, int si, int sj, vector<vector<bool>> &visited, int m, int n, int k){ if(i>=m || j>=n || k<si+sj || visited[i][j])return 0; visited[i][j]=true; return 1+dfs(i+1, j, (i+1)%10!=0?si+1:si-8,sj,visited,m,n,k)+ dfs(i,j+1,si,(j+1)%10!=0?sj+1:sj-8,visited,m,n,k); } };38 字符串的排列输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。示例:输入：s = "abc" 输出：["abc","acb","bac","bca","cab","cba"]限制：1 <= s 的长度 <= 8题解class Solution { public: vector<string> permutation(string s) { dfs(s, 0); return res; } private: vector<string> res; void dfs(string s, int x){ if(x==s.size()-1){ res.push_back(s); return; } set<int> st; for(int i=x;i<s.size();i++){ if(st.find(s[i])!=st.end())continue;//重复则剪枝 st.insert(s[i]); swap(s[i], s[x]);//交换，将s[i]固定在x位 dfs(s, x+1);//固定x+1各字符 swap(s[i],s[x]);//恢复交换 } } };
11（154） 旋转数组的最小数字把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。示例 1：输入：numbers = [3,4,5,1,2] 输出：1示例 2：输入：numbers = [2,2,2,0,1] 输出：0提示：n == numbers.length1 <= n <= 5000-5000 <= numbers[i] <= 5000numbers 原来是一个升序排序的数组，并进行了 1 至 n 次旋转题解class Solution { public: int minArray(vector<int>& numbers) { int i = 0, j = numbers.size() - 1; while (i < j) { int m = (i + j) / 2; if (numbers[m] > numbers[j]) i = m + 1; else if (numbers[m] < numbers[j]) j = m; else j--; } return numbers[i]; } };53 - I 在排序数组中查找数字统计一个数字在排序数组中出现的次数。示例 1:输入: nums = [5,7,7,8,8,10], target = 8 输出: 2示例 2:输入: nums = [5,7,7,8,8,10], target = 6 输出: 0提示：0 <= nums.length <= 105-109 <= nums[i] <= 109nums 是一个非递减数组-109 <= target <= 109题解class Solution { public: int helper(vector<int>& nums, int tar) { int i = 0, j = nums.size() - 1; while(i<=j){ int m = (i+j)/2; if(nums[m]<=tar)i=m+1; else j = m-1; } return i; } int search(vector<int>& nums, int target) { return helper(nums, target) - helper(nums, target -1); } };53 - II 0~n-1中缺失的数字一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。示例 1:输入: [0,1,3] 输出: 2示例 2:输入: [0,1,2,3,4,5,6,7,9] 输出: 8限制：1 <= 数组长度 <= 10000题解class Solution { public: int missingNumber(vector<int>& nums) { int i = 0, j = nums.size()-1; while(i<=j){ int m = (i+j)/2; if(nums[m]==m) i=m+1; else j=m-1; } return i; } };（34）在排序数组中查找元素的第一个和最后一个位置题解class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { return {searchLeftOrRightBound(nums,target,"left"),searchLeftOrRightBound(nums,target,"right")}; } private: int searchLeftOrRightBound(vector<int>& nums, int target, const string& bound) { int left = 0, right = nums.size() - 1; int res = -1; while(left <= right){ int mid = (left + right) >> 1; if(nums[mid] < target){ left = mid+1; } else if(nums[mid]>target){ right = mid-1; } else{ res = mid; if(bound == "left"){ right = mid - 1; } else if(bound == "right"){ left = mid + 1; } else{ } } } return res; } };