class063 双向广搜【算法】

package class063;
import java.util.HashSet;
import java.util.List;
// 单词接龙
// 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列
// 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk ：
// 每一对相邻的单词只差一个字母。
// 对于 1 <= i <= k 时，每个 si 都在 wordList 中
// 注意， beginWord 不需要在 wordList 中。sk == endWord
// 给你两个单词 beginWord 和 endWord 和一个字典 wordList
// 返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目
// 如果不存在这样的转换序列，返回 0 。
// 测试链接 : https://leetcode.cn/problems/word-ladder/
public class Code01_WordLadder {
  public static int ladderLength(String begin, String end, List<String> wordList) {
    // 总词表
    HashSet<String> dict = new HashSet<>(wordList);
    if (!dict.contains(end)) {
      return 0;
    }
    // 数量小的一侧
    HashSet<String> smallLevel = new HashSet<>();
    // 数量大的一侧
    HashSet<String> bigLevel = new HashSet<>();
    // 由数量小的一侧，所扩展出的下一层列表
    HashSet<String> nextLevel = new HashSet<>();
    smallLevel.add(begin);
    bigLevel.add(end);
    for (int len = 2; !smallLevel.isEmpty(); len++) {
      for (String w : smallLevel) {
        // 从小侧扩展
        char[] word = w.toCharArray();
        for (int j = 0; j < word.length; j++) {
          // 每一位字符都试
          char old = word[j];
          for (char change = 'a'; change <= 'z'; change++) {
            // // 每一位字符都从a到z换一遍
            if (change != old) {
              word[j] = change;
              String next = String.valueOf(word);
              if (bigLevel.contains(next)) {
                return len;
              }
              if (dict.contains(next)) {
                dict.remove(next);
                nextLevel.add(next);
              }
            }
          }
          word[j] = old;
        }
      }
      if (nextLevel.size() <= bigLevel.size()) {
        HashSet<String> tmp = smallLevel;
        smallLevel = nextLevel;
        nextLevel = tmp;
      } else {
        HashSet<String> tmp = smallLevel;
        smallLevel = bigLevel;
        bigLevel = nextLevel;
        nextLevel = tmp;
      }
      nextLevel.clear();
    }
    return 0;
  }
}

package class063;
// 牛牛的背包问题 & 世界冰球锦标赛
// 牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为w。
// 牛牛家里一共有n袋零食, 第i袋零食体积为v[i]。
// 牛牛想知道在总体积不超过背包容量的情况下,他一共有多少种零食放法(总体积为0也算一种放法)。
// 输入描述：
// 输入包括两行
// 第一行为两个正整数n和w(1 <= n <= 30, 1 <= w <= 2 * 10^9),表示零食的数量和背包的容量
// 第二行n个正整数v[i](0 <= v[i] <= 10^9),表示每袋零食的体积
// 输出描述：
// 输出一个正整数, 表示牛牛一共有多少种零食放法。
// 测试链接 : https://www.nowcoder.com/practice/d94bb2fa461d42bcb4c0f2b94f5d4281
// 测试链接 : https://www.luogu.com.cn/problem/P4799
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下所有代码，把主类名改成Main，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
public class Code02_SnacksWaysBuyTickets {
  public static int MAXN = 40;
  public static int MAXM = 1 << 20;
  public static long[] arr = new long[MAXN];
  public static long[] lsum = new long[MAXM];
  public static long[] rsum = new long[MAXM];
  public static int n;
  public static long w;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer in = new StreamTokenizer(br);
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    while (in.nextToken() != StreamTokenizer.TT_EOF) {
      n = (int) in.nval;
      in.nextToken();
      w = (long) in.nval;
      for (int i = 0; i < n; i++) {
        in.nextToken();
        arr[i] = (long) in.nval;
      }
      out.println(compute());
    }
    out.flush();
    out.close();
    br.close();
  }
  public static long compute() {
    int lsize = f(0, n >> 1, 0, w, lsum, 0);
    int rsize = f(n >> 1, n, 0, w, rsum, 0);
    Arrays.sort(lsum, 0, lsize);
    Arrays.sort(rsum, 0, rsize);
    long ans = 0;
    for (int i = lsize - 1, j = 0; i >= 0; i--) {
      while (j < rsize && lsum[i] + rsum[j] <= w) {
        j++;
      }
      ans += j;
    }
    return ans;
  }
  // arr[i....e]结束，e再往右不展开了！
  // 返回值 : ans数组填到了什么位置！
  public static int f(int i, int e, long s, long w, long[] ans, int j) {
    if (s > w) {
      return j;
    }
    // s <= w
    if (i == e) {
      ans[j++] = s;
    } else {
      // 不要arr[i]位置的数
      j = f(i + 1, e, s, w, ans, j);
      // 要arr[i]位置的数
      j = f(i + 1, e, s + arr[i], w, ans, j);
    }
    return j;
  }
}

package class063;
import java.util.Arrays;
// 最接近目标值的子序列和
// 给你一个整数数组 nums 和一个目标值 goal
// 你需要从 nums 中选出一个子序列，使子序列元素总和最接近 goal
// 也就是说，如果子序列元素和为 sum ，你需要 最小化绝对差 abs(sum - goal)
// 返回 abs(sum - goal) 可能的 最小值
// 注意，数组的子序列是通过移除原始数组中的某些元素（可能全部或无）而形成的数组。
// 数据量描述:
// 1 <= nums.length <= 40
// -10^7 <= nums[i] <= 10^7
// -10^9 <= goal <= 10^9
// 测试链接 : https://leetcode.cn/problems/closest-subsequence-sum/
public class Code03_ClosestSubsequenceSum {
  public static int MAXN = 1 << 20;
  public static int[] lsum = new int[MAXN];
  public static int[] rsum = new int[MAXN];
  public static int fill;
  public static int minAbsDifference(int[] nums, int goal) {
    int n = nums.length;
    long min = 0;
    long max = 0;
    for (int i = 0; i < n; i++) {
      if (nums[i] >= 0) {
        max += nums[i];
      } else {
        min += nums[i];
      }
    }
    if (max < goal) {
      return (int) Math.abs(max - goal);
    }
    if (min > goal) {
      return (int) Math.abs(min - goal);
    }
    // 原始数组排序，为了后面递归的时候，还能剪枝
    // 常数优化
    Arrays.sort(nums);
    fill = 0;
    collect(nums, 0, n >> 1, 0, lsum);
    int lsize = fill;
    fill = 0;
    collect(nums, n >> 1, n, 0, rsum);
    int rsize = fill;
    Arrays.sort(lsum, 0, lsize);
    Arrays.sort(rsum, 0, rsize);
    int ans = Math.abs(goal);
    for (int i = 0, j = rsize - 1; i < lsize; i++) {
      while (j > 0 && Math.abs(goal - lsum[i] - rsum[j - 1]) <= Math.abs(goal - lsum[i] - rsum[j])) {
        j--;
      }
      ans = Math.min(ans, Math.abs(goal - lsum[i] - rsum[j]));
    }
    return ans;
  }
  public static void collect(int[] nums, int i, int e, int s, int[] sum) {
    if (i == e) {
      sum[fill++] = s;
    } else {
      // nums[i.....]这一组，相同的数字有几个
      int j = i + 1;
      while (j < e && nums[j] == nums[i]) {
        j++;
      }
      // nums[ 1 1 1 1 1 2....
      //       i         j
      for (int k = 0; k <= j - i; k++) {
        // k = 0个
        // k = 1个
        // k = 2个
        collect(nums, j, e, s + k * nums[i], sum);
      }
    }
  }
}