292. Nim 游戏
你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。
你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。
输入: 4
输出: false
解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；
因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。
思路：我该怎么拿。
我如果后手拿，
第一次先手拿完之后，我拿到剩余石头数目为4的倍数，然后不管对面怎么拿，我都拿4-X；
我如果先手拿，
如果是已经4的倍数，不管怎么拿，对面都会拿4-X；那么最后一定对面赢，我赢不了。
如果不是4的倍数，我先拿到剩余只是4的倍数，无论对面怎么拿，我都拿4-X；我稳赢。
因此，先手拿 概率是75% 后手是1/4；
代码：因为4是2的2次方，用与操作代替%； hash&(n-1) = hash %n;(HashMap源码)
class Solution {
public boolean canWinNim(int n) {
return (n&3)==0?false :true;
}
}
192. 统计词频
写一个 bash 脚本以统计一个文本文件 words.txt 中每个单词出现的频率。
为了简单起见，你可以假设：
-
words.txt只包括小写字母和' '。 - 每个单词只由小写字母组成。
- 单词间由一个或多个空格字符分隔。
假设 words.txt 内容如下：
the day is sunny the the
the sunny is is
你的脚本应当输出（以词频降序排列）：
the 4
is 3
sunny 2
day 1
思路：本题是脚本统计题，用awk命令即可。
awk中，可以将字符串当作索引。 $i指的是文本中当前行的第i个字符；
sort默认是从小到大 -r逆序 -k指第几列 -n为按照数值大小排序
awk '{for(i=1;i<=NF;i++){words[$i]++}} END{for(word in words){print word,words[word]}}' words.txt | sort -k2 -nr
146. LRU缓存机制
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
思路： 用linkedHashMap，linkedHashMap构造器如下：
linkedHashMap(int capacity, double loadfactor, boolean accessOrder){
}; 其中，accessOrder表示的是排序方式，默认为false，即：按照插入顺序排序。若为true，则按照访问顺序排序从小到大排序。
class LRUCache {
LinkedHashMap<Integer,Integer> map;
int size;
int count;
public LRUCache(int capacity) {
map = new LinkedHashMap(capacity,0.75F,true);
count = 0;
size = capacity;
}
public int get(int key) {
return map.getOrDefault(key,-1);
}
public void put(int key, int value) {
if(map.containsKey(key)){
map.put(key,value);
return;
}
if(count==size){
// 删除linkedHashMap中的第一个结点，用iterator迭代器更保险
Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
Iterator<Map.Entry<Integer, Integer>> iterator = entries.iterator();
if(iterator.hasNext()){
iterator.next();
iterator.remove();
}
count--;
}
map.put(key,value);
count++;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
460. LFU缓存
设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。
get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。
思路： 最少~ 想到最小堆。因此采用HashMap存储key，value；堆存储顺序的方法。
HashMap<Integer,Node>，其中Node包含value信息。
堆存储Node，根据Node的frequency及时间排序。
Node(int key, int value , int cnt, long time);
class LFUCache {
private Map<Integer, Node> m;
private PriorityQueue<Node> q;
private int size;
private int capacity;
public LFUCache(int capacity) {
size = 0;
m = new HashMap<>();
q = new PriorityQueue<>((n1, n2) -> {
if (n1.getCnt() != n2.getCnt())
return n1.getCnt() - n2.getCnt();
return (int) (n1.getTime() - n2.getTime());
});
this.capacity = capacity;
}
public int get(int key) {
if (!m.containsKey(key))
return -1;
Node node = m.get(key);
touch(node);
return node.getValue();
}
private void touch(Node node) {
node.setCnt(node.getCnt() + 1);
node.setTime(System.nanoTime());
q.remove(node);
q.add(node);
}
public void put(int key, int value) {
if (capacity <= 0)
return;
if (m.containsKey(key)) {
Node node = m.get(key);
node.setValue(value);
touch(node);
return;
}
if (size == capacity) {
Node poll = q.poll();
m.remove(poll.getKey());
size -= 1;
}
Node node = new Node(key, value, 1, System.nanoTime());
q.add(node);
m.put(key, node);
size += 1;
}
}
class Node {
private int key;
private int value;
private int cnt;
private long time;
Node(int key,int value,int cnt, long time){
this.key = key;
this.value = value;
this.cnt = cnt;
this.time = time;
}
public int getKey() {return key; }
public void setKey(int key) { this.key = key; }
public int getValue() { return value; }
public void setValue(int value) { this.value = value; }
public int getCnt() { return cnt; }
public void setCnt(int cnt) {this.cnt = cnt; }
public long getTime() { return time; }
public void setTime(long time) { this.time = time; }
}
470. 用 Rand7() 实现 Rand10()
已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。
不要使用系统的 Math.random() 方法。
思路：
这题重点在生成等概率的随机数。 7（rand7()-1）可以生成 0,7,14,``` 在此基础上，加上1~7 就可以填满1~49；并且每个数字出现的次数都是1. 如果直接rand7()rand7()，中间很多数字调用不到。 如果不是7，如1 直接+1，得到1~-13，中间很多数字重复了。
优化方案：大于40的9个数也是等概率的，因此可以利用这9个数，继续生成等概率的数
(nums-40-1)*7 ，再用7填满中间的空
/**
* The rand7() API is already defined in the parent class SolBase.
* public int rand7();
* @return a random integer in the range 1 to 7
*/
class Solution extends SolBase {
public int rand10() {
int nums = (rand7()-1)*7+rand7();
return nums >40 ? rand10() :nums%10+1;
}
}
792. 匹配子序列的单词数
给定字符串 S 和单词字典 words, 求 words[i] 中是 S 的子序列的单词个数。
示例:
输入:
S = "abcde"
words = ["a", "bb", "acd", "ace"]
输出: 3
解释: 有三个是 S 的子序列的单词: "a", "acd", "ace"。</pre>
class Solution {
public int numMatchingSubseq(String S, String[] words) {
int count = 0;
int[] dp = new int[words.length];
for(int i=0;i<words.length;i++){
if(i>0&&words[i].equals(words[i-1])){
if(dp[i-1]==1){
dp[i] = dp[i-1];
count++;
}
continue;
}
if(juage(S,words[i])){
dp[i]=1;
count++;
}
}
return count;
}
public boolean juage(String s, String b){
int sL = s.length();
int bL = b.length();
int i=0;
int j=0;
while(i!=sL&&j!=bL){
if(s.charAt(i)==b.charAt(j)){
i++;
j++;
}
else{
i++;
}
}
if(j==bL){
return true;
}
return false;
}
}
741. 摘樱桃
一个N x N的网格(grid) 代表了一块樱桃地，每个格子由以下三种数字的一种来表示：
- 0 表示这个格子是空的，所以你可以穿过它。
- 1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
- -1 表示这个格子里有荆棘，挡着你的路。
你的任务是在遵守下列规则的情况下，尽可能的摘到最多樱桃：
- 从位置 (0, 0) 出发，最后到达 (N-1, N-1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为0或者1的格子）；
- 当到达 (N-1, N-1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；
- 当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为0）；
- 如果在 (0, 0) 和 (N-1, N-1) 之间不存在一条可经过的路径，则没有任何一个樱桃能被摘到。
示例 1:
输入: grid =
[[0, 1, -1],
[1, 0, -1],
[1, 1, 1]]
输出: 5
解释：
玩家从（0,0）点出发，经过了向下走，向下走，向右走，向右走，到达了点(2, 2)。
在这趟单程中，总共摘到了4颗樱桃，矩阵变成了[[0,1,-1],[0,0,-1],[0,0,0]]。
接着，这名玩家向左走，向上走，向上走，向左走，返回了起始点，又摘到了1颗樱桃。
在旅程中，总共摘到了5颗樱桃，这是可以摘到的最大值了。
</pre>
说明:
-
grid是一个N*N的二维数组，N的取值范围是1 <= N <= 50。 - 每一个
grid[i][j]都是集合{-1, 0, 1}其中的一个数。 - 可以保证起点
grid[0][0]和终点grid[N-1][N-1]的值都不会是 -1。
思路：动态规划分别求两次最优解，其答案并不是最优解，只是次优解。必须综合考虑。
- 看成两个人同时从(0,0)走向(m-1,m-1)；坐标分别为（r1,c1）、（r2、c2）；
同时走，即c2 = r1+c1-r2; - 同时走，则dp有四个方向。分别是 下下、右右、下右、右下
因此用递归dp（grid,memo，r1,c1,r2);
class Solution {
public int cherryPickup(int[][] grid) {
// 求最优解，用dp；求匹配/用backtrace
int m = grid.length;
int memo[][][] = new int[m][m][m];
for (int[][] layer: memo)
for (int[] row: layer)
Arrays.fill(row, Integer.MIN_VALUE);
int res = dp(grid,memo,0,0,0);
return Math.max(res,0);
}
public int dp(int[][] grid,int[][][] memo,int r1,int c1, int r2){
int c2 =r1+c1-r2;
if(r1==grid.length||r2==grid.length||c1==grid.length||c2==grid.length||grid[r1][c1]==-1||grid[r2][c2]==-1){
return -99999;
}
if(r1==grid.length-1&&c1==grid.length-1){
return grid[r1][c1];
}
if(memo[r1][c1][r2]!=Integer.MIN_VALUE){
return memo[r1][c1][r2];
}
int ans = 0;
if(r1!=r2){
ans = max(dp(grid,memo,r1+1,c1,r2+1),dp(grid,memo,r1+1,c1,r2),dp(grid,memo,r1,c1+1,r2+1),dp(grid,memo,r1,c1+1,r2) ) + grid[r1][c1] + grid[r2][c2];
}else{
ans = max(dp(grid,memo,r1+1,c1,r2+1),dp(grid,memo,r1+1,c1,r2),dp(grid,memo,r1,c1+1,r2+1),dp(grid,memo,r1,c1+1,r2)) + grid[r1][c1];
}
memo[r1][c1][r2] = ans;
return ans;
}
public int max(int a, int b,int c,int d){
a = Math.max(a,b);
a = Math.max(a,c);
a = Math.max(a,d);
return a;
}
}
410. 分割数组的最大值
给定一个非负整数数组和一个整数 m，你需要将这个数组分成 *m *个非空的连续子数组。设计一个算法使得这 *m *个子数组各自和的最大值最小。
注意:
数组长度 *n *满足以下条件:
- 1 ≤ n ≤ 1000
- 1 ≤ m ≤ min(50, n)
示例:
输入:
nums = [7,2,5,10,8]
m = 2
输出:
18
解释:
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。</pre>
思路：
dp； dp难问题主要是两种：
- 最大的最小值/最小的最大值：这种需要找到dp[i][j]与子问题的动态转移方程。然后遍历每一种可能去max/min；如：鸡蛋掉落，本题。
- 直接dp维度不够，需要dp[][][];如摘樱桃，移除盒子。
假设dp[i][j]是nums[0~i]经k次分割得到的最小的最大值。假设最后一刀划在k上面，那么：
dp[i][j] = max(dp[k][j-1],sum(nums[k~i]));因为需要得到最小的最大值，因此遍历k；取最小的。
class Solution {
public int splitArray(int[] nums, int m) {
int[][] memo = new int[nums.length][m+1];
int res = Integer.MAX_VALUE;
res = Math.min(res,dp(nums,nums.length-1,m,memo));
return res;
}
public int dp(int[] nums , int i, int m,int[][] memo){
if(m>i+1){
return 0;
}
if(m==1){
return sum(nums,0,i);
}
if(memo[i][m]!=0){
return memo[i][m];
}
int minValue = Integer.MAX_VALUE;
for(int k=0;k<i;k++){
minValue = Math.min(minValue,Math.max(dp(nums,k,m-1,memo),sum(nums,k+1,i)));
}
memo[i][m] = minValue;
return minValue;
}
public int sum(int[] nums, int i, int j){
int maxValue = 0;
for(int k=i;k<=j;k++){
maxValue += nums[k];
}
return maxValue;
}
}
446. 等差数列划分 II - 子序列
难度困难45 收藏 分享 切换为英文 关注 反馈
如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。
例如，以下数列为等差数列:
1 2 3 4 5
示例：
输入：[2, 4, 6, 8, 10]
输出：7
解释：
所有的等差子序列为：
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]
class Solution {
public int numberOfArithmeticSlices(int[] A) {
int n = A.length;
long ans = 0;
Map<Integer, Integer>[] cnt = new Map[n];
for (int i = 0; i < n; i++) {
cnt[i] = new HashMap<>(i);
// f[i][diff] 表示以 A[i]为结尾，差为diff的子序列数目（长度为2个以上的子序列数目）
// f[i][A[i]-A[j]] = f[j][A[i]-A[j]] + 1;
// 可能出现重复的情况 A[i]-A[j] 重复。即j值重复。
// 那么，f[i][A[i]-A[j]] += f[j][A[i]-A[j]] + 1;
// 其中 +1 指增加了[A[i],A[j]];
// 举例 若f[j][1] 包含 {2,3} {1,2,3}
// 那么 f[i][1] 包含 {2,3,4} {1,2,3,4} {3,4}
// 用n个HashMap存 f[j][diff]的值；
// 存的是该A[i]为结尾的数组，Map为 diff:count
for (int j = 0; j < i; j++) {
long delta = (long)A[i] - (long)A[j];
if (delta < Integer.MIN_VALUE || delta > Integer.MAX_VALUE) {
continue;
}
int diff = (int)delta;
int sum = cnt[j].getOrDefault(diff, 0);
int origin = cnt[i].getOrDefault(diff, 0);
cnt[i].put(diff, origin + sum + 1);
ans += sum;
}
}
return (int)ans;
}
}
4. 寻找两个有序数组的中位数
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5</pre>
思路：
要求复杂度为O(log(m+n))，则不能单纯合并链表排序去中间的。
可以看成是在排序数组中取第K小的数。K = （m+n）/2;
将K/2；分别在该nums1和nums2中找到该索引，并比较值。较小值不可能为第K个数。因此舍弃较小值所在数组的1~K/2；如K=7；
舍弃之后，K = K-K/2 = 4；即，重新求第4小的数。
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
//处理任何一个nums为空数组的情况
if (m == 0) {
if (n % 2 != 0)
return 1.0 * nums2[n / 2];
return (nums2[n / 2] + nums2[n / 2 - 1]) / 2.0;
}
if (n == 0) {
if (m % 2 != 0)
return 1.0 * nums1[m / 2];
return (nums1[m / 2] + nums1[m / 2 - 1]) / 2.0;
}
int total = m + n;
if((total&1)==1){
return findKth(nums1,0,nums2,0,total/2+1);
}
else{
return (findKth(nums1,0,nums2,0,total/2) + findKth(nums1,0,nums2,0,total/2+1))/2.0;
}
}
public int findKth(int[] nums1, int index1, int[] nums2 ,int index2, int k){
if(index1>=nums1.length){
return nums2[index2+k-1];
}
if(index2>=nums2.length){
return nums1[index1+k-1];
}
if (k == 1){
return Math.min(nums1[index1], nums2[index2]);
}
int mid1 = Integer.MAX_VALUE;
int mid2 = Integer.MAX_VALUE;
if((index1+k/2-1)<nums1.length){
mid1 = nums1[index1+k/2-1];
}
if(index2+k/2-1<nums2.length){
mid2 = nums2[index2+k/2-1];
}
// 如果mid2>mid1 或者mid2为无穷，则nums[index1+k/2]肯定不是第K大的数值。
if(mid1<mid2){
return findKth(nums1,index1+k/2,nums2,index2,k-k/2);
}else{
return findKth(nums1,index1,nums2,index2+k/2,k-k/2);
}
}
}
327. 区间和的个数
给定一个整数数组 nums，返回区间和在 [lower, upper] 之间的个数，包含 lower 和 upper。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。
说明:
最直观的算法复杂度是 O(n2) ，请在此基础上优化你的算法。
示例:
输入: nums = [-2,5,-1], lower = -2, upper = 2,
输出: 3
解释: 3个区间分别是: [0,0], [2,2], [0,2]，它们表示的和分别为: `-2, -1, 2。
思路：暴力法较简单，不再讨论。
这题类似于求数组中逆序对的个数：归并排序。
区间和为连续的和；因此，用前缀和来做。
即用sum[i]表示，0~i区间内的nums之和。
那么 区间和表示为 s[j]-s[i] 及 [i,j]的区间和。
s[j] - s[i] >= lower && s[j] - s[i] <= upper 即满足条件。
如果存在下面这个序列，左边蓝色部分是有序的，右边黄色部分是有序的，求有多少个答案满足：
0≤S[i]−S[j]≤4,S[i]∈黄色，S[j]∈蓝色
我们尝试求解:
首先Left指针指向蓝色部分最左端，Lower指针和Upper指针指向黄色部分最左端。
此时Upper - Lower就是Left（-1）所对应的个数，这里等于0，因为Upper和Lower之后的值更大，更不可能满足要求。
接着向左移动Left，但是Upper和Lower并不需要往后移动。
因此Left（0）对应个数为0，继续移动Left,并相应地移动Upper和Lower得到：
可以得到Left(7)对应个数为2,最后移动Left，Upper和Lower得到：
可以得到Left(9)对应个数为0。
因此最后答案为2，并且我们通过线性的实现就完成了求解过程，因为Left,Upper,Lower都只向右扫描了一遍。
我们回顾一下归并排序，归并排序能够将两个有序序列在线性时间复杂度下完成合并，我们这里是类似的。
// 归并的坑： 注意 一： left=right 时（即一个数字时，需要判断该数字是否满足条件）
//注意二： 需要使用long类型。
class Solution {
int res = 0;
public int countRangeSum(int[] nums, int lower, int upper) {
int left = 0;
int right = nums.length-1;
if(right<0){
return 0;
}
long[] sum = new long[nums.length];
long count = 0;
for(int i=0;i<nums.length;i++){
count += nums[i];
sum[i] = count;
}
merge(sum,left,right,lower,upper);
return res;
}
public void merge(long[] nums, int left, int right, int lower, int upper){
if(left>=right){
if(nums[left]>=lower&&nums[left]<=upper){
res++;
}
return;
}
int mid = (left+right)/2;
merge(nums,left,mid,lower,upper);
merge(nums,mid+1,right,lower,upper);
mergeSort(nums,left,mid,right,lower,upper);
}
public void mergeSort(long[] nums, int left, int mid, int right, int lower, int upper){
long[] temp = new long[nums.length];
int index = left;
int leftStart= left;
int leftEnd = mid;
int rightStart = mid+1;
int rightEnd = right;
int lowerIndex = mid+1;
int upperIndex = mid+1;
int numElements = rightEnd - leftStart + 1;
for(int i=leftStart;i<=leftEnd;i++){
while(lowerIndex<=right&&nums[lowerIndex]-nums[i]<lower){
lowerIndex++;
}
while(upperIndex<=right&&nums[upperIndex]-nums[i]<=upper){
upperIndex++;
}
res += upperIndex-lowerIndex;
}
while(leftStart<=leftEnd&&rightStart<=rightEnd){
if(nums[leftStart]<nums[rightStart]){
temp[index++] = nums[leftStart++];
}else{
temp[index++] = nums[rightStart++];
}
}
if(leftStart>leftEnd){
while(rightStart<=rightEnd){
temp[index++] = nums[rightStart++];
}
}else{
while(leftStart<=leftEnd){
temp[index++] = nums[leftStart++];
}
}
for(int i = 0; i < numElements; i++,rightEnd--) {
nums[rightEnd] = temp[rightEnd];
}
}
}
664. 奇怪的打印机
有台奇怪的打印机有以下两个特殊要求：
- 打印机每次只能打印同一个字符序列。
- 每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。
给定一个只包含小写英文字母的字符串，你的任务是计算这个打印机打印它需要的最少次数。
示例 1:
输入:* "aaabbb"
输出: 2
解释: 首先打印 "aaa" 然后打印 "bbb"。
</pre>
示例 2:
输入: "aba"
输出: 2
解释: 首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。</pre>
思路：
用dp[i][j]表示从打印s[i~j]的最小使用次数。
其中s[i]肯定是一次打印。那么在s[i~j]中找到与s[i]相同或的s[k]，s[i]==s[k]，
那么可以用一次打印从i~打印到k。这样可以减少一次打印s[k]的次数。那么dp[i][k] = dp[i][k-1];
dp[i][j] = dp[i][k-1] + dp[k+1][j];
在所有满足条件的k中选择最小的：于是有
dp[i][j] = Math.min(dp[i][k-1]+dp[k+1][j])；
如果不存在满足条件的k，那么默认就打印一个s[i]，即初始化dp[i][j] = 1 + dp[i+1][j]；
class Solution {
int[][] memo;
public int strangePrinter(String s) {
// dp[i][j] 打印s[i~j]所需要的次数。
// s[i] = s[k]，则可以从i打印到k，一次打印s[k]，且dp[i][k] = dp[i][k-1];
// dp[i][j] = min(dp[i][k-1]+dp[k+1][j])
int n = s.length();
memo = new int[n][n];
int i=0;
return dp(s,0,n-1);
}
public int dp(String s , int i, int j){
if(i>j){
return 0;
}
if(memo[i][j]!=0){
return memo[i][j];
}
int res = dp(s, i+1, j) + 1;
int index = 0;
for(int k=i+1;k<=j;k++){
if(s.charAt(i)==s.charAt(k)){
res = Math.min(res,dp(s,i,k-1)+dp(s,k+1,j));
}
}
memo[i][j] = res;
return res;
}
}
