leetcode131 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: “aab” 输出: [ [“aa”,“b”], [“a”,“a”,“b”] ]
解析：首先利用冬天规划得到回文子串的（i,j），之后利用分治思想加递归。
class Solution { public List<List<String>> partition(String s) { boolean[][] dp = new boolean[s.length()][s.length()]; int length = s.length(); for (int len = 1; len <= length; len++) { for (int i = 0; i <= s.length() - len; i++) { int j = i + len - 1; dp[i][j] = s.charAt(i) == s.charAt(j) && (len < 3 || dp[i + 1][j - 1]); } } return partitionHelper(s, 0, dp); } public List<List<String>> partitionHelper(String str,int start ,boolean [][]dp){ if(start==str.length()){ List<String> list = new ArrayList<>(); List<List<String>> ans = new ArrayList<>(); ans.add(list); return ans; } List<List<String>> ans = new ArrayList<>(); for(int i=start;i<str.length();i++){ if(dp[start][i]){ String left=str.substring(start,i+1); for(List<String> right:partitionHelper(str,i+1,dp)){ right.add(0,left); ans.add(right); } } } return ans; } }leetcode133 给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（Int） 和其邻居的列表（list[Node]）。 示例： 输入： {“KaTeX parse error: Expected '}', got 'EOF' at end of input: …"neighbors":[{"id”:“2”,“neighbors”:[{“KaTeX parse error: Expected 'EOF', got '}' at position 9: ref":"1"}̲,{"id”:“3”,“neighbors”:[{“KaTeX parse error: Expected 'EOF', got '}' at position 9: ref":"2"}̲,{"id”:“4”,“neighbors”:[{“KaTeX parse error: Expected 'EOF', got '}' at position 9: ref":"3"}̲,{"ref”:“1”}],“val”:4}],“val”:3}],“val”:2},{"$ref":“4”}],“val”:1}
解释： 节点 1 的值是 1，它有两个邻居：节点 2 和 4 。 节点 2 的值是 2，它有两个邻居：节点 1 和 3 。 节点 3 的值是 3，它有两个邻居：节点 2 和 4 。 节点 4 的值是 4，它有两个邻居：节点 1 和 3 。
提示： 节点数介于 1 到 100 之间。 无向图是一个简单图，这意味着图中没有重复的边，也没有自环。 由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。 必须将给定节点的拷贝作为对克隆图的引用返回。
**解析：利用map存储拷贝节点，利用queue宽度优先遍历原节点。 注意深拷贝非索引，而是 Node clone = new Node(node.val, new ArrayList<>()); **
class Solution { public Node cloneGraph(Node node) { if (node == null) return null; Map<Node, Node> lookup = new HashMap<>(); Node clone = new Node(node.val, new ArrayList<>()); lookup.put(node, clone); Deque<Node> queue = new LinkedList<>(); queue.offer(node); while (!queue.isEmpty()) { Node tmp = queue.poll(); for (Node n : tmp.neighbors) { if (!lookup.containsKey(n)) { lookup.put(n, new Node(n.val, new ArrayList<>())); queue.offer(n); } lookup.get(tmp).neighbors.add(lookup.get(n)); } } return clone; } }leetcode134 在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。 如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
说明: 如果题目有解，该答案即为唯一答案。 输入数组均为非空数组，且长度相同。 输入数组中的元素均为非负数。 示例 1:
输入: gas = [1,2,3,4,5] cost = [3,4,5,1,2] 输出: 3 解释: 从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油 开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油 开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油 开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油 开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油 开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。 因此，3 可为起始索引。 示例 2:
输入: gas = [2,3,4] cost = [3,4,3] 输出: -1 解释: 你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。 我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油 开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油 开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油 你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。 因此，无论怎样，你都不可能绕环路行驶一周。
解析：想清楚两点 1：如果0-i不能达到，则直接从i+1开始(0-i之间任何节点都不能到达) 2：如果总的gas>总的cost，则一定存在某节点能遍历。则从遍历到n-1的那个i+1开始的结点即是所求得节点
class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int total = 0, sum = 0, start = 0; for (int i = 0; i < gas.length; ++i) { total += gas[i] - cost[i]; sum += gas[i] - cost[i]; if (sum < 0) { start = i + 1; sum = 0; } } return (total < 0) ? -1 : start; // total 小于 0，说明总消耗大于总油量，那必定无法行驶完所有站点 } }leetcode137 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。 说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1: 输入: [2,2,3,2] 输出: 3
示例 2: 输入: [0,1,0,1,0,1,99] 输出: 99
解析：利用模拟三进制，for (int i = 0; i < 32; i++) 对每个进制位进行计算，nums[j] >>> i & 1就将数字转变成第i位
class Solution { public int singleNumber(int[] nums) { int ans = 0; //考虑每一位 for (int i = 0; i < 32; i++) { int count = 0; //考虑每一个数 for (int j = 0; j < nums.length; j++) { //当前位是否是 1 if ((nums[j] >>> i & 1) == 1) { count++; } } //1 的个数是否是 3 的倍数 if (count % 3 != 0) { ans = ans+(1 << i); } } return ans; } }