发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/single-number-ii/

　　数组中只有一个数出现一次，其它数都出现三次。要求时间复杂度O(n)，空间复杂度为O(1)

题目分析

　　思路参考了这里：http://www.acmerblog.com/leetcode-single-number-ii-5394.html

　　第一种比较直观的思路是：因为每个数字都有32位，把数组中所有的元素对应位相加，32位中的每一位都可以得到一个和，把这个和模3得到的结果（注意模3的结果只能是0和1，不可能是2）就是答案在该位的值。但这种方法需要频繁地移位操作，虽然时间和空间能满足题目要求。

阅读全文 »

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/convert-a-number-to-hexadecimal/

　　将一32位整数转成补码表示

题目分析

　　其实就是把整数在计算机内的真实存储形式表示出来，注意题目要求结果的前面不允许有引导‘0’。（正数转换成相应的负数（反过来也一样）的方式都是：所有位取反然后加1，0要单独考虑）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    private static char[] symbol = new char[]{'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";
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 8; i++) {
            sb.append(symbol[num & 15]);
            num >>= 4;
        }
        String tmp = sb.reverse().toString();
        StringBuilder sb2 = new StringBuilder();
        boolean found = false;
        for (int i = 0; i < 8; i++) {
            if (tmp.charAt(i) != '0') {
                found = true;
            }
            if (found) {
                sb2.append(tmp.charAt(i));
            }
        }
        return sb2.toString();
    }
}

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/largest-rectangle-in-histogram/

　　给你一个数组，数组中每个元素的值都代表了直方图的高度，最后让你求直方图中的最大面积矩形面积值。

题目分析

　　此题是Hard题，我没有想出来O(n)解法，看了一下这个解法比较好理解，有两个辅助数组left和right。left和right数组代表的含义对于某个位置i，能向左和向右伸展到的位置，意思就是说在i这个位置，以nums[i]为高度的矩形面积就是(right[i] - left[i] + 1) * nums[i]。实际在生成left的数组中，对于每个位置i需要进行不断“跳跃”，比如说求left[i]时，初始值是i，那么先看跟i-1位置的值进行比较，如果i-1位置的值更大，那么自然left[i]可以跳跃到left[i-1]的位置，那么再看此时位置-1的位置的值跟nums[i]比较再决定是否继续跳跃。构造right数组也同理，逆向思维即可。

阅读全文 »