题目一 大矩阵3x3查找
给你一个大小为 n x n 的整数矩阵 grid 。
生成一个大小为 (n - 2) x (n - 2) 的整数矩阵 maxLocal ，并满足：
maxLocal[i][j] 等于 grid 中以 i + 1 行和 j + 1 列为中心的 3 x 3 矩阵中的 最大值 。
换句话说，我们希望找出 grid 中每个 3 x 3 矩阵中的最大值。
返回生成的矩阵。
class Solution {
public int[][] largestLocal(int[][] grid) {
int[][] ans = new int[grid.length-2][grid.length-2];
//矩阵移动
for (int i = 0; i < grid.length-2; i++) {
for (int j = 0; j < grid.length-2; j++) {
ans[i][j]=max(i,j,grid);
}
}
return ans;
}
//求最大值函数
public int max(int i,int j,int[][] grid){
int max = grid[i][j];
for (int k = i; k < i+3; k++) {
for (int l = j; l < j+3; l++) {
if (max < grid[k][l]){
max = grid[k][l];
}
}
}
return max;
}
}
本题的关键点在于，外层双循环是矩阵起始遍历坐标，从每个起始遍历坐标开始才进行3x3矩阵遍历求最大值
题目二 浮点数二进制转换
二进制数转字符串。给定一个介于0和1之间的实数（如0.72），类型为double，打印它的二进制表达式。如果该数字无法精确地用32位以内的二进制表示，则打印“ERROR”。
class Solution {
public String printBin(double num) {
String ans = "0.";
//乘2取整,循环30次
for (int i = 0; i < 30; i++) {
num *= 2;
if (num >=1){
ans+="1";
num-=1;
if (num == 0){
return ans;
}
}else {
ans+="0";
}
}
return "ERROR";
}
}
本题关键在于如何转换10进制小数为2进制小数，也就是简单来说是乘2取整正序排列，注意当能够正好转化尽的也就是乘2后为1.00便可以结束转换，不能被转换尽的在30次循环后返回题目中规定的”ERROR”即可
题目三 无重复字符最长字串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
class Solution3 {
public int lengthOfLongestSubstring(String s) {
HashSet<Object> d = new HashSet<>();
int longest = 0;
//当前串长度
int nowLength = 0;
//右指针
int rk = 0;
//左指针不断左移
for (int i = 0; i < s.length(); i++) {
//右指针右移
for (int j = rk; j < s.length(); j++) {
if (!d.contains(s.charAt(j))){
d.add(s.charAt(j));
nowLength+=1;
}else {
//检查到重复更新右指针
rk = j;
break;
}
}
//更新最长字串长度
if (nowLength > longest){
longest = nowLength;
}
//删除字符
d.remove(s.charAt(i));
//当前字串长度-1
nowLength -= 1;
}
return longest;
}
}
本题使用滑块法（也就是左右指针法），能减少时间复杂度
我们只要把队列的左边的元素移出，直到满足题目要求
这里的双重循环代表的实际上是左右指针的移动，不是循环次数
题目四 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数
算法的时间复杂度应该为 O(log (m+n))
class Solution4 {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
ArrayList<Integer> integers = new ArrayList<>();
for (int i : nums1) {
integers.add(i);
}
for (int i : nums2) {
integers.add(i);
}
int n = nums1.length + nums2.length;
Collections.sort(integers);
return (n % 2 == 0)?((double) integers.get(n/2-1)+integers.get(n/2))/2:integers.get((n)/2);
}
}
使用合并排列查询的方式，注意偶数中位数需要强制转换double类型再除
方法二计算出中位数所在k值，使用双指针查找k值所在数位
题目五 找到离给定两个节点最近的节点
给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，每个节点 至多 有一条出边。
有向图用大小为 n 下标从 0 开始的数组 edges 表示，表示节点 i 有一条有向边指向 edges[i] 。如果节点 i 没有出边，那么 edges[i] == -1 。
同时给你两个节点 node1 和 node2 。
请你返回一个从 node1 和 node2 都能到达节点的编号，使节点 node1 和节点 node2 到这个节点的距离 较大值最小化。如果有多个答案，请返回 最小 的节点编号。如果答案不存在，返回 -1 。
注意 edges 可能包含环
class Solution5 {
public int closestMeetingNode(int[] edges, int node1, int node2) {
int deep = 0;
HashMap<Integer, Integer> n1 = new HashMap<>();
HashMap<Integer, Integer> n2 = new HashMap<>();
checkPathNode(edges,node1,n1,deep);
checkPathNode(edges,node2,n2,deep);
Set<Integer> nodeSet = n1.keySet();
Set<Integer> nodeSet2 = n2.keySet();
int min=-1;
int minNode=-1;
for (Integer i1 : nodeSet) {
for (Integer i2 : nodeSet2) {
if (i1.equals(i2)){
int more = n1.get(i1) > n2.get(i2)?n1.get(i1):n2.get(i2);
if (more < min || min == -1){
minNode = i1;
min = more;
}
}
}
}
return minNode;
}
private void checkPathNode(int[] edges, int node1, HashMap<Integer, Integer> n1,int deep) {
int node = node1;
while (true){
if (edges[node] == -1){
n1.put(node,deep);
return;
}
if (n1.containsKey(node)){
return;
}
n1.put(node,deep);
node = edges[node];
deep++;
}
}
}
初步方案，可行，但是时间复杂度太大，需要继续化简
题目六 保证文件名唯一
给你一个长度为 n 的字符串数组 names 。你将会在文件系统中创建 n 个文件夹：在第 i 分钟，新建名为 names[i] 的文件夹。
由于两个文件 不能 共享相同的文件名，因此如果新建文件夹使用的文件名已经被占用，系统会以 (k) 的形式为新文件夹的文件名添加后缀，其中 k 是能保证文件名唯一的 最小正整数 。
返回长度为 n 的字符串数组，其中 ans[i] 是创建第 i 个文件夹时系统分配给该文件夹的实际名称。
class Solution6 {
public String[] getFolderNames(String[] names) {
HashMap<String, Integer> sameNameFileNumMap = new HashMap<>();
String[] strings = new String[names.length];
for (int i = 0; i < names.length; i++) {
strings[i] = checkNameAndReturn(sameNameFileNumMap, names[i]);
}
return strings;
}
//查表返回新建唯一名
public String checkNameAndReturn(HashMap<String,Integer> sameNameFileNumMap,String name){
String newName = "";
//查表是否存在同名文件
if (sameNameFileNumMap.containsKey(name)){
//存在，获取当前序列
Integer integer = sameNameFileNumMap.get(name);
//尝试创建新文件,增加后缀序列
int k = 1;
//检查需要增加的k值
while (true){
if (sameNameFileNumMap.containsKey(name + "(" + (integer + k) + ")")){
k++;
}else {
break;
}
}
newName = name + "("+(integer+k)+")";
//增加当前序列
sameNameFileNumMap.put(name,integer+k);
//新文件作为老文件的序列文件，本身也是新的文件名，序列为0
sameNameFileNumMap.put(newName,0);
}else {
//不存在,创建文件
newName = name;
//加入文件集合,序列为0
sameNameFileNumMap.put(newName,0);
}
return newName;
}
}
这里的思路是使用HashMap作为历史文件名检查表，表中应该记录已经创建的文件名以及所对应的同名文件序列号，如果只有单独一个文件则为0，如果有两个同名如a,a(1),则记录为1，当需要创建文件时，都要去表中检查是否已经有同名文件，如果存在则需要获取当前已经有多少个同名文件，也就是查表获得到同名文件目前所拓展的序列号是多少，这时候就可以根据旧的序列号去推算需要新建的序列号是多少
注意：在这之前我们还需要处理一个问题，由于每次新建文件都将当前文件名（可能与表中已经拓展序列号的某个文件名名字重复，如需要创建a(1),但是之前已经创建过a(1)），作为新的文件名放入表中，并设置序列号为0，所以我们不能简单的给旧的序列号进行+1操作，还需要在拓展同名文件序列号时，检查历史表中是否有和拓展序列号文件重复的同名文件，期间我们需要设置一个增加量k值，通过不断递增k值的方式来检查新建的拓展文件名是否已经在记录表中存在过，如果存在则继续增加k值，直到满足最小正数序列号为止。此时我们就能创建同名文件的拓展序列号文件，更新同名文件当前拓展序列号的值，将新建的拓展序列号文件名也存入表中，设置序列号为0
题目七 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution7 {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode p1,p2,p3;
ListNode newList = new ListNode();
p1 = list1;
p2 = list2;
p3 = newList;
if (p1 == null && p2 == null){
return null;
}
while (true){
if (p1 == null){
p3.val = p2.val;
p3.next = p2.next;
break;
}
if (p2 == null){
p3.val = p1.val;
p3.next = p1.next;
break;
}
if (p1.val < p2.val){
p3.val = p1.val;
p1 = p1.next;
}else {
p3.val = p2.val;
p2 = p2.next;
}
p3.next = new ListNode();
p3 = p3.next;
}
return newList;
}
}
使用指针移动的方式，p1指向旧链表1头节点，p2指向旧链表2头节点，p3指向新链表3头节点，每次只需要比较p1和p2节点值，将较小值放入p3节点，然后右移此指针，当遇到某个指针指到末尾就结束比较，将剩下的另一个指针节点连接到新链表上即可
题目八 按位与为零的三元组
给你一个整数数组 nums ，返回其中 按位与三元组 的数目。
按位与三元组 是由下标 (i, j, k) 组成的三元组，并满足下述全部条件：
0 <= i < nums.length
0 <= j < nums.length
0 <= k < nums.length
nums[i] & nums[j] & nums[k] == 0 ，其中 & 表示按位与运算符。
class Solution8 {
public int countTriplets(int[] nums) {
int n=0;
HashMap<Integer, Integer> map = new HashMap<>();
//时间复杂度n^2
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length; j++) {
Integer integer = map.get((nums[i] & nums[j]));
if (integer != null){
map.put(nums[i] & nums[j],integer +1);
}else {
map.put(nums[i] & nums[j],1);
}
}
}
Set<Integer> keySet = map.keySet();
System.out.println(map);
//时间复杂度 n*2^16
for (Integer key : keySet) {
Integer time = map.get(key);
for (int num : nums) {
if ((num & key) == 0){
n += time;
}
}
}
return n;
}
}
最简单的就是3重循环num[i] & num[j] num[k] == 0 判断，但是时间复杂度为O(n^3)
这里使用哈希表来存储双重循环下num[i] & num[j] 产生的结果以及次数，
遍历哈希表，根据0<=num[i] < 2^16 可以推出，nums[i] & nums[j] 可产生结果最多为2^16，因此再遍历nums，计算与nums[k] 的按位与计算结果 需要循环最多 2^16n次，因此总共时间复杂度为O(n^2+2^16*n)，降低了时间复杂度
题目九 青蛙过河
一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。
给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃 1 个单位（即只能从单元格 1 跳至单元格 2 ）。
如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。
class Solution9 {
public boolean canCross(int[] stones) {
HashMap<Integer, Integer> map = new HashMap<>();
//记忆化容器：问题参数: k值_i位置
HashMap<String, Boolean> cache = new HashMap<>();
for (int i = 0; i < stones.length; i++) {
map.put(stones[i],i);
}
return dfs(stones, 0, 1, stones.length, map, cache);
}
private boolean dfs(int[] stones,int i, int k, int n,HashMap<Integer,Integer> map, HashMap<String, Boolean> cache) {
//命名问题
String key = i+"_"+k;
//检查问题
if (cache.containsKey(key)){
//已计算过结果，直接返回
return cache.get(key);
}
if (i == n - 1)
return true;
//新问题，此循环代表不同决策
for (int j = -1; j <= 1; j++) {
//得到新步长
int nk = k + j;
if (nk == 0){
//原地踏步，不计算
continue;
}
//对于第一次只能走1步
if (i == 0 && nk != 1){
return false;
}
//下一个石头序号
Integer nextStoneIndex = map.get(stones[i] + nk);
if (nextStoneIndex != null){
//存在石子可以跳跃
//继续dfs
boolean ans = dfs(stones,nextStoneIndex, nk, n, map, cache);
if (ans){
return true;
}
}
}
cache.put(key,false);
return false;
}
}
本题目采用了记忆化容器的思想，由于此问题如果要走完所有的分支，会出现大量的重复计算问题，因此需要用一张哈希表记录已经计算过的问题，当再次遇到此问题时，只需要从表中查找计算过的结果返回即可
题目十 经营摩天轮的最大利润
你正在经营一座摩天轮，该摩天轮共有 4 个座舱 ，每个座舱 最多可以容纳 4 位游客 。你可以 逆时针 轮转座舱，但每次轮转都需要支付一定的运行成本 runningCost 。摩天轮每次轮转都恰好转动 1 / 4 周。
给你一个长度为 n 的数组 customers ， customers[i] 是在第 i 次轮转（下标从 0 开始）之前到达的新游客的数量。这也意味着你必须在新游客到来前轮转 i 次。每位游客在登上离地面最近的座舱前都会支付登舱成本 boardingCost ，一旦该座舱再次抵达地面，他们就会离开座舱结束游玩。
你可以随时停下摩天轮，即便是 在服务所有游客之前 。如果你决定停止运营摩天轮，为了保证所有游客安全着陆，将免费进行所有后续轮转 。注意，如果有超过 4 位游客在等摩天轮，那么只有 4 位游客可以登上摩天轮，其余的需要等待 下一次轮转 。
返回最大化利润所需执行的 最小轮转次数 。 如果不存在利润为正的方案，则返回 -1 。
class Solution11 {
public int minOperationsMaxProfit(int[] customers, int boardingCost, int runningCost) {
//等待指针
int i = 0;
//等待游客数量
int wN = 0;
int profit = 0;
int maxProfit = 0;
int time = 0;
int maxTime = 0;
while (true){
if (i >= customers.length && wN == 0){
break;
}else if (i < customers.length){
//游客抵达
wN += customers[i];
}
if (wN == 0){
profit -= runningCost;
time++;
}else {
time++;
if (wN <=4){
profit += wN * boardingCost - runningCost;
wN = 0;
}else {
wN -= 4;
profit += 4 * boardingCost - runningCost;
}
}
if (profit > maxProfit){
maxProfit = profit;
maxTime = time;
}
//下一轮游客
i++;
}
if (maxProfit > 0){
return maxTime;
}else {
return -1;
}
}
}
这个题目读懂比较费解，意思就是求摩天轮启动到摩天轮运载完所有乘客期间取得利润最大值时，所周转的次数
思路比较清晰，设置一个值wN来记录目前等待的游客数量，每次都将游客列队中的游客加到wN上，每次最多装载4名游客，直到wN为0并且游客列队全部遍历完毕才没有新利润产生，因此可以结束循环
用一个maxProfit和maxTime来记录利润最大值和次数，和每次的新利润比较，如果新利润更大则更新maxProfit和maxTime
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以邮件至 1300452403@qq.com
