目录

zrlong 的个人博客

希望大家都能保护好自己身上的特质,无论是五年还是十年,永远善良,不服输,热爱你所热爱。在漫长岁月的变迁里,是这些让你永远迷人,富有生命力。

标签: 算法 (6)

约瑟夫环 有更新!

约瑟夫问题 约瑟夫问题是个著名的问题:N个人围成一圈,第一个人从1开始报数,报M的将被杀掉,下一个人接着从1开始报。如此反复,最后剩下一个,求最后的胜利者。 解决方法 模拟法 刚学数据结构的时候,我们可能用链表的方法去模拟这个过程,N个人看作是N个链表节点,节点1指向节点2,节点2指向节点3,……,节点N-1指向节点N,节点N指向节点1,这样就形成了一个环。然后从节点1开始1、2、3……往下报数,每报到M,就把那个节点从环上删除。下一个节点接着从1开始报数。最终链表仅剩一个节点。它就是最终的胜利者。 缺点 可以想象如果数据量特别大时,算法的时间复杂度非常高,高达O(nm)。 公式法 既然没办法暴力解决,那我们就来找找其中的规律。 // 我们规定数到三的人出圈 // 当有1个人时,最终留下来的下标为0 f(1,3) = 0; // 当有2个人时,最终留下来的下标为1 f(2,3) = 1; // 当有3个人时,最终留下来的下标为1 f(3,3) = 1; // 当有4个人时,最终留下来的下标为0 f(4,3) = 0; // 当有5个人时,最终留下来的下标为3 f(5,3....

又被妙到了之位运算 有更新!

起因 今天写了一道分组位运算,让我再次感受到了位运算的奇妙。我整理的时候在想,会不会出现数组中有三个相同数的情况,整理完,我打开下一道题,真的是三个数的!这可把我难住了。我只想到了遍历,把所有出现的数的二进制各个数位相加,最后除以三取余。看到了别人的解析,我真是佩服的五体投地。 题目 剑指 Offer 56 - II. 数组中数字出现的次数 II - 力扣(LeetCode) (leetcode-cn.com) 在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。 解析 有限状态自动机 二进制的各位进制规则相同,因此考虑一位就可以了。对于所有数字中的某二进制位 1 的个数,存在 3 种状态,即对 3 余数为 0, 1, 2。 输入二进制位1,则状态按如下顺序转换 输入二进制位0,则状态不变 0→1→2→0→⋯ 一位二进制只能表示两种状态,因此我们需要二位二进制来表示三种状态。设高位为two ,低位为one。则状态转换为: 对于单个二进制位的位运算的一些特点: 异或运算:x ^ 0 = x , x ^ 1 = ~x 与运算....

妙妙妙的分组位运算

写在前面的位运算知识点 与运算 按位与运算符(&) 参加运算的两个数,按二进制位进行“与”运算。 运算规则:只有两个数的二进制同时为1,结果才为1,否则为0。(负数按补码形式参加按位与运算) 即 0 & 0= 0 ,0 & 1= 0,1 & 0= 0, 1 & 1= 1。 例:3 &5 即 00000011 & 00000101 = 00000001 ,所以 3 & 5的值为1。 或运算 按位或运算符(|) 参加运算的两个数,按二进制位进行“或”运算。 运算规则:参加运算的两个数只要两个数中的一个为1,结果就为1。 即 0 | 0= 0 , 1 | 0= 1 , 0 | 1= 1 , 1 | 1= 1 。 例:2 | 4 即 00000010 | 00000100 = 00000110 ,所以2 | 4的值为 6 。 异或运算 异或运算符(^) 参加运算的两个数,按二进制位进行“异或”运算。 运算规则:参加运算的两个数,如果两个相应位为“异”(值不同),则该位结果为1,否则为0。 即 0 ^ 0=0 , 0 ^ ....

区间dp 有更新!

什么是区间dp? 顾名思义:区间dp就是在区间上进行动态规划,求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。 思路 既然让我们求一个区间上的最优解,那我们就可以把一个长区间分为许多个小区间,求出每个小区间的最优解,然后再合并。 伪代码 for(int len = 1;len <= n;len++){//枚举长度 for(int j = 1;j + len - 1 <= n;j++){//枚举起点,ends<=n int ends = j + len - 1; for(int i = j;i < ends;i++){//枚举分割点,更新小区间最优解 dp[j][ends] = min(dp[j][ends],dp[j][i] + dp[i+1][ends] + something); } } } 经典例题 [石子合并](石子合并 - 蓝桥云课 (lanqiao.cn)) 根据区间dp的思想我们可以得出状态转移方程 dp[i][j] = Math.min(dp[i][j],dp[i][k] + dp[k + ....

N皇后

题目描述 n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。 给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。 class Solution { public List<List<String>> solveNQueens(int n) { List<List<String>> ans = new ArrayList<>(); //记录每行皇后摆放位置 int[] arr = new int[n]; queen(n,0,arr,ans); return ans; } //判断是否冲突 public static boolean judge(int m,int[] arr){ for(int i=0;i<m;i++){ //判断是否在同一列或者在斜线上 if(arr[i] == arr[m] || M....

最大最小公倍数 有更新!

题目描述 已知一个正整数 N,问从 1~N中任选出三个数,他们的最小公倍数最大可以为多少。 输入描述 输入一个正整数 N。 1≤N≤10^6。 输出描述 输出一个整数表示答案。 输入输出样例 示例 1 输入 9 输出 504 这个题分四种情况: 1.小于2的直接输出n 2.n为偶数,且不为3的倍数,输出ans = n * (n - 1) * (n - 3),因为如果n可以被2整除,那么n - 2也会被2整除,n和n- 2就不是互质了; 3.n为偶数,且为3的倍数,输出ans = (n - 1) * (n - 2) * (n - 3),因为如果n可以被3整除,那么n - 3也会被3整除,n和n- 3就不是互质了; 4.n为奇数,输出ans = n * (n - 1) * (n - 2),因为这三个数之间两两互质; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); //在此....