ChatGPT 做LeetCode题(989)

ChatGPT最近大火,趁热让它做做LeetCode每日一题看看。

https://leetcode.com/problems/add-to-array-form-of-integer/

“问题描述

The array-form of an integer num is an array representing its digits in left to right order.

    For example, for num = 1321, the array form is [1,3,2,1].

Given num, the array-form of an integer, and an integer k, return the array-form of the integer num + k.


Example 1:

Input: num = [1,2,0,0], k = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

Example 2:

Input: num = [2,7,4], k = 181
Output: [4,5,5]
Explanation: 274 + 181 = 455

Example 3:

Input: num = [2,1,5], k = 806
Output: [1,0,2,1]
Explanation: 215 + 806 = 1021

Constraints:

    1 <= num.length <= 104
    0 <= num[i] <= 9
    num does not contain any leading zeros except for the zero itself.
    1 <= k <= 104

我的解答

这个问题是Easy题,只要一个个累加就可以了,但注意不能将num展开为整数,再和k相加,因为会整数溢出。

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        List<Integer> result = new ArrayList<>();
        int carry = 0;
        for(int i=num.length-1; i >= 0 || k > 0 || carry > 0; i--) {
            int d1 = i>=0 ? num[i] : 0;
            int d2 = k % 10;
            k /= 10;
            
            result.add((d1+d2+carry) % 10);
            carry = (d1+d2+carry) / 10;
        }
        Collections.reverse(result);
        return result;
    }
}

然后我把我的Solution给ChatGPT让它优化下

ChatGPT给的回答如下

The given implementation looks already quite efficient in terms of both time and space complexity. However, one possible improvement to consider is to use a LinkedList instead of an ArrayList for the result list. This is because the LinkedList implementation offers constant time complexity for appending elements at the beginning or end of the list, whereas the ArrayList implementation may require copying the entire array when it reaches its capacity. Since we are appending digits to the end of the list in this implementation, using a LinkedList can help to avoid potential performance bottlenecks when working with large input arrays.

Another possible improvement is to use bit manipulation instead of the division and modulus operations to extract the least significant digit of k. Specifically, we can use the bitwise AND operator with the value 0x1 to obtain the least significant bit of k, and then use the bitwise right shift operator to remove this bit and shift the remaining bits to the right by one position. This can offer a small speedup in some cases, as bit manipulation operations are generally faster than division and modulus operations.

Here is an updated implementation that incorporates these improvements:

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        LinkedList<Integer> result = new LinkedList<>();
        
        int carry = 0;
        for(int i = num.length - 1; i >= 0 || k > 0 || carry > 0; i--) {
            
            int d1 = i >= 0 ? num[i] : 0;
            int d2 = k & 0x1;
            k >>= 1;
            
            result.addFirst((d1 + d2 + carry) % 10);
            carry = (d1 + d2 + carry) / 10;
        }
        
        return result;
    }
}

ChatGPT说了两个改进点,但是给的解答是错的。因为k是十进制的,没法用 k & 0x1 得到k的最低位。可能是它做过这个题的二进制形式的?

我们直接把原问题抛给他看看ChatGPT怎么回答。

ChatGPT的方案如下

public List<Integer> addToArrayForm(int[] num, int k) {
    int n = 0;
    for (int i = 0; i < num.length; i++) {
        n = n * 10 + num[i];
    }
    n += k;

    List<Integer> res = new ArrayList<>();
    while (n > 0) {
        int r = n % 10;
        res.add(r);
        n /= 10;
    }
    if (res.isEmpty()) {
        res.add(0);
    }
    Collections.reverse(res);
    return res;
}

这里ChatGPT犯了最开始说的错误,它直接把num展开为一个整数了,由于num的长度最多10000位,所以会溢出。

大家暂时不用害怕失业了。ChatGPT大致思路是OK的,但在处理边缘条件时,是会犯错的。lol

为什么iPhone的闹钟,再睡一会是9分钟?

A: 该起床了。 B: 让我再睡一会。 A: 多久? B: 九分钟。

一直有一个疑问,iPhone的闹钟响了后,再睡一会,为什么是会等待9分钟后再次响起?为什么不弄个10分整呢,或者6分钟也行啊(一小时的1/10),特别是强迫症患者(悲痛)。

Quora上对此问题的一个答复

早期的钟表是齿轮式的,因此很难准确地设置10分钟的贪睡时间。 因此,他们的目标是少于10分钟,也就是9分钟。 直到50年代,这都是相当标准的事情。

Telechron 是最早生产待贪睡功能的闹钟厂商之一。

当时的那个带Snooze的闹钟

虽说是电子表,但据称控制snooze的齿轮是9齿的,所以实现9分钟比较容易。

还有很多不同的解释

对先辈的致敬。

当闹钟响起时,第一分钟也已经开始了,如果闹钟最多响1分钟的话,增加9分钟其实就刚好10分钟后起床。

难怪有人说,9分钟的瞌睡已经是一个业界标准了,但成因是众说纷纭的。Apple将这个半个多世纪前,小睡一会应该是多久的公认标准保留到了现在。

你觉得如何呢?上面可有一个理由说服你?

glTF预览时,用图案去替换模型中的材质内容

背景:如今很多应用场景会需要显示3D的场景,例如商品展示、在线试衣、选车时替换车身颜色,等等。

市面上有很多CAD设计软件满足不同需求场景的设计需求,如游戏、建筑、产品包装设计、3D打印等。这么多中的商业软件和文件格式,如果要开发不同的预览系统,是工作量很大的。

glTF是一种通用3D发布格式,有了它之后,其他应用可以通过导出为glTF格式,来实现内容的发布,而不需要开发很多不同格式的展示系统。

glTF是一个JSON文件,设计材质图案替换的最主要结构,大致有:mesh, material, texture, image。可以参考glTF的官网文档了解相关内容。

像针对车身换色,产品包装图案修改等需要动态改变展示内容的场景,可以通过更改glTF中的material来完成。

如,基于 https://gltf-viewer.donmccurdy.com/使用的threejs, GLTFLoader和TextureLoader,可以通过如下的更改完成。

    var changedMaterials = {"material1": fileobj1, "material2": fileobj2}; // from caller side
    
    traverseMaterials(this.content, (node) => {
      const textureLoader = new TextureLoader();

      if(changedMaterias[node.name]) {
        console.log('Change Material ' + node.name );
        var textureFile = changedMaterias[node.name];

        (function(file) {
          var reader = new FileReader();
            reader.onload = function(e) {
              var imgData = e.target.result;
              var map = textureLoader.load(imgData);
              map.flipY = false;
              if (node.map) {
                 // copy repeat and offset, for meshoptmizer models
                 map.repeat.copy(node.map.repeat);
                 map.offset.copy(node.map.offset);
              }
              node.map = map;
              node.needsUpdate = true;
            };
            reader.readAsDataURL(file);
        })(textureFile);


      } else {
        console.log('Material ' + node.name + ' not changed.');
      }

    });

一个限制:
glTF的标准规定了引擎至少需要实现两个UV坐标。所以市面上很多的glTF引擎都无法显示多个UV Mapping的模型。例如threejs,只会显示两个,而且第二个只针对AO (Ambient Occlusion)才会使用。

Client implementations must support at least two UV texture coordinate sets, one vertex color, and one joints/weights set.

在此限制下,如果你要为多个表面替换内容,需要将它们map到一个同一个UV Coordinate上。而不能像在CAD系统中,为多个material指定多个texture image并指定material使用的UV Map。

意味着如果你想要替换多个表面的图形,你可以:

a) 定义一个整体材质分配到多个面; 将多个面的图形合成为一个图;然后用大图替换整体材质的图片。

b) 分别为每个面定义材质;将每个面分别unwrap到整个UV coordinate中,并缩放到整个UV coordinate大小;将每个面的材质分别替换为需要的图片。

当然,还是有支持多个UV Map的引擎的。一个支持多个UV Mapping的引擎,是Sketchfab的实现。
一个例子(包含了6个UV coordinate):https://sketchfab.com/3d-models/cube-with-6-uv-mapping-71aac715d45642089906b2b68e100927

找到直线分割半圆和三角形面积的和

前天在Twitter上看到个数学题,据称是小学的,想了很久 🙂

题目如下:

一个直径为10的半圆,和一个三边长分别是6,8,10的三角形,拼成如图的图形。请作一条直线,将此图形分成面积相等的两部分。

 

这个问题当然有无数多个解,但如何找到一个简单的答案呢?

 

 

方法1:

在圆心O处,作AB的垂线,交圆于P,交BC于Q。

连接PQ,那PQ左边的图形面积显然大于PQ右边的图形面积。

连接PC,那PC左边的图形面积显然小于PC右边的图形面积。

所以如果这条分割点是经过P点的那一条,那么它和图形的另一个交点在C和Q之间,设其为M。直线PM将图形分成面积相等的两部分。

由于弧PA=PB,所以PB和PB两个饼状部分面积相同。所以直线PM将四边形PACB分成面积相等的两部分。

四边形PACB的面积是三角形PAB和三角形ABC的和,即S=1/2*5*5 + 1/2*6*8 = 49

设PH垂直于BM。

我们知道△BOQ和△BCA相似,所以OQ/OB=AC/BC,即OQ=AC/BC*OB = 15/4

BQ = OQ*5/3 = 25/4

S△BPQ = 1/2 * PQ * OB = 1/2 * BQ * PH

所以 PH = PQ * OB / BQ = (5+15/4) * 5 / (25/4) = 7

所以 S△BPM= 1/2 * BM * PH = 49/2

BM = 7

 

方法2

我们连接PO,那么PO将半圆分成面积相等的两部分。我们连接OC,那么OC将三角形ABC分成面积相等的两部分。

但可惜PO、PC不共线。

我们可以看到,PO,PC右边部分面积(图形的一半面积)S1=S⌔POB+S△OBQ+S△OCQ。

我们连接PC,然后过O作PC的平行线,交BC于M。

PM右边的部分面积 S2 = S⌔POB + S△OBQ + S△PMQ。

而,

S△PMQ/S△PCQ = MQ/CQ,

S△OCQ/S△PCQ = OQ/PQ。

由于OM与PC平行,有MQ/CQ=OQ/PQ,所以S△OCQ = S△PMQ。

所以S2 – S1 = S△PMQ – S△OCQ  = 0,

所以PM也将图形分成了面积相等的两部分。

这个方法就不用算算算了。

 

 

第一天!

金庸去世了,留下了很多作品。突然想起今年印象最深的几句话:

一个人停止创造内容了,对世界就没有价值了。

人死之后,唯一留下的,就是艺术。

我应该是那种可以快速感兴趣的人。之前有人说我是好奇宝宝,是有三分钟热度,却浅尝辄止的那种孩子。就像很多年前去学素描、去攀岩、去骑车等。但开始之后,也许慢慢就失去兴趣了,或者没有放很多精力在上面。就像我经常说自己很喜欢钓鱼,可真有休闲时,有多少时候真的会出门呢。恐怕有点叶公好龙吧,懒癌果然是无药可救的。

最近几年坚持比较久的活动,应该就数2015年时去考了司法考试,也是情不知所起吧,没想到竟然真的能考出来(虽然没啥用😂)。

今年9月底去开始在上的法语语音课。希望自己可以坚持下去,而不是不停的挖坑。今年挖的坑:健身,素描,法语,书法。

不容易坚持的人永远都不会幸福吧,在这给自己立个小目标,小flag。

 

眼睛

建筑