Java面试常见算法
程序员文章站
2022-06-05 14:09:53
...
java常见算法
反转链表
while循环
public ListNode reverseListNode(ListNode head)
{
ListNode now = head;
ListNode pre = null;
while(null != now)
{
ListNode next = now.next;
now.next = pre;
pre = now;
now = next;
}
return pre;
}
递归
public ListNode reverseListNode(ListNode head)
{
if(null == head || null == head.next)
return head;
ListNode newHead = reverseListNode(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
设计LRU缓存
public class LRUCache
{
public class DLinkedNode
{
int key;
int value;
DLinkedNode pre;
DLinkedNode next;
public DLinkedNode(){};
public DLinkedNode(int key, int value){ this.key = key; this.value = vlaue;};
}
private int size;
private int capacity;
private DLinkedNode head;
private DLinkedNode tail;
private Map<Integer, DLinkedNode> map;
public LRUCache(){};
public LRUCache(int capaticy)
{
this.size = 0;
this.capacity = capatity;
this.head = new DLinkedNode();
this.tail = new DLinkedNode();
this.map = new HashMap<>();
this.head.pre = this.tail;
this.head.next = this.tail;
this.tail.pre = this.head;
this.tail.next = this.head;
};
public int get(int key)
{
DLinkedNode node = this.map.get(key);
if(null == node)
return -1;
else
{
node.pre.next = node.next;
node.next.pre = node.pre;
head.next.pre = node;
node.next = head.next;
head.next= node;
node.pre = head;
return node.value;
}
}
public void put(int key, int value)
{
DLinkedNode node = this.map.get(key);
if(null == node)
{
node = new DLinkedNode(key, vlaue);
head.next.pre = node;
node.next = head.next;
head.next = node;
node.pre = head;
this.size++;
if(this.size > this.capacity)
{
this.map.remove(tail.pre.value);
this.size --;
tail.pre = tail.pre.pre;
tail.pre.next = tail;
}
this.map.put(key, node);
}
else
{
node.value = value;
node.pre.next = node.next;
node.next.pre = node.pre;
head.next.pre = node;
node.next = head.next;
head.next = node;
node.pre = head;
}
}
}
求一个字符串的最大子串
public int getSubStringMaxLength(String s)
{
if(null == s)
return 0;
Map<Character, Integer> map = new HashMap<>();
int left = 0;
int max = 0;
for(int i =0; i < s.length(); i++)
{
if(map.containsKey(s.charAt(i)))
left = Math.max(left, s.charAt(i) + 1);
map.put(s.charAt(i), i);
max = Math.max(max, i - left + 1);
}
return max;
}
K个一组反转一个链表
public ListNode reverseGroupK(ListNode head, int k)
{
if(null == head)
return head;
ListNode now = head;
for(int i = 1; i < k; i++)
{
now = now.next;
if(null == now)
return head;
}
ListNode nextNode = now.next;
now.next = null;
ListNode newHead = reverseListNode(head);
ListNode node = reverseGroupK(nextNode, k);
head.next = node;
return newHead;
}
public ListNode reverseListNode(ListNode head)
{
if(null == head || null == head.next)
retuen null;
ListNode newHead = reverseListNode(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
两数之和 等于目标值的下标的集合
public int[] twoSum(int[] nums, int target)
{
for(int i = 0; i < nums.length; i++)
{
for(int j = i + 1; j < nums.length; j++)
{
if(nums[i] + nums[j] == target)
return new int[]{i, j};
}
}
return new int[]{};
}
判断一个链表中是否有环
public boolean hasCycle(ListNode head)
{
if(null == head)
return false;
ListNode fast = head;
ListNode slow = head;
while(null != fast.next && null != fast.next.next)
{
fast = fast.next.next;
slow = slow.next;
if(fast == slow)
return true;
}
return false;
}
最大子序列的和
public int maxSubSum(int nums)
{
int res = nums[0];
int sum = 0;
for(int num: nums)
{
if(sum > 0)
sum = sum + num;
else
sum = num;
res = Math.max(res, sum);
}
return res;
}
合并两个有序的链表
public ListNode mergeTwoLists(ListNode l1, ListNode l2)
{
if(null == l1)
return l2;
else if(null == l2)
return l1;
else if(l1.val < l2.val)
{
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else
{
l2.next = megerTwoLists(l1, l2.next);
return l2;
}
}
查找两个链表的交点
public ListNode getIntersectionNode(ListNode headA, ListNode headB)
{
if(null == headA && null == headB)
return null;
ListNode pa = headA;
ListNode pb = headB;
while(pa != pb)
{
pa = null == pa? headB: pa.next;
pb = null == pb? headA: pb.next;
}
return pa;
}
二叉树的层序遍历
public List<List<Integer>> leveOrderTreeNode(TreeNode root)
{
List<List<Integer>> res = new ArrayList<>();
if(null == root)
return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty())
{
int maxSize = queue.size();
List<Integer> list = new ArrayList<>();
for(int i = 0; i < maxSize; i++)
{
if(null != queue.peek().left)
queue.offer(queue.peek().left);
if(null != queue.peek().right)
queue.offer(queue.peek().right);
list.add(queue.poll().val);
}
res.add(list);
}
return res;
}
二叉树的锯齿状的层次遍历
public List<List<Integer>> zigzagLevelOrderTreeNode(TreeNode node)
{
List<List<Integer>> res = new ArrayList<>();
if(null == root)
return res;
Deque<TreeNode> deque = new LinkedList<>();
deque.offerFirst(root);
boolean flag = true;
while(!deque.isEmpty())
{
int maxSize = deque.size();
List<Integer> list = new ArrayList<>();
for(int i = 0; i < maxSize; i++)
{
if(flag)
{
if(null != deque.peekFirst().left)
deque.offerLast(deque.peekFirst().left)
if(null != deque.peekFirst.right)
deque.offerLast(deque.peekFirst.right)
list.add(deque.pollFirst().val);
}
else
{
if(null != deque.peekLast().right)
deque.offerFirst(deque.peekLast().right);
if(null != deque.peekLast().left)
deque.offerFirst(deque.peekLast.left);
list.add(deque.pollLast().val);
}
}
flag = !flag;
res.add(list);
}
return res;
}
合并两个非递减的有序数组
public void meger(int[] nums1, int m, int[] nums2, int n)
{
int tail = m + n - 1;
int p1 = m - 1;
int p2 = n - 1;
int curr;
while(p1 >= 0 || p2 >= 0)
{
if(p1 == -1)
curr = nums2[p2 --];
else if(p2 == -1)
curr = nums1[p1 --];
else if(nums1[p1] > nums2[p2])
curr = nums1[p1 --];
else
curr = nums2[p2 --];
nums1[tail --] = curr;
}
}
二叉树的公共祖先
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
{
if(null == root)
return null;
if(p.val == root.val || q.val == root.val)
return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(null == left && null == right)
return null;
if(null == left)
return right;
if(null == right)
return left;
return root;
}
有效的括号
public boolean isValid(String s)
{
if(null == s)
return true;
Stack<Character> stack = new Stack<>();
char[] chars = s.toCharArray();
for(char c: chars)
{
if(c == '(' || c =='{' || c == '[')
stack.push(c);
else
{
if(stack.isEmpty())
return false;
else
{
char right = stack.pop();
if(c == ')' && right != '(' || c == '}' && right != '{' || c == ']' && right != '[')
return false;
}
}
}
return stack.isEmpty();
}
字符串相加
public String addString(Strign num1, String num2)
{
int l1 = num1.length();
int l2 = num2.length();
int maxL = Math.max(l1, l2) + 1;
int add = 0;
StringBuffer sb = new StringBuffer();
for(int i = 1; i <= maxL; i++)
{
if(i > l1 && i > l2)
{
if(add != 0)
sb.append(add);
}
else if(i > l1)
{
int sum = num2.charAt(l2 -i) - '0' + add;
add = sum / 10;
sb.append(sum % 10);
}
else if(i > l2)
{
int sum = num1.charAt(l1 - i) - '0' + add;
add = sum / 10;
sb.append(sum % 10);
}
else
{
int sum = num1.charAt(l1 - i) - '0' + num2.charAt(l2 - i) - '0' + add;
add = sum / 10;
sb.append(sum % 10);
}
}
sb.reverse();
return sb.toString();
}
环形链表（环形的第一个节点）
public ListNode detectCycle(ListNode head)
{
if(null == head)
return null;
ListNode fast = head;
ListNode slow = head;
while(null != fast.next && null != fast.next.next)
{
fast = fast.next.next;
slow = slow.next;
if(fast == slow)
{
fast = head;
while(fast != slow)
{
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
return null;
}
三数之和（不能重复）
public List<List<Integer>> threeSum(int[] nums)
{
List<List<Integer>> res = new ArrayList<>();
if(null == nums)
return res;
Arrays.sort(nums);
for(int i = 0; i < nums.length; i++)
{
if(nums[i] > 0) return res;
if(i > 0 && nums[i] == nums[i -1]) continue;
int r = i + 1;
int l = nums.length - 1;
while(r < l)
{
int sum = nums[i] + nums[r] + nums[l];
if(sum < 0)
while(r < l && nums[i] == nums[++i]);
else if(sum > 0)
while(r < l && nums[l] == nums[--l]);
else
{
res.add(new ArrayList<>(Arrays.asList(nums[i], nums[r], nums[l])));
while(r < l && nums[r] == nums[++r]);
while(r < l && nums[l] == nums[--l]);
}
}
}
return res;
}
上一篇： php中将文本数据库转为mysql数据库
下一篇： ecshop $_CFG