Lyuyk's Blog - CS
type: channel
link: https://lyuyk.com/category/ComputerScience/
items: 【CS】Git相关
items: 【Vue】小记
items: 【LeetCode】剑指Offer——其它
items: 【LeetCode】剑指Offer——位运算
items: 【LeetCode】剑指Offer——数学
items: 【LeetCode】剑指Offer——动态规划
items: 【LeetCode】剑指Offer——排序
items: 【LeetCode】剑指Offer——搜索
items: 【LeetCode】剑指Offer——分治
items: 【LeetCode】剑指Offer——二分查找

【CS】Git相关
type: item
date: 2023-10-06T09:06:00+00:00
description: ## 创建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

【Vue】小记
type: item
date: 2023-07-27T03:25:00+00:00
description: 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 关键字，你可以将函数 …

【LeetCode】剑指Offer——其它
type: item
date: 2023-04-15T01:11:02+00:00
description: 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-…

【LeetCode】剑指Offer——位运算
type: item
date: 2023-04-12T10:22:06+00:00
description: 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) …

【LeetCode】剑指Offer——数学
type: item
date: 2023-04-12T08:13:13+00:00
description: 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/

【LeetCode】剑指Offer——动态规划
type: item
date: 2023-04-11T14:41:40+00:00
description: 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(re…

【LeetCode】剑指Offer——排序
type: item
date: 2023-04-10T13:30:59+00:00
description: 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-…

【LeetCode】剑指Offer——搜索
type: item
date: 2023-04-07T03:31:00+00:00
description: 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 字符串的排列输入一个字符串，打印出该字符串中字符的…

【LeetCode】剑指Offer——分治
type: item
date: 2023-04-06T13:01:45+00:00
description: 35（50） 数值的整数次方实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。示例 1：输入：x = 2.00000, n = 10 输出：1024.00000示例 2：输入：x = 2.10000, n = 3 输出：9.26100示例 3：输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25提示：-100.0 < x < 100.0-231 <= n <= 231-1n 是一个整数-104 <= xn <= 104题解class Solution { public: double myPow(double x, int n) { long long b = n; double res = 1.0; while(b){ if(b<0){ x=1/x; b=-b; } //按位与判断 if( b&1 == 1){ res=res*x; } x=x*x; b>>=1; //右移即删除最后一位 } return res; } };

【LeetCode】剑指Offer——二分查找
type: item
date: 2023-04-06T04:20:00+00:00
description: 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){…