LeetCode算法(二)
一、13. 罗马数字转整数
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II ，27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况： I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。 X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。 给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1: 输入: "III" 输出: 3 示例 2: 输入: "IV" 输出: 4 示例 3: 输入: "IX" 输出: 9 示例 4: 输入: "LVIII" 输出: 58 解释: L = 50, V= 5, III = 3. 示例 5: 输入: "MCMXCIV" 输出: 1994 解释: M = 1000, CM = 900, XC = 90, IV = 4.
class Solution {
public int romanToInt(String s) {
Map<Character, Integer> map = new HashMap<>();
map.put('I', 1);
map.put('V', 5);
map.put('X', 10);
map.put('L', 50);
map.put('C', 100);
map.put('D', 500);
map.put('M', 1000);
int ans = 0;
int pre = map.get(s.charAt(0));
for(int i = 0; i < s.length(); i++){
int n = map.get(s.charAt(i));
if(n > pre){
ans += n;
ans -= pre*2;
}else{
ans += n;
pre = n;
}
}
return ans;
}
}自评：需要先将每个罗马数字代表的数字保存起来。循环提取每一个罗马数字。因为不同的位置会有不同的做法，所以记录之前罗马数字的值，如果比上一次加的值大，则本次减去2倍的该值。
二、21. 合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode newNode = new ListNode(0);
ListNode temp = newNode;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
temp.next = l1;
temp = temp.next;
l1 = l1.next;
}else{
temp.next = l2;
temp = temp.next;
l2 = l2.next;
}
}
if(l1 == null){
temp.next = l2;
}else{
temp.next = l1;
}
return newNode.next;
}
}自评：设置一个新的节点，创建一个副本节点。循环判断两个链表第一个节点的值的大小，谁小，把新链表节点的下一个节点指向它。直到有一个链表为空时，把新链表的尾部指向另一个链表剩下的所有节点。
三、191. 位1的个数
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
示例 1： 输入：00000000000000000000000000001011 输出：3 解释：输入的二进制串 00000000000000000000000000001011 中， 共有三位为 '1'。 示例 2： 输入：00000000000000000000000010000000 输出：1 解释：输入的二进制串 00000000000000000000000010000000 中， 共有一位为 '1'。 示例 3： 输入：11111111111111111111111111111101 输出：31 解释：输入的二进制串 11111111111111111111111111111101 中， 共有 31 位为 '1'。
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int b = 0;
int j = 1;
for(int i = 0; i < 32; i++){
if((n & j) != 0){
b++;
}
j <<= 1;
}
return b;
}
}自评：设置 j 来循环逻辑与 n 的各个位，如果不为0，则 1 的位数加一。
四、283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说明: 必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。
class Solution {
public void moveZeroes(int[] nums) {
int n = nums.length;
for(int i = 0, j = 0; i < n; i++){
if(nums[i] != 0){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
j++;
}
}
}
}自评：设置一个 j 变量，使其停留在从前往后的 0 的位置，当循环下一个数字不为 0 时则交换位置。
五、122. 买卖股票的最佳时机 II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。 你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1: 输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5） 的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入， 在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2: 输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。 示例 3: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int ans = 0;
for(int i = 1; i < n; i++){
if(prices[i] > prices[i-1]){
ans += (prices[i] - prices[i-1]);
}
}
return ans;
}
}自评：使用贪心算法，当天的价格比昨天要高，就卖掉，不管赚多少钱都卖。
六、242. 有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。 示例 1: 输入: s = "anagram", t = "nagaram" 输出: true 示例 2: 输入: s = "rat", t = "car" 输出: false
class Solution {
public boolean isAnagram(String s, String t) {
if(s.length() != t.length()){
return false;
}
int[] count = new int[26];
for(int i = 0; i < s.length(); i++){
count[s.charAt(i) - 'a']++;
}
for(int i = 0; i < t.length(); i++){
count[t.charAt(i) - 'a']--;
if(count[t.charAt(i) - 'a'] < 0){
return false;
}
}
return true;
}
}自评：把第一个单词的所有字母出现次数保存起来。遍历第二个单词字母时，第一个保存完的字母次数数组减去第二个每个字母出现次数，如果出现负数则不为异位词。
七、202. 快乐数
编写一个算法来判断一个数是不是“快乐数”。 一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。 示例: 输入: 19 输出: true 解释: 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1
class Solution {
public boolean isHappy(int n) {
int sum = 0;
while(true){
while(n > 0){
sum += (n%10) * (n%10);
n /= 10;
}
if(sum == 1){
return true;
}
n = sum;
if(sum == 4 || sum == 16 || sum == 37 || sum == 58 || sum == 145 || sum == 42 || sum== 20){
return false;
}
sum = 0;
}
}
}自评：主要因为有无限循环的数字，所以遇到这些数字就直接返回false。
八、371. 两整数之和
不使用运算符 + 和 - ，计算两整数 a 、b 之和。
示例 1: 输入: a = 1, b = 2 输出: 3 示例 2: 输入: a = -2, b = 3 输出: 1
class Solution {
public int getSum(int a, int b) {
int sum = a ^ b;
int d = a & b;
if(d != 0){
d <<= 1;
return getSum(sum, d);
}else{
return sum;
}
}
}自评：异或求无进位值，逻辑与左移一位求进位，递归次过程，直到没有进位。
九、268. 缺失数字
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
示例 1: 输入: [3,0,1] 输出: 2 示例 2: 输入: [9,6,4,2,3,5,7,0,1] 输出: 8
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
for(int i = 0; i < nums.length; i++){
n ^= nums[i] ^ i;
}
return n;
}
}自评：从0到n的数字循环异或数组中的数字，最后会剩下缺失的数字例如
1^1^2^2^3 = 3。
十、38. 报数
报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
1. 1 2. 11 3. 21 4. 1211 5. 111221 1 被读作 "one 1" ("一个一") , 即 11。 11 被读作 "two 1s" ("两个一"）, 即 21。 21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。 给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。 注意：整数顺序将表示为一个字符串。
public class CountAndSay {
public static String countAndSay(int n) {
return countHelper("1", n);
}
/**
* 尾递归
* @param str
* @param n
* @return
*/
private static String countHelper(String str, int n) {
if (n == 1) return str;
else {
//求下一个数
StringBuilder stringBuilder = new StringBuilder();
int i = 0;
//一直读数
while (i < str.length()) {
int count = 1;
//如果一直是同一个数
while (i < str.length() - 1 && str.charAt(i) == str.charAt(i + 1)) {
count++;
i++;
}
//下一个数更新
stringBuilder.append(Integer.toString(count) + str.charAt(i));
i++;
}
str = stringBuilder.toString();
}
return countHelper(str, n - 1);
}
}