2. 两数相加
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode ln = new ListNode(); ListNode p1 = l1, p2 = l2, p = ln; // 标志上一位如果超过10，下一位进1，即加一 int flag = 0; while (p1 != null || p2 != null) { // p1,p2指向null 则值为0 int num1 = p1 == null ? 0 : p1.val; int num2 = p2 == null ? 0 : p2.val; int res = num1 + num2 + (flag == 1 ? 1 : 0); p.val = res % 10; flag = 0; if (res > 9) flag = 1; // p1,p2 指向下一个节点,直到指向null为止. p1 = p1 == null ? p1 : p1.next; p2 = p2 == null ? p2 : p2.next; if (p1 == null && p2 == null) { // 结束最后一位, 也需进一, if (flag == 1) { p = p.next = new ListNode(); p.val = 1; } p.next = null; } else p = p.next = new ListNode(); } return ln; }
3. 无重复字符的最长子串
public static int lengthOfLongestSubstring(String s) { int max = 0; char[] chars = s.toCharArray(); StringBuilder sb = new StringBuilder(); for (int i = 0; i < s.length(); i++) { for (int j = i; j < s.length(); j++) { // 存在跳出, 不存在加入 if(sb.indexOf(chars[j] + "") != -1) break; else sb.append(chars[j]); if (sb.length() > max) max = sb.length(); } //重置字符串sb sb.setLength(0); } return max; }
7. 整数反转
/** * @Author Tiam * @Date 2022/6/28 13:13 * @Description: 7. 整数反转 victory */ public class Demo06 { public static void main(String[] args) { System.out.println(reverse(2432)); } public static int reverse(int x) { long n = x % 10; while ((x /= 10) != 0) { n = n * 10 + x % 10; } if (n > Integer.MAX_VALUE || n < Integer.MIN_VALUE) return 0; return (int)n; } }
8. 字符串转换整数 (atoi)
/** * @Author Tiam * @Date 2022/6/28 19:02 * @Description: 8. 字符串转换整数 (atoi) victory */ public class Demo07 { public static void main(String[] args) { // System.out.println(4365 / 100.0); // System.out.println(Character.digit('0', 10)); System.out.println(myAtoi("-91283472332")); //System.out.println(Double.parseDouble("-43.234")); } public static int myAtoi(String s) { if ("".equals(s.trim())) return 0; char[] chars = s.trim().toCharArray(); long n = 0; //标记负数 int i = 0, flag = 0; if (!Character.isDigit(chars[i])) { if (chars[i] == '-') { flag = 1; } else { if (chars[i] != '+') return 0; } i++; } for (; i < chars.length; i++) { //判断是否为数字 if (Character.isDigit(chars[i])) { n = n * 10 + Character.digit(chars[i], 10); if (flag == 0 && n > Integer.MAX_VALUE) { return Integer.MAX_VALUE; } if (flag == 1 && -n < Integer.MIN_VALUE) { return Integer.MIN_VALUE; } } else { break; } } n = flag == 0 ? n : -n; return (int) n; } }
9. 回文数
/** * @Author Tiam * @Date 2022/6/29 8:12 * @Description: 9. 回文数 victory */ public class Demo08 { public static void main(String[] args) { System.out.println(isPalindrome(121)); } public static boolean isPalindrome(int x) { if (x < 0) return false; int n = 0, m = x; while (x > 0) { n = n * 10 + x % 10; x /= 10; } return m == n ? true : false; } }
704. 二分查找
/** * @Author Tiam * @Date 2022/6/29 8:41 * @Description: 704. 二分查找 victory */ public class Demo09 { public int search(int[] nums, int target) { int low = 0,high = nums.length-1,mid; while (low<=high){ mid = (low + high)/2; if(nums[mid]>target) high = mid - 1; else if(nums[mid]<target) low = mid + 1; else return mid; } return -1; } }
278. 第一个错误的版本
/** * @Author Tiam * @Date 2022/6/29 8:47 * @Description: 278. 第一个错误的版本 false false true true true * victory */ public class Demo10 { public static void main(String[] args) { System.out.println(firstBadVersion(2126753390)); } public static int firstBadVersion(int n) { long low = 1, high = n, mid; while (low <= high) { mid = (low + high) / 2; if (isBadVersion((int) mid) && !isBadVersion((int) mid - 1)) return (int) mid; else if (isBadVersion((int) mid)) { high = mid - 1; } else low = mid + 1; } //无解抛出异常 throw new IllegalArgumentException("The equation has no solution"); } static boolean isBadVersion(int n) { if (n >= 1702766719) return true; else return false; } }
35. 搜索插入位置
/** * @Author Tiam * @Date 2022/6/29 10:01 * @Description: 35. 搜索插入位置 victory * 在升序数组nums中，寻找target，找到返回其下标，没找到返回其待插入的位置。 */ public class Demo11 { public static void main(String[] args) { int[] nums = {1, 3, 5, 6}; int target = 4; System.out.println(searchInsert(nums, target)); } public static int searchInsert(int[] nums, int target) { int low = 0, high = nums.length - 1, mid; while (low <= high) { mid = (low + high) / 2; if (nums[mid] > target) high = mid - 1; else if (nums[mid] < target) low = mid + 1; else return mid; } return low; } }
删除排序数组中的重复项
/** * @Author Tiam * @Date 2022/6/29 12:23 * @Description: 删除排序数组中的重复项 victory */ public class Demo12 { public static void main(String[] args) { int[] nums = {0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4}; System.out.println(removeDuplicates_(nums)); } public static int removeDuplicates(int[] nums) { int count = 0; for (int i = 0; i < nums.length - count - 1; ) { if (nums[i] == nums[i + 1]) { for (int j = i + 1; j < nums.length - count - 1; j++) { nums[j] = nums[j + 1]; } count++; } else i++; } return nums.length - count; } /** 方式二 */ public static int removeDuplicates_(int[] nums) { int p = 0, q = 1; for(;q < nums.length;q++) //寻找右指针与当前p不同的值, 存储到p的下一位. if(nums[p] != nums[q]) nums[++p] = nums[q]; return ++p; } }
买卖股票的最佳时机 II
/** * @Author Tiam * @Date 2022/6/29 13:01 * @Description: 买卖股票的最佳时机 II victory */ public class Demo13 { public static void main(String[] args) { //int[] nums = {1,2,3,4,5}; //int[] nums = {7,1,5,3,6,4}; //int[] nums = {7,6,4,3,1}; int[] nums = {2, 1, 2, 0, 1}; System.out.println(maxProfit(nums)); } public static int maxProfit(int[] prices) { // -1 标记未购入 int in = -1, rise = 0; for (int i = 0; i < prices.length - 1; i++) { if (prices[i + 1] > prices[i] && in == -1) in = prices[i]; if (prices[i + 1] < prices[i] && in != -1) { rise += prices[i] - in; in = -1; } else if (i + 1 == prices.length - 1 && in != -1) { rise += prices[i + 1] - in; in = -1; } } return rise; } }
实现 pow(x, n)
/** * @Author Tiam * @Date 2022/6/29 14:38 * @Description: 实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。 */ public class Demo14 { public static void main(String[] args) { System.out.println(myPow(2.00000, -2147483648)); System.out.println(myPow_(5, -1)); } /** x的n次方,适用于正整数求幂 */ public static int myPow_(int x, int n) { int r = 1; while (n > 1) { if ((n & 1) == 1) r *= x; x *= x; n >>= 1; } return r * x; } public static double myPow(double x, int n) { //特殊情况 if (x == 1) return 1; if (x == 0) return 0; if (x == -1) return n % 2 == 0 ? 1 : -1; if (n == Integer.MIN_VALUE) return 0.0; int flag = 0; if (n < 0) { n = -n; flag = 1; } double res = 1.0; for (int i = 0; i < n; i++) { res *= x; } return flag == 0 ? res : 1 / res; } }
存在重复元素,返回true,否则 false
/** * @Author Tiam * @Date 2022/6/30 8:28 * @Description: 存在重复元素,返回true,否则 false */ public class Demo15 { public static void main(String[] args) { int[] nums = {1,2,3,4}; System.out.println(containsDuplicate_1(nums)); } public static boolean containsDuplicate(int[] nums) { for (int i = 0; i<nums.length;i++){ for (int j = i+1; j < nums.length; j++) { if(nums[j] == nums[i]) return true; } } return false; } public static boolean containsDuplicate_(int[] nums) { // 先排序后,重复的元素会相邻 Arrays.sort(nums); for (int i = 0; i<nums.length-1;i++){ if(nums[i] == nums[i+1]) return true; } return false; } /** * set集合不能含有重复元素 * add 添加元素时,如含有重复元素则添加失败返回 false * 较上面效率更高 */ public static boolean containsDuplicate_1(int[] nums) { HashSet<Object> objects = new HashSet<>(); for(int i: nums){ if(!objects.add(i)) return true; } return false; } }
977. 有序数组的平方
/** * @Author Tiam * @Date 2022/6/30 9:00 * @Description: 977. 有序数组的平方 */ public class Demo16 { public static void main(String[] args) { System.out.println(5); } public int[] sortedSquares(int[] nums) { int[] squares = new int[nums.length]; for (int i = 0; i < nums.length; i++) { squares[i] = nums[i] * nums[i]; } Arrays.sort(squares); return squares; } public int[] sortedSquares_(int[] nums) { for (int i = 0; i < nums.length; i++) { nums[i] *= nums[i]; } Arrays.sort(nums); return nums; } }
189. 轮转数组
/** * @Author Tiam * @Date 2022/6/30 9:30 * @Description: 189. 轮转数组 */ public class Demo17 { public static void main(String[] args) { int[] nums = {0, 1, 2, 3}; rotate(nums, 2); System.out.println(Arrays.toString(nums)); } /** * 超时 overtime */ public void rotate_(int[] nums, int k) { int temp; for (int i = 0; i < k; i++) { temp = nums[nums.length - 1]; for (int j = nums.length - 1; j > 0; j--) { nums[j] = nums[j - 1]; } nums[0] = temp; } } public static void rotate(int[] nums, int k) { // 复制数组 int[] nums_ = Arrays.copyOf(nums, nums.length); for (int i = 0; i < nums.length; i++) { int j = i + k; if (j > nums.length - 1) j %= nums.length; nums[j] = nums_[i]; } } }
