原理：为了考虑到六种特殊情况，我们需要在遍历字符串时对比当前项和下一项：
（1）若当前项小于下一项，给总数添加（下一项的对应数值 - 当前项的对应数值）。此时这两项都被使用完了，下标直接指向当前项的下一项的下一项。
（2）否则，给总数添加当前项，考虑到下一项和下一项的下一项可能存在（1）关系，所以不给总值添加下一项的对应数值，而让下标指向当前项下一项。
这么写时要注意 for 循环的写法：
若 for 循环中单次表达式是 int i = 0，条件表达式是 i < 字符串.length()，末尾循环体不写：
那么假设倒数第二项的最后一项满足对比关系中的（2）关系，那么当下标指向最后一项时，会因调用字符串 i+1（此时的 i+1 溢出了字符串的最大范围）而报错
解决方法：在 for 循环里的 if 判断语句的判断条件处写如下代码
for(int i = 0; i < len;){
// &&的短路功能，当第一个表达式的值为false的时候，则不再计算第二个表达式；&则两个表达式都执行。
// 所以当 i+1 等于 len 时，也就是当前项 i 为最后一项时
// 跳过 && 右侧会报错的部分直接执行 else，把当前项的对应数值加入总值
if(i+1 < len && Roma.get(String.valueOf(s.charAt(i+1))) > Roma.get(String.valueOf(s.charAt(i)))){
sum += Roma.get(String.valueOf(s.charAt(i+1))) - Roma.get(String.valueOf(s.charAt(i)));
i+=2;
} else {
sum += Roma.get(String.valueOf(s.charAt(i)));
i++;
}
}
根据题给字符对应数字关系建立哈希表后，我们需要在 for 循环中调用该表，这里的注意点：
HashMap.get() 方法：括号里写的是键key，方法会返回对应的值
字符串取对应下标值使用 s.charAt( i ) 方法，该方法返回一个 char 字符型，但由于我的哈希表键用了 String 类型，如果直接把该方法写入 .get() 中二者会因类型不匹配而报错，所以我们需要将 char 型转换为 String 型，用 String.valueOf() 方法
完整代码：
class Solution {
public int romanToInt(String s) {
// 创建哈希表，里面键对应字符，值对应数字
HashMap Roma = new HashMap();
Roma.put("I", 1);
Roma.put("V", 5);
Roma.put("X", 10);
Roma.put("L", 50);
Roma.put("C", 100);
Roma.put("D", 500);
Roma.put("M", 1000);
// 要返回的整数
int sum = 0;
int len = s.length();
// 遍历字符串
for(int i = 0; i < len;){
// 若前大于后，说明属于特殊规则
if(i+1 < len && Roma.get(String.valueOf(s.charAt(i+1))) > Roma.get(String.valueOf(s.charAt(i)))){
sum += Roma.get(String.valueOf(s.charAt(i+1))) - Roma.get(String.valueOf(s.charAt(i)));
i+=2;
} else {
sum += Roma.get(String.valueOf(s.charAt(i)));
i++;
}
}
return sum;
}
}
方法二：高效率的简单方法：
原理：
按照题目的描述，可以总结如下规则：
罗马数字由 I,V,X,L,C,D,M 构成；
当小值在大值的左边，则减小值，如 IV=5-1=4；
当小值在大值的右边，则加小值，如 VI=5+1=6；
由上可知，右值永远为正，因此最后一位必然为正。
总结：把一个小值放在大值的左边，就是做减法（要返回的整数 - 该小值），否则为加法（要返回的整数 + 该小值）
在代码实现上，可以往后看多一位，对比当前位与后一位的大小关系，从而确定当前位是正的还是负的。当没有下一位时，做加法即可。
也可保留当前位的值，当遍历到下一位的时，对比保留值与遍历位的大小关系，再确定保留值为正还是负。最后一位做加法即可。
import java.util.*;
class Solution {
public int romanToInt(String s) {
int sum = 0;
// 保存当前项，也就是下一项的前一项
int preNum = getValue(s.charAt(0));
// 从第二项，下标 1 开始遍历
for(int i = 1;i < s.length(); i ++) {
// 获得当前项的int
int num = getValue(s.charAt(i));
// 比较当前项与前一项，并给总值添加前一项的 int
if(preNum < num) {
sum -= preNum;
} else {
sum += preNum;
}
// 前一项变为当前项，当前项变为下一项
// 在循环的最后，preNum 指向最后一项
preNum = num;
}
// 最后一项无论如何是正的，直接添加即可
sum += preNum;
return sum;
}
// 用来查询字符和数字的关系
private int getValue(char ch) {
switch(ch) {
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
default: return 0;
}
}
}
191、难度简单：
要求：如果多次调用这个函数，该如何优化你的算法
提示：在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在输入如 11111111111111111111111111111101 类型的二进制串时，题目真正输入的数据为有符号整数 -3
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/number-of-1-bits/solution/wei-1de-ge-shu-by-leetcode-solution-jnwf/
原理：我们可以直接循环检查给定整数 n 的二进制位的每一位是否为 1。
具体代码中，当检查第 i 位时，我们可以让 n 与 2^i 进行与运算，当且仅当 n 的第 i 位为 1 时，运算结果不为 0
JAVA中 << 表示左移，不分正负数，低位补0
比如 20 << 2 表达的为：20的二进制补码：0001 0100 向左移动两位后：0101 0000 结果：r = 80
public class Solution {
public int hammingWeight(int n) {
int ret = 0;
for (int i = 0; i < 32; i++) {
// 1 << i 中 i 代表当前位数，而 1 的二进制就是 1 ，左移后 1 右侧的数全为 0
if ((n & (1 << i)) != 0) {
ret++;
}
}
return ret;
}
}
方法二：位运算优化：空间复杂度：O(1)
时间复杂度：O(logn)。循环次数等于 n 的二进制位中 1 的个数，最坏情况下 n 的二进制位全部为 1。我们需要循环 logn 次
原理：观察这个运算：n & (n−1)，其运算结果恰为把 n 的二进制位中的最低位的 1 变为 0 之后的结果。
如：6 & (6−1)=4，6=(110) 2，4=(100) 2，运算结果 4 即为把 6 的二进制位中的最低位的 1 变为 0 之后的结果。这样我们可以利用这个位运算的性质加速我们的检查过程，在实际代码中，我们不断让当前的 n 与 n−1 做与运算，直到 n 变为 0 即可。因为每次运算会使得 n 的最低位的 1 被翻转，因此运算次数就等于 n 的二进制位中 1 的个数。
public class Solution {
public int hammingWeight(int n) {
int ret = 0;
while (n != 0) {
n &= n - 1;
ret++;
}
return ret;
}
}
