397 核心思想应该是尽量减少奇数操作
public static int integerReplacement(int n) {
if (n == Integer.MAX_VALUE){
return 0;
}
int k = 0;
int result = 0;
while (n !=1){
System.out.println(Integer.toBinaryString(n));
if ((n&1)==0){
n>>=1;
}else {
if (n == 3){
n--;
} else if (((n>>(k+1)) & 1 ) == 0){
n--;
}else {
n++;
}
}
result++;
}
return result;
}
477 汉明距离总和
我的解法是这样
public static int totalHammingDistance(int[] nums) {
int max = Integer.MIN_VALUE;
for (int num : nums) {
max = Math.max(max,num);
}
int result = 0;
Integer len = Integer.toBinaryString(max).length();
int total = nums.length;
for (int i = 0; i < len ; i++) {
int c = 0;
for (int num : nums) {
if ( ((num>>i) & 1) == 0){
c++;
}
}
result+=( (total-c)*c);
}
return result;
}
784 字母大小写全排列
暴力解法如下，效率低，但是我看官方给的几种答案复杂度都和我这个一样。。。。
public static List<String> letterCasePermutation(String S) {
List<String> list = new ArrayList<>();
if (S.length() == 0){
return list;
}
for (int i = 0; i < S.length(); i++) {
char c = S.charAt(i);
if (i == 0){
if (c>='0' && c <= '9'){
list.add(c+"");
}else {
list.add(Character.toLowerCase(c)+"");
list.add(Character.toUpperCase(c)+"");
}
continue;
}
List<String> tp = new ArrayList<>();
for (String s : list) {
if (c>='0' && c <= '9'){
tp.add(s+c);
}else {
tp.add(s+Character.toLowerCase(c));
tp.add(s+Character.toUpperCase(c));
}
}
list = tp;
}
return list;
}
898 和上题有点像
public static int subarrayBitwiseORs(int[] arr) {
Set<Integer> set = new HashSet<>();
Set<Integer> res = new HashSet<>();
for (int i = 0; i < arr.length; i++) {
int k = arr[i];
Set<Integer> tps = new HashSet<>();
for (Integer p : set) {
tps.add(p|k);
}
tps.add(k);
set = tps;
res.addAll(set);
}
return res.size();
}
100
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
return check(p,q);
}
private static boolean check(TreeNode p,TreeNode q){
if ((p != null && q == null) || (p == null && q != null)){
return false;
}
if (p == null && q == null){
return true;
}
if (p.val != q.val ){
return false;
}
if (!check(p.left,q.left)){
return false;
}
if (!check(p.right,q.right)){
return false;
}
return true;
}
}
101
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null){
return true;
}
return check(root.left,root.right);
}
public static boolean check(TreeNode p,TreeNode q) {
if ((p != null && q == null) || (p == null && q != null)){
return false;
}
if (p == null && q == null){
return true;
}
if (p.val != q.val ){
return false;
}
if (!check(p.left,q.right)){
return false;
}
if (!check(p.right,q.left)){
return false;
}
return true;
}
}
104
class Solution {
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
return check(root,1);
}
public int check(TreeNode p,int level) {
if (p == null){
return level-1;
}
return Math.max(check(p.left, level + 1), check(p.right, level + 1));
}
}
108
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return setVal(0,nums.length-1,nums);
}
public static TreeNode setVal(int left,int right,int[] nums){
if (left>right){
return null;
}
int len = (left+right)/2;
TreeNode node = new TreeNode(nums[len]);
TreeNode leftNode = setVal(left, len-1, nums);
node.left = leftNode;
TreeNode rightNode = setVal(len+1, right, nums);
node.right = rightNode;
return node;
}
}
110 判断平衡二叉树
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
int level = getLevel(root.left);
int level1 = getLevel(root.right);
if (level == -1 || level1 == -1){
return false;
}
return Math.abs(level-level1) <=1;
}
public static int getLevel(TreeNode root){
if (root == null)return 0;
int left = getLevel(root.left);
int right = getLevel(root.right);
if (left == -1 || right == -1){
return -1;
}
if (Math.abs(left-right) >1){
return -1;
}
return Math.max(left+1,right+1);
}
}
111 这题注意nil节点不是子节点
class Solution {
public int minDepth(TreeNode root) {
if(root == null){
return 0;
}
int left = check(root.left, 1);
int right = check(root.right, 1);
if(root.left != null && root.right != null){
return Math.min(left,right);
}
if(root.left != null){
return left;
}else{
return right;
}
}
public int check(TreeNode p,int level) {
if (p == null){
return level;
}
int left = check(p.left, level + 1);
int right = check(p.right, level + 1);
if(p.left != null && p.right != null){
return Math.min(left,right);
}
if(p.left != null){
return left;
}else{
return right;
}
}
}
112 路径总和
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null){
return false;
}
if (root.left == null && root.right == null && root.val == targetSum){
return true;
}
if (root.left != null && count(root.left,root.val,targetSum) ){
return true;
}
if (root.right != null && count(root.right,root.val,targetSum) ){
return true;
}
return false;
}
public static boolean count(TreeNode root,int score,int target){
int co = score+root.val;
if (root.left != null && count(root.left,co,target)){
return true;
}
if (root.right != null && count(root.right,co,target)){
return true;
}
if (root.left == null && root.right == null && co == target){
return true;
}
return false;
}
}
226 反转二叉树
我能写出来，所以我离进谷歌就只差一个homebrew了吗
class Solution {
public TreeNode invertTree(TreeNode root) {
invert(root);
return root;
}
private static void invert(TreeNode treeNode){
if (treeNode == null){
return;
}
TreeNode left = treeNode.left;
TreeNode right = treeNode.right;
treeNode.left = right;
treeNode.right = left;
invert(left);
invert(right);
}
}
235 最近公共父节点
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int k = root.val;
if ((k-p.val)*(k-q.val) <=0){
return root;
}
return lowestCommonAncestor((k-p.val)>0?root.left:root.right,p,q);
}
}
257
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>();
if(root == null){
return result;
}
if (root.left == null && root.right == null){
result.add(root.val+"");
return result;
}
find(root.left,result,root.val+"");
find(root.right,result,root.val+"");
return result;
}
public static void find(TreeNode root, List<String> result,String current){
if (root == null){
return;
}
if (root.left == null && root.right == null){
result.add(current+"->"+root.val);
return;
}
find(root.left,result,current+"->"+root.val);
find(root.right,result,current+"->"+root.val);
}
}