网站上传的流程,建立网站加强家园沟通和联系的做法有何利弊,两学一做网站视频,门户网站开发架构面试 Java 算法高频题五问五答第一期 作者#xff1a;程序员小白条#xff0c;个人博客 相信看了本文后#xff0c;对你的面试是有一定帮助的#xff01;
⭐点赞⭐收藏⭐不迷路#xff01;⭐
1#xff09;括号生成:
数字 n 代表生成括号的对数#xff0c;请你设计一个…面试 Java 算法高频题五问五答第一期 作者程序员小白条个人博客 相信看了本文后对你的面试是有一定帮助的
⭐点赞⭐收藏⭐不迷路⭐
1括号生成:
数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。
主要思想递归回溯,递归函数形参(int n,int m,StringBuilder stringBuilder),先左括号再右括号
n表示左括号m表示右括号,stringBuilder用来保存每次append后的临时字符串
if(n0m0) 说明左右括号都生成完毕添加临时字符串到集合中
if(n0) 说明应该左括号生成append左括号递归(n-1,m,stringBuilder)递归完成后再删除最后一个字符
if(mn)说明右括号应该生成先左后右append右括号递归(n,m-1,stringBuilder), 递归完成后再删除最后一个字符
class Solution {public ArrayListString arrayList new ArrayList();public ListString generateParenthesis(int n) {StringBuilder stringBuilder new StringBuilder();backTrack(n,n,stringBuilder);return arrayList;}public void backTrack(int n,int m,StringBuilder stringBuilder){if(n0m0){arrayList.add(stringBuilder.toString());return;}if(n0){stringBuilder.append(();backTrack(n-1,m,stringBuilder);stringBuilder.deleteCharAt(stringBuilder.length()-1);}// 因为先走if(n0) 先左括号然后左括号就会n-1,然后应该是右括号此时mn,因此如果要按左右的形式此时条件应该是mnif(mn){stringBuilder.append());backTrack(n,m-1,stringBuilder);stringBuilder.deleteCharAt(stringBuilder.length()-1);}}
}2单词搜索:
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中返回 true 否则返回 false 。
单词必须按照字母顺序通过相邻的单元格内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1 输入board [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word “ABCCED” 输出true
主要思想深度优先搜索递归回溯
dfs函数传入board二维字符数组i,j,此时的位置String word,int index字符串该访问的位置如果i和j此时不在范围内或者board[i][j]!s.charAt(index)return false; else if(indexword.length()-1) 如果已经到达最后一个字符return true先将此时board[i][j] 置为任意一个不符合字母的字符然后分别向上下左右进行dfs递归有一个方向成立就是result true, 然后将字符重置回来board[i][j] word[index];return result;
主函数遍历二维字符数组如果dfs为true,返回true,跳出所有循环返回false.
class Solution {public boolean exist(char[][] board, String word) {char[] words word.toCharArray();for(int i 0; i board.length; i) {for(int j 0; j board[0].length; j) {if (dfs(board, words, i, j, 0)) return true;}}return false;}boolean dfs(char[][] board, char[] word, int i, int j, int k) {if (i board.length || i 0 || j board[0].length || j 0 || board[i][j] ! word[k]) return false;if (k word.length - 1) return true;board[i][j] \0;boolean res dfs(board, word, i 1, j, k 1) || dfs(board, word, i - 1, j, k 1) || dfs(board, word, i, j 1, k 1) || dfs(board, word, i , j - 1, k 1);board[i][j] word[k];return res;}
}3将有序数组转换为二叉搜索树:
给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例 1 输入nums [-10,-3,0,5,9] 输出[0,-3,9,-10,null,5] 解释[0,-10,5,null,-3,null,9] 也将被视为正确答案
主要思想分治递归二叉中序遍历
功能函数build: 接受三个形参nums数组left左边界right右边界,if(leftright) return null; int mid (leftright)1,因为仅仅一个中序遍历确定不了具体的树可以以中间节点的左边为分界也可以mid(leftright1)1,以右边为分界,TreeNode treeNode new TreeNode(nums[mid]);tree.left build(left,mid-1),tree.right build(mid1,right),return treeNode;
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return build(nums,0,nums.length-1);}public TreeNode build(int [] num,int left,int right){if(leftright){return null;}int mid (leftright)1;TreeNode treeNode new TreeNode(num[mid]);treeNode.left build(num,left,mid-1);treeNode.right build(num,mid1,right);return treeNode;}
}4排序链表:
给你链表的头结点 head 请将其按 升序 排列并返回 排序后的链表 。
示例 1 输入head [4,2,1,3] 输出[1,2,3,4]
主要思想分治递归合并链表
创建一个merge用于合并链表,主函数调用递归函数,传入两个链表一个是头一个是尾
if(headnull) return head;
if(head.next tail) head.next null; return head;
用快慢指针找出中间节点,while(fast!tailfast.next!tail) slow slow.next; fast fast.next.next;
ListNode mid slow; 调用递归函数(head,mid) (mid,right)得到leftNode,rightNode,然后merge这两个链表即可。
5最大子数组和:
主要思想API函数动态规划
class Solution {public int maxSubArray(int[] nums) {int tempMax nums[0];int maxSum nums[0];for(int i 1;inums.length;i){tempMax Math.max(nums[i],tempMaxnums[i]);maxSum Math.max(tempMax,maxSum);}return maxSum;}
}一起加油算法需要正向反馈建议从专项练起很多算法的数据结构解题思路都需要接触思维开拓了就可以一题多解。
