75. 颜色分类
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，**原地**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
思路：
可以先定义两个下标 一个标记0下标 这里是zeroIndex 初始化是0 也就是还没出现
然后从0开始遍历如果遍历到了0那就把 zeroindex对应元素和当前的 遍历的这个0交换一下然后 zero++ 那么完成之后 从0到 zeroIndex-1 就都是0 这个数字了 对于1 也 是同理 当然了 在对1进行检测交换的时候 可以直接从下标 zeroIndex开始
代码如下
public static void sortColors(int[] nums)
{
int zeroLastIndex=0;
for (int i = 0; i < nums.length; i++)
{
if (nums[i]==0)
{
nums[i]=nums[zeroLastIndex];
nums[zeroLastIndex++]=0;
}
}
int oneLastIndex=zeroLastIndex;
for (int i = zeroLastIndex; i < nums.length; i++)
{
if (nums[i]==1)
{
nums[i]=nums[oneLastIndex];
nums[oneLastIndex++]=1;
}
}
}
347. 前 K 个高频元素
(据说是腾讯的笔试题呢) leetcode的要求是要时间复杂度nlogn以下
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
这个题 先建立一个 num与次数 count的映射 hashmap 然后遍历 遍历的途中维护一个最大堆 这里用的优先队列
PriorityQueue<int[]> queue=new PriorityQueue<>((o1, o2) -> o1[1]-o2[1]);
int[] 第一个数组代表num 第二个数字代表count 后面是排序 这里就有点绕了 如果是个数组 按照这种排序方式 得到理论是个升序才对 但是这里是个优先队列 也是就peek 位置总是堆里面最小的元素 所以在遍历map 只需要与peek[1]比较即可 大于它的话就替换它就行了 当然了 如果堆都没有弄满题目的要求k 那就不判断直接插入堆就行了
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map=new HashMap<>();
for (int i = 0; i < nums.length; i++)
{
Integer count=map.get(nums[i]);
if (count==null)map.put(nums[i],1);
else map.put(nums[i],count+1);
}
PriorityQueue<int[]> queue=new PriorityQueue<>((o1, o2) -> o1[1]-o2[1]);
Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
for (Map.Entry<Integer, Integer> entry : entries)
{
Integer num = entry.getKey();
Integer count = entry.getValue();
if (queue.size()==k)
{
if (count>queue.peek()[1])
{
queue.poll();
queue.add(new int[]{num,count});
}
}
else
{
queue.add(new int[]{num, count});
}
}
int[] res = new int[k];
int cnt=0;
while (queue.size()>0)
{
res[cnt++]=queue.poll()[0];
}
return res;
}
290. 单词规律
给定一种规律
pattern和一个字符串str，判断str是否遵循相同的规律。这里的 遵循 指完全匹配，例如，pattern里的每个字母和字符串str中的每个非空单词之间存在着双向连接的对应规律。
示例1:
输入: pattern = "abba", str = "dog cat cat dog"
输出: true
先分割str 得到数组 然后比较数组的长度和pattern是不是相等 然后开始遍历 i->len 如果第一次遇到pattern中的字符 那么就应该为它建立映射 映射到 str数组里面了 但是要先检查 就是str[i]这个字符串是否已经被别的映射了 这种情况也不行的 如果也没有被映射 就可以建立了 如果 不是第一次遇到pattern中的字符那就检查 映射的字符串和str[i]是不是相等的即可
public boolean wordPattern(String pattern, String s) {
String[] strings = s.split(" ");
if (pattern.length()!=strings.length)return false;
Map<Character,String> map=new HashMap<>();
for (int i = 0; i < pattern.length(); i++)
{
char ch = pattern.charAt(i);
String firstValue=map.get(ch);
if (firstValue!=null)
{
if (!strings[i].equals(map.get(ch)))return false;
}
else
{
if (map.containsValue(strings[i]))return false;
else map.put(ch,strings[i]);
}
}
return true;
}
36. 有效的数独
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
-
数字 1-9 在每一行只能出现一次。
-
数字 1-9 在每一列只能出现一次。
-
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
这个题中 有三种情况 行 列 和小数独块 分别为他们设置三个哈希表数组
行 : rowMap=hashMap[9]
列 : colMap=hashMap[9]
子图: sonGraphMap=hashMap[9]
然后对图进行遍历 遍历的过程中 对于点 i j 直接把他映射到对应的map中去 rowMap[i].put colMap[j].put 当然了如果已经存在这个字符了 那就直接返回false了
这里计算子图hashmap数组的下标 是用的如下表达式
sonGraphIndex=i/3*3+j/3
sonGraphMap[sonGraphIndex].put 就行了 这样做时间短一点 但是用了很多空间
public boolean isValidSudoku(char[][]board)
{
HashMap<Character,Integer> [] rowMap=new HashMap[9];
HashMap<Character,Integer> [] colMap=new HashMap[9];
HashMap<Character,Integer> [] sonGraphMap=new HashMap[9];
for (int i = 0; i < 9; i++) {
rowMap[i] = new HashMap<>();
colMap[i] = new HashMap<>();
sonGraphMap[i] = new HashMap<>();
}
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
char cur=board[i][j];
if (cur!='.')
{
if (rowMap[i].get(cur)!=null)return false;
rowMap[i].put(cur,1);
if (colMap[j].get(cur)!=null)return false;
colMap[j].put(cur,1);
int sonGraphMapIndex=(i/3)*3+j/3;
if (sonGraphMap[sonGraphMapIndex].get(cur)!=null)return false;
sonGraphMap[sonGraphMapIndex].put(cur,1);
}
}
}
return true;
}
3. 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
思路：用一个hashmap把每个字母一次出现的位置记录下来并且维护一个curheadIndex指针 用来计算当前的子串的长度 当前的i-curheadIndex+1就是当前子串的长度 每一次计算之后都更新一下maxLength变量
在遍历的时候 如果当前的 字符已经出现过 说明curHeadIndex只能从这个字符出现过的位置的下一个位置 当然并不是在这个时候就直接把curHeadIndex赋值为 map.get(ch) + 1还是要首先判断一下这个位置是不是比我当前的curhead的位置大 curheadindex不能后退 例如 给出输入"abba" 如果不判断的话 curheadIndex的变化如下
a 第一次出现 curheadindex不变 还是0
b 第一次出现 curheadindex不变 还是0
b 第二次出现 curheadindex修改为 2
a 第二次出现 curheadindex 修改为1
最后一次修改就不对了 因为此时 i=3 对应的子串是bba不符合条件 所以在保持curHeadIndex不后退的情况下一直保持下去那子串就是没有重复字符的
public static int lengthOfLongestSubstring(String s) {
if (s==null||s.length() == 0)return 0;
Map<Character,Integer>map=new HashMap<>();
int maxLength=Integer.MIN_VALUE;
int curHeadIndex=0;
for (int i = 0; i < s.length(); i++)
{
Character ch=s.charAt(i);
if (map.get(ch) != null)
{
if (map.get(ch)+1>curHeadIndex)
curHeadIndex = map.get(ch) + 1;
}
map.put(ch,i);
maxLength=Math.max(maxLength,i-curHeadIndex+1);
}
return maxLength;
}
503. 下一个更大元素||
在496题的基础 把数改成了循环数组 要求输出每一个元素对应的右侧的最大近更大的元素
几乎是一样的做法 但是需要循环两遍 而且第二遍不需要push i 了因为第一遍 如果i 能够如栈就已经入栈了 第二遍只是检查在循环的情况下 如果栈里面有剩余元素 看能否再次找到一些有下一个更大元素的 相当于栈内的元素 在第二次遍历前还是有机会找到自己的下一个更大元素 的 原因就是这是一个循环数组
6 3 4 5 5 第一次遍历 栈里面肯定还剩余 6 5 5 (应该是写下标的 这里为了表达的清楚就直接写了元素) 然后第二次遍历 5 5 就可以出栈进行记录 了6最后剩余在栈里面因此得到的 res=[-1, 4, 5, 6, 6]
代码如下
public int[] nextGreaterElements(int[] nums) { Stack<Integer> stack=new Stack<>(); int[] res=new int[nums.length]; for (int i = 0; i < nums.length; i++) { while (!stack.isEmpty()&&nums[i]>nums[stack.lastElement()]) { int topIndex=stack.pop(); res[topIndex]=nums[i]; } stack.push(i); } if (stack.isEmpty())return res; for (int i = 0; i < nums.length; i++) { while (!stack.isEmpty()&&nums[i]>nums[stack.lastElement()]) { int topIndex=stack.pop(); res[topIndex]=nums[i]; } } while (!stack.isEmpty()) { res[stack.pop()]=-1; } return res; }
496.下一个更大元素
给定两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].输出: [-1,3,-1]
这是个单调栈的问题 跟下面的每日温度属于同一个类型的题 既然nums1是nums2的子集然后找到右侧的第一个比当前元素大的元素 那只需要设置一个栈 然后遍历nums2 维持这个栈为一个从栈底到栈顶递减的栈 例如上面的例子过程如下
首先因为是空 1 入栈 然后3 比1 大 1出栈 这里就表示1右边的第一个比他大的元素就是3 用一个hashmap的键值对存储起来 1->3 ，然后3 入栈 接下来是4 4比3大 3出栈 map放入3->4 然后4入栈 下面是 2 直接入栈
那对于 4 1 2 得到的res数组就是 -1 3 2 因为4,和1 还在栈里面并没有存储到map 那map如果get不到这个值 就直接让对应的res[i]=-1就行了 下面是代码
public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
int res[]=new int[nums1.length];
Stack<Integer> stack=new Stack<>();
Map<Integer,Integer> firstNumBigThanNum=new HashMap<>();
for (int i = 0; i < nums2.length; i++)
{
int cur=nums2[i];
while (!stack.isEmpty()&&stack.lastElement()<cur)
{
firstNumBigThanNum.put(stack.pop(),cur);
}
stack.push(cur);
}
for (int i = 0; i < nums1.length; i++)
{
Integer get = firstNumBigThanNum.get(nums1[i]);
res[i]=get!=null?get:-1;
}
return res;
}
522.设计循环队列
利用数组实现 设置两个值 head 和tail 每一个时刻
tail=(head+size)%capacity
size表示队列的元素个数 capacity表示队列的最大容量 在返回rear队尾元素时候 返回的是tail的前一个元素
int index=tail-1<0?(tail-1+capacity):tail-1;
return queue[index];
下面是全部代码
class MyCircularQueue {
private int[] queue;
private int capacity;
private int size;
private int head;
private int tail;
public MyCircularQueue(int k) {
queue=new int[k];
size=0;
head=0;
tail=0;
capacity=k;
}
public boolean enQueue(int value) {
if (size==capacity)return false;
queue[tail]=value;
size++;
tail=(head+size)%capacity;
return true;
}
public boolean deQueue() {
if (size==0)return false;
size--;
head=(head+1)%capacity;
return true;
}
public int Front() {
if (size==0)return -1;
return queue[head];
}
public int Rear() {
if (size==0)return -1;
int index=tail-1<0?(tail-1+capacity):tail-1;
return queue[index];
}
public boolean isEmpty() {
return size==0;
}
public boolean isFull() {
return size==capacity;
}
// public void show()
// {
// if (size==0)System.out.println("null");
// else
// {
// System.out.println("head="+head+" tail="+tail+" size="+size) ;
// do
// {
// if (head >= capacity) head = head % capacity;
// System.out.print(queue[head++] + " ");
// } while (head != tail);
// }
// }
}
232.用两个栈来实现队列
一个栈inStack 一个outStack 一个顺序的队列进栈出栈再进栈 顺序不变
push的时候 如果out里面没有元素了 那就把in里面所有的元素送到out 否则的直接push到In即可
pop的时候要看out是否为空 如果为空 就要把in的所有元素都添加过来 然后在Pop
总之就是以out优先 因为out里面的顺序才是元素添加进来的真实顺序才满足队列的要求
class MyQueue { private Stack<Integer> inStack; private Stack<Integer> outStack; public MyQueue() { inStack=new Stack<>(); outStack=new Stack<>(); } public void push(int x) { if (outStack.isEmpty()) { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } inStack.push(x); } public int pop() { if (outStack.isEmpty()) { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } return outStack.pop(); } public int peek() { if (outStack.isEmpty()) { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } return outStack.lastElement(); } public boolean empty() { return inStack.isEmpty()&&outStack.isEmpty(); }}
225.用两个队列实现栈
思路 一个主队列 一个副队列
当有元素要push进来的时候 直接加入在主队列后面
如果要pop的时候先让主队列依次poll到副队列 然后让队列尾部的元素poll 再把副队列的的元素挪回来 相当于前面的人暂时消失 队尾的人打到饭走了 然后前面的人回来了
peek也是同理 empty的话 两个队列都是空就返回empty就行了
public int pop() { while (mainQueue.size()>1) { viceQueue.add(mainQueue.poll()); } int popRes=mainQueue.poll(); while (!viceQueue.isEmpty()) { mainQueue.add(viceQueue.poll()); } return popRes; }
155 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
思路就是 除了基本的数据栈 还增加一个 辅助栈 minDataStack
push的话就是 如果需要push的话 当然是先入数据栈 然后判断
小于等于辅助栈 栈顶元素 那就入栈 为什么是小于等于呢 考虑如下的情况 假设不是小于等于而是小于的情况下 push 100 87 87 那我的辅助栈就处于现在的情况了100 87 然后假设我Pop87 现在 数据栈还剩余100 和87 但是辅助栈剩余 100 显示的当前的最小值就是100 当然是不行的
pop的话 就是pop当前的元素 并且和辅助栈栈顶部的元素比较 如果等于栈顶的元素 说明这就是一个最小值 需要把minDataStack也pop掉 其他的没什么好说的 要获取当前的最小值的话就是return minDataStack.lastElement就行了
public void push(int x) {
s.push(x);
if (minData.isEmpty()||x<=minData.lastElement())minData.push(x);
}
public void pop() {
if (minData.lastElement().equals(s.pop()))minData.pop();
}
739.每日温度
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]
这个题首先遍历T数组
设置一个栈 来存储每个温度对应的下标索引值 并且这些索引对应的温度体现在这个栈内部应该是一个温度递减的栈 为什么要温度递减？ 因为我们要求的是接下来的多少天能够使得温度升高 那就只要把中间一直在递减的温度的索引一直存进去 知道遇到某个索引时 他对应的温度不满足递减了 那就用这个索引减去栈内部的索引得到的差值就是需要的天数 注意点 如果当前的温度一直比栈顶对应的温度高 那就要一直pop并且把对应的天数存储到结果数组里面去 举例如下
[73, 74, 75, 71, 69, 72, 76, 73] 这个温度序列 遍历它
t=73 stack empty 0入栈
t=74 比栈顶0对应的温度高 那就把0出栈 res[0]=1(74的索引)-0=1;
然后把 74的索引入栈 1 因为栈已经空了 否则还要继续比下去
t=75 同样的 74对应的1 出栈 75的2进栈 res[1]=1;
然后就是 71 69 他们是递减的 直接入栈即可
然后就是 72 那 71 69就要出栈 并且在res的的对应位置上赋值 值就是72的索引减去他们各自的索引 然后72 入栈 此时栈内还剩 2对应温度75,5(对应温度72） 然后继续进行下去就可以了
最后还需要判断一下 栈里面还没有元素 还有的话依次把他们出栈 并且他们的对应的res的值为0 表示的就是自这个温度以后找不到更高的温度了 那就只能是0
240.搜索二维矩阵
在一个有规律的矩阵中搜索特定的值
这个矩阵的规律如下
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
解法1
逐行遍历 二分搜索 每次遍历先判断一下
if (matrix[i][0]>target)break;if (matrix[i][matrix[i].length-1]<target)continue;
如果本行的第一个元素大于target 这一行就不用看了
如果本行的最后一个元素小于target 这一行也不用看了
算是个小的优化
解法2
数组从左到右和从上到下都是升序的，如果从右上角出发开始遍历呢？会发现每次都是向左数字会变小，向下数字会变大，有点和二分查找树相似。二分查找树的话，是向左数字变小，向右数字变大。所以我们可以把 target 和当前值比较。如果 target 的值大于当前值，那么就向下走。如果 target 的值小于当前值，那么就向左走。如果相等的话，直接返回 true 。也可以换个角度思考。如果 target 的值小于当前值，也就意味着当前值所在的列肯定不会存在 target 了，可以把当前列去掉，从新的右上角的值开始遍历。同理，如果 target 的值大于当前值，也就意味着当前值所在的行肯定不会存在 target 了，可以把当前行去掉，从新的右上角的值开始遍历。看下边的例子。[2, 5, 8, 12, 19],[3, 6, 9, 16, 22],[10, 13, 14, 17, 24],[18, 21, 23, 26, 30]如果 target = 9，如果我们从 15 开始遍历, cur = 15 target < 15, 去掉当前列, cur = 11[1, 4, 7, 11],[2, 5, 8, 12],[3, 6, 9, 16],[10, 13, 14, 17],[18, 21, 23, 26] target < 11, 去掉当前列, cur = 7 [1, 4, 7],[2, 5, 8],[3, 6, 9],[10, 13, 14],[18, 21, 23] target > 7, 去掉当前行, cur = 8 [2, 5, 8],[3, 6, 9],[10, 13, 14],[18, 21, 23] target > 8, 去掉当前行, cur = 9, 遍历结束 [3, 6, 9],[10, 13, 14],[18, 21, 23]
代码如下
if (matrix==null||matrix.length==0||matrix[0].length==0)return false;int curCol=matrix[0].length-1;int curRow=0;int cur;while (curCol>=0&&curRow<matrix.length){ cur=matrix[curRow][curCol]; if (cur==target)return true; else if (cur>target) curCol--; else curRow++;}return false;
283. 移动0
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
输入: [0,1,0,3,12]输出: [1,3,12,0,0]
思路:可以把这个数组当成一条路，两个指针（i,j），相当于两个人，其中i具有飞行能力，j没有，这条路0相当于一条河（i可以飞过去，j不行），所以当碰到河（0）时，i飞过去了，j就停在河边，当i碰到非0（陆地）时，他会将这个陆地（非0）复制到j的前面让j前进。
这样一个过程下来，i会将这条路（数组）走完，j会停留在河流（0）或者重复陆地（非0）边。此时j的后面就是重复的数字或者0了，直接for赋值为0即可
public void moveZeroes(int[] nums) { if (nums==null||nums.length==0)return ; int i=0; int j=0; for (;i<nums.length;i++) { if (nums[i]!=0) { nums[j++]=nums[i]; } } for (;j<nums.length;j++) { nums[j]=0; } }
566.重塑矩阵
先判断 重塑前的总元素个数是否等于需要重塑后的尺寸 相等的话 遍历二维数组依次填充即可
填充方法
int[][] newNums = new int[r][c]; int newRow=0; int newCol=0; for (int i=0;i<nums.length;i++) { for (int j=0;j<nums[i].length;j++) { newNums[newRow][newCol++]=nums[i][j]; if (newCol==c) { newCol=0; newRow++; } } }return newNums;
697.数组的度
题目: 给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。
你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
思路:具有度数 d 的数组必须有一些元素 x 出现 d 次。如果某些子数组具有相同的度数，那么某些元素 x （出现 d 次）。最短的子数组是将从 x 的第一次出现到最后一次出现的数组。
对于给定数组中的每个元素，让我们知道 left 是它第一次出现的索引； right 是它最后一次出现的索引。例如，当 nums = [1,2,3,2,5] 时，left[2] = 1 和 right[2] = 3。
然后，对于出现次数最多的每个元素 x，right[x] - left[x] + 1 将是我们的候选答案，我们将取这些候选的最小值。
一个map left放第一次出现的位置 一个right 放最后一次出现的位置 一个counts放每个数字出现的次数
遍历数组 right存入当前的数字以及位置 因为存储的最后的位置 只需要不断覆盖就行 然后判断left.get(当前数字)是不是为空 是的话存入当前位置并且设置count=1 后面每次不为空的时候就更新count 更新方法就是先取出然后覆盖 官方有一个小技巧写法
counts.put(cur,counts.getOrDefault(cur,0)+1);
代码:
Map<Integer,Integer> left=new HashMap<>();
Map<Integer,Integer> right=new HashMap<>();
Map<Integer,Integer> counts=new HashMap<>();
for (int i=0;i<nums.length;i++)
{
int cur=nums[i];
right.put(cur,i);
if (left.get(cur)!=null)
{
Integer count = counts.get(cur);
counts.put(cur,count+1);
}
else
{
left.put(cur,i);
counts.put(cur,1);
}
}
Integer maxCount = Collections.max(counts.values());
int res=nums.length;
for (Integer key:counts.keySet())
{
if (counts.get(key).equals(maxCount))
{
res=Math.min(res,right.get(key)-left.get(key)+1);
}
}
return res;
1365.求数组中有多少小于当前数字的数字
思路 用一个哈希表来存储
Map<Integer,HashSet()>indexOfValues
复制一份原数组 进行排序 排序完成后 对于每一个元素我的索引是多少 就有多少数字比我小 我只需要把每个数字对应的排序后的索引存储到indexOfValues的对应的key的hashset中 然后遍历原数组 对于每一个元素 找到这个元素对应的装索引的HashSet 取最小的值 就是小于这个数字的数字的个数
代码如下
int len=nums.length;
Map<Integer, HashSet<Integer>>indexOfValues=new HashMap<>();
int[] newNums = Arrays.copyOf(nums, len);
Arrays.sort(newNums);
for (int i=0;i<newNums.length;i++)
{
int cur=newNums[i];
HashSet<Integer> indexSet = indexOfValues.getOrDefault(cur,new HashSet<>());
indexSet.add(i);
indexOfValues.put(cur,indexSet);
}
int[] res=new int[len];
for (int i=0;i<len;i++)
{
int cur=nums[i];
Integer min = Collections.min(indexOfValues.get(cur));
res[i]=min;
}
return res;
766.托普利茨矩阵
如果矩阵上每一条由左上到右下的对角线上的元素都相同，那么这个矩阵是 托普利茨矩阵 。
例如
[1,2,3,4],
[5,1,2,3],
[9,5,1,2]
给定一个 M x N 的矩阵，当且仅当它是托普利茨矩阵时返回 True。
思路:同一条对角线 有一个直线表达式 例如最长的对角线就满足j-i=0;
我们将j-i所有可以取到的值放入map 并且从第一排和第一列取一个验证值放进去作为value 然后遍历整个矩阵 如果i行j列的元素不等于map.get(j-i)中取出来的value验证值 说明不是托普利茨矩阵
Map<Integer,Integer> dataOfEveryLine=new HashMap<>(); for (int j=0;j<matrix[0].length;j++) { dataOfEveryLine.put(j-0,matrix[0][j]); } for (int i=1;i<matrix.length;i++) { dataOfEveryLine.put(0-i,matrix[i][0]); } for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[i].length; j++) { if (matrix[i][j]!=dataOfEveryLine.get(j-i))return false; } } return true;
645.错误的集合
集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。
给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
示例 1:
输入: nums = [1,2,2,4]
输出: [2,3]
思路:
第一次遍历数组 对于每个数组元素 这个元素-1一定会对应一个唯一的下表 除了那个重复的元素 所以我们通过这个下标来把第一次访问的元素置为负数 这样遍历下去 如果发现 某一次通过当前的元素值-1得到的下标 已经是个负数了 说明这个值的绝对值对应的就是重复的元素 存储下来即可 不需要进行改变 这个过程中总共 置负了length-1次 有一次是判断到负数了 所以必然有一个值没有被赋值 这个值的下标+1就是缺失的元素了
第二次遍历数组 只需要找到是正数的那个元素
注意点:在取元素然后-1作为下标的时候其实要取的是元素的绝对值
int repeatNum = 0;
//System.out.println(Arrays.toString(nums));
for (int i=0;i<nums.length;i++)
{
int cur=nums[i];
if (nums[Math.abs(cur)-1]>0)nums[Math.abs(cur)-1]*=-1;
else
{
repeatNum=Math.abs(cur);
}
//System.out.println(Arrays.toString(nums));
}
int missing = 0;
for (int i = 0; i < nums.length; i++)
{
if (nums[i]>0)
{
missing=i+1;
}
}
return new int[]{repeatNum,missing};
面试题08.12 八皇后问题
设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。
注意：本题相对原题做了扩展
示例:
输入：4
输出：[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解释: 4 皇后问题存在如下两个不同的解法。[ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ]
采用回溯法解决这个问题
构建一个queenMap[n][n]数组 从第一层开始搜索
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> res=new ArrayList<>();
char[][] queenMap=new char[n][n];
for (char[] chars : queenMap)
{
Arrays.fill(chars,'.');
}
// 开始递归
recursionQueens(n,0,queenMap,res);
return res;
}
public void recursionQueens(int n, int curRow, char[][] queenMap, List<List<String>> res)
{
if (curRow==n)
{
/**
* 搜索完成
*/
res.add(generateQueenRes(queenMap));
return;
}
for (int i = 0; i < queenMap[curRow].length; i++)
{
if (queenPosIsValid(curRow,i,queenMap))
{
queenMap[curRow][i]='Q';
recursionQueens(n,curRow+1,queenMap, res);
queenMap[curRow][i]='.';
}
}
}
public boolean queenPosIsValid(int row, int col,char[][]queenMap) {
/**
* 判断行
*/
for (int i = 0; i < queenMap.length; i++)
{
for (int j = 0; j < queenMap[i].length; j++)
{
if ((i-j)==(row-col)||(i+j)==(col+row)||i==row||j==col)
{
if (queenMap[i][j]=='Q')
{
return false;
}
}
}
}
return true;
}
public List<String> generateQueenRes(char[][] queenMap)
{
List<String> res=new ArrayList<>();
for (char[] chars : queenMap)
{
res.add(new String(chars));
}
return res;
}
}
10. 正则表达式匹配
难度-困难
给你一个字符串
s和一个字符规律p，请你来实现一个支持'.'和'*'的正则表达式匹配。
'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素所谓匹配，是要涵盖 整个 字符串
s的，而不是部分字符串。示例 1：
输入：s = "aa" p = "a"输出：false解释："a" 无法匹配 "aa" 整个字符串。示例 2:
输入：s = "aa" p = "a*"输出：true解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。示例 3：
输入：s = "ab" p = ".*"输出：true解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。示例 4：
输入：s = "aab" p = "c*a*b"输出：true解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。示例 5：
输入：s = "mississippi" p = "mis*is*p*."输出：false
思路:
设置一个二维DP数组 dp[i][j]表示当前第s中以i下标字母结束的字符串能和p中以j下标字母结束的字符串匹配 例如 s=aa p=a*
那么 dp[0][0]=true
对于 [普通字母/ '.']* 这种组合 如何判断他们能否匹配？
假设*前面的字母为 例如我们要匹配aa 和a*
S中第二个a位置为i a*中 *的位置为j
那么有如下逻辑
if (p.charAt(j-2)==s.charAt(i-1)||p.charAt(j-2)=='.')
{
dp[i][j]=dp[i][j-2]||dp[i][j-1]||dp[i-1][j];
}
else
{
dp[i][j]=dp[i][j-2];
}
-
如果
*前面的字母和i位置的字母无法判定相等 那么我们只能舍弃*和他前面的字母 只能让
dp[i][j]=dp[i][j-2];
也就是让舍弃掉这两个符号之前的字符串和当前i位置的S字符串进行匹配 -
那么如果当前*前面的字母和i位置的字母是可以判定相等的呢？ 那么有这样的情况
-
舍弃掉*号 直接到
j-1和S串进行匹配 那么此时dp[i][j]也就是dp[i][j-1] -
和第一种大情况一样 舍弃掉两个字符 也就是
dp[i][j]=dp[i][j-2]; -
然后就是最关键的一种情况 把
*看做许多个a 此时我们可以这样假设 有经过*的复制 有无穷多个a*=无穷多个a那么我们舍弃掉最后一个a 也无所谓 然后把S串上的aa 尾部 减去一个a 也就是 让我无穷多个-1个
a去和S串中-去尾部的一个a进行匹配所以有
dp[i][j]=dp[i-1][j];
-
class Solution {
public boolean isMatch(String s, String p) {
boolean [][]dp=new boolean[s.length()+1][p.length()+1];
if (s.charAt(0)==p.charAt(0)||p.charAt(0)=='.')
dp[1][1]=true;
dp[0][0]=true;
/**
* 初始化第0行
*/
for (int i = 1; i < dp[0].length; i++)
{
if (i==1)
{
if (p.charAt(i-1)=='*')dp[0][i]=true;
else
{
dp[0][i]=false;
}
}
else
{
if (p.charAt(i-1)=='*')
{
dp[0][i]=dp[0][i-2];
}
else
{
dp[0][i]=false;
}
}
}
for (int i = 1; i < dp.length; i++)
{
for (int j = 1; j < dp[i].length; j++)
{
if (j==1)
{
if (p.charAt(j-1)==s.charAt(i-1)||p.charAt(j-1)=='.')
{
dp[i][j]=i==1;
}
}
else
{
if (p.charAt(j-1)=='*')
{
if (p.charAt(j-2)==s.charAt(i-1)||p.charAt(j-2)=='.')
{
dp[i][j]=dp[i][j-2]||dp[i][j-1]||dp[i-1][j];
}
else
{
dp[i][j]=dp[i][j-2];
}
}
else
{
dp[i][j]=dp[i-1][j-1]&&(p.charAt(j-1)==s.charAt(i-1)||p.charAt(j-1)=='.');
}
}
}
}
return dp[s.length()][p.length()];
}
}
顺时针打印数组（回形数组）
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
思路
设置一组边界 top right bottom left 也就是矩形的四条边 每次遍历完成一条边 就把当前的变缩小1
例如3*3的数组 第一次的边界为
left=0 right=2;
top=0 bottom=2;
遍历完成第一条上边界之后 top++
以此类推 完成顺时针打印 当左边界>右边界或者上边界大于下边界的时候那么结束打印
class Solution {
public int[] spiralOrder(int[][] matrix) {
if (matrix==null)return null;
if (matrix.length==0)return new int[0];
int left=0;
int right=matrix[0].length-1;
int top=0;
int bottom=matrix.length-1;
int resLen=(bottom+1)*(right+1);
int [] res=new int[resLen ];
int cur=0;
while (true)
{
if (left>right)break;
for (int i = left; i <=right; i++)
{
res[cur++]=matrix[top][i];
}
top++;
if (top>bottom)break;
for (int i = top; i <=bottom; i++)
{
res[cur++]=matrix[i][right];
}
right--;
if (left>right)break;
for (int i = right; i >= left; i--)
{
res[cur++]=matrix[bottom][i];
}
bottom--;
if (top>bottom)break;
for (int i=bottom;i>=top;i--)
{
res[cur++]=matrix[i][left];
}
left++;
}
return res;
}
}
剑指 Offer 56 - I. 数组中数字出现的次数
难度中等
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
思路:
如果数组中只有一个 出现一次的数字 那么我们直接将数组中的所有元素进行遍历 做异或运算 得到的结果就是 出现一次的数字
因为a^a=0 ; 0^x=x;
但是现在数组中有两个只出现一次的元素，还是采取这种做法 得到结果就是 x^y;xy分别为出现一次的两个元素
如何将他们区分开呢？
可以这样考虑 只要这两个数字不一样 那么必定有一位数字不同
我们只需要找到这一位数字 然后令一个数字m在这一位上面为1其他的位数都是0
举例:
x=4 y=6;
x: 100
y: 110;
那么m就设置为 010;即可 如此一来我们可以将所有的数字与m做与预算然后判断与运算的结果是0还是非0 就可以区分出X 和Y
那么如何确定m在哪一位为1呢？
我们知道x^y的结果其实反映的就是xy的不同的位数上面的数字的相等关系 显而易见 我们从x^y的最低位找起 设置m的初始值为1;
如果 (x^y)&m ==0 那么也就是说 第一位 数字 x与y相等 异或运算相同为0嘛 接下来就以此类推 将m*2—>10 再重复上面的运算 直到那个结果!=0为止 我们就找到了m的值
然后就可以对数组进行分组了
完整代码如下:
public int[] singleNumbers(int[] nums) {
int xy=0; //两个不相同的数字的 ^ 异或
for (int num : nums) {
xy^=num;
}
// 1000000010000
// 0000000010000 --->m
// 1 3 3 4 4 6 ---> 1^6 001^100--->101
//从低位开始找到第一位不相同的数字 根据这个来分组
//例如 x和y的第3位不一样 那么就将所有数字的第三位进行与运算
int m=1;
while ((m&xy)==0)
{
m<<=1;
}
int x=0;
int y=0;
for (int num : nums) {
if ((num&m)==0) x^=num;
else y^=num;
}
return new int[]{x,y};
}
剑指 Offer 62. 圆圈中最后剩下的数字
难度简单565
0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
示例 1：
输入: n = 5, m = 3
输出: 3
示例 2：
输入: n = 10, m = 17
输出: 2
思路:
这是一个约瑟夫环问题 可以采用迭代的方式来思考
考虑如下的例子
n = 8 m=3
0 1 2 3 4 5 6 7 8
3 4 5 6 7 8 0 1
6 7 8 0 1 3 4
0 1 3 4 6 7
4 6 7 0 1
0 1 4 6
6 0 1
6 0
0
n=5 m=3
0 1 2 3 4
3 4 0 1
1 3 4
1 3
3
数组中的数字被删掉之后 由于是从被删除的位置开始计数 所以把被删除的位置后面那个元素作为新的数组的头依次向下排放
可以看到最后剩下来的数字是0 只要能找到结果数字的下标变化的规律 我们就能找到答案
从上往下看 我们可以观察到 每次删除一个元素 所有的元素的下标都-3 也就是-m了 例如第一行到第二行 0下标的元素 数字0的下标 变为了 -2 也就是 7±2=5(循环队列 为负数就是表示在后面)；第三行0元素 的下标为 5-3=2；
所以我们可以进行逆推 假设队列中只有一个元素 那么它的下标一定为0 当然 对于这个题目来说 由于数组中的n个数字正好就是0-n-1
所以这一个单独的元素就是0 但是这些元素是不是自然数0-n-1其实并不重要 因为我们从始至终考虑的都是结果数字的下标问题 而不是这个值等于多少 由于这道题的特殊性 我们知道了最终数字在初始（也就是未被删除元素）时的下标 直接就是答案了 如果是题目给出了数组 算出了下标还需要取值一次才行
刚才说到从上往下每次下标-3 那么逆推就是 从下往上每次结果下标+3 但 +3 之后可能会遇到大于当前的数组的长度 那么对当前的数组长度取模即可
所以代码如下
public int lastRemaining(int n, int m) {
int f=0;
for (int i = 2; i <= n; i++) {
f=(f+m)%i;
}
return f;
}