day16-算法每日4题

43. 字符串相乘

class Solution { /**     * 给定两个以字符串形式表示的非负整数num1和num2，返回num1和num2的乘积，它们的乘积也表示为字符串形式。     * 注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。     */    public String multiply(String num1, String num2) { if (num1 == null || num1.length() == 0 || num2 == null || num2.length() == 0) return ""; if (num1.equals("0") || num2.equals("0")) return "0"; int len1 = num1.length(); int len2 = num2.length(); // 存某一列的运算结果 // //   1     2     3     i //   4     5     6     j //   + -------------------- //   6    12    18 //      5   10   15 //   4  8   12 //   4  13  28   27    18 //   ------------------------ //   5  6   0     8    8 // 最长是两个数字的长度之和 int[] ansArr = new int[len1 + len2]; // 从个位开始 for (int i = len1 - 1; i >= 0; i--) {     int x = num1.charAt(i) - '0';     for (int j = len2 - 1; j >= 0; j--) {  int y = num2.charAt(j) - '0';  // 这一列的和存在 i+j+1的索引位置  ansArr[i + j + 1] += x * y;     } } // 统一进位 for (int i = len1 + len2 - 1; i > 0; i--) {     // 前面一位     ansArr[i - 1] += ansArr[i] / 10;     // 当前位     ansArr[i] %= 10; } StringBuilder ans = new StringBuilder(); // 看最高位有没有填数字 int idx = ansArr[0] == 0 ? 1 : 0; while (idx < len1 + len2) {     ans.append(ansArr[idx]);     idx++; } return ans.toString();    }}

912. 排序数组

class Solution {    public int[] sortArray(int[] nums) { quickSort(nums, 0, nums.length - 1); return nums;    } /**     * 快速排序     * 选取一个数字作为Pivot中心轴,     * 将大于Pivot的数字放在Pivot的右边     * 将小于Pivot的数字放在Pivot的左边     * 分别对左右子序列重复前三步操作     */    void quickSort(int[] nums, int L, int R) { if (L >= R) return; int left = L, right = R; // 以最左边的为中心轴 int pivot = nums[left]; while (left < right) {     // 如果right的值比pivot大,right--  此 while 结束时恰好 nums[right] < pivot     while (left < right && nums[right] >= pivot) right--;     // 将右边的值赋值到最左边     if (left < right) nums[left] = nums[right];     //如果left的值比pivot小,right++  此 while 结束时恰好 nums[left] > pivot     while (left < right && nums[left] <= pivot) left++;     // 将左边的值赋值到最右边     if (left < right) nums[right] = nums[left];     // 当左右位置重合时,将Pivot赋值到这个重合位置     if (left >= right) nums[left] = pivot; } // 重合的位置左右两边继续重复操作 // 左边 quickSort(nums, L, right - 1); // 右边 quickSort(nums, right + 1, R);    }   /**     * 冒泡排序 会超时     * 比较相邻的元素,如果第一个比第二个大,就交换     * 对每一对相邻元素进行同样的操作,从开始的第一队到最后一对,这样最后的元素应该是最大的     * 然后重复上面的步骤     */    void bubbleSort(int[] nums) { for (int i = 0; i < nums.length - 1; i++) {     // 一轮比较n-1次     for (int j = 0; j < nums.length - 1; j++) {  // 相邻两个数字进行比较  if (nums[j] > nums[j + 1]) {      swap(nums, j, j + 1);  }     } }    }    void swap(int[] nums, int i, int j) { if (nums[i] == nums[j]) return; nums[i] = nums[i] ^ nums[j]; nums[j] = nums[i] ^ nums[j]; nums[i] = nums[i] ^ nums[j];    }}

396. 旋转函数

class Solution {   /**     * nums的元素之和为numSum     * F(0)= 0×nums[0] + 1×nums[1]+…+(n−1)×nums[n−1]     * F(1)= 1×nums[0] + 2×nums[1] + (n-1)×nums[n−2] +…+ 0 × nums[n−1]=  F(0) + numSum − n × nums[n−1]     * F(k)= F(k−1) + numSum− n×nums[n−k]     */    public int maxRotateFunction(int[] nums) { if (nums == null || nums.length == 0) return 0; int f = 0, n = nums.length, numSum = Arrays.stream(nums).sum(); for (int i = 0; i < n; i++) {     f += i * nums[i]; } int res = f; for (int i = n - 1; i > 0; i--) {     f += numSum - n * nums[i];     res = Math.max(res, f); } return res;    }}

206. 反转链表

public class Solution {    /**     * 递归进行翻转链表     */    public ListNode reverseList(ListNode head) { // 如果链表只有一个节点的时候反转也是它自己，直接返回即可。 if (head == null || head.next == null) return head; //    1   -> reverse( 2 -> 3 -> 4 -> null)    翻转后 1  -> reverse( 2 <- 3 <- 4) //  headhead last // 输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。 ListNode last = reverseList(head.next); // 含义: last.next -> head head.next.next = head; head.next = null; return last;    }    /**     * 迭代     * 将链表中每一个节点的 next 引用指向其前驱节点     */    public ListNode reverseList2(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) {     ListNode next = curr.next;     curr.next = prev;     prev = curr;     curr = next; } return prev;    }}