只记录感觉比较有趣的题
1.二叉树合并
Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
INPUT:[1,3,2,5][2,1,3,null,4,null,7]
OUTPUT:[3,4,5,5,4,null,7]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
/* Current Node have 4 Condition
* 【NotNull && NotNull】 【Null && NotNull】 【NotNull && Null】 【Null && Null】
* If return t1 means you only concern about condition 1 and 2,3,4 are not matter
*/
if(t1!=null&&t2!=null){
t1.val += t2.val;
if(t1.left==null&&t2.left!=null){
t1.left = t2.left;
}else if(t1.left!=null&&t2.left!=null){
mergeTrees(t1.left,t2.left);
}
if(t1.right==null&&t2.right!=null){
t1.right = t2.right;
}else if(t1.right!=null&&t2.right!=null){
mergeTrees(t1.right,t2.right);
}
}else if(t1==null&&t2!=null){
t1 = t2;
}
return t1;
}
}
Result:85/85 Time:6ms
2.计算汉明距离
汉明距离
between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, calculate the Hamming distance.
INPUT:1,4
OUTPUT:2
/*
* 原本我是用除2取余右移，但相比直接或运算，慢太多了，没想到啊
*/
class Solution {
public int hammingDistance(int x, int y) {
int n = x^y;
int setBits = 0;
while(n>0){
setBits += n&1;
n >>= 1;
}
return setBits;
}
}
3.DI字符串匹配
Given a string S that only contains “I” (increase) or “D” (decrease), let N = S.length.
Return any permutation A of [0, 1, …, N] such that for all i = 0, …, N-1:
If S[i] == “I”, then A[i] < A[i+1]
If S[i] == “D”, then A[i] > A[i+1]
INPUT:”IDID”
OUTPUT:[0,4,1,3,2]
/*
* 几乎是最优的办法
*/
class Solution {
public int[] diStringMatch(String S) {
int len = S.length();
int[] result = new int[len+1];
int min=0,max=len;
for(int i = 0;i<len;i++){
result[i] = S.charAt(i) == 'I' ? min++:max--;
}
result[len] = max;
return result;
}
}
4.二叉树最大深度
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
int i = 0;
return searchTreeNode(root,i);
}
public int searchTreeNode(TreeNode node,int depth){
int leftDepth,rightDepth;
if(node!=null){
depth++;
leftDepth = searchTreeNode(node.left,depth);
rightDepth = searchTreeNode(node.right,depth);
depth = leftDepth > rightDepth ? leftDepth : rightDepth;
}
return depth;
}
}
5.求单次出现的数字
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?要求空间要极度小
class Solution {
public int singleNumber(int[] nums) {
int a = 0;
//思想就是用异或，异或两次还是会恢复原来的值这个思想，保证会恢复，妙啊
for (int n : nums) a ^= n;
return a ;
}
}
原来我是用HashSet在第二次出现就移除那个点，到最终HashSet中只有一个数字就是那个SingleNum,但是对比这种方法还是太笨了，位运算是真滴6
6.移动0
Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.
class Solution {
public void moveZeroes(int[] nums) {
if(nums == null || nums.length == 0) return;
int k = -1;
for(int i = 0; i < nums.length; i++) {
if(nums[i] != 0) {
//k为非0的索引,一步到位直接把非数字移动到应该在的位置
nums[++k] = nums[i];
}
}
//最终0-k则为所有非0的内容,k+1到length再补上0
for(int i = k + 1; i < nums.length; i++) {
nums[i] = 0;
}
}
}
把重点放在非0而不是0，用一个索引作为维护非0的位置，达到无论中间多少个0都能一步到位到达非0的最大位置，最终才填充0，这是最优的办法了(自己有想到这个思路，但是复杂化了，把重点注重在0的位置，用k维护是最简单直接的方法)
7.不用+-实现两数之和
class Solution {
public int getSum(int a, int b) {
return (a&b)==0 ? a^b : getSum( (a&b)<<1, a^b );
}
}
8. Shortest Distance to a Character
双向前进求距离，当当前最近一个C的位置是未知时，先把距离设为MAXVALUE，因为反向遍历时会填满。只记录前进中最后一个查到的C的距离，达到自动最近的作用。
class Solution {
public int[] shortestToChar(String S, char C) {
int[] res = new int[S.length()];
if(S == null || S.length() == 0) return res;
char[] c = S.toCharArray();
int prev = -1;
for(int i = 0; i < c.length; i++) {
if(c[i] == C) {
prev = i;
}
res[i] = prev == -1 ? Integer.MAX_VALUE : i - prev;
}
prev = Integer.MAX_VALUE;
for(int i = c.length-1; i >= 0; i--) {
if(c[i] == C) {
prev = i;
}
res[i] = Math.min(res[i], prev - i);
}
return res;
}
}