Tag: 数学

Posted 2022-08-04Updated 2022-08-04LeetCode / Medium2 minutes read (About 326 words)

Question

There is a special square room with mirrors on each of the four walls. Except for the southwest corner, there are receptors on each of the remaining corners, numbered 0, 1, and 2.

The square room has walls of length p and a laser ray from the southwest corner first meets the east wall at a distance q from the 0th receptor.

Given the two integers p and q, return the number of the receptor that the ray meets first.

The test cases are guaranteed so that the ray will meet a receptor eventually.

Solution

激光在箱子里折射，可以想象成在无限延展的空间内直线发射光线。
因此三个接收器可以被视作组成了一个无限延展的矩阵。

只需要将q和p化简，然后确定坐标(q, p)所对应的接收器即可。
由于接收器是间隔的，因此只需要先化简q，p后计算两者的奇偶性即可。

如果q与p皆为奇数，则返回1号接收器。
如果q是奇数，p不是，则返回0号接收器。
如果p是奇数，q不是，则返回2号接收器。

Code

class Solution {
    public int mirrorReflection(int p, int q) {
        int gcd = gcd(p, q);
        p/=gcd;
        q/=gcd;
        boolean xIsOdd = (p & 1) == 1, yIsOdd = (q & 1) == 1;
        if(xIsOdd && yIsOdd) return 1;
        else if(xIsOdd) return 0;
        else return 2;
    }
    
    private int gcd(int a, int b){
        if(a == b) return a;
        if(a > b) return gcd(b, a-b);
        else return gcd(a, b-a);
    }
}

Posted 2022-07-04Updated 2022-07-04LeetCode / Hard / 复习2 minutes read (About 227 words)

135. Candy

Question

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.

Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Solution

双向遍历。
先从左至右遍历数组，如果上一个数值小于当前数值，则当前糖果等于上一个糖果数+1。
然后从右至左遍历数组，同理计算right的数值。
然后保存right与left[]里较大的数值，作为需要分配的糖果数加入到res。

Code

class Solution {
    public int candy(int[] ratings) {
        int[] left = new int[ratings.length];
        for(int i = 0; i < ratings.length; i++){
            if(i > 0 && ratings[i] > ratings[i-1]){
                left[i] = left[i-1] + 1;
            }
            else{
                left[i] = 1;
            }
        }
        
        int right = 0, res = 0;
        for(int i = ratings.length-1; i >= 0; i--){
            if(i < ratings.length-1 && ratings[i] > ratings[i+1]){
                right++;
            }
            else{
                right = 1;
            }
            res += Math.max(left[i], right);
        }
        return res;
    }
}

Posted 2022-05-31Updated 2022-05-31LeetCode / Medium / 复习4 minutes read (About 619 words)

29. Divide Two Integers

Question

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

Return *the quotient after dividing dividend by *divisor.

**Note: **Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For this problem, if the quotient is strictly greater than 231 - 1, then return 231 - 1, and if the quotient is strictly less than -231, then return -231.

Solution

解题思路类似于快速幂。

使用快速乘法来快速的获得商。

计算过程相当于：
60/8 = (60-32)/8 + 4 = (60-32-16)/8 + 2 + 4 = 1 + 2 + 4 = 7

需要注意的是由于只使用了整数（int）而不是长整数（long）储存数据，因此计算时需要处理各种溢出问题。

整数溢出

由于采用32位整数记录数字，负数要比正数的值范围大1。
因此当divisor为负数时，如果负数为整数最小值，则需要返回对应的整数最大值。

同时，为了在计算时防止整数溢出，因此将被除数与除数统一转为负数计算。（负数的数值比整数范围大）
当向下递归时，要保持dividend和divisor的正负性不变。

快速乘

只要被除数大于除数，则商至少为1。
循环，当被除数大于两倍的除数时，则商的结果可以直接翻倍。

否则将被除数减去当前的除数，然后向下递归新的被除数和除数。
最后返回快速乘中计算出的商加上向下递归返回的结果。

Code

class Solution {
    public int divide(int dividend, int divisor) {
        if(dividend == 0) return 0;
        if(divisor == 1) return dividend;
        if(divisor == -1) return dividend == Integer.MIN_VALUE ? Integer.MAX_VALUE : -dividend; //当dividend为最小整数时，其负数溢出，此时返回Integer.MAX_VALUE
        int a = dividend, b = divisor;
        int sign = a > 0 && b > 0 || a < 0 && b < 0 ? 1 : -1;   //记录除数与被除数是否同号
        if(dividend > 0) a = -a;    //将除数与被除数转换为负数，因为负数能记录的数值比正数大1，防止溢出
        if(divisor > 0) b = -b;
        if(a > b) return 0; //被除数小于除数时返回0
        int res = 1;
        while(a <= b+b && b+b < 0){ //算法核心，快速乘法
            b += b; //除数每次翻倍，直到大于被除数
            res += res; //商的结果翻倍
        }
        res = sign == 1 ? res : -res;   //根据是否同号记录商
        
        divisor = dividend > 0 ? -divisor : divisor;  //当原有被除数是正数时，要将除数取反
        return res + divide(a-b, divisor);
    }
}

Posted 2022-05-28Updated 2022-05-27LeetCode / Easya minute read (About 220 words)

268. Missing Number

Question

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Solution 1

采用数学方法，从0到n的和减去从nums中的每个元素的和，得到的即是缺失的数字。
循环所有下标，每次在结果上加上下标的值，并减去下标对应的元素。最后需要再加上nums内元素数量+1的值。

Code

class Solution {
    public int missingNumber(int[] nums) {
        int sum = nums.length;
        for(int i = 0; i < nums.length; i++){
            sum -= nums[i];
            sum += i;
        }
        
        return sum;
    }
}

Solution 2

遍历，采用一个数组found[]记录是否访问过。
再次遍历，如果存在未访问过的位置，则返回下标。

Code

class Solution {
    public int missingNumber(int[] nums) {
        int res = 0;
        int[] found = new int[nums.length+1];
        for(int i = 0; i < nums.length; i++){
            found[nums[i]] = 1;
        }
        
        for(int i = 0; i <= nums.length; i++){
            if(found[i] == 0) res = i;
        }
        return res;
    }
}

Posted 2022-05-22Updated 2022-05-21LeetCode / Medium2 minutes read (About 271 words)

2280. Minimum Lines to Represent a Line Chart

Question

You are given a 2D integer array stockPrices where stockPrices[i] = [dayi, pricei] indicates the price of the stock on day dayi is pricei. A line chart is created from the array by plotting the points on an XY plane with the X-axis representing the day and the Y-axis representing the price and connecting adjacent points. One such example is shown below:

Solution

如果只有一个点，无法组成线段则返回0。否则至少可以组成1条线段。

首先将所有点根据x的位置排序，然后一次比较连续的各个向量的方向。
为了防止除法精度问题，计算两个向量（三个点组成两个向量）的叉乘，如果叉乘为0，则说明两个向量是平行的，此时不需要增加计数。
如果叉乘结果不等于0，则将计数+1。

最后返回计数的结果。

Code

class Solution {
    public int minimumLines(int[][] stockPrices) {
        if(stockPrices.length == 1) return 0;
        
        Arrays.sort(stockPrices, (a,b) -> a[0] - b[0]);
        int count = 1, lastX = 0, lastY = 0;
        
        for(int i = 1; i < stockPrices.length; i++){
            int x = stockPrices[i][0] - stockPrices[i-1][0];
            int y = stockPrices[i][1] - stockPrices[i-1][1];
            
            int k = lastX * y - lastY * x;
            if(k != 0) count++;
            lastX = x;
            lastY = y;
        }
        return count;
    }
}

Posted 2022-05-06Updated 2022-05-07LeetCode / Hard / 复习3 minutes read (About 423 words)

149. Max Points on a Line

Question

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Solution

首先选取一个点，然后创建哈希表。记录这个点与其他点的斜率关系与出现次数。记录一个出现次数最多的max值，如果当前次数大于max则更新max。

注意计算斜率时对y == 0和 x == 0时要返回无穷大和0，否则会有精度问题。
最后返回max + 1。

可以优化的地方是，当max大于总点数的一半，或者max大于剩余的点时，因为已经找到了最大的max值，可以直接返回答案。

Code

class Solution {
    public int maxPoints(int[][] points) {
        int n = points.length;
        if(n == 1) return 1;
        else if(n == 2) return 2;
        int max = 0;
        
        for(int i = 0; i < points.length; i++){
            if(max > points.length / 2) break;
            if(max > points.length - i) break;
            HashMap<Double, Integer> map = new HashMap<>();
            
            for(int j = i+1; j < points.length; j++){
                double k = getSlope(points[i], points[j]);
                int count = map.getOrDefault(k, 0) + 1;
                max = Math.max(max, count);
                map.put(k, count);
            }
        }
        return max + 1 ;
        
    }
    
    private double getSlope(int[] p1, int[] p2){
        double x1 = p1[0], y1 = p1[1], x2 = p2[0], y2 = p2[1];
        if(y1-y2 == 0) return Double.MAX_VALUE;
        if(x1-x2 == 0) return 0;
        double k = (x1 - x2) / (y1 - y2);
        return k;
    }
}

叉乘计算可以判断两个向量是否重合。
由于叉乘乘积（$|a||b|sinθ$）的模等于两个向量组成的平行四边形的面积，因此当两者乘积为0时，则两个向量重合。

点乘乘积得到的是向量在另一个向量上的投影的乘积，$|a||b|cosθ$

Posted 2022-05-06Updated 2022-05-05LeetCode / Easy / 复习2 minutes read (About 353 words)

202. Happy Number

Question

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.

Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.

Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Solution

首先证明，快乐数的计算不会趋近于无穷大。
我们可以考虑每一个位数的最大数字（9999…999）。
其下一个数值等于(81*n)。
对于三位数以下，其最大的值得下一个结果不会大于243。
对于四位数以上，下一个结果会快速收缩到三位数。
因此计算结果不会趋近于无穷。

当我们计算快乐数的值时，形成了一个隐式链表。
因此我们可以用快慢指针的方式，查询链表上是否有环。
快指针比慢指针初始值快1个单位，且移动速度为慢指针的一倍。
如果链表中有环，则两者终能相遇。
如果fast指针先走到1，等于走到了链表的终点。

Code

class Solution {
    public boolean isHappy(int n) {
        int slow = n, fast = getNext(n);
        while(fast != 1 && fast != slow){
            fast = getNext(getNext(fast));
            slow = getNext(slow);
        }
        return fast == 1;
    }
    
    private int getNext(int n){
        int sum = 0;
        while(n != 0){
            int digit = n % 10;
            sum += (digit * digit);
            n = n / 10;
        }
        return sum;
    }
}

Posted 2022-05-05Updated 2022-05-04LeetCode / Medium3 minutes read (About 401 words)

384. Shuffle an Array

Question

Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.

Implement the Solution class:

Solution(int[] nums) Initializes the object with the integer array nums.

int[] reset() Resets the array to its original configuration and returns it.

int[] shuffle() Returns a random shuffling of the array.

Solution

Fisher-Yates洗牌算法。将数组分为两组部分，一组为已打乱的部分，一组为未打乱的部分。每次从未打乱部分中取一个元素，随机和一个未打乱部分的元素（包括自身）交换，则该位置变为已打乱的部分。

Code

class Solution {
    int[] data;
    int[] shuffle;
    Random r;
    public Solution(int[] nums) {
        data = nums;
        shuffle = new int[nums.length];
        r = new Random();
        for(int i = 0; i < data.length; i++){
            shuffle[i] = nums[i];
        }
    }
    
    public int[] reset() {
        return data;
    }
    
    public int[] shuffle() {
        for(int i = data.length-1 ; i >= 0; i--){
            swap(i, r.nextInt(i+1));
        }
        return shuffle;
    }
    
    private void swap(int i, int j){
        int temp = shuffle[i];
        shuffle[i] = shuffle[j];
        shuffle[j] = temp;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */

Solution 2

将静态数组转换为动态数组，每次随机取动态数组里的一个index。
将其按顺序填入result数组，并删除动态数组这个位置。
最后返回result。

Code

class Solution {
    int[] data;
    Random r;
    public Solution(int[] nums) {
        data = nums;
        r = new Random();
    }
    
    public int[] reset() {
        return data;
    }
    
    public int[] shuffle() {
        ArrayList<Integer> bin = new ArrayList<>();
        for(int i = 0; i < data.length; i++){
            bin.add(data[i]);
        }
        
        int[] ret = new int[data.length];
        for(int i = 0 ; i < data.length; i++){
            int random = r.nextInt(bin.size());
            ret[i] = bin.get(random);
            bin.remove(random);
        }
        return ret;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */

Posted 2022-05-04Updated 2022-05-04LeetCode / Medium3 minutes read (About 499 words)

343. Integer Break

Question

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

Solution

动态规划，用数组dp[]记录最大乘积。
在n < 4之前为特例，由于必须拆分，因此乘积小于自身。但由于之后的数字要用到拆分的特性，因此这三个数字要特殊设置为自身。
在此之后，每个数字可以拆分成两个数的加和，然后乘积等于对应两个数的乘积。
（dp[4]可以不设置计算得出，但是指定值的话可以加快速度。）

Code

class Solution {
    public int integerBreak(int n) {
        if(n <= 1) return 0;
        if(n == 2) return 1;
        if(n == 3) return 2;
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 4;
  
        for(int i = 4; i <= n; i++){
            for(int j = 1; j <= (i/2)+1; j++){
                int k = i - j;
                dp[i] = Math.max(dp[i], dp[j] * dp[k]);
            }
        }
        return dp[n];
    }
}

Solution 2

数学方法，当两数之和大于4时，拆分成两个更小的加和可以得到更大的乘积。
而当等于4时，可以拆分为两个2相乘。
因此，最终有意义的拆分结果只会有2和3。

拆分规则：

最优： 3 。把数字 n 可能拆为多个因子 3 ，余数可能为 0,1,2 三种情况。

次优： 2 。若余数为 2 ；则保留，不再拆为 1+1 。

最差： 1 。若余数为 1 ；则应把一份 3+1 替换为 2 + 22+2，因为 2 * 2 > 3 * 1

Code

class Solution {
    public int integerBreak(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int quotient = n / 3;
        int remainder = n % 3;
        if (remainder == 0) {
            return (int) Math.pow(3, quotient);
        }
        else if (remainder == 1) {
            return (int) Math.pow(3, quotient - 1) * 4;
        }
        else {
            return (int) Math.pow(3, quotient) * 2;
        }
    }
}

Solution 3

同样，我们可以将之前的结论用在动态规划上，j只取2或3，将时间复杂度从O(n^2)降低到O(n)。

Code

class Solution {
    public int integerBreak(int n) {
        if(n <= 1) return 0;
        if(n == 2) return 1;
        if(n == 3) return 2;
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 4;
  
        for(int i = 4; i <= n; i++){
            for(int j = 2; j <= 3; j++){
                int k = i - j;
                dp[i] = Math.max(dp[i], dp[j] * dp[k]);
            }
        }
        return dp[n];
    }
}

Posted 2022-04-30Updated 2022-04-292 minutes read (About 322 words)

1823. Find the Winner of the Circular Game

There are n friends that are playing a game. The friends are sitting in a circle and are numbered from 1 to n in clockwise order. More formally, moving clockwise from the ith friend brings you to the (i+1)th friend for 1 <= i < n, and moving clockwise from the nth friend brings you to the 1st friend.

The rules of the game are as follows:

1.Start at the 1st friend.

2.Count the next k friends in the clockwise direction including the friend you started at. The counting wraps around the circle and may count some friends more than once.

3.The last friend you counted leaves the circle and loses the game.

4.If there is still more than one friend in the circle, go back to step 2 starting from the friend immediately clockwise of the friend who just lost and repeat.

5.Else, the last friend in the circle wins the game.
Given the number of friends, n, and an integer k, return the winner of the game.

约瑟夫环问题。
根据题目要求，当去除一个成员时，下一个节点的编号为k+1。
当新的循环开始时，总人数n-1，同时k+1变为新循环中的1。

因此可以采用递归，当n剩下一个人时，返回其编号1。
对应上层这个成员的位置为k+1，向上递归。
由于k+1可以越界，因此每次返回需要对其取模。

class Solution {
    public int findTheWinner(int n, int k) {
        if(n == 1) return 1;
        int ans = findTheWinner(n-1, k) + k;
        return ans % n == 0 ? n : ans % n;
    }
}

Posted 2022-04-29Updated 2022-04-29LeetCode / Mediuma minute read (About 189 words)

413. Arithmetic Slices

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences.
Given an integer array nums, return the number of arithmetic subarrays of nums.

A subarray is a contiguous subsequence of the array.

动态规划，遍历一次记录所有数字的差。
然后遍历并计算连续相同的数字数量temp。
当不相同时，则计算temp长度可以选择的组合数，将其添加到count。

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {

        if(nums.length == 1) return 0;
        int[] difference = new int[nums.length-1];
        for(int i = 0; i < nums.length-1; i++){
            difference[i] = nums[i+1] - nums[i];
        }
        
        int count = 0;
        int temp = 1;
        int prev = difference[0];
        for(int j = 1; j < nums.length-1; j++){
            if(difference[j] == prev){
                temp++;
            }
            else{
                count += combinations(temp);
                temp = 1;
            }
            prev = difference[j];
        }
        count += combinations(temp);
        return count;
    }
    
    private int combinations(int n){
        return (n * (n-1)) / 2;
    }
}

Posted 2022-04-23Updated 2022-04-23LeetCode / Medium / 复习a minute read (About 214 words)

43. Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

两个字符串的位数做乘法，每次计算进位。
当前位等于自身加上计算结果的个位（由于有之前的进位存在。），下一位等于计算结果的十位。

class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length();
        int n = num2.length();
        if( num1.equals("0") || num2.equals("0")){
            return "0";
        }
        int[] product = new int[m+n];
        
        char[] arr1 = num1.toCharArray();
        char[] arr2 = num2.toCharArray();
        
        for(int i = m-1; i >= 0; i--){
            for(int j = n-1; j >=0; j--){
                int sum = product[i+j+1] + (arr1[i] - '0') * (arr2[j] - '0');
                int curr = sum % 10;
                int carry = sum / 10;
            
                product[i+j] += carry;
                product[i+j+1] = curr;
            }
        }
        StringBuffer sb = new StringBuffer();
        for(int k = 0; k < m+n; k++ ){
            if(k == 0 && product[k] == 0 ) continue;
            sb.append(product[k]);
        }
        return sb.toString();
    }
}

Posted 2022-04-20Updated 2022-04-20LeetCode / Medium / 复习2 minutes read (About 243 words)

560. Subarray Sum Equals K

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

对于数组中每个数字，计算其前缀的和。
前缀[i]减去前缀[j]的差，等于[j]-[i]之间数字的和。（类似一种DP，数组可以用一个变量代替。）

因此，原题目等于寻找找前缀[i]-前缀[j] = k。
用哈希表储存已经遍历过的前缀和出现的次数。
每次遍历时先查看哈希表内是否有当前[前缀和-k]的键在。
如果有则加入到count中。
（哈希表中需要提前放入一个0键，值等于1，为了计算[前缀和-k]等于0的情况。）

class Solution {
    public int subarraySum(int[] nums, int k) {
        
        int[] sum = new int[nums.length + 1];
        HashMap<Integer, Integer> map = new HashMap();
        int count = 0;
        map.put(0, 1);
        
        for(int i = 1; i <= nums.length; i++){
            sum[i] = sum[i-1] + nums[i-1];
            count += map.getOrDefault(sum[i]-k, 0);
            map.put(sum[i], map.getOrDefault(sum[i], 0) + 1);
        }
        
        return count;
    }
}

Posted 2022-04-20Updated 2022-04-20LeetCode / Medium / 复习2 minutes read (About 258 words)

238. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

当前数字之外的积等于左边所有数字的积乘以右边所有数字的积。
因此可以维护两个数组，分别计算从左到右的乘积，和从右到左的乘积。

由于返回答案不算占用空间，因此可以将左侧乘积的数组保存在答案数组上。
然后在遍历时，从右至左遍历，使用一个变量储存右边的乘积，直接将两者的乘积更新在答案数组上。
此时空间复杂度为O(1)。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] ans = new int[nums.length];
        ans[0] = 1;
        
        for(int i = 1; i < nums.length; i++){
            ans[i] = ans[i-1] * nums[i-1];
        }
        
        int rightProduct = 1;
        
        for(int j = nums.length-1; j >=0; j--){
            ans[j] = ans[j] * rightProduct;
            rightProduct *= nums[j];
        }
        return ans;   
    }
}

Posted 2022-04-18Updated 2022-08-30LeetCode / Medium / 复习3 minutes read (About 505 words)

48. Rotate Image

Question

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Solution 1

此方法是in-place算法。

visited[][]数组记录访问情况，遍历所有位置，如果已访问则跳过。
循环替换矩阵上的每一个位置，如果已经访问过则break。
如果未访问则将要替换位置的值保存，并且在visited[][]数组上记录。
然后继续遍历替换过的位置。

Code

class Solution {
    public void rotate(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] visited = new int[m][n];
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(visited[i][j] == 1) continue;
                int x = i, y = j;
                int value = matrix[i][j];
                while(true){
                    int s = n-1-x, t = y;
                    if(visited[t][s] == 1) break;
                    int temp = matrix[t][s];
                    matrix[t][s] = value;
                    value = temp;
                    visited[t][s] = 1;
                    x = t;
                    y = s;
                }
            }
        }
    }
}

Solution 2

此方法类似Solution 1，但是并非原地算法。

Code

class Solution {
    public void rotate(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] mat = new int[m][n];
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int s = n-1-i, t = j;
                mat[t][s] = matrix[i][j];
            }
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                matrix[i][j] = mat[i][j];
            }
        }
    }
}

Solution 3

辅助方法getPixel计算旋转后的像素位置。
旋转时候矩阵内的四个分区的像素会互相替换。
因此需要将需要旋转的初始位置记录进入队列。
旋转图像时根据getPixel方法计算出需要替换的位置。
然后依次替换像素。

Code

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        Queue<Integer> queue = new LinkedList();
        for (int p = 0; p < n/2; p++){
            for(int q = 0; q < (n+1)/2; q++){
                queue.offer(p * n + q);
            }
        }

        while(!queue.isEmpty()){
            int i = queue.poll();
            int INDEX = i;
            boolean flag = true;
            int temp = matrix[i/n][i%n];
            while(i != INDEX || flag ){
                flag = false;
                int j = getPixel(n, i);
                int swap = matrix[j / n][j % n];
                matrix[j / n][j % n] = temp; 
                temp = swap;
                i = j;
            }
        }     
    }
    
    private int getPixel(int n, int o){
        int row = o / n;
        int col = o % n;
        int newRow = col;
        int newCol = n - (row + 1);
        return (newRow * n) + newCol;
    }
}

Question

Solution

Code

Question

Solution

Code

Question

Solution

整数溢出

快速乘

Code

Question

Solution 1

Code

Solution 2

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Solution 2

Code

Question

Solution

Code

Solution 2

Code

Solution 3

Code

Question

Solution 1

Code

Solution 2

Code

Solution 3

Code

Recents

Archives

Links