编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 “”。
示例 1:
输入:strs = ["flower","flow","flight"]
输出:"fl"
示例 2:
输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。
public static String longestCommonPrefixSolution(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
String str = strs[0];
for (int i = 1; i < strs.length; i++) {
int index = 0;
while (index < Math.min(str.length(), strs[i].length()) && str.charAt(index) == strs[i].charAt(index)) {
index++;
}
str = str.substring(0, index);
}
return str;
}
LeetCode地址—>14. 最长公共前缀
给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = "()"
输出:true
示例 2:
输入:s = "()[]{}"
输出:true
输入:s = "(]"
输出:false
public static boolean isVaild(String s) {
// 输入的 s 字符串长度为奇数或第一项是右括号直接 false
if (s.length() % 2 != 0)
return false;
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(')
stack.push(')');
else if (c == '{')
stack.push('}');
else if (c == '[')
stack.push(']');
else if (stack.empty() || c != stack.pop())
return false;
}
return stack.empty();
}
巧法 forEach遍历每个字符; 如果存在左边括号; 则使用栈的方式存储对应的右边括号,成为待匹配的右括号,等待下一轮循环进来与 c 比较同时 pop(); (就巧在这次比较,如果 c 为右括号,执行
else if (stack.empty() || c != stack.pop()) return false;
最后若栈为空,则一定是正确的括号
LeetCode地址—>20. 有效的括号
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
示例 2:
输入:l1 = [], l2 = []
输出:[]
示例 3:
输入:l1 = [], l2 = [0]
输出:[0]
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if(list1==NULL) return list2;
if(list2==NULL) return list1;
if(list1->val < list2->val){
list1->next = mergeTwoLists(list1->next,list2);
return list1;
}else{
list2->next = mergeTwoLists(list1,list2->next);
return list2;
}
}
使用递归: 一直进行比较直到其中一个链表值为NULL,此为判断递归结束条件。 然后开始返回,是在原有链表的基础之上往后面拼接节点。 递归到最后一层才开始拼接链表。
LeetCode地址—>21.合并两个有序链表
给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度,所以必须将结果放在数组nums的第一部分。更规范地说,如果在删除重复项之后有 k 个元素,那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1:
输入:nums = [1,1,2]
输出:2, nums = [1,2,_]
解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2:
输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
双指针算法思路:
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int p = 0, q = 1;
while (q < nums.length) {
if (nums[p] != nums[q]) {
nums[++p] = nums[q];
}
q++;
}
return p + 1;
}
使用双指针; q指向前面元素,p指向后面待比较元素。 每一次比较下来q都要自增,当两下标对应的元素不相等时,p会自增,并自增后的下标指向的元素赋值为q下标指向的元素。
LeetCode地址—>26.删除有序数组中的重复项