NC120 二进制中1的个数

描述

输入一个整数 n ，输出该数32位二进制表示中1的个数。其中负数用补码表示。

示例1

输入：

1
10

返回值：

1
2

说明：

1
十进制中10的32位二进制表示为0000 0000 0000 0000 0000 0000 0000 1010，其中有两个1。

示例2

输入：

1
-1

返回值：

1
32

说明：

1
负数使用补码表示 ，-1的32位二进制表示为1111 1111 1111 1111 1111 1111 1111 1111，其中32个1

思路：

  • 计算机中存储数据都是补码的形式
  • 正数的反码和补码是它本身
  • 负数的反码是除符号位外的相反数，补码是反码加一
  • 补码为反码+1
  • 负数在计算机中存储形式为补码
  • 负数右移符号位补1
  • 采用与位左移代替数字右移

解答：

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public int NumberOf1(int n) {
        int ans = 0;
        int flag = 1;
        while (flag != 0) {
            if ((n & flag) != 0) ans++;
            flag = flag << 1;
        }
        return ans;
    }
}

NC107 寻找峰值

描述

给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。

1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于

2.假设 nums[-1] = nums[n] = -\infty−∞

3.对于所有有效的 i 都有 nums[i] != nums[i + 1]

4.你可以使用O(logN)的时间复杂度实现此问题吗？

数据范围：

1 \le nums.length \le 2\times 10^5 \1≤num**s.lengt**h≤2×105

-2^{31}<= nums[i] <= 2^{31} - 1−231<=num**s[i]<=231−1

如输入[2,4,1,2,7,8,4]时，会形成两个山峰，一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰，如下图所示：

img

示例1

输入：

1
[2,4,1,2,7,8,4]

返回值：

1
1

说明：

1
4和8都是峰值元素，返回4的索引1或者8的索引5都可以

示例2

输入：

1
[1,2,3,1]

返回值：

1
2

说明：

1
3 是峰值元素，返回其索引 2

思路：

  • 注意第一位和最后一位
  • 当前位比前一位小就说明前一位为峰值

解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int findPeakElement (int[] nums) {
        // write code here
        if(nums.length == 1) return 0;
        int tmp = Integer.MIN_VALUE;
        for(int i = 0; i < nums.length; i++) {
            if (nums[i] < tmp) return (i-1);
            tmp = nums[i];
        }
        return nums.length-1;
    }
}