LeetCode

记录一些LeetCode上不错的题

Sum of Two Integers - 不用加减乘除运算符计算加法 

1
2
3
4
5
6
public class Solution {
    public int getSum(int a, int b) {
		int tempResult = a & b;
		return tempResult == 0 ? a ^ b : getSum(tempResult << 1, a ^ b);     
    }
}

A&B – 确定进位位 / A^B – 不带进位加

Add Digits - 不断计算数字各项项加,最终只剩一位时,返回该数字

1
2
3
4
5
public class Solution {
    public int addDigits(int num) {
        return num == 0 ? 0 : (num % 9 == 0 ? 9 : (num % 9));
    }
}

因为ab%9%9%9==ab%9, 故只需return num%9; 特殊情况为num==0 or num==9

Longest Palindrome - 字符串所有字符可构成最大回文数长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
	public int longestPalindrome(String s) {
		if (s == null)
			return 0;
		HashSet<Character> set = new HashSet<Character>();
		for (int i = 0; i < s.length(); i++) {
			if (set.contains(s.charAt(i))) {
				set.remove(s.charAt(i));
			} else {
				set.add(s.charAt(i));
			}
		}
		int temp = s.length() - set.size();
		
		return set.size() > 0 ? temp + 1 : temp;
	}
}

主要依据Set集合元素的唯一性

Convert a Number to Hexadecimal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    
    char[] map = {'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
    
    public String toHex(int num) {
        if(num == 0) return "0";
        String result = "";
        while(num != 0){
            result = map[(num & 15)] + result; 
            num = (num >>> 4);
        }
        return result;
    }
    
}

转换为十六进制、>>>无符号右移,左边填充0

ClimbingStairs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
		int a = 1;
		int b = 1;
		if (n < 2) {
			return a;		
		}
		for (int i = 2; i < n + 1; i++) {
			a = a + b;
			b = a - b;
		}
		return a;
    }
}

每次可以走1步或者2步,计算最终到达n的所有方式数目
实际是斐波那契数列问题
因为走到第n步,是由第n-1步再一次走1步或者第n-2步再一次走2步
所以,PathToStep(n) = PathToStep(n-1) + PathToStep(n-2)

House Robber

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int rob(int[] nums) {
		if (nums.length == 0)
			return 0;
		if (nums.length == 1)
			return nums[0];
			
		int[] mark = new int[nums.length];
		
		mark[0] = nums[0];
		mark[1] = Math.max(nums[0], nums[1]);
		
		for (int i = 2; i < nums.length; i++) {
			mark[i] = Math.max(nums[i] + mark[i - 2], mark[i - 1]);
		}
		return mark[nums.length - 1];     
    }
}

动态规划问题,数组不相邻数的最大累计和
mark[i] = Math.max(nums[i] + mark[i - 2], mark[i - 1]);

PowerOfNum

1
2
3
4
5
6
7
8
9
10
public class Solution {
	public boolean isPowerOfNum1(int num, int n) {
		return Integer.toString(num, n).matches("10*");
	}
	public boolean isPowerOfNum2(int num, int n) {
		return (Math.log10(num) / Math.log10(n)) % 1 == 0;
	}
}

判断num是否是n的次方数的二种方式

Arranging Coins

1
2
3
4
5
public class Solution {
    public int arrangeCoins(int n) {
        return (int)(Math.sqrt(2*(long)n + 0.25) - 0.5);
    }
}

第1层1个、后面每一层比上一层多一个,累加和,输入n为总数,返回能构成的最大层数
容易想到的是从1开始验证,然后就很明显的超时了,其实是解方程,反解出层数
((x+1)x)/2=n ,解方程x^2 + x = 2 n 解得：x = sqrt(2 * n + 0.25) - 0.5

Pascal’s Triangle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
	public List<List<Integer>> generate(int numRows) {
		List<List<Integer>> allrows = new ArrayList<List<Integer>>();
		ArrayList<Integer> row = new ArrayList<Integer>();
		for (int i = 0; i < numRows; i++) {
			row.add(0, 1);
			for (int j = 1; j < row.size() - 1; j++)
				row.set(j, row.get(j) + row.get(j + 1));
			allrows.add(new ArrayList<Integer>(row));
		}
		return allrows;
	}
}

For example, given numRows = 5,
Return [ [1], [1,1], [1,2,1], [1,3,3,1],[1,4,6,4,1] ]

Reverse Bits

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
		int result = 0;
		for (int i = 0; i < 32; ++i) {
			if ((n & 1) == 1) {
				result = (result << 1) + 1;
			} else {
				result = result << 1;
			}
			n = n >> 1;
		}
		return result;
    }
}

32位无符号数的二进制形式反转,返回反转后的十进制数
主要还是位运算,通过n不断的右移并与1进行&位运算,检测最后一位是否为1
与此同时,result也在不断地左移,若n右移到最后一位为1,则result末位加1,左移32次,达到逆序的效果

Rotate Function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int maxRotateFunction(int[] A) {
        int allSum = 0;
        int len = A.length;
        int F = 0;
        for (int i = 0; i < len; i++) {
            F += i * A[i];
            allSum += A[i];
        }
        int max = F;
        for (int i = len - 1; i >= 1; i--) {
            F = F + allSum - len * A[i];
            max = Math.max(F, max);
        }
        return max;           
    }
}

F(k) = 0 Bk[0] + 1 Bk[1] + … + (n-1) * Bk[n-1].

Calculate the maximum value of F(0), F(1), …, F(n-1).

实际是数学运算..

F(k) = 0 Bk[0] + 1 Bk[1] + … + (n-1) Bk[n-1]
F(k-1) = 0 Bk-1[0] + 1 Bk-1[1] + … + (n-1) Bk-1[n-1]
= 0 Bk[1] + 1 Bk[2] + … + (n-2) Bk[n-1] + (n-1) Bk[0]

F(k) - F(k-1) = Bk[1] + Bk[2] + … + Bk[n-1] + (1-n)Bk[0]
= (Bk[0] + … + Bk[n-1]) - nBk[0]
= sum - nBk[0]

F(k) = F(k-1) + sum - nBk[0]

k = 0; B[0] = A[0];
k = 1; B[0] = A[len-1];
k = 2; B[0] = A[len-2];
…