面试题随笔-21/4/3

环形链表

// 环形链表 (该方法还不是理解)
public boolean hashCycle(ListNode head) {
  HashMap<ListNode,Integer> map = new HashMap<>();
  while (head != null) {
    if (map.containsKey(head)) {
      return true;
    } else {
      map.put(head, head.val);
    }

    head = head.next;
  }
  return false;
}

public boolean hashCycle2(ListNode head) {
  ListNode slow,fast;
  slow = fast = head;
  while (fast != null && fast.next != null) {
    fast = fast.next.next;
    slow = slow.next;

    if (fast == slow)
      return true;
  }

  return false;
}

两数相加

// 两数相加
public ListNode addTwoNumbers(ListNode l1,ListNode l2) {
  ListNode result = new ListNode(0);
  int tmp = 0;

  int i = 0;
  ListNode head = null;

  while (l1 != null || l2 != null || tmp != 0) {
    if (l1 != null) {
      tmp += l1.val;
      l1 = l1.next;
    }

    if (l2 != null) {
      tmp += l2.val;
      l2 = l2.next;
    }

    result.next = new ListNode(tmp % 10);
    tmp = tmp / 10;
    result = result.next;

    if (i == 0) {
      head = result;
    }
    i++;
  }

  return head;
}

爬楼梯

// 爬楼梯
public int climbStairs(int n) {
  if (n == 1) {
    return 1;
  }

  int[] dp = new int[n + 1];
  dp[1] = 1;
  dp[2] = 2;
  for (int i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

最大子序和

// 最大子序和
public int maxSubArray(int[] nums) {
  if (nums.length < 1) {
    return 0;
  }

  int[] dp = new int[nums.length];
  int result = nums[0];
  dp[0] = nums[0];

  for (int i = 1; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
    result = Math.max(dp[i], result);
  }

  return result;
}

最长上升子序列

// 最长上升子序列
public int lengthOfLIS(int[] nums) {
  if (nums.length < 1) {
    return 0;
  }

  int[] dp = new int[nums.length];
  int result = 1;

  for (int i = 0; i < nums.length; i++) {
    dp[i] = 1;
    for (int j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[j] + 1, dp[i]);
      }
    }
    result = Math.max(result, dp[i]);
  }

  return result;
}

三角形最小路径和

// 三角形最小路径和
public int minimumTotal(List<List<Integer>> triangle) {
  int n = triangle.size();
  int[][] f = new int[n][n];
  f[0][0] = triangle.get(0).get(0);

  for (int i = 1; i < n; ++i) {
    f[i][0] = f[i - 1][0] + triangle.get(i).get(0);
    for (int j = 1; j < i; j++) {
      f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle.get(i).get(j);
    }
    f[i][i] = f[i - 1][i - 1] + triangle.get(i).get(i);
  }

  int minTotal = f[n - 1][0];
  for (int i = 0; i < n; ++i) {
    minTotal = Math.min(minTotal, f[n - 1][i]);
  }
  return minTotal;
}

最小路径

// 最小路径
public int miniPathSum(int[][] grid) {
  if (grid == null || grid.length == 0 || grid[0].length == 0) {
    return 0;
  }

  int rows = grid.length, columns = grid[0].length;
  int[][] dp = new int[rows][columns];

  dp[0][0] = grid[0][0];

  for (int i = 1; i < rows; i++) {
    dp[i][0] = dp[i - 1][0] + grid[i][0];
  }

  for (int j = 0; j < columns; j++) {
    dp[0][j] = dp[0][j - 1] + grid[0][j];
  }

  for (int i = 1; i < rows; i++) {
    for (int j = 1; j < columns; j++) {
      dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
    }
  }
  return dp[rows - 1][columns - 1];
}

打家劫舍

// 打家劫舍
public int rob(int[] nums) {

  if (nums.length < 1) {
    return 0;
  }

  if (nums.length == 1) {
    return nums[0];
  }

  if (nums.length == 2) {
    return Math.max(nums[0], nums[1]);
  }

  int[] dp = new int[nums.length];
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  for (int i = 2; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  }
  return dp[nums.length - 1];
}

反转字符串

// 反转字符串
public char[] reverseString(char[] s) {
  int left = 0;
  int right = s.length - 1;

  char tmp = '#';

  while (left < right) {
    tmp = s[left];
    s[left] = s[right];
    s[right] = tmp;

    left++;
    right--;
  }

  return s;
}

第一唯一字符

// 第一唯一字符
public int firstUniqueChar(String s) {
  Map<Character, Integer> frequency = new HashMap<Character, Integer>();
  for (int i = 0; i < s.length(); i++) {
    char ch = s.charAt(i);
    frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
  }

  for (int i = 0; i < s.length(); i++) {
    if (frequency.get(s.charAt(i)) == 1) {
      return i;
    }
  }

  return -1;
}

sunday匹配

// sunday 匹配
public int strStr(String origin, String aim) {
  if (origin == null || aim == null) {
    return 0;
  }
  if (origin.length() < aim.length()) {
    return -1;
  }

  // 目标串匹配索
  int originIndex = 0;
  // 模式串匹配索引
  int aimIndex = 0;
  // 成功匹配完终止条件： 所有aim均成功匹配
  while (aimIndex < aim.length()) {
    // 针对origin匹配完，但aim未匹配完情况处理 如 mississippi sippia
    if (originIndex > origin.length() - 1) {
      return -1;
    }

    if (origin.charAt(originIndex) == aim.charAt(aimIndex)) {
      // 匹配则index均加1
      originIndex++;
      aimIndex++;
    } else {
      // 在我们上面的样例中，第一次计算值为6，第二次值为13
      int nextCharIndex = originIndex - aimIndex + aim.length();
      // 判断下一个目标字符（上面图里的那个绿框框）是否存在。
      if (nextCharIndex < origin.length()) {
        // 判断目标字符在模式串中匹配到，返回最后一个匹配的index
        int step = aim.lastIndexOf(origin.charAt(nextCharIndex));
        if (step != -1) {
          // 不存在的话，设置到目标字符的下一个元素
          originIndex = nextCharIndex + 1;
        } else {
          // 存在的话，移动对应的数字（参考上文中的存在公式）
          originIndex = nextCharIndex - step;
        }
        // 模式串总是从第一个开始匹配
        aimIndex = 0;
      } else {
        return -1;
      }
    }
  }
  return originIndex - aimIndex;
}