网站建设的摘要怎么写,青岛品牌网站制作电话,闵行网站建设公司纸,wordpress注册模板下载这里写目录标题 day1 二叉树和为某一路径day2复杂链表的复刻day3二叉搜索树与双向链表day4数字排列day5找出出现次数超过一半的次数day6 二进制中1的个数day7 二叉树的最近公共祖先day8 字符串转换为整数day9 构建乘积数组day10不用加减乘除的加法day11求12....nday11 股票的最… 这里写目录标题 day1 二叉树和为某一路径day2复杂链表的复刻day3二叉搜索树与双向链表day4数字排列day5找出出现次数超过一半的次数day6 二进制中1的个数day7 二叉树的最近公共祖先day8 字符串转换为整数day9 构建乘积数组day10不用加减乘除的加法day11求12....nday11 股票的最大价值day13扑克牌的顺子day14骰子的点数day15滑动窗口的最大值 day1 二叉树和为某一路径 思路分析 初步想法这个题就是一个典型的爆搜问题我们最简单的一个想法就是搜索所有路径并求和进行判断所以我们可以使用dfs模板简化为了判断是否于tar相等我们需要每次递归时都传入sumtar两个参数我们可以将加法转化为减法与0进行比较在这里我们需要使用递归函数所以采用递归三步法进行分析定义终止条件单层逻辑 class Solution {static ListListInteger ans;static ListInteger resnew ArrayList();public ListListInteger findPath(TreeNode root, int sum) {ansnew ArrayList();dfs(root,sum);return ans;}//1.定义:对路径进行搜索无返回值public static void dfs(TreeNode root,int sum){//2.递归终止条件当传入节点为null时则无需进行下一步递归。if(rootnull)return;//如果为null则直接返回//3.单层逻辑res.add(root.val);//3.1将该值加入ressumsum-root.val;//3.2并用sum减去该值//3.3判断此时的节点是否符合要求//**********重点**********/*为什么在ans.add(new ArrayList(res)) 要重新建立一个list*答:在该题中res为成员变量所有的方法共享一个指向同一地址*如果直接加入在后续语句中依旧会修改res导致其答案不一样**/if(root.leftnull root.rightnull sum0)ans.add(new ArrayList(res));//3.4递归处理左右子树dfs(root.left,sum);dfs(root.right,sum);res.remove(res.size()-1);//恢复现状如果该条路不同则退出该值}
day2复杂链表的复刻 思路分析 首先我们可以使用hash表存储每个点对应的来next指针 random指针而后复现在这里我们还有另一种做法 1. 在每个点对应的后面复制每一个点 2. 遍历链表处理random指针 3. 将这两条互相交叉的链分开必须将原有链恢复原样不然会报错 class Solution {public ListNode copyRandomList(ListNode head) {//1.在原链表的每一个节点后加上节点的复制if(headnull)return null;for(ListNode p head ; p ! null;){ListNode q new ListNode(p.val);//防止断链ListNode next p.next;p.next q;q.next next;p next;}//2.将新加入的节点的random指针指向原链表的random指针for(ListNode p head ; p ! null ; p p.next.next){if(p.random ! null){//新节点的random指针指向原节点random指针指向的下一个节点p.next.random p.random.next;}}//3.将两条链分开ListNode dummy new ListNode(-1);ListNode cur dummy;for(ListNode p head; p ! null; p p.next){cur.next p.next;cur cur.next;// 前面破坏了原head链表恢复链表p.next p.next.next;
}return dummy.next;}
}day3二叉搜索树与双向链表 思路分析 我们可以知道对于一个二叉搜索树中序遍历与有序列表的元素顺序相同所以我们在这里使用中序遍历的模板对于中序遍历会先重最左边的节点4开始处理 class Solution {//指针用来记录前一个节点·static TreeNode prenull;public TreeNode convert(TreeNode root) {if(rootnull)return null;dfs(root);while(root.left!null)rootroot.left;return root;}//我们一第一个节点4[6]来讲解这个单层逻辑 //1.函数定义将二叉搜索树变为有序的双向链表无返回值public static void dfs(TreeNode root){//2.递归终止条件若节点为空则结束if(rootnull)return;dfs(root.left);//由于中序遍历所以root 会依次是 4 6 8 10 .。。。root.leftpre;// null—4(-6)[4—6]if(pre!null)pre.rightroot;//pre为空不执行 [4—(——)6]preroot;//pre4;[pre6]dfs(root.right);}}day4数字排列 思路分析 很容易知道这里应该使用回溯算法求解很经典 class Solution {static ListInteger path;static boolean[] st;//该数是否被使用static SetListInteger res;static int n;public ListListInteger permutation(int[] nums) {pathnew ArrayList();stnew boolean[nums.length];resnew HashSet();nnums.length;dfs(0,nums);ListListInteger ansnew ArrayList(res);return ans;}public static void dfs(int u,int[] nums){if(un){res.add(new ArrayList(path));return;}for(int i0;in;i){if(!st[i]){path.add(nums[i]);st[i]true;dfs(u1,nums);st[i]false;path.remove(path.size()-1);}}}
}day5找出出现次数超过一半的次数 class Solution {public int moreThanHalfNum_Solution(int[] nums) {int cnt1,valnums[0];for(int i0;inums.length;i){if(nums[i]val)cnt;else cnt--;//如果出现问题则进行重置if(cnt0){valnums[i];cnt1;}}return val;}
}测试例子解析 例1input[1,2,1,1,3] i0nums[i]1val1cnt2 i1nums[i]2val1cnt1 i2nums[i]1val1cnt2 i3nums[i]1val1cnt3 i4nums[i]3val1cnt2 例2input[2,0,1,1,3] i0nums[i]2val2cnt2 i1nums[i]0val2cnt1 i2nums[i]1val2cnt0重置val1cnt1 i3nums[i]1val1cnt2 i4nums[i]3val1cnt1 day6 二进制中1的个数 基本知识点
计算机中数的二进制表示 3:00000011 -3:使用补码进行表示 先计算-3绝对值的二进制 00000011 取反11111100 加111111101这就是计算级的-3表示 无符号整数计算机里的数是用二进制表示的最左边的这一位一般用来表示这个数是正数还是负数这样的话这个数就是有符号整数。无符号整数包括0和正数。 举例假设有一个 数据类型有8位组成 无符号整数8位全部表示数值范围位[0,2^8-1] 有符号整数最左边表示符号后7位表示数值范围[-111 1111,111 1111] 位运算 un1:将二进制的个位取出 un1:将个位删掉 思路分析 如果n位正数0我们直接挨个将每一位数字取出计算即可 负数我们可以将负数先转换位无符号整数在进行与正数相同操作 class Solution {public int NumberOf1(int n) {int res0;int unn 0xffffffff;//将数字转换为无符号整数0xffffffff表示32个1while(un!0){resres(un1);unun1;}return res;}
}day7 二叉树的最近公共祖先
这里推荐一个大佬的题解 大佬题解非常详细有用 思路分析 day8 字符串转换为整数 思路分析 按照以下步骤就可以 最前面的空格判断符号数位相乘计算整数char 转换位数字 char-‘0’ class Solution {public int strToInt(String str) {long res0;char[] chstr.toCharArray();int k0;//去除空格while(kch.length ch[k] )k;int flag1;if(kch.length ch[k]-){flag-1;k;}else if(kch.length ch[k]) k;// System.out.println(kch.length ch[k]0 ch[k]9);while(kch.length ch[k]0 ch[k]9){// System.out.println(ch[k]-0);resres*10(ch[k]-0);if (res 1e11) break;k;}// System.out.println(res);res(res*flag);if (res Integer.MAX_VALUE) res Integer.MAX_VALUE;if (res Integer.MIN_VALUE) res Integer.MIN_VALUE;return (int)res;}
}day9 构建乘积数组 思路分析 B[i]主要由 A[0,i] 与A[i1,n-1] 两个连续部分组成 [0,i-1]的计算 B[i-1]A[0]…*A[i-2] B[i] A[0]… *A[i-2] * A[i-1] 观测可知 B[i]B[i-1]*A[i-1] 在后半部分计算有着同样的规律所以我们可以利用两个循环来实现答案的计算
class Solution {
/*分析可知
*1.B[i]的乘积有两部分组成[0,i-1]与[i1,r]
*2.我们可以注意到在计算[0,i-1]部分上的B[i]乘积时可以利用前一个B[i-1]*a[i-1]得到
*3.第二部分倒序计算时有着相同的规律
*5.所以我们可以利用两次循环来获得结果
*/public int[] multiply(int[] A) {int[] ansnew int[A.length];if(A.length0)return ans;ans[0]1;//循环计算第一部分for(int i1;iA.length;i){ans[i]ans[i-1]*A[i-1];}//计算第二部分循环int tmp1;//tmp记录前一个循环的值for(int iA.length-2;i0;i--){tmptmp*A[i1];ans[i]*tmp;}return ans; }
}day10不用加减乘除的加法 思路分析
这里我们利用位运算来求解位运算根据值的不同可以分为4种情况 | a(i) | b(i) | c(i) | c(i1) | | ---- | ---- | ---- | ------ | | 0 | 0 | 0 | 0 | | 0 | 1 | 1 | 0 | | 1 | 0 | 1| 0 | | 1 | 1 | 0 | 1 |本位当两个同为1/0时等于0否则为1即 本位 为 a^b进位两个数同为 1 时 为1 所以 进位 为 ab我们可以类比10进制当知道10位数为a个位数为b— (a*10b ) 同理二进制即为ab1a^b; 由于不能用加法我们可以多次循环值进位为0则此时的 非进位即所求答案 大佬详解
class Solution {public int add(int num1, int num2) {if(num20)return num1;return add(num1^num2,(num1num2)1);}
}day11求12…n 思路分析
根据题意不能使用循环和乘除法所以很容易想到使用递归最小子问题 n1 return 1单层逻辑ngetSum(n-1)
class Solution {public int getSum(int n) {if(n1)return 1;return ngetSum(n-1);}
}day11 股票的最大价值 思路分析
状态表示 状态集合前i个元素中任选两个元素的所有选法属性序号后-序号前的最大值 状态计算 不包含 nums[i] 最大值为 dp[i-1]包含nums[i] 最大值 为 nums[i]-min(前i个元素的最小值)
所以状态转移方程为 dp[i]Math.max(dp[i-1],nums[i]-min)
day13扑克牌的顺子
day14骰子的点数
day15滑动窗口的最大值
