Given two strings s and t, determine if they are isomorphic.Two strings are isomorphic if the characters in s can be replaced to get t.All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.For example,
Given "egg", "add", return true.Given "foo", "bar", retur...
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.解题思路一:之前我们有mergeTwoLists(ListNode l1, ListNode l2)方法,直接调用的话,需要k-1次调用,每次调用都需要产生一个ListNode[],空间开销很大。如果采用分治的思想,对相邻的两个ListNode进行mergeTwoLists,每次将规模减少一半,直到规模变为2为止,空间开销就会小很多。JAVA实现如下: static public ListNode me...
Given a binary tree, find the maximum path sum.The path may start and end at any node in the tree.For example:Given the below binary tree, 1/ 2 3
Return 6. 对于树,我们可以找到其左右子树中终止于根节点的最大路径值,称为最大半路径值,如果都是正数,则可以把它们以及根节点值相加,如果其中有负数,则舍弃那一边的值(即置为零)。如此可以找到包含根节点的最大路径值。然后选择左右子树的最大半路径...
题目描述:Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.解题思路:链表的常见操作。代码如下:/*** Definition for singly-linked list.* public class ListNode {* int val;* ...
题目: Implement atoi to convert a string to an integer.Hint: Carefully consider all possible input cases. If you wanta challenge, please do not see below and ask yourself what are the
possible input cases.
Notes:
It is intended for this problem to be specified vaguely (ie, no given
input specs). You are responsible to gather all the input requirements
up front. spoilers alert... click to show...
分析与其说是算法题,不如说是语言特性题。
这题要是对Java的String相关函数掌握的比较熟练,写起来的速度(各种意义上)就会很快。
大致的思路都是一致的,差不到哪里去,无非是枚举长度。值得一提的是,从长到短的枚举顺序要比从短到长优得多。代码class Solution {public String longestCommonPrefix(String[] strs) {if (strs == null || strs.length == 0) {return "";}String prefix = strs[0];for (int i = 1; i < strs.len...
题目描述:Given two strings s and t, determine if they are isomorphic.Two strings are isomorphic if the characters in s can be replaced to get t.All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.For example,Given "egg", "add", return true.Given "foo", "ba...
Combination Sum IIGiven a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.Each number in C may only be used once in the combination.Note:All numbers (including target) will be positive integers.Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).The solution set ...
Given a binary tree and a sum, find all root-to-leaf paths where each path‘s sum equals the given sum.For example:
Given the below binary tree and sum = 22, 5/ 4 8/ / 11 13 4/ \ / 7 2 5 1return[[5,4,11,2],[5,8,4,5]
]
解题思路:DFS,JAVA实现如下: static public List<List<Integer>> pathSum(TreeNode root, int sum) {List<List<Integer>> list ...
描述:给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。思路一:利用滑动窗口:类似于一个队列,比如例题中的 abcav,进入这个窗口为 abc 满足题目要求,当再进入 a,队列变成了 abca,这时候不满足要求。所以,我们要移动这个队列,此时的...
题目描述:Given a sorted linked list, delete all duplicates such that each element appear only once.For example,Given 1->1->2, return 1->2.Given 1->1->2->3->3, return 1->2->3.代码如下:代码一,正常解法:/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/
public class Solution {public ListNode deleteDuplicates(Lis...
题目:Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:Only one letter can be changed at a timeEach intermediate word must exist in the dictionaryFor example,Given:start = "hit"end = "cog"dict = ["hot","dot","dog","lot","log"]Return [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]思路:先建立dict的邻接链表...
题目:Given a binary tree, return the postorder traversal of its nodes‘ values.
For example:
Given binary tree {1,#,2,3}, 12/3return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively? 题解:递归方法代码: 1 public void helper(TreeNode root, ArrayList<Integer> re){ 2 if(root==null) 3 return; 4 5 helper(root.left,re); 6 help...
【057-Insert Interval(插入区间)】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题 Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9]. Example 2: Given [1,2],[3,5]...
Copy List with Random PointerA linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.Return a deep copy of the list.https://leetcode.com/problems/copy-list-with-random-pointer/ 第一把直接暴力两轮遍历。第一轮遍历copy链表,用hash表记录下各个节点,第二乱遍历去赋值链表里的random对象。然后稍稍改进了一下,一次遍历里把能的找到...