第一天就有点偷懒，做的全是简单题，还没做几个。
整数反转
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−2^31, 2^31 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
输入123
输出321
输入-123
输出-321
public int reverse(int x) {
int result = 0, tmp = 0;
while (x != 0) {
tmp = result;
result = result * 10 + (x % 10);
if (result / 10 != tmp)
return 0;
x /= 10;
}
return result;
}
核心算法比较简单，重点在于对于整数溢出情况的处理，这里使用的一个tmp存放了result以前的值，若result处理后再除10不等于原来的值，result值被改变
，说明发生了溢出。
回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。
输入：x = 121
输出：true
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
无脑做法
public boolean isPalindrome(int x) {
if (x < 0)
return false;
int[] tmp = new int[32];
int i = 0;
while ( x != 0) {
tmp[i++] = x % 10;
x /= 10;
}
for (int j = 0; j != i && j != i + 1; j++) {
if (tmp[j] != tmp[--i])
return false;
}
return true;
}
第二种
既然我们前面做了反转数字，那么可以利用前面的反转，将数字反转后与原数字对比，若相等，则为回文。
public static boolean isPalindrome(int x) {
if (x < 0)
return false;
int result = 0, tmp = x;
while (tmp != 0) {
result = result * 10 + (tmp % 10);
tmp /= 10;
}
return x == result;
}
最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
输入：strs = ["flower","flow","flight"]
输出："fl"
输入：strs = ["dog","racecar","car"]
输出：""
先上我自己写的，效率也还不错
public static String longestCommonPrefix(String[] strs) {
if (strs.length == 1)
return strs[0];
StringBuilder res = new StringBuilder();
char tmp = '\0';
for (int j = 0; j < 200; j++){
int i = 0;
for (; i < strs.length - 1; i++) {
// 检查是否遍历完某个字符串
if (strs[i].length() == j || strs[i+1].length() == j)
return res.toString();
// 检查对应的字符是否相等
if (strs[i].charAt(j) != strs[i+1].charAt(j)){
i = 0;
break;
}
}
if (i == 0)
return res.toString();
res.append(strs[0].charAt(j));
}
return res.toString();
}
后面发现有使用java提供的函数starWith写的，思路差不多，代码简洁很多，贴一下
public String longestCommonPrefix(String[] strs) {
if(strs.length==0)return "";
//公共前缀比所有字符串都短，随便选一个先
String s=strs[0];
for (String string : strs) {
while(!string.startsWith(s)){
if(s.length()==0)return "";
//公共前缀不匹配就让它变短！
s=s.substring(0,s.length()-1);
}
}
return s;
}
有效括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
输入：s = "(]"
输出：false
输入：s = "()[]{}"
输出：true
代码
public char getRev(char c) {
if (c == ']') return '[';
if (c == '}') return '{';
if (c == ')') return '(';
return c;
}
public boolean isValid(String s) {
Stack<Character> st = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char tmp = getRev(s.charAt(i));
if (s.charAt(i) == tmp) {
st.push(tmp);
} else if (st.isEmpty() || st.pop() != tmp)
return false;
}
return st.isEmpty();
}
合并两个有序列表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null)
return l1 == null ? l2 : l1;
ListNode list = new ListNode();
ListNode head = list;
while (l1 != null && l2 != null) {
list.next = l1.val < l2.val ? l1 : l2;
if (list.next == l1)
l1 = l1.next;
else
l2 = l2.next;
list = list.next;
}
list.next = l1 == null ? l2 : l1;
return head.next;
}
删除有序数组中的重复项
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
输入：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 。不需要考虑数组中超出新长度后面的元素。
使用一个idx记录我们所需要的索引（不包含重复元素的索引）
public static int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
int tmp = nums[0], idx = 1;
for (int i = 1; i < nums.length;i++) {
if (nums[i] == tmp) {
continue;
}
tmp = nums[i];
nums[idx++] = tmp;
}
return idx;
}