每日一道算法题系列，这些你都会吗
算法题几乎成为了各个大厂的标配，尤其以字节、猿辅导最为代表，多则三四道，少则一两道不等，因此算法这块一定不能忽视。这周的七道热门算法题，你都会做吗？
1、给你一个字符串 s，找到 s 中最长的回文子串
public String longestPalindrome(String s) {
// 特判
if(null==s || s.length()<2) return s;
// 中心扩散法
int res =1; //最大长度
int ll=0; //最大回文串的左指针
int rr=0; //最大回文串的右指针
//将字符串转成char数组，不在循环中去使用str.charAt(i)
char[] chArr =s.toCharArray();
// 开始遍历char数组
for(int i =0; i<chArr.length; i++){
// 以i为中心向两边扩散，寻找最长子串（通俗：回文串为奇数长度i为中心）
int l =i-1;
int r =i+1;
while(l>=0 && r<chArr.length && chArr[l]==chArr[r]){
int len =r-l+1;
if(len>res){
res=len;
ll=l;
rr=r;
}
l--;
r++;
}
// 以i为左指针，i+1为右指针（通俗：回文串为偶数长度）
l=i;
r=i+1;
while(l>=0 && r<chArr.length && chArr[l]==chArr[r]){
int len =r-l+1;
if(len>res){
res=len;
ll=l;
rr=r;
}
l--;
r++;
}
}
return s.substring(ll,rr+1);
}2、二叉树的中序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
// 中序遍历：左 根 右
List<Integer> list = new ArrayList<Integer>();
leftOrder(root,list);
return list;
}
private void leftOrder(TreeNode node, List list){
if(null==node) return;
leftOrder(node.left,list);
list.add(node.val);
leftOrder(node.right,list);
}
}`3、删除链表的倒数第n个位置
#import "SinglyLinkedList.h"
/**
给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
输入：head = [1,2], n = 1
输出：[1]
*/
// 2
LinkList removeNthFromEnd(LinkList head, int n) {
if (n < 1) {
return head;
}
LinkList fast = head->next;
LinkList slow = head;
// fast slow固定的间隔
for (int i = 0; i < n; ++i) {
if (!fast) {
return head;
}
fast = fast->next;
}
while (fast) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return head;
}
int main(int argc, const char * argv[]) {
Status iStatus;
LinkList L;
iStatus = createLinkList(&L);
for(int j=1; j<=10; j++)
{
insertElemByIndex(&L, 1, j);
}
printList(L);
L = removeNthFromEnd(L, 2);
printList(L);
return 0;
}4、快排
public void quicksort(int [] a,int left,int right)
{
int low=left;
int high=right;
//下面两句的顺序一定不能混，否则会产生数组越界！！！very important！！！
if(low>high)//作为判断是否截止条件
return;
int k=a[low];//额外空间k，取最左侧的一个作为衡量，最后要求左侧都比它小，右侧都比它大。
while(low<high)//这一轮要求把左侧小于a[low],右侧大于a[low]。
{
while(low<high&&a[high]>=k)//右侧找到第一个小于k的停止
{
high--;
}
//这样就找到第一个比它小的了
a[low]=a[high];//放到low位置
while(low<high&&a[low]<=k)//在low往右找到第一个大于k的，放到右侧a[high]位置
{
low++;
}
a[high]=a[low];
}
a[low]=k;//赋值然后左右递归分治求之
quicksort(a, left, low-1);
quicksort(a, low+1, right);
}5、合并K个升序链表
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0){
return null;
}
//虚拟节点
ListNode head = new ListNode(0);
ListNode tail = head;
//优先队列
PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length,(a, b)->(a.val-b.val));
//将K个链表头节点合并最小堆
for (ListNode node: lists) {
if (node != null) {
queue.add(node);
}
}
while (!queue.isEmpty()) {
//获取最小节点，放到结果链表中
ListNode node = queue.poll();
tail.next = node;
if (node.next != null) {
queue.add(node.next);
}
//指针链表一直往前
tail = tail.next;
}
return head.next;
}
}6、在二叉树中找到两个节点的最近公共祖先
class Solution {
public:
int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
// write code here
unordered_map<int, int> hash;
queue<TreeNode*> q;
q.push(root);
hash.insert(make_pair(root->val, INT_MAX));
while(q.size()) {
if(hash.count(o1) && hash.count(o2)) //层序遍历提前终止，遍历到o1、o2即可。
break;
auto t = q.front();
auto left = t->left;
auto right = t->right;
q.pop();
if(left) {
hash.insert(make_pair(left->val, t->val));
q.push(left);
}
if(right) {
hash.insert(make_pair(right->val, t->val));
q.push(right);
}
}
unordered_set<int> path;
while(hash.count(o1)) {
path.insert(o1);
o1 = hash[o1];
}
while(!path.count(o2)) {
o2 = hash[o2];
}
return o2;
}
};7、岛屿数量
class Solution {
public:
/**
* 判断岛屿数量
* @param grid char字符型vector<vector<>>
* @return int整型
*/
int solve(vector<vector<char> >& grid) {
// write code here
int res = 0;
int n = grid.size(), m = grid[0].size();
int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
for(int i = 0; i < n; i ++) {
for(int j = 0; j < m; j ++) {
if(grid[i][j] == '0')
continue;
else {
res ++;
queue<pair<int, int>> q;
q.push(make_pair(i, j));
while(q.size()) {
auto t = q.front();
q.pop();
grid[t.first][t.second] = '0';
for(int i = 0; i < 4; i ++) {
int x = t.first + dx[i], y = t.second + dy[i];
if(x >= 0 && x < n && y >= 0 && y < m
&& grid[x][y] != '0') {
q.push(make_pair(x, y));
}
}
}
}
}
}
return res;
}
};
更多算法题，可以在这里练习。
#算法##Android##面经##秋招##面试#