1. 两数之和(1)
给定一个整数数组 nums
和一个整数目标值 target
,请你在该数组中找出 和为目标值 target
的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
思想:哈希表
class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < nums.length; ++i) { if (map.containsKey(target - nums[i])) { return new int[]{map.get(target - nums[i]), i}; } map.put(nums[i], i); } return new int[0]; } }
2. 有序列表转换二叉搜索树 (109)
给定一个单链表的头节点 head
,其中的元素 按升序排序 ,将其转换为高度平衡的二叉搜索树。
二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。
思想:分值,left,mid,right指针
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { ListNode globalHead; public TreeNode sortedListToBST(ListNode head) { globalHead =head; int length = getLength(head); return buildTee(0,length-1); } private TreeNode buildTee(int left , int right) { if (left>right){ return null; } int mid = (left+right)/2; TreeNode root = new TreeNode(); root.left = buildTee(left,mid-1); root.val = globalHead.val; globalHead = globalHead.next; root.right = buildTee(mid+1,right); return root; } private int getLength(ListNode head) { int ret = 0; while(head!=null){ ret++; head =head.next; } return ret; } }
3. 扰乱字符串 (87)
使用下面描述的算法可以扰乱字符串 s
得到字符串 t
:
- 如果字符串的长度为 1 ,算法停止
- 如果字符串的长度 > 1 ,执行下述步骤:
- 在一个随机下标处将字符串分割成两个非空的子字符串。即,如果已知字符串
s
,则可以将其分成两个子字符串x
和y
,且满足s = x + y
。 - 随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即,在执行这一步骤之后,
s
可能是s = x + y
或者s = y + x
。 - 在
x
和y
这两个子字符串上继续从步骤 1 开始递归执行此算法。
- 在一个随机下标处将字符串分割成两个非空的子字符串。即,如果已知字符串
给你两个 长度相等 的字符串 s1
和 s2
,判断 s2
是否是 s1
的扰乱字符串。如果是,返回 true
;否则,返回 false
。
思想:动态规划
显然「扰乱字符串」的关系是具有对称性的,即如果 s1是 s2的扰乱字符串,那么 s2是 s1的扰乱字符串。为了叙述方便,我们称这种情况下,s1和 s2是「和谐」的。
如果 s1=s2,那么它们是「和谐」的;如果 s1和 s2的长度不同,那么它们一定不是「和谐」的;如果 s1中某个字符 c出现了 x1次,而 c在 s2中出现了 x2次,且 x1≠x2,那么它们一定不是「和谐」的。
class Solution { int [][][] memo; String s1,s2; public boolean isScramble(String s1, String s2) { int length = s1.length(); this.memo = new int[length][length][length+1]; this.s1=s1; this.s2=s2; return dfs(0,0,length); //一开始如果不和谐,则不会进行子串比较 } private boolean dfs(int i1, int i2, int length) { if (memo[i1][i2][length] != 0){ return memo[i1][i2][length]==1; //如果是0 表明还么开始比较 } // 判断两个子串是否相等 if (s1.substring(i1,i1+length) .equals(s2.substring(i2,i2+length))){ memo[i1][i2][length]=1; return true; } // 判断是否存在字符 c 在两个子串中出现的次数不同 if(!checkSame(i1,i2,length)){ memo[i1][i2][length]=-1; return false; } //因为两字符串长度是相同的 // 枚举分割位置,i是切分长度 for (int i = 1; i <length ; i++) { //不交换的情况, i1,i2是两个字符串的切分起始点 if (dfs(i1,i2,i) && dfs(i1+i,i2+i,length-i)){ memo[i1][i2][length]=1; return true; } //交换 if (dfs(i1,i2+length-i,i) && dfs(i1+i,i2,length-i)){ memo[i1][i2][length]=1; return true; } } memo[i1][i2][length]=-1; return false; } private boolean checkSame(int i1, int i2, int length) { HashMap<Character, Integer> map = new HashMap<Character, Integer>(); for (int i = i1; i <i1+length ; i++) { char c = s1.charAt(i); map.put(c,map.getOrDefault(c,0)+1); } for (int i = i2; i <i2+length ; i++) { char c = s2.charAt(i); map.put(c,map.getOrDefault(c,0)-1); } for (Map.Entry<Character, Integer> entry : map.entrySet()) { int value = entry.getValue(); if (value!=0){ return false; } } return true; } }
4. 位1 的个数 (191)
编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 '1' 的个数(也被称为汉明重量)
思想: 位操作
class Solution { // you need to treat n as an unsigned value public int hammingWeight(int n) { int num = 0; while (n!=0){ num+= n&1; //只比较最后一位 011111& 00001 = 000001 011110& 00001 = 000000 n=n>>>1; //无符号右移一位 } return num; } }
5. 分裂二叉树的最大乘积
给你一棵二叉树,它的根为 root
。请你删除 1 条边,使二叉树分裂成两棵子树,且它们子树和的乘积尽可能大。
由于答案可能会很大,请你将结果对 10^9 + 7 取模后再返回。
思想: 深度遍历
int avg, half;// avg:整棵树总值的中间值 half:真正的中间值 public int maxProduct(TreeNode root) { int total = getTotal(root); // 获取这棵树总值 avg = total/2; half=total; //优化half 使它不断接近整棵树一半的值 getTotal(root); return (int)((long)half*(total-half)%(1e9+7)); } private int getTotal(TreeNode root) { if (root==null){ return 0; } int val = root.val+getTotal(root.left)+getTotal(root.right); //遍历到当前节点 对比其它节点 更接近中间值,把节点当作树 if (Math.abs(val-avg)<Math.abs(half-avg)){ half =val; } return val; }
标签:return,val,int,length,918,TreeNode,打卡,root From: https://www.cnblogs.com/forever-fate/p/17711922.html