面试题随笔-21/4/2

面试题随笔-21/4/2

进程和线程共享资源？

共享：

• 进程代码段
• 进程的公有数据（利用这些共享的数据，线程很容易的实现相互之间的通讯）
• 进程打开的文件描述符
• 进程用户id和进程组id

线程独有：

• 线程id
• 寄存器组的值
• 线程的栈
• 错误返回码

单链表长度

public class Node {
    //链表节点的数据
    int data;
    //链表指向的下一个节点的指针
    Node next = null;

    public Node(int data) {
        this.data = data;
    }
}

public int length(Node head) {
    Node curNode = head;
    int length = 0;
    while (curNode != null) {
      curNode = curNode.next;
      length ++;
    }
    return length;
}

最大子串

public static int lengthOfLongestSubstring(String s) {
    int length = s.length();
    int ans = 0;
    Map<Character, Integer> m = new HashMap<>();
    for (int start = 0, end = 0; end < length; end++) {
      char c = s.charAt(end);
      if (m.containsKey(c)) {
        start = Math.max(start, m.get(c));
      }
      ans = Math.max(ans, end - start + 1);
      m.put(c, end + 1);
    }
    return ans;
}

数组求交集

// 数组求交集
public static HashSet intersection(Integer[] strOne, Integer[] strTwo) {
    if (ArrayUtils.isEmpty(strOne) || ArrayUtils.isEmpty(strTwo)) {
      return null;
    }
    HashSet<Integer> set = new HashSet<>(Arrays.asList(strOne));
    set.retainAll(Arrays.asList(strTwo));
    return set;
}

词联想问题

public static List<String> search(String in, List<String> data){
    in=in.trim();
    List<String> result = new ArrayList<>();
    int flag;
    for(String s:data){
      flag=s.indexOf(in);
      if (flag != -1) {
        result.add(s);
      }
    }
    return result;
}

狼羊草问题

// 狼羊草问题
private List<String> listThis = new ArrayList<String>();
private List<String> listThat = new ArrayList<String>();

public boolean isSafe(List<String> list) {
  if (list.contains("狼") && list.contains("羊") || list.contains("羊") && list.contains("草")) {
    return false;
  }else {
    return true;
  }
}

public void thisToThat() {
  String str = listThis.get(0);
  listThis.remove(str);

  if (this.isSafe(listThis)) {
    System.out.println("农夫带着 " + str + "从此岸到彼岸");
    System.out.println("此岸" + listThis + "," + "彼岸" + listThat);
    System.out.println();
    listThat.add(str);
    thatToThis();
  }else{
    listThis.add(str);
    thisToThat();
  }
}

public void thatToThis(){
  if (listThis.isEmpty()) {
    System.out.println("此岸" + listThis + "," + "彼岸" + listThat);
    return;
  }

  if (isSafe(listThat)) {
    System.out.println("农夫从彼岸到此岸");
    System.out.println("此岸" + listThis + "," + "彼岸" + listThat);
    System.out.println();
    thisToThat();
  } else {
    String str = listThat.get(0);
    listThat.remove(0);
    if (isSafe(listThat)) {
      System.out.println("农夫带着 " + str + "从彼岸到此岸");
      System.out.println("此岸" + listThis + "," + "彼岸" + listThat);
      System.out.println();
      listThis.add(str);
      thisToThat();
    } else {
      listThat.add(str);
      thatToThis();
    }
  }
}

数组的交集

public int[] intersect(int[] num1, int[] num2) {
  HashMap<Integer, Integer> map = new HashMap<>();

  for (int i = 0; i < num1.length; i++) {
    if (map.get(num1[i]) == null) {
      map.put(num1[i], 1);
    } else {
      map.put(num1[i], map.get(num1[i]) + 1);
    }
  }

  int k = 0;
  for (int i = 0; i < num2.length; i++) {
    if (map.get(num2[i]) != null && map.get(num2[i]) > 0){
      map.put(num2[i], map.get(num2[i]) - 1);
      num2[k] = num2[i];
      k++;
    }
  }
  return Arrays.copyOfRange(num2, 0, k);
}

最长公共前缀

// 最长公共前缀
public String longestCommonPrefix(String[] strs) {
  if (strs.length < 1) {
    return "";
  }
  String prefix = strs[0];
  for (int i = 0; i < strs.length; i++) {
    while (strs[i].indexOf(prefix) != 0) {
      if (prefix.length() == 0) {
        return "";
      }
      prefix = prefix.substring(0, prefix.length() - 1);
    }
  }
  return prefix;
}

旋转数组

// 旋转数组
public int[] rotate(int[] nums, int k) {
  int[] reverse_1 = reverse(nums);
  int[] reverse_2 = reverse(reverse_1);
  int[] reverse_3 = reverse(reverse_2);

  return reverse_3;
}

private int[] reverse(int[] arrs) {
  int tmp = 0;
  for (int i = 0; i < arrs.length / 2; i++) {
    tmp = arrs[i];
    arrs[i] = arrs[arrs.length - i - 1];
    arrs[arrs.length - i - 1] = tmp;
  }
  return arrs;
}

加一

public int[] plusOne(int[] digits) {
  int length = digits.length;

  for (int i = length - 1; i > 0; i--) {
    digits[i]++;
    digits[i] %= 10;
    if (digits[i] != 0) {
      return digits;
    }
  }

  // 针对第三种情况单独讨论
  digits = new int[length + 1];
  digits[0] = 1;
  return digits;
}

两数之和

// 两数之和 （ 暴力破解）
public int[] twoSum(int[] nums, int target) {
  for (int i = 0; i < nums.length; i++) {
    for (int j = i+1; j < nums.length; j++) {
      if (target - nums[j] == nums[i]) {
        return new int[]{i, j};
      }
    }
  }
  return null;
}

public int[] twoSum2(int[] nums, int target) {
  Map<Integer, Integer> map = new HashMap<>();

  for (int i = 0; i < nums.length; i++) {
    if (map.containsKey(target - nums[i])) {
      return new int[]{map.get(target - nums[i]), i};
    }
    map.put(nums[i], i);
  }

  return new int[0];

z字形变换

// z字形变换
public static String convert(String s, int numRows) {
  if(numRows == 1)
    return s;

  String[] arr = new String[numRows];
  Arrays.fill(arr, "");
  char[] chars = s.toCharArray();
  int len = chars.length;
  int period = numRows * 2 - 2;
  for (int i = 0; i < len; i++) {
    int mod = i % period;
    if (mod < numRows) {
      arr[mod] += chars[i];
    } else {
      arr[period - mod] += String.valueOf(chars[i]);
    }
  }

  StringBuilder res = new StringBuilder();
  for (String ch : arr) {
    res.append(ch);
  }

  return res.toString();
}

删除链表倒数第N个节点

// 删除链表倒数第N个节点
public ListNode removeNthFromEnd(ListNode head, int n) {
  ListNode result = new ListNode(0);
  result.next = head;

  ListNode pre = null;
  ListNode cur = result;

  int i = 1;

  while (head != null) {
    if (i >= n) {
      pre = cur;
      cur = cur.next;
    }
    head = head.next;
    i++;
  }

  pre.next = pre.next.next;
  return result.next;
}

合并两个有序链表

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  ListNode prehead = new ListNode(-1);
  ListNode result = prehead;

  while (l1 != null && l2 != null) {
    if (l1.val < l2.val) {
      prehead.next = l1;
      l1 = l1.next;
    } else {
      prehead.next = l2;
      l2 = l2.next;
    }
    prehead = prehead.next;
  }

  if (l1 != null) {
    prehead.next = l1;
  }
  if (l2 != null) {
    prehead.next = l2;
  }

  return result.next;
}