【020-Week01】总结思考

[lcfgrn]

链表的总结思考

题目：
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
自己写的代码实现：
/**

• Definition for singly-linked list.

• public class ListNode {

• int val;
  

• ListNode next;
  

• ListNode(int x) { val = x; }
  

• }
  */
  class Solution {
  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  int addVal = 0;
  ListNode head = null;
  if (l1 != null && l2 != null) {
  int sum = l1.val + l2.val + addVal;
  head = new ListNode(sum%10);
  addVal = sum/10;
  l1 = l1.next;
  l2 = l2.next;
  }
  ListNode p = head;
  while(l1 != null && l2 != null) {
  int sum = l1.val + l2.val + addVal;
  p.next = new ListNode(sum%10);
  addVal = sum/10;
  l1 = l1.next;
  l2 = l2.next;
  p = p.next;
  }

    if(l1 == null) {
        while(addVal != 0) {
            if(l2 != null) {
                int sum = l2.val + addVal;
                p.next = new ListNode(sum%10);
                addVal = sum/10;
                l2 = l2.next;
            } else {
                p.next = new ListNode(addVal);
                addVal = addVal/10;
            }
            p = p.next;
        }
        p.next = l2;   
    }
    
    if(l2 == null) {
        while(addVal != 0) {
            if(l1 != null) {
                int sum = l1.val + addVal;
                p.next = new ListNode(sum%10);
                addVal = sum/10;
                l1 = l1.next;
            } else {
                p.next = new ListNode(addVal);
                addVal = addVal/10;
            }
            p = p.next;
        }
        p.next = l1;   
    }
    
    return head;
  

  }
  }
  参照题解，写的代码
  /**

• Definition for singly-linked list.

• public class ListNode {

• int val;
  

• ListNode next;
  

• ListNode(int x) { val = x; }
  

• }
  */
  class Solution {
  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  ListNode dummyHead = new ListNode(0);
  ListNode p=l1, q = l2, curr = dummyHead;
  int addVal = 0;
  while(p != null || q != null) {
  int x = (p!=null) ? p.val : 0;
  int y = (q!=null) ? q.val : 0;
  int sum = x + y + addVal;
  curr.next = new ListNode(sum % 10);
  addVal = sum / 10;
  curr = curr.next;
  if(p!=null)
  p = p.next;
  if(q!=null)
  q = q.next;
  }

    if(addVal > 0) {
        curr.next = new ListNode(addVal);
    }
    
    return dummyHead.next;
  

  }
  }
  总体印象：
  1.自己写的代码很臃肿，难于理解
  总结：
  1.未针对l1为空，l2不为空（或l1不为空,l2为空）的情况，与普通情况进行合并，仅需一个三元判断就行；
  2.未使用哨兵头节点简化编程难度，可以添加哨兵节点后，在返回时使用dummyHead.next，得到结果。

哈希表的总结思考
题目
Given an array of strings, group anagrams together.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
Note:

• All inputs will be in lowercase.
• The order of your output does not matter.

自己的实现
class Solution {
public List<List> groupAnagrams(String[] strs) {
List<List> strLists = new ArrayList<>();
Map<String, List> strMap = new HashMap<>();
for (String str : strs) {
int[] arr = new int[26];
for (char ch : str.toCharArray()) {
arr[ch - 'a'] ++;
}
String key = transInts2Str(arr);
if (strMap.containsKey(key)) {
strMap.get(key).add(str);
} else {
List strList = new ArrayList<>();
strList.add(str);
strMap.put(key, strList);
}
}
for (List strList : strMap.values()) {
strLists.add(strList);
}
return strLists;
}

    private String transInts2Str(int[] arr) {
        StringBuffer sb = new StringBuffer();
        for (int i : arr) {
            sb.append(i);
        }
        return sb.toString();
    }

}
别人的实现
class Solution {
public List<List> groupAnagrams(String[] strs) {
Map<String, List> strMap = new HashMap<>();
for (String str : strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = String.valueOf(chars);
strMap.putIfAbsent(key, new ArrayList<>());
strMap.get(key).add(str);
}
return new ArrayList<>(strMap.values());
}
}
总体印象：
1.下面的实现感觉很优雅
本题解题思路：
1.将字符串组中的每个字符串都转换成可以用来比较的key（我采用的是int[26]，参考采用的是将字符串中每个字符排序得到新的字符串）；
2.使用哈希表，将字符串比较分组，转换为对key的比较分组。