【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的比较分组。