51.编写一个程序，找到两个单链表相交的起始节点。
双指针法
1.创建两个指针pA和pB，分别初始化为链表A和B的头结点。然后让它们向后逐结点遍历。
2.当pA到达链表的尾部时，将它重定位到(它的next=B)链表B的头结点 (你没看错，就是链表B); 类似的，当pB到达链表的尾部时，将它重定位到链表A的头结点。
3.若在某一时刻pA和pB相遇，则pA/pB为相交结点。
4.想弄清楚为什么, 可以考虑以下两个链表:A={1,3,5,7,9,11}和B={2,4,9,11}，相交于结点9。 由于B.length (=4) < A.length (=6)，pB比pA少经过2个结点，会先到达尾部。将pB重定向到A的头结点，pA重定向到B的头结点后，pB要比pA多走2个结点。因此，它们会同时到达交点。
5.如果两个链表存在相交，它们末尾的结点必然相同。因此当pA/pB到达链表结尾时，记录下链表A/B对应的元素。若最后元素不相同，则两个链表不相交。
复杂度分析
时间复杂度 :O(m+n)。
空间复杂度 :O(1)。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
/**
定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差)
两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度
**/
if(headA == null || headB == null) return null;
ListNode pA = headA, pB = headB;
// 在这里第一轮体现在pA和pB第一次到达尾部会移向另一链表的表头, 而第二轮体现在如果pA或pB相交就返回交点, 不相交最后就是null==null
while(pA != pB) {
//注意这里是pA等于 不是连接起来pA.next=
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
52.给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数
输入: [2,2,1,1,1,2,2]
输出: 2
从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，减到0就重新换个数开始计数，总能找到最多的那个
//摩尔投票法,先假设第一个数过半数并设cnt=1；
//遍历后面的数如果相同则cnt+1，不同则减一，
//当cnt为0时则更换新的数字为候选数（成立前提：有出现次数大于n/2的数存在）
public int majorityElement(int[] nums) {
int c=1;
int res=nums[0];
for(int i=1,j=nums.length-1;i<j;i++){
if(nums[i]==res){
c++;
}else{
c--;
if(c==0){
res = nums[i+1];
}
}
}
return res;
}
53.你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
dp 方程
dp[i] = max(dp[i-2]+nums[i], dp[i-1])注意dp[0]dp[1]的处理 是返回dp[n-1]
public int rob(int[] nums) {
int n = nums.length;
if (n <= 1) return n == 0 ? 0 : nums[0];
int[] memo = new int[n];
memo[0] = nums[0];
memo[1] = Math.max(nums[0], nums[1]);//注意0 1 的处理
for (int i = 2; i < n; i++)
memo[i] = Math.max(memo[i - 1], nums[i] + memo[i - 2]);
return memo[n - 1];
}
54.给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
输入:
11000
11000
00100
00011
输出: 3
并查集
使用并查集解决本问题的思想很简单：
1、如果当前是“陆地”，尝试与周围(向右和向下)合并一下；
2、如果当前是“水域”，就把所有的“水域”合并在一起，为此，我设置了一个虚拟的结点，表示“所有的水域都和这个虚拟结点是连接的”。
㈠如果当前是 “陆地”，尝试与周围合并一下”，此时 “周围” 并不需要像 “深度优先遍历” 和 “广度优先遍历” 一样，方向是四周。事实上，只要 “向右”、“向下” 两个方向就可以了
㈡针对上面的第 2 点：由于我设置了“虚拟结点”，最后返回“岛屿个数”的时候，应该是连通分量个数 - 1，不要忘记将 “虚拟结点” 代表的 “水域” 分量去掉，剩下的连通分量个数就是 “岛屿个数”。
private int n,m;
private int[] pre;
private int[][] directions = {{1,0},{0,1}};//向右向下
public boolean isover(int x,int y){
if(x>=0&&x<n&&y>=0&&y<m){
return true;
}else{
return false;
}
}
public int find(int x){
if(pre[x]==x)
return pre[x];
return find(pre[x]);
}
public void join(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy){
if(fx<fy){
pre[fy]=fx;
}else{
pre[fx]=fy;
}
}
}
public int numIslands(char[][] grid) {
if(grid.length==0)
return 0;
m=grid.length;
n=grid[0].length;
pre = new int[m*n+1];
//把二维转换为1维 i*n+(j+1)
//所以水域的虚拟老大设为0，因为i*n+(j+1)不会为0
for(int i=0;i<pre.length;i++){
pre[i]=i;//开始自己上级都是自己
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]=='0')//是水域
{
pre[i*n+(j+1)] = 0;
}else{
//向下向右如果都是陆地，即 "1"，就要合并一下
for(int[] temp : directions){
int newx = i+temp[0];
int newy = j+temp[1];
//判断是否越界
if(isover(newx,newy)){
System.out.println(newx+" "+newy);
if(grid[newx][newy]=='1'){
join(i*n+(j+1),newx*n+(newy+1));
}else{
pre[newx*n+(newy+1)] = 0;
}
}
}
}
}
}
int count=0;
for(int i=1;i<=m*n;i++){
// System.out.println(i+""+pre[i]);
if(pre[i]==i)
count++;
}
return count;
}
55.反转一个单链表。
看注释
public ListNode reverseList(ListNode head) {
ListNode prev = null; //前指针节点
ListNode curr = head; //当前指针节点
//每次循环，都将当前节点指向它前面的节点，然后当前节点和前节点后移
while (curr != null) {
ListNode nextTemp = curr.next; //临时节点，暂存当前节点的下一节点，用于后移
curr.next = prev; //将当前节点指向它前面的节点
prev = curr; //前指针后移
curr = nextTemp; //当前指针后移
}
return prev;
}
题目变成
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null) {
return null;
}
////当前指针节点和前指针节点
ListNode cur = head, prev = null;
while (m > 1) {//这是m>1 注意
prev = cur;
cur = cur.next;
m--;
n--;
}
ListNode con = prev, tail = cur;//con保存开始的父亲 tail保存开始的起点
ListNode third = null;//临时节点，暂存当前节点的下一节点，用于后移
//每次循环，都将当前节点指向它前面的节点，然后当前节点和前节点后移
while (n > 0) {
third = cur.next;//暂存当前节点的下一节点，用于后移
cur.next = prev;//将当前节点指向它前面的节点
prev = cur;//前指针后移
cur = third;//当前指针后移
n--;
}
if (con != null) {
con.next = prev;//开始的父亲等于结尾的这个节点
} else {
head = prev;
}
tail.next = third;//开始的起点的结束后的下一个节点
return head;
}
56.现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
1.课程安排图是否是 有向无环图(DAG)。即课程间规定了前置条件，但不能构成任何环路，否则课程前置条件将不成立。
2.通过 拓扑排序 判断
拓扑排序是对 DAG 的顶点进行排序，使得对每一条有向边(u, v)，均有u（在排序记录中）比v先出现。亦可理解为对某点v而言，只有当v的所有源点均出现了，v才能出现。
3.通过课程前置条件列表prerequisites可以得到课程安排图的 邻接矩阵adjacency
广度优先遍历BFS
算法流程：
1.统计课程安排图中每个节点的入度，生成 入度表 indegrees。
2.借助一个队列 queue，将所有入度为 0 的节点入队。
3.当 queue 非空时，依次将队首节点出队，在课程安排图中删除此节点 pre：
-并不是真正从邻接表中删除此节点 pre，而是将此节点连接的节点(它的孩子) cur 的入度 −1，即 indegrees[cur] -= 1。
当这些孩子节点cur入度 -1后 孩子cur 的入度为 0，说明 孩子cur 所有的前驱节点已经被 “删除”，此时将孩子 cur 入队。
在每次 pre 出队时，执行 numCourses--；
若整个课程安排图是有向无环图（即可以安排），则所有节点一定都入队并出队过，即完成拓扑排序。
换个角度说，若课程安排图中存在环，一定有节点的入度始终不为 0。
因此，拓扑排序出队次数等于课程个数，返回 numCourses == 0 判断课程是否可以成功安排
public boolean canFinish(int numCourses, int[][] prerequisites){
if(numCourses==0)
return true;
//得到所有节点的入度数组 因为prerequisites里面的都是【1，0】这种 ，前者是子，后者是父
int[] indegrees = new int[numCourses];//java默认初始化为0
for(int[] temp : prerequisites){
indegrees[temp[0]]++;//前者是子，后者是父
}
Queue<Integer> queue = new LinkedList<>();
//初始化队列，把入度为0 的装进去
for(int i=0;i<numCourses;i++){
if(indegrees[i]==0)
queue.add(i);
}
//依次出队然后删除
while (!queue.isEmpty()){
int pre = queue.poll();
numCourses--;//计算出队的个数
for (int[] temp : prerequisites){
if(temp[1]==pre){//找到以它为父的边
indegrees[temp[0]]--;//删除它就是删除这条边 它的孩子入度--
if(indegrees[temp[0]]==0){//减后孩子的入度为0 表示它是没有父的 没有了依赖所以可以入队
((LinkedList<Integer>) queue).add(temp[0]);
}
}
}
}
return numCourses==0?true:false;
}
深度优先遍历DFS
算法流程（思路是通过 DFS 判断图中是否有环）：
1.借助一个标志列表 flags，用于判断每个节点 i （课程）的状态：
-未被 DFS 访问：i == 0；
-已被其他节点启动的DFS访问：i == -1；
-已被当前节点启动的DFS访问：i == 1。
2.对 numCourses 个节点依次执行 DFS，判断每个节点起步 DFS 是否存在环，若存在环直接返回 False。
DFS 流程
终止条件：
1.当 flag[i] == -1，说明当前访问节点已被其他节点启动的 DFS 访问，无需再重复搜索，直接返回 TrueTrue。
2.当 flag[i] == 1，说明在本轮 DFS 搜索中节点 i 被第 2 次访问，即 课程安排图有环，直接返回 False。
3.将当前访问节点 i 对应 flag[i] 置 1，即标记其被本轮 DFS 访问过；
4.递归访问当前节点 i 的所有邻接节点(即孩子节点) j，当发现环直接返回 False；
5.当前节点所有邻接节点已被遍历，并没有发现环，则将当前节点 flag 置为 -1并返回 True。
6.若整个图 DFS 结束并未发现环，返回 True
public boolean canFinish(int numCourses, int[][] prerequisites){
//构建地图 更好的知道每个点它的孩子和父亲
int[][] map = new int[numCourses][numCourses];
int[] flag = new int[numCourses];//每个节点的访问标志位
for(int[] temp : prerequisites){
map[temp[0]][temp[1]] = 1 ;//代表哪俩个节点连接一起 且前面是父 后面是子
}
for(int i=0;i<numCourses;i++){
if(!DFS(map,i,flag))return false;//验证每个节点的DFS
}
return true;
}
public boolean DFS(int[][] map,int num,int[] flag){
//递归终点
if(flag[num]==1)return false;//本轮第二次访问说明有环
if(flag[num]==-1)return true;//别的节点在DFS时候已经判断过了，这不用讨论了
flag[num]=1;//先表示访问了
//递归访问它的所有孩子节点
for(int i=0;i<map.length;i++){
if(map[num][i]==1){
if(DFS(map,i,flag)==false){
return false;
}
}
}
flag[num]=-1;//表示这个节点是安全的 下次不用再判断它了
return true;
}
57.实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
说明:
你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true
以下是节点不保存数据的解法， 很简单。
整棵树由一个root节点为根节点， 每个节点并不显式地存储数据， 而是使用下标来存储。
可以类比为用树的边来保存数据：将word的每一个字符存储在一条一条的边上
package wg;
public class Trie {
class Node{
boolean isword=false;
Node[] chars = new Node[26];
}
Node root = new Node();
public Trie() {
}
/** Inserts a word into the trie. */
public void insert(String word) {
Node p = root;
for(char ch : word.toCharArray()){
if(p.chars[ch-'a']==null){
p.chars[ch-'a'] = new Node();
p=p.chars[ch-'a'];
}else{
p=p.chars[ch-'a'];
}
}
p.isword=true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
Node p = root;
for(char ch : word.toCharArray()){
if(p.chars[ch-'a']==null){
return false;
}else{
p=p.chars[ch-'a'];
}
}
return p.isword;
}
/** 如果trie中有任何以给定前缀开头的单词，则返回true。 */
public boolean startsWith(String prefix) {
Node p = root;
for(char ch : prefix.toCharArray()){
if(p.chars[ch-'a']==null){
return false;
}else{
p=p.chars[ch-'a'];
}
}
return true;
}
public static void main(String[] args) {
Trie obj = new Trie();
obj.insert("str");
boolean param_2 = obj.search("str");
boolean param_3 = obj.startsWith("st");
}
}
58.在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
O(n)桶排思想
1.一次遍历找到最大最小值
2.再一次遍历，把每个值与最小值的差装进桶bucket[差值]++；
3.从后往前一次遍历桶找到倒数第K个最大值
`注意可能减去”最后一个“桶中个数后 k小于0了，说明就是那个桶中的数
public int findKthLargest(int[] nums, int k) {
int max = Integer.MIN_VALUE,min = Integer.MAX_VALUE;
for(int i : nums){
max = Math.max(i,max);
min = Math.min(i,min);
}
int[] bucket = new int[max-min+1];//就是有点费空间
for(int i : nums){
int t = i-min;
bucket[t]++;
}
for(int i=max-min;i>=0;i--){
if(bucket[i]>0){
k-=bucket[i];
}
if(k<=0){
return i+min;
}
}
return 0;
}
59.在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
当我们判断以某个点为正方形右下角时最大的正方形时，那它的上方，左方和左上方三个点也一定是某个正方形的右下角。这是定性的判断，那具体的最大正方形边长呢？我们知道，该点为右下角的正方形的最大边长，最多比它的上方，左方和左上方为右下角的正方形的边长多1，最好的情况是是它的上方，左方和左上方为右下角的正方形的大小都一样的，这样加上该点就可以构成一个更大的正方形。 但如果它的上方，左方和左上方为右下角的正方形的大小不一样，合起来就会缺了某个角落，
因为这三个点是构成以这个为右下角为正方形必不可少的点。这时候只能取那三个正方形中最小的正方形的边长加1了，如果其中有个为0，则他能构成的就只有变成为1的正方形，即它本身。假设dp[i]表示以i,j为右下角的正方形的最大边长，则有dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1当然，如果这个点在原矩阵中本身就是0的话，那dp[i]肯定就是0了。
public int maximalSquare(char[][] matrix) {
int m=matrix.length;
if(m==0)
return 0;
int n=matrix[0].length;
int[][] dp = new int[m+1][n+1];//默认为0
int maxlong = 0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(matrix[i-1][j-1]=='1'){
dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i-1][j-1]),dp[i][j-1])+1;
maxlong = Math.max(dp[i][j],maxlong);
}
else dp[i][j]=0;
}
}
return maxlong*maxlong;
}
60.翻转一棵二叉树。
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
1.
// 先序遍历--从顶向下交换
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
// 保存右子树
TreeNode rightTree = root.right;
// 递归交换左右子树的位置，直到为空
root.right = invertTree(root.left);
root.left = invertTree(rightTree);
return root;
}
2.
public TreeNode invertTree(TreeNode root) {
// 层次遍历--直接左右交换即可
if (root == null) return null;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
TreeNode node = queue.poll();
TreeNode rightTree = node.right;
node.right = node.left;
node.left = rightTree;
if (node.left != null){
queue.offer(node.left);
}
if (node.right != null){
queue.offer(node.right);
}
}
return root;
}
网友评论