面试代码复习

迎难而上，祝我好运。

1. Two Sum

• 给定一串整型数组，给一个目标值，求数组中唯一的一对数字，相加得到该目标值。
• 需要考虑数组中可能有重复项，每个项只能用一次，答案一定存在且唯一。
• 方法一：用hashmap记录数组中每一个值对应的首次出现的index。然后遍历数组求target减去当前项，看是否在map的key中并且不等于当前索引（只能用一次）。

  public int[] twoSum(int[] nums, int target) {
      if (nums == null || nums.length == 0) {
          return new int[0];
      }
      
      // take val as key and index as value in the map
      Map<Integer, Integer> val2Index = new HashMap<>();
      for (int i = 0; i < nums.length; i++) {
          if (!val2Index.containsKey(nums[i])) {
              val2Index.put(nums[i], i);
          }
      }
      
      // take the index of (target - nums[i]) out of map, if exists
      for (int i = 0; i < nums.length; i++) {
          int temp = target - nums[i];
          if (val2Index.containsKey(temp) && val2Index.get(temp) != i) {
              return new int[] {i, val2Index.get(temp)};
          }
      }
      return new int [0];
  }

2. Add 2 Num

• 给两个链表，每个节点是一个反序存放的数字（个-十-百-千-万），输出也是一个链表，每个节点就是那两个输入链表对应节点的值之和。
• 需要考虑链表是否为空？会否有多余的0开头的节点？链表本身表示的数或者相加之后的结果是否越界都没关系，因为输入本身和结果都用链表表示。
• 方法一：遍历之。

  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
      if (l1 == null) {
          return l2;
      }
      if (l2 == null) {
          return l1;
      }
      
      ListNode ans = new ListNode(0);
      ListNode curr = ans;
      int carry = 0;
      while (l1 != null && l2 != null) {
          int val = l1.val + l2.val + carry;
          carry = val / 10;
          val = val % 10;
          curr.next = new ListNode(val);
          l1 = l1.next;
          l2 = l2.next;
          curr = curr.next;
      }
      while (l1 != null) {
          int val = l1.val + carry;
          carry = val / 10;
          val = val % 10;
          curr.next = new ListNode(val);
          l1 = l1.next;
          curr = curr.next;
      }
      while (l2 != null) {
          int val = l2.val + carry;
          carry = val / 10;
          val = val % 10;
          curr.next = new ListNode(val);
          l2 = l2.next;
          curr = curr.next;
      }
      if (carry > 0) {
          curr.next = new ListNode(carry);
      }
      return ans.next;
  }

3. Longest substring

• 给一个字符串，找其中不含重复字符的最长子串的长度。
• 考虑原字符串是否为null或""？只含有一个字符？字符交替出现？
• 子串问题，优先考虑双指针。右指针不断往后找字符，将字符及对应索引放入map，当发现已经存在key时，先计算目前长度更新到ans中，然后将左指针已到右指针指向字符上一次出现的位置的下一个或者不变（因为可能上一次出现的位置反而回退了）。

  public int lengthOfLongestSubstring(String s) {
      if (s == null || s.length() == 0) {
          return 0;
      }
      Map<Character, Integer> map = new HashMap<>();
      char[] sChar = s.toCharArray();
      int left = 0, right = 0, ans = 1;   // warning not MIN_VALUE
      for (right = 0; right < sChar.length; right++) {
          if (!map.containsKey(sChar[right])) {   // first occurance
              map.put(sChar[right], right);
          } else {
              ans = Math.max(ans, right - left);  // locate to last occurance
              left = Math.max(map.get(sChar[right]) + 1, left);   // move left. warning not go back
              map.put(sChar[right], right);       // update latest occurance
          }
      }
      return Math.max(ans, right - left);     // warning not ans
  }

4. Median of 2 sorted arrays

• 给两个int数组，返回二者合并后的中位数。

• 朴素的做法，逐个merge，然后分奇数、偶数求中位数。注意这里需要返回的是double。时间复杂度Linear,O((m + n)/2)。

  public double findMedianSortedArrays(int[] nums1, int[] nums2) {
      int len_total = nums1.length + nums2.length;
      int len_total_half = len_total >> 1;
      int[] merged = new int [len_total];
      
      int i = 0, j = 0, len = 0;
      boolean finished = false;
      while (!finished && i < nums1.length && j < nums2.length) {
          if (nums1[i] < nums2[j]) {
              merged[len++] = nums1[i++];
          } else {
              merged[len++] = nums2[j++];
          }
          if (len > len_total_half) {
              finished = true;
          }
      }
      while (!finished && i < nums1.length) {
          merged[len++] = nums1[i++];
          if (len > len_total_half) {
              finished = true;
          }
      }
      while (!finished && j < nums2.length) {
          merged[len++] = nums2[j++];
          if (len > len_total_half) {
              finished = true;
          }
      }
      
      if (len_total % 2 == 1) {
          return merged[len_total_half];
      } else {
          return (double)((merged[len_total_half] + merged[len_total_half-1])/2.0);
      }

• follow-up：要求在O(log(m+n))的时间复杂度以内？

• 中位数可以把有序数组分成等长的两部分，因此在数组1取i个元素、数组2取j个元素，使得i + j == 剩余数字个数并且满足大小关系

  public double findMedianSortedArrays(int[] nums1, int[] nums2) {
      if (nums1 == null || nums2 == null) {
          return 0;
      }
      int m = nums1.length, n = nums2.length;
      if (nums1.length > nums2.length) {  // ensure the len of 1 <= 2
          return findMedianSortedArrays(nums2, nums1);
      }
      
      // to ensure equality of the two parts after merged, i + j = m - i + n - j
      int iLo = 0, iHi = m, allMid = (n + m + 1) / 2; // odd: i = j, even: i = j - 1
      
      // i stands for "how many num taken from nums1 as front part" 0 ~ i-1 | i ~ m-1
      // j stands for "how many num taken from nums2 as front part" 0 ~ j-1 | j ~ n-1
      while (iLo <= iHi) {
          int i = (iLo + iHi) / 2, j = allMid - i;
          
          // nums1[i-1], nums2[j-1] are the largest element of front part of nums1, nums2
          // nums1[i], nums2[j] are the smallest of lag part of nums1, nums2
          if (i < m && nums2[j - 1] > nums1[i]) { // i not big enough
              iLo = i + 1;
          } else if (i > 0 && nums1[i - 1] > nums2[j]) {
              iHi = i - 1;
          } else {
              int maxLeft = 0, minRight = 0;
              if (i == 0) {
                  maxLeft = nums2[j - 1];
              } else if (j == 0) {
                  maxLeft = nums1[i - 1];
              } else {
                  maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
              }
              
              if ((m + n) % 2 == 1) { // I think thats why to make (allMid = (n + m + 1)/2)
                  return maxLeft;     // -- to make left part always at least no fewer than right
              }
              
              if (i == m) {
                  minRight = nums2[j];
              } else if (j == n) {
                  minRight = nums1[i];
              } else {
                  minRight = Math.min(nums1[i], nums2[j]);
              }
              return (maxLeft + minRight) / 2.0;
          }
      }
      
      return 0;
  }

403. frog-jump

给一个数组表示石头所处的x坐标，青蛙每次只能跳上一次跳跃长度的-1,0,1三种可能，判断能否跳到最后一个石头。
相当于BFS，每个石头处维护一个set存放他可以跳的长度，然后每次都往后跳看看能否有新的石头，有就更新那个石头的可跳长度。

public boolean canCross(int[] stones) {
    if (stones.length == 0) {
        return true;
    }
    
    HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>(stones.length);
    map.put(0, new HashSet<Integer>());
    map.get(0).add(1);
    for (int i = 1; i < stones.length; i++) {
        map.put(stones[i], new HashSet<Integer>() );
    }
    
    for (int i = 0; i < stones.length - 1; i++) {
        int stone = stones[i];
        for (int step : map.get(stone)) {
            int reach = step + stone;
            if (reach == stones[stones.length - 1]) {
                return true;
            }
            HashSet<Integer> set = map.get(reach);
            if (set != null) {
                set.add(step);
                if (step - 1 > 0) set.add(step - 1);
                set.add(step + 1);
            }
        }
    }
    
    return false;
}

249. group-shifted-strings

给一个String的数组，要求将其中能通过平移相同offset后相同的字符串group在一起.
先根据第一个字母算出与a的offset，然后将后续所有字母都根据这个offset来挪，拼接成key存入map。

public class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> result = new ArrayList<List<String>>();
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strings) {
            int offset = str.charAt(0) - 'a';
            String key = "";
            for (int i = 0; i < str.length(); i++) {
                char c = (char) (str.charAt(i) - offset);
                if (c < 'a') {
                    c += 26;
                }
                key += c;
            }
            if (!map.containsKey(key)) {
                List<String> list = new ArrayList<String>();
                map.put(key, list);
            }
            map.get(key).add(str);
        }
        for (String key : map.keySet()) {
            List<String> list = map.get(key);
            Collections.sort(list);
            result.add(list);
        }
        return result;
    }
}

[Extra][tree]

给一个二叉树，和两个节点A，B，找出从A到B的路径，返回结果要求顺序存到一个链表中。

public class Apple {
	public static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		public TreeNode(int val) {
			this.val = val;
		}
	}
	public static void main(String[] args) {
		TreeNode root = new TreeNode(0);
		TreeNode n1 = new TreeNode(1);
		TreeNode n2 = new TreeNode(2);
		TreeNode n3 = new TreeNode(3);
		TreeNode n4 = new TreeNode(4);
		TreeNode n5 = new TreeNode(5);
		TreeNode n6 = new TreeNode(6);
		TreeNode n7 = new TreeNode(7);
		root.left = n1;
		root.right = n2;
		n1.left = n5;
		n1.right = n6;
		n2.left = n3;
		n2.right = n4;
		n3.left = n7;
		System.out.println(findPathBetween(root, n2, n5));
	}
	public boolean workBreak(String s, List<String> wordDict) {
		if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) {
			return false;
		}
		Set<String> wordSet = new HashSet<>();
		int maxLen = 0;
		for (String word: wordDict) {
			wordSet.add(word);
			maxLen = Math.max(maxLen, word.length());
		}
		boolean[] dp = new boolean [s.length() + 1];
		for (int i = 1; i <= s.length(); i++) {
			for (int j = i - 1; j >= 0 && i - j <= maxLen; j--) {
				if (dp[j] && wordSet.contains(s.substring(j, i))) {
					dp[i] = true;
					break;
				}
			}
		}
		return dp[s.length()];
	}
	public int firstUniqChar2(String s) {
        if (s == null || s.length() == 0) {
            return -1;
        }
        char[] sChar = s.toCharArray();
        int[] bucket = new int [256];
        for (int i = 0; i < sChar.length; i++) {
        	bucket[sChar[i]]++;
        }
        for (int i = 0; i < sChar.length; i++) {
        	if (bucket[sChar[i]] == 1) {
        		return i;
        	}
        }
        return -1;
    }

	public int firstUniqChar1(String s) {
        if (s == null || s.length() == 0) {
            return -1;
        }
        char[] sChar = s.toCharArray();
        int[] bucket = new int [256];
        Map<Character, Integer> map = new LinkedHashMap<>();
        for (int i = 0; i < sChar.length; i++) {
            if (bucket[sChar[i]]++ == 0) {
                map.put(sChar[i], i);
            } else {
                map.remove(sChar[i]);
            }
        }
        Iterator it = map.entrySet().iterator();
        if (it.hasNext()) {
            Map.Entry pair = (Map.Entry)it.next();
            return (Integer)pair.getValue();
        }
        return -1;
    }
	private static TreeNode getLCA(TreeNode root, TreeNode n1, TreeNode n2) {
		if (root == null) {
			return null;
		}
		if (root == n1 || root == n2) {
			return root;
		}
		TreeNode left = getLCA(root.left, n1, n2);
		TreeNode right = getLCA(root.right, n1, n2);
		if (left != null && right != null) {
			return root;
		}
		if (left == null && right == null) {
			return null;
		}
		return left == null? right: left;
	}

	private TreeNode prev1 = null;
	private boolean validateBST1(TreeNode root) {
		if (root == null) {
			return true;
		}
		if (!validateBST1(root.left)) {
			return false;
		}
		if (prev1 != null && prev1.val >= root.val) {
			return false;
		}
		prev1 = root;
		return validateBST1(root.right);
	}
	private boolean validateBST2(TreeNode root) {
		if (root == null) {
			return true;
		}
		Stack<TreeNode> stack = new Stack<>();
		TreeNode prev = null;
		while (root != null || !stack.isEmpty()) {
			while (root != null) {
				stack.push(root);
				root = root.left;
			}
			root = stack.pop();
			if (prev != null && prev.val >= root.val) {
				return false;
			}
			prev = root;
			root = root.right;
		}
		return true;
	}
	private boolean validateBST3(TreeNode root) {
		return dvcq(root, Long.MIN_VALUE, Long.MAX_VALUE);
	}
	private boolean dvcq(TreeNode root, long min, long max) {
		if (root == null) {
			return true;
		}
		if (root.val <= min || root.val >= max) {
			return false;
		}
		return dvcq(root.left, min, Math.min(root.val, max))
				&& dvcq(root.right, Math.max(root.val, min), max);
	}
	
	private static String findPathBetween(TreeNode root, TreeNode start, TreeNode end) {
		if (root == null) {
			return "";
		}
		TreeNode lca = getLCA(root, start, end);
		List<TreeNode> pathToStart = new ArrayList<TreeNode>();
		findPathTo(lca, start, pathToStart);
		List<TreeNode> pathToEnd = new ArrayList<TreeNode>();
		findPathTo(lca, end, pathToEnd);
		
		StringBuilder sb = new StringBuilder();
		for (int i = pathToStart.size() - 1; i > 0; i--) {
			if (sb.length() == 0) {
				sb.append(pathToStart.get(i).val);
			} else {
				sb.append("->");
				sb.append(pathToStart.get(i).val);
			}
		}
		for (TreeNode node : pathToEnd) {
			sb.append("->");
			sb.append(node.val);
		}
		return sb.toString();
		
	}
	private static boolean findPathTo(TreeNode start, TreeNode end, List<TreeNode> curr) {
		curr.add(start);
		if (start == end) {
			return true;
		} else {
			if (start.left != null) {
				if (findPathTo(start.left, end, curr)) {
					return true;
				}
			}
			if (start.right != null) {
				if (findPathTo(start.right, end, curr)) {
					return true;
				}
			}
		}
		curr.remove(curr.size() - 1);
		return false;
	}
}

[extra][interval]

给两个interval的数组，求二者overlap的部分.
定义一个endCurr表示当前的结尾，然后取两个数组中start较小的与它比较，如果重合就将start为起点、endCurr为结尾new一个新的interval存入结果，然后更新endCurr（如果比该start处对应的end小了的话）

public List<Interval> findOverlapping(Interval[] i1, Interval[] i2) {
    List<Interval> res = new ArrayList<Interval>();
    int i = 0;
    int j = 0;
    int endCurr = i1[0].start > i2[0].start ? i2[0].start : i1[0].start;
    while (i < i1.length && j < i2.length) {
        if (i1[i].start > i2[j].start) {
            if (i2[j].start < endCurr) {
                Interval temp = new Interval(i2[j].start, endCurr);
                res.add(temp);
            }
            endCurr = Math.max(i2[j].end, endCurr);
            j++;
        } else {
            if (i1[i].start < endCurr) {
                Interval temp = new Interval(i1[i].start, endCurr);
                res.add(temp);
            }
            endCurr = Math.max(i1[i].end, endCurr);
            i++;
        }
    }
    return res;
}

Linux命令行

awk:分析与处理

• 对文本进行逐行分段处理，awk '条件类型1{动作1} 条件类型2{动作2}' filename. awk的处理流程是:
  1. 读第一行, 将第一行资料填入变量 $0, $1… 等变量中
  2. 依据条件限制, 执行动作(awk一次处理是一行, 而一次中处理的最小单位是一个区域)
  3. 接下来执行下一行
• 三个变量：NF: 每一行处理的字段数，NR 目前处理到第几行，FS 目前的分隔符。

  sed:编辑

  以行为单位的文本编辑工具，sed可以直接修改档案，sed [-nef] '[动作]' [输入文本]
• -n : 安静模式, 一般sed用法中, 来自stdin的数据一般会被列出到屏幕上, 如果使用-n参数后, 只有经过sed处理的那一行被列出来.
• -e : 多重编辑, 比如你同时又想删除某行, 又想改变其他行, 那么可以用 sed -e ‘1,5d’ -e ‘s/abc/xxx/g’ filename
• -f : 首先将 sed的动作写在一个档案内, 然后通过 sed -f scriptfile 就可以直接执行 scriptfile 内的sed动作 (没有实验成功, 不推荐使用)
• -i : 直接编辑, 这回就是真的改变文件中的内容了, 别的都只是改变显示. (不推荐使用)
  动作:
• a 新增, a 后面可以接字符串, 而这个字符串会在新的一行出现. (下一行)
• c 取代, c 后面的字符串, 这些字符串可以取代 n1,n2之间的行
• d 删除, 后面不接任何东西
• i 插入, 后面的字符串, 会在上一行出现
• p 打印, 将选择的资料列出, 通常和 sed -n 一起运作 sed -n ‘3p’ 只打印第3行
• s 取代, 类似vi中的取代, 1,20s/old/new/g

  grep:截取

  文本搜集工具, 结合正则表达式非常强大.grep [要匹配的内容] [文件名].
• -c : 只输出匹配的行
• -I : 不区分大小写
• -h : 查询多文件时不显示文件名
• -l : 查询多文件时, 只输出包含匹配字符的文件名
• -n : 显示匹配的行号及行
• -v : 显示不包含匹配文本的所有行(我经常用除去grep本身)

  tail

• 从文档末尾往前取